Page 95 - 6571

відвідувач з найменшим номером. Відмінність полягає в тому, що
для визначення черговості обслуговування відвідувачі звіряються
один з одним, а не із загальним лічильником.
Як і в алгоритмі квитка, нехай turn[1: n] – масив цілих

чисел з початковими значеннями 0. Щоб увійти в критичну
секцію, процес CS[i] спочатку присвоює змінній turn[i]

значення, яке на 1 більше, ніж максимальне серед поточних
значень елементів масиву turn. Потім CS[i] очікує, поки
значення turn[i] не стане найменшим серед ненульових
елементів масиву turn. Виходячи з критичної секції, процес

CS[i] присвоює turn[i] значення 0.
У лістингу 12 показаний крупномодульний варіант

алгоритму поліклініки, у якому дотримано зазначені умови.
Перша неподільна дія забезпечує унікальність всіх ненульових
значень елементів масиву turn. Оператор for гарантує, що
інваріант має значення «істина», коли процес P[i] виконує свою

критичну секцію. Даний алгоритм задовольняє умові взаємного
виключення, оскільки одночасно не можуть бути істинними

умови turn[i] != 0 для всіх i. Ненульові значення елементів
масиву turn унікальні і, як і передбачалося, кожен процес
зрештою виходить із своєї критичної секції, тому взаємні
блокування відсутні. Відсутні також зайві затримки процесів,

оскільки відразу після виходу процесу CS[i] з критичної секції
turn[i] отримує значення 0. Значення елементів масиву turn в

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

Лістинг 12 – Алгоритм поліклініки (крупномодульне рішення)

int turn[1: n] = ([n] 0);
process CS[i = 1 to n] {
while (true) {
<turn[i] = max(turn[1: n])+1;>
for [j = 1 to n st j!= i]
< await (turn[j] == 0 or turn[i] <turn[j]);>
критична секція;
turn[i] = 0;
некритична секція;

94