Page 77 - 4868

75 Ошибка! Стиль не определен.

11.3. Алгоритм поліклініки
Алгоритм квитка можна безпосередньо реалізувати на машинах, що
мають підтримку операції типу «витягти і скласти». Якщо така інструкція
недоступна, то можна виконати моделювання її алгоритму роботи. Але для
цього потрібен ще один протокол критичної секції, і рішення не обов’язково
буде мати властивість справедливості. Представлений тут алгоритм
поліклініки, подібний алгоритму квитка. Він забезпечує справедливість
планування і не вимагає спеціальних машинних інструкцій. Проте, він
складніший для практичної реалізації, ніж алгоритм квитка.
Згідно алгоритму квитка кожен відвідувач отримує унікальний номер і
очікує, поки значення змінної next не стане рівним цьому номеру. Алгоритм
поліклініки використовує трохи інший підхід. Заходячи в поліклініку,
відвідувач дивиться на всіх інших і вибирає номер, який більший усіх інших
вибраних номерів. Усі відвідувачі повинні чекати, поки не назвуть їх номер.
Як і в алгоритмі квитка, наступним обслуговується відвідувач з найменшим
номером. Відмінність полягає в тому, що для визначення черговості
обслуговування відвідувачі звіряються один з одним, а не із загальним
лічильником.
Як і в алгоритмі квитка, нехай turn[1: n] – масив цілих чисел з
початковими значеннями 0. Щоб увійти в критичну секцію, процес CS[i]
спочатку присвоює змінній turn[i] значення, яке на 1 більше, ніж
максимальне серед поточних значень елементів масиву turn. Потім CS[i]

очікує, поки значення turn[i] не стане найменшим серед ненульових
елементів масиву turn. Виходячи з критичної секції, процес CS[i]
присвоює turn[i] значення 0.
У лістингу 1.12 показаний крупномодульний варіант алгоритму
поліклініки, у якому дотриманозазначені умови. Перша неподільна дія
забезпечує унікальність всіх ненульових значень елементів масиву turn.
Оператор for гарантує, що інваріант має значення «істина», коли процес
P[i] виконує свою критичну секцію. Даний алгоритм задовольняє умові
взаємного виключення, оскільки одночасно не можуть бути істинними умови
turn[i] != 0 для всіх i. Ненульові значення елементів масиву turn
унікальні і, як і передбачалося, кожен процес зрештою виходить із своєї
критичної секції, тому взаємні блокування відсутні. Відсутні також зайві
затримки процесів, оскільки відразу після виходу процесу CS[i] з критичної
секції turn[i] отримує значення 0. Значення елементів масиву turn в
алгоритмі поліклініки можуть бути як завгодно великі, але значення
елементів масиву turn продовжують зростати, тільки у випадку, якщо є хоча
б один процес, який намагається увійти в критичну секцію, однак на практиці
це малоймовірно.
Алгоритм поліклініки в лістингу 1.11 не можливо безпосередньо

реалізувати на сучасних машинах. Щоб присвоїти змінній turn[i] значення,
необхідно знайти максимальне з n значень, а оператор await двічі
звертається до спільної змінної turn[j]. Дані операції можна було б