The design of the UNIX Operating System 26 страница
while (some condition) { ready[i] = 1; while(ready[1-i]);
critical section ready[i] = 0;
remainder section
}
Полученный алгоритм обеспечивает взаимоисключение, позволяет процессу, готовому к входу в крити-ческий участок, войти в него сразу после завершения эпилога в другом процессе, но все равно нарушает условие прогресса. Пусть процессы практически одновременно подошли к выполнению пролога. После выполнения присваивания ready[0]=1 планировщик передал процессор от процесса 0 процессу 1, кото - рый также выполнил присваивание ready[1]=1. После этого оба процесса бесконечно долго ждут друг друга на входе в критическую секцию. Возникает ситуация, которую принято называть тупиковой (deadlock). (Подробнее о тупиковых ситуациях рассказывается в лекции 7.)
|
|
|
Алгоритм Петерсона
| Основы операционных систем | 55 |
Первое решение проблемы, удовлетворяющее всем требованиям и использующее идеи ранее рассмот-ренных алгоритмов, было предложено датским математиком Деккером (Dekker). В 1981 году Петерсон (Peterson) предложил более изящное решение. Пусть оба процесса имеют доступ к массиву флагов готов-ности и к переменной очередности.
|
|
|
shared int ready[2] = {0, 0}; shared int turn;
while (some condition) { ready[i] = 1;
turn =1-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 (когда оба процесса выполняют цикл , значения переменных из-мениться не могут). Пусть процесс P0 первым вошел в критический участок, тогда процесс P1 должен был выполнить перед вхождением в цикл while по крайней мере один предваряющий оператор (turn = 0;) . Однако после этого он не может выйти из цикла до окончания критического участка процесса P0, так как при входе в цикл ready[0] == 1 и turn == 0, и эти значения не могут измениться до тех пор, пока процесс P0 не покинет свой критический участок. Мы пришли к противоречию. Следовательно, имеет место взаимоисключение.
Докажем выполнение условия прогресса. Возьмем, без ограничения общности, процесс P0. Заметим, что он не может войти в свою критическую секцию только при совместном выполнении условий ready[1] == 1 и turn == 1. Если процесс P1 не готов к выполнению критического участка, то ready[1] == 0, и процесс P0 может осуществить вход. Если процесс P1 готов к выполнению критического участка, то ready[1] == 1 и переменная turn имеет значение 0 либо 1, позволяя процессу P0 либо процессу P1 начать выполнение критической секции. Если процесс P1 завершил выполнение критического участка, то он сбросит свой флаг готовности ready[1] == 0, разрешая процессу P0 приступить к выполнению критической работы. Та-ким образом, условие прогресса выполняется.
Дата добавления: 2021-01-21; просмотров: 100; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!