Page 75 - 4868

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

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

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

Лістинг 1.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.10 містить три крупномодульні дії. Оператор
await легко реалізується циклом з активним очікуванням, оскільки в
булевому виразі використана тільки одна спільна змінна. Останню
неподільну дію, що виконує збільшення змінної next, можна реалізувати за
допомогою звичайних інструкцій завантаження і збереження, оскільки в
будь-який момент часу тільки один процес виконує протокол виходу. На
жаль, перша неподільна дія (зчитування значення number і його збільшення)
реалізувати програмно досить складно.
У деяких машин є інструкції, які повертають попереднє значення змінної
і збільшують або зменшують її в одній неподільній дії. Дані інструкції
виконують необхідні для реалізації алгоритму квитка дії. Як приклад
наведемо інструкцію «витягти і скласти» (Fetch-and-Add – FA), яка працює
наступним чином.

FA(var, incr):
< int tmp = var; var = var + incr; return tmp;>

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

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

int number = 1, next = 1, turn[1: n] = ([n] 0);