Page 78 - 4868

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

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

Лістинг 1.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;
некритична секція;
}
}

Для вирішення задачі синхронізації 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 відповідно з
оптимізованим варіантом представленим у лістингу 1.12, а оператори await
реалізовані у вигляді циклу з активним очікуванням.
Проблема даного рішення полягає в тому, що ні оператори
присвоювання, ні цикли while не виконуються неподільним чином. Отже,
процеси можуть розпочати виконання своїх протоколів входу приблизно
одночасно, і обидва присвоять змінним turn1 та tum2 значення 1. Якщо це
трапиться, то обидва процеси опиняться в своїх критичних секціях в один і
той же час.
Частково вирішити дану проблему можна за аналогією з алгоритмом 1.8:
якщо обидві змінні turn1 і turn2 мають значення 1, то один із процесів
повинен виконуватися, а інший – призупинятися. Наприклад, нехай
виконується процес з меншим номером, тоді в умові циклу затримки процесу
CS2 змінимо другу кон’юнкцію: turn2 >= turn1.
На жаль, обидва процеси все ще можуть одночасно виявитися в
критичній секції. Припустимо, що процес CS1 зчитує значення turn2 і
отримує 0. Процес CS2 починає виконувати свій протокол входу, визначає,
що змінна turn1 все ще має значення 0, присвоює змінній turn2 значення 1

і входить в критичну секцію. У цей момент CS1 може продовжити виконання