Page 96 - 6571

}
}

Алгоритм поліклініки в лістингу 11 не можливо

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

turn[j]. Дані операції можна було б реалізувати неподільним
чином, використовуючи ще один протокол критичної секції,
наприклад, алгоритм розриву вузла, але це надто неефективно.

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

узагальнити його на n процесів. Отже, розглянемо наступний
протокол входу для процесу CS1.

turn1 = turn2+1;
while (turn2 != 0 and turn1 > turn2) skip;

Аналогічний і наступний протокол входу для процесу CS2.

turn2 = turn1+1;
while (turn1 != 0 and turn2 > turn1) skip;

Кожен процес присвоює значення своїй змінній turn
відповідно з оптимізованим варіантом представленим у лістингу

12, а оператори await реалізовані у вигляді циклу з активним
очікуванням.
Проблема даного рішення полягає в тому, що ні оператори

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

змінним turn1 та tum2 значення 1. Якщо це трапиться, то обидва
процеси опиняться в своїх критичних секціях в один і той же час.
Частково вирішити дану проблему можна за аналогією з

алгоритмом 8: якщо обидві змінні turn1 і turn2 мають значення
1, то один із процесів повинен виконуватися, а інший –
призупинятися. Наприклад, нехай виконується процес з меншим

номером, тоді в умові циклу затримки процесу CS2 змінимо
другу кон’юнкцію: turn2 >= turn1.
На жаль, обидва процеси все ще можуть одночасно

виявитися в критичній секції. Припустимо, що процес CS1 зчитує

95