Page 94 - 6571

(наприклад циклічні блокування або алгоритм розриву вузла).
Наприклад, нехай CSenter – протокол входу критичної секції, a
CSexit - відповідний протокол виходу. Тоді в програмі з

лістингу 11 інструкцію «витягти і скласти» можна замінити
наступною послідовністю операторів:

CSenter;
turn[i] = number;
number = number+1;
CSexit;

Такий підхід виглядає незвичайним, але на практиці він
працює добре, особливо якщо для реалізації протоколів входу і

виходу доступна інструкція типу «перевірити-встановити». При
виконанні інструкції «перевірити-встановити» процеси
отримують номери, що не обов’язково відповідають порядку, в
якому вони намагаються це зробити, і теоретично процес може

зациклитися назавжди. Але з дуже високою ймовірністю кожен
процес отримає номер, і більшість номерів будуть обрані в
порядку їх зростання. Основна причина виникнення затримок в

алгоритмі квитка – це очікування, поки значення змінної next не
стане рівним значенню turn[i].

11.3 Алгоритм поліклініки

Алгоритм квитка можна безпосередньо реалізувати на маши-

нах, що мають підтримку операції типу «витягти і скласти». Як-
що така інструкція недоступна, то можна виконати моделювання
її алгоритму роботи. Але для цього потрібен ще один протокол

критичної секції, і рішення не обов’язково буде мати властивість
справедливості. Представлений тут алгоритм поліклініки, подіб-
ний алгоритму квитка. Він забезпечує справедливість планування
і не вимагає спеціальних машинних інструкцій. Проте, він склад-
ніший для практичної реалізації, ніж алгоритм квитка.

Згідно алгоритму квитка кожен відвідувач отримує
унікальний номер і очікує, поки значення змінної next не стане
рівним цьому номеру. Алгоритм поліклініки використовує трохи

інший підхід. Заходячи в поліклініку, відвідувач дивиться на всіх
інших і вибирає номер, який більший усіх інших вибраних
номерів. Усі відвідувачі повинні чекати, поки не назвуть їх
номер. Як і в алгоритмі квитка, наступним обслуговується

93