Page 74 - 4868

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

своїх критичних секцій, процес CS[i] отримає можливість виконуватися на
наступному етапі. Таким чином, не більше n-1 процесів можуть пройти

перший етап, n-2 – другий і так далі. Це гарантує те, що пройти всі n етапів і
виконувати свою критичну секцію процеси можуть тільки по одному.

Лістинг 1.9– Алгоритм розриву вузла для n процесів
int in[1: n] = ([n] 0), last[1: n] = ([n] 0);
process CS[i = 1 to n] {
while (true) {
for [j = 1 to n] { /* протокол входу */
//запам'ятати, що процес i знаходиться на етапі j
// і є останнім
last[j] = i;
in[і] = j;
for [k = 1 to n st i!= k] {
//чекати, якщо процес k знаходиться на етапі
// з великим номером і процесiбув останнім
// із пройшовших на етап j
while (in[k] >= in[i] and last[j] == i) skip;
}
}
критична секція;
in[і] = 0; /* протокол виходу */
некритична секція;
}
}

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

11.2. Алгоритм квитка

Алгоритм розриву вузла для n процесів дуже складний та заплутаний,
оскільки не завжди очевидне узагальнення алгоритму для двох процесів на
випадок n процесів. Побудуємо більш прозоре рішення задачі критичної
секції для n процесів, що ілюструє використання цілочисельних лічильників
для впорядкування процесів. Це рішення називається алгоритмом квитка,
оскільки ґрунтується на витягуванні квитків (номерів) і подальшого
очікування своєї черги (лістинг 1.10).
Нехай number та next – цілочисельні змінні з початковими значеннями
1, a turn[1: n] – масив цілих чисел з початковими значеннями 0. Щоб
увійти в критичну секцію, процес CS[i] спочатку присвоює елементу
turn[i] поточне значення number і збільшує значення number на 1. Для
того, щоб процеси (відвідувачі) отримували унікальні номери, ці дії повинні