Page 90 - 6571

критична секція;
in1 = false; /* протокол виходу */
некритична секція;
}

}
process CS2 {
while (true) {
last = 2; in2 = true; /* протокол входу */
while (in1 and last == 2) skip;
критична секція;
in2 = false; /* протокол виходу */
некритична секція;
}
}

У даній програмі вирішується проблема критичних секцій

для двох процесів. Таку ж основну ідею можна використовувати
для вирішення задачі при будь-якому числі процесів. Зокрема,
для кожного з n процесів протокол входу повинен складатися з

циклу, який проходить n-1 етапів. На кожному етапі використо-
вуються екземпляри алгоритму розриву вузла для двох процесів,
щоб визначити, які процеси проходять на наступний етап. Якщо

гарантується, що всі n-1 етапів може пройти не більше, ніж один
процес, то в критичній секції одночасно буде знаходитися не бі-
льше одного процесу.
Нехай in[1: n] та last[1: n] – цілочисельні масиви. Зна-

чення елемента in[i] вказує на номер етапу, який виконує про-
цес CS[i]. Значення last[j] вказує на номер етапу, який остан-

нім почав виконувати етап CS[j]. Підхід з використанням даних
змінних представлено в лістингу 9. Зовнішній цикл for викону-
ється n-1 раз. Внутрішній цикл for процесу CS[i] перевіряє всі

інші процеси. Процес CS[i] очікує, якщо деякий інший процес
знаходиться на етапі з рівним або більшим номером етапу, а про-
цес CS[i] був останнім процесом, що досягнув етапу j. Як тіль-

ки етапу j досягне ще один процес, або всі процеси «перед» про-
цесом CS[i] вийдуть із своїх критичних секцій, процес CS[i]
отримає можливість виконуватися на наступному етапі. Таким

чином, не більше n-1 процесів можуть пройти перший етап, n-2

89