Вопросы_к_экзамену_по_операционным. Функции и механизмы программдиспетчеров, предшественников операционных систем
 Скачать 1.12 Mb.
|
Алгоритмы реализации взаимоисключений.Требования, предъявляемые к алгоритмамОрганизация взаимоисключения для критических участков, конечно, позволит избежать возникновения race condition, но не является достаточной для правильной и эффективной параллельной работы кооперативных процессов. Сформулируем пять условий, которые должны выполняться для хорошего программного алгоритма организации взаимодействия процессов, имеющих критические участки, если они могут проходить их в произвольном порядке.
Надо заметить, что описание соответствующего алгоритма в нашем случае означает описание способа организации пролога и эпилога для критической секции. Переменная-замок В качестве следующей попытки решения задачи для пользовательских процессов рассмотрим другое предложение. Возьмем некоторую переменную, доступную всем процессам, и положим ее начальное значение равным 0. Процесс может войти в критическую секцию только тогда, когда значение этой переменной-замка равно 0, одновременно изменяя ее значение на 1 — закрывая замок. При выходе из критической секции процесс сбрасывает ее значение в 0 — замок открывается (как в случае с покупкой хлеба студентами в разделе 5.2.). shared int lock = 0; while (some condition) { while(lock); lock = 1; critical section lock = 0; remainder section } К сожалению, внимательное изучение показывает, что такое решение, не удовлетворяет условию взаимоисключения, так как действие while(lock); lock = 1; не является атомарным. Допустим, что процесс P0протестировал значение переменной lock и принял решение двигаться дальше. В этот момент, еще до присваивания переменной lock значения 1, планировщик передал управление процессу P1. Он тоже изучает содержимое переменной lock и тоже принимает решение войти в критический участок. Мы получаем два процесса одновременно выполняющих свои критические секции. 5.3.4. Строгое чередование Попробуем решить задачу сначала для двух процессов. Очередной подход будет также использовать общую для них обоих переменную с начальным значением 0. Только теперь она будет играть не роль замка для критического участка, а явно указывать, кто может следующим войти в него. Для i-го процесса это выглядит так: shared int turn = 0; while (some condition) { while(turn != i); critical section turn = 1-i; remainder section } Легко видеть, что взаимоисключение гарантируется, процессы входят в критическую секцию строго по очереди: P0, P1, P0, P1, P0, ... Но наш алгоритм не удовлетворяет условию прогресса. Например, если значение turn равно 1 и процесс P0 готов войти в критический участок, он не может сделать этого, даже если процесс P1находится в remainder section. 5.3.5. Флаги готовности Недостаток предыдущего алгоритма заключается в том, что процессы ничего не знают о состоянии друг друга в текущий момент времени. Давайте попробуем исправить эту ситуацию. Пусть два наши процесса имеют разделяемый массив флагов готовности входа процессов в критический участок shared int ready[2] = {0, 0}; Когда i-й процесс готов войти в критическую секцию, он присваивает элементу массива ready[i] значение равное 1. После выхода из критической секции он, естественно, сбрасывает это значение в 0. Процесс не входит в критическую секцию, если другой процесс уже готов ко входу в критическую секцию или находится в ней. 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). 5.3.6. Алгоритм Петерсона Первое решение проблемы, удовлетворяющее всем требованиям и использующее идеи ранее рассмотренных алгоритмов, было предложено датским математиком Деккером (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 приступить к выполнению критической работы. Таким образом, условие прогресса выполняется. Отсюда же вытекает выполнение условия ограниченного ожидания. Так как в процессе ожидания разрешения на вход процесс P0 не изменяет значения переменных, то он сможет начать исполнение своего критического участка после не более чем одного прохода по критической секции процесса P1. |