Page 92 - 6571

ґрунтується на витягуванні квитків (номерів) і подальшого очіку-
вання своєї черги (лістинг 10).

Лістинг 10 – Алгоритм квитка (крупномодульне рішення)
int number = 1, next = 1, turn[1: n] = ([n] 0);

process CS[i = 1 to n] {
while (true) {
<turn[i] = number;
number = number+1;>
< await(turn[i] == next);>
критична секція;
<next = next+1;>
некритична секція;
}
}

Нехай number та next – цілочисельні змінні з початковими
значеннями 1, a turn[1: n] – масив цілих чисел з початковими

значеннями 0. Щоб увійти в критичну секцію, процес CS[i]
спочатку присвоює елементу turn[i] поточне значення number
і збільшує значення number на 1. Для того щоб процеси

(відвідувачі) отримували унікальні номери, ці дії повинні
виконуватися неподільним чином. Після цього процес CS[i]

очікує, поки значення змінної next не стане рівним номеру, який
вони отримали. При завершенні критичної секції процес CS[i]
знову в неподільній дії збільшує на 1 значення next.
На відміну від алгоритму розриву вузла, алгоритм квитка має

потенційний недолік, загальний для алгоритмів, що
використовують нарощення лічильника: значення number та

next необмежені. Якщо алгоритм квитка виконувати досить
довго, то збільшення лічильників призведе до арифметичного
переповнення. Однак на практиці це малоймовірно і не є
суттєвою проблемою.

Алгоритм в лістингу 10 містить три крупномодульні дії.
Оператор await легко реалізується циклом з активним

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

91