<<
>>

Алгоритм Петерсона

Первое решение проблемы, удовлетворяющее всем требованиям и использующее идеи ранее рассмотренных алгоритмов, было предложено датским математиком Деккером (Dekker). В 1981 году Петерсон (Peterson) предложил более изящное решение.
Пусть оба процесса имеют доступ к массиву флагов готовности и к переменной очередности:

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.

<< | >>
Источник: В.Е. Карпов К.А. Коньков. Основы операционных систем. 2005

Еще по теме Алгоритм Петерсона:

  1. МЕТОДИКА ПЕТЕРСОНОВ
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. АЛГОРИТМ
  4. АЛГОРИТМ УДАЧИ
  5. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  6. Алгоритм исцеления:
  7. Алгоритм избавления от боли
  8. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  9. Алгоритм обработки результатов.
  10. 2. Специфика и алгоритмы работы с источниками.
  11. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  12. 2. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.
  13. ЗАДАЧА: РЕШЕНИЕ
  14. Переживание