Page 91 - 6571

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

Лістинг 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 процесів, що ілюструє
використання цілочисельних лічильників для впорядкування
процесів. Це рішення називається алгоритмом квитка, оскільки

90