Page 76 - 4868

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

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 гарантовано має правильний приріст, але процеси

можуть не отримати унікальних номерів. Наприклад, кожен з процесів може
виконати перше присвоювання приблизно в один і той же час, і отримати
один і той же номер. Тому важливо, щоб обидва присвоювання виконувалися
в одній неподільній дії.
Щоб забезпечити неподільність отримання номерів, можна скористатися
будь-яким із рішень задачі критичної секції (наприклад циклічні блокування
або алгоритм розриву вузла). Наприклад, нехай CSenter– протокол входу
критичної секції, a CSexit - відповідний протокол виходу. Тоді в програмі з
лістингу 1.11 інструкцію «витягти і скласти» можна замінити наступною
послідовністю операторів:
CSenter;
turn[i] = number;
number = number+1;
CSexit;

Такий підхід виглядає незвичайним, але на практиці він працює добре,
особливо якщо для реалізації протоколів входу і виходу доступна інструкція
типу «перевірити-встановити». При виконанні інструкції «перевірити-
встановити» процеси отримують номери, що не обов’язково відповідають
порядку, в якому вони намагаються це зробити, і теоретично процес може
зациклитися назавжди. Але з дуже високою ймовірністю кожен процес
отримає номер, і більшість номерів будуть обрані в порядку їх зростання.
Основна причина виникнення затримок в алгоритмі квитка – це очікування,
поки значення змінної next не стане рівним значенню turn[i].