Page 79 - 4868

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

свого протоколу входу, присвоїти змінній turn1 значення 1 і потім увійти в
критичну секцію, оскільки змінні turn1 та turn2 мають значення 1, і процес

CS1 в цьому випадку отримує перевагу. Така ситуація називається станом
гонок, оскільки процес CS1 «обганяє» CS2 і не враховує, що процес CS2
змінив значення змінної turn2.
Щоб уникнути стану гонок, необхідно, щоб кожен процес присвоював
своїй змінній turn значення 1 (або будь-яке відмінне від нуля значення) на
самому початку протоколу входу. Після цього процес повинен перевірити
значення змінної turn для інших процесів і переприсвоїти значення своєї
змінної, тобто протокол входу процесу CS1 виглядає наступним чином.

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

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

turn2 = 1; turn2 = turn1+1;
while (turn1 != 0 and turn2 >= turn1) skip;
Тепер один процес не може вийти з циклу while, поки інший не

закінчить розпочате раніше присвоювання змінній turn. У даному рішенні
процесу CS1 віддається перевага перед CS2, коли в обох процесів встановлені
ненульові значення змінної turn.
Протоколи входу процесів несиметричні, оскільки умова затримки
другого циклу злегка відрізняється від першого. Проте їх можна записати і в
симетричному вигляді. Нехай (a, b) та (c, d) – пари цілих чисел.
Визначимо відношення порівняння для них наступним чином:

(a, b) > (c, d) == true, якщо a > c або a == c та b > d
== false, в іншому випадку
Тепер можна переписати умову turn1 > turn2 процесу CS1 у вигляді
(turn1, 1) > (turn2, 2), а умову turn2 >= turn1 в процесі CS2 –
(turn2, 2) > (turn1, 1).
Перевага симетричного запису полягає в тому, що тепер алгоритм
поліклініки для двох процесів легко узагальнити на випадок n процесів
(лістинг 1.13). Кожен з процесів спочатку сигналізує, що він збирається
увійти в критичну секцію, присвоюючи своїм змінним turn значення 1, а

потім він знаходить максимальне значення з усіх turn[i] і додає до нього 1.
Нарешті, процес запускає цикл for і, як і в крупномодульному рішенні,
очікує своєї черги. Дані дії не є неподільними, тому точний результат не
гарантується. Однак, якщо декілька процесів отримують одне і те ж саме
значення, то вони упорядковуються відповідно до правила визначеного вище.

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

int turn[1: n] = ([n] 0);
process CS[i = 1 to n] {
while (true) {