Page 93 - 6571

момент часу тільки один процес виконує протокол виходу. На
жаль, перша неподільна дія (зчитування значення number і його
збільшення) реалізувати програмно досить складно.
У деяких машин є інструкції, які повертають попереднє зна-

чення змінної і збільшують або зменшують її в одній неподільній
дії. Дані інструкції виконують необхідні для реалізації алгоритму
квитка дії. Як приклад наведемо інструкцію «витягти і скласти»

(Fetch-and-Add – FA), яка працює наступним чином.
FA(var, incr):
< int tmp = var; var = var + incr; return tmp;>

У лістингу 11 показано алгоритм квитка, реалізований за
допомогою інструкції FA.

Лістинг 11 – Алгоритм квитка (дрібномодульне рішення)
int number = 1, next = 1, turn[1: n] = ([n] 0);
process CS[i = 1 to n] {
while (true) {
turn[i] = FA(number, 1); /* протокол входу */
while (turn[i] != next) skip;

критична секція;
next = next+1; /* протокол виходу */
некритична секція;
}
}

Для машин, що не мають інструкції типу «витягти і скласти»,
необхідний інший метод. Головна вимога алгоритму квитка – ко-
жен процес повинен отримати унікальний номер. Якщо у машини

є інструкція неподільного інкременту, то перший крок протоколу
входу можна реалізувати наступним чином:

turn[i] = number;
<number = number+1;>

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

в один і той же час, і отримати один і той же номер. Тому важливо,
щоб обидва присвоювання виконувалися в одній неподільній дії.
Щоб забезпечити неподільність отримання номерів, можна

скористатися будь-яким із рішень задачі критичної секції

92