Алгоритм Петерсона
shared int ready [2] = {0, 0}';
shared int turn;
while (some condition) { ready[i] = 1 ;
turn =l-i;
while(ready[1-i] && turn == 1-i);
critical section ready [i] = 0;
remainder section
}
При исполнении пролога критической секции процесс Pi заявляет о своей готовности выполнить критический участок и одновременно предлагает другому процессу приступить к его выполнению. Если оба процесса подошли к прологу практически одновременно, то они оба объявят о своей готовности и предложат выполняться друг другу. При этом одно из предложений всегда следует после другого. Тем самым работу в критическом участке продолжит процесс, которому было сделано последнее предложение.
Давайте докажем, что все пять наших требований к алгоритму действительно удовлетворяются.
Удовлетворение требований 1 и 2 очевидно.
Докажем выполнение условия взаимоисключения методом от противного. Пусть оба процесса одновременно оказались внутри своих критических секций. Заметим, что процесс Pi может войти в критическую секцию, только если ready [ 1-i ] == 0 или turn == i. Заметим также, что если оба процесса выполняют свои критические секции одновременно, то значения флагов готовности для обоих процессов совпадают и равны 1. Могли ли оба процесса войти в критические секции из состояния, когда они оба одновременно находились в процессе выполнения цикла while? Нет, так как в этом случае переменная turn должна была бы одновременно иметь значения 0 и 1 (когда оба процесса выполняют цикл, значения ‘переменных измениться не могут). Пусть процесс Ро первым вошел в критический участок, тогда процесс Pi должен был выполнить перед вхождением в цикл while по крайней мере один предваряющий оператор (turn = 0;).
Однако после этого он не может выйти из цикла до окончания критического участка процесса Ро, так как при входе в цикл ready [0] == 1 и turn == 0, и эти значения не могут измениться до тех пор, пока процесс Ро не покинет свой критический участок. Мы пришли к противоречию. Следовательно, имеет место взаимоисключение.Докажем выполнение условия прогресса. Возьмем, без ограничения общности, процесс Ро. Заметим, что он не может войти в свою критическую
секцию только при совместном выполнении условий ready [1] == 1 и
turn == 1. Если процесс Pi не готов к выполнению критического участка, то ready [1] == 0, и процесс Ро может осуществить вход. Если
процесс Pi готов к выполнению критического участка, то ready [ 1 ] == 1 и переменная turn имеет значение 0 либо 1, позволяя процессу Ро либо процессу Pi начать выполнение критической секции. Если процесс Pi завершил выполнение критического участка, то он сбросит свой флаг готовности ready [ 1 ] == 0, разрешая процессу Ро приступить к выполнению критической работы. Таким образом, условие прогресса выполняется.
Отсюда же вытекает выполнение условия ограниченного ожидания. Так как в процессе ожидания разрешения на вход процесс р0 не изменяет значения переменных, он сможет начать исполнение своего критического участка после не более чем одного прохода по критической секции процесса Pi.
Еще по теме Алгоритм Петерсона:
- МЕТОДИКА ПЕТЕРСОНОВ
- Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
- АЛГОРИТМ
- АЛГОРИТМ УДАЧИ
- Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
- Алгоритм исцеления:
- Алгоритм избавления от боли
- § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
- Алгоритм обработки результатов.
- 2. Специфика и алгоритмы работы с источниками.
- СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
- 2. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.
- ЗАДАЧА: РЕШЕНИЕ
- Переживание