Page 94 - 6571
P. 94
(наприклад циклічні блокування або алгоритм розриву вузла).
Наприклад, нехай CSenter – протокол входу критичної секції, a
CSexit - відповідний протокол виходу. Тоді в програмі з
лістингу 11 інструкцію «витягти і скласти» можна замінити
наступною послідовністю операторів:
CSenter;
turn[i] = number;
number = number+1;
CSexit;
Такий підхід виглядає незвичайним, але на практиці він
працює добре, особливо якщо для реалізації протоколів входу і
виходу доступна інструкція типу «перевірити-встановити». При
виконанні інструкції «перевірити-встановити» процеси
отримують номери, що не обов’язково відповідають порядку, в
якому вони намагаються це зробити, і теоретично процес може
зациклитися назавжди. Але з дуже високою ймовірністю кожен
процес отримає номер, і більшість номерів будуть обрані в
порядку їх зростання. Основна причина виникнення затримок в
алгоритмі квитка – це очікування, поки значення змінної next не
стане рівним значенню turn[i].
11.3 Алгоритм поліклініки
Алгоритм квитка можна безпосередньо реалізувати на маши-
нах, що мають підтримку операції типу «витягти і скласти». Як-
що така інструкція недоступна, то можна виконати моделювання
її алгоритму роботи. Але для цього потрібен ще один протокол
критичної секції, і рішення не обов’язково буде мати властивість
справедливості. Представлений тут алгоритм поліклініки, подіб-
ний алгоритму квитка. Він забезпечує справедливість планування
і не вимагає спеціальних машинних інструкцій. Проте, він склад-
ніший для практичної реалізації, ніж алгоритм квитка.
Згідно алгоритму квитка кожен відвідувач отримує
унікальний номер і очікує, поки значення змінної next не стане
рівним цьому номеру. Алгоритм поліклініки використовує трохи
інший підхід. Заходячи в поліклініку, відвідувач дивиться на всіх
інших і вибирає номер, який більший усіх інших вибраних
номерів. Усі відвідувачі повинні чекати, поки не назвуть їх
номер. Як і в алгоритмі квитка, наступним обслуговується
93