Дейкстра представил алгоритм взаимных исключений для двух процессов, предложенный голландским математиком Деккером. Рассмотрим его поэтапно.
1-я попытка. Наиболее общим механизмом может служить ограничение, согласно которому к некоторой ячейке памяти в определенный момент времени может осуществляться только одно обращение.
Рассмотрим два процесса, которые конкурируют за один ресурс. Введем глобальную переменную, что указывает на номер процесса int turn = 0. Если процесс (Р0 или Р1) намерен выполнить критический раздел, то он сначала проверяет содержимое ячейки turn. Если значение ее равно номеру процесса, то процесс может войти в критический раздел. Такая процедура известна как пережидание занятости. После выхода из критического раздела процесс должен обновить значение turn, присвоив ему номер другого процесса.
№1 /* Процес 0 */ /* Процес 1 */
while (turn ! = Ø ); /* ждем */ while (turn ! = 1 ); /* ждем */
< критичний розділ > < критичний розділ >
turn = 1; turn = 0;
Это решение гарантирует корректную работу взаимоисключения, однако имеет два недостатка. Во-первых, при входе в критический раздел процессы должны строго чередоваться. Поэтому скорость работы диктуется более медленным из двух процессов. Если процессу Р0 вход в критический раздел требуется один раз в час, а процессу Р1 – 100 раз в час, то темп работы Р1 будет таким же, как и у процесса Р0. Во-вторых, гораздо более серьезная ситуация возникает в случае сбоя одного из процессов – при этом второй процесс будет заблокирован.
2-я попытка. Проблема в 1-ой попытке заключается в том, что в глобальной переменной хранилось имя процесса, который имел право входа в критический раздел, в то время как нам в действительности требуется информация об обоих процессах. По сути, каждый процесс должен иметь собственный ключ к критическому разделу, так что если даже произойдет сбой одного процесса, второй все равно сможет получить доступ к критическому разделу.
Для удовлетворения этого условия определим логический вектор flag, в котором flag[0] соответствует процессу Р0, а flag[1] – процессу Р1. Их можно проверять обоим процессам, но изменять - только свою.
Теперь, в случае сбоя одного из процессов вне критического раздела (включая код установки значения флага), второй процесс заблокирован не будет. Второй процесс будет иметь возможность входа в критический раздел всякий раз, как только ему потребуется, поскольку флаг другого процесса всегда будет иметь значение false. Однако если сбой произойдет в критическом разделе (или перед входом в критический раздел, но после установки значения флага равным true), то другой процесс окажется навсегда заблокированным.
№2 while (flag[1]); /* ждем */ while (flag[0]); /* ждем */
flag[0] = true; flag[1] = true;
< критический раздел >< критический раздел >
flag[0] = false; flag[1] = false;
Описанное решение, по сути, оказывается еще хуже 1-го решения, поскольку даже не гарантирует взаимного исключения. Рассмотрим такую последовательность действий:
Р0 выполняет инструкцию while и находит, что flag[1] равен false;
Р1 выполняет инструкцию while и находит, что flag[0] равен false;
Р0 устанавливает значение flag[0] = true и входит в критический раздел;
Р1 устанавливает значение flag[1] = true и входит в критический раздел.
Поскольку оба процесса одновременно находятся в критическом разделе, программа некорректна. Проблема в том, что предложенное решение не является независимым от относительной скорости выполнения процессов.
3-я попытка.Возможно, нам удастся исправить ситуацию внесением в код небольшого изменения.
№3 flag[0]=true; flag[1]=true;
while (flag[1]); / * ждем */ while (flag[0]); / * ждем */
/* критический раздел */ /* критический раздел */
flag[0]=false flag[1]=false
Проверим гарантированность взаимоисключения, проследив за процессом Р0. Если РО установить flag[0] = true, Р1 не сможет войти в критический раздел до тех пор, пока туда не войдет и затем не покинет его процесс РО. Может оказаться так, что процесс Р1 уже находиться в критическом разделе в тот момент, когда РО устанавливает свой флаг.
В этом случае Р0 будет заблокирован оператором WHІLE до тех пор, пока Р1 не покинет критический раздел. Одно и то же возникает для Р1. То самим гарантируется взаимное исключение, но третья попытка порождает еще одну проблему. Если оба процесса устанавливают flag[0], flag[1] равным true до того, как один из них выполнит оператор while, то каждый из процессов будет считать, что другой находится в критическом разделе, и тем самим состоится взаимоблокировка.
4-я попытка. В третьей попытке установка процессом флага состояния выполнялась без учета информации о состоянии другого процесса. Взаимоблокировка возникла из-за того, что каждый процесс мог добиваться своих прав на вход в критический раздел, и отсутствовала возможность возвратиться назад из этого положения. Можно попробовать исправить ситуацию, делая процессы более "уступчивыми": каждый процесс, устанавливая свой flag равным true, указывает о своем желании войти в критический раздел, но готов отложить свой вход, уступая другому процессу, как это показано в 4 - ой попытке.
№4 flag[0]=true; flag[1]=true;
while (flag[1]) while (flag[0])
{ flag[0]=false; { flag[1]=false;
/ * Задержка*/ / * Задержка*/
flag[0]=true; } flag[1]=true; }
/* критический раздел */ /* критический раздел*/
flag[0]=false; flag[1]=false;
Это уже лучше, но не совсем. Взаимоисключение гарантируется (в чем можно убедиться, применяя те же рассуждения, что и при 3-ей попытке), но рассмотрим возможный ряд событий.
Р0 устанавливает flag[0] true
Р1 устанавливает flag[1]true
Р0 проверяет flag[1]
Р1 проверяет flag[0]
Р0 устанавливает flag[0] false
Р1 устанавливает flag[1] false
Р0 устанавливает flag[0] true
Р1 устанавливает flag[1] true
Эту последовательность можно продолжать долго - и ни один из процессов не сможет войти в критический раздел. Строго говоря, это не взаимоблокировка, поскольку любое изменение относительной скорости двух процессов разорвет замкнутый круг и позволит одному из процессов войти в критический раздел. Назовем эту ситуацию неустойчивой взаимоблокировкой. Обычное взаимоблокировка осуществляется, когда несколько процессов желают войти в критический раздел, но ни одному из них это не удается. В случае неустойчивой взаимоблокировки существует приводящая к успеху последовательность действий, но, вместе с тем, возможная и такая, когда ни один из процессов не сможет войти в критический раздел.
Хотя такой сценарий маловероятен, и вряд ли такая последовательность будет продолжаться долго, тем не менее, теоретически такая возможность имеется. Поэтому мы должны отвергнуть как неудачную и 4-ю попытку.
Правильное решение.
У нас уже есть возможность следить за состоянием обоих процессов с помощью flag. Но, как показала четвертая попытка, этого недостаточно. Мы должны навязать определенный порядок действий двум процессам, во избежание проблемы "взаимной вежливости", с которой только что столкнулись. Для этого можно использовать переменную turn из 1-ой попытки. В нашем случае эта переменная указывает, какой из процессов имеет право на вход в критический раздел.
Можно описать это решение так. Когда Р0 намеревается войти в критический раздел, он устанавливает свой флаг равным true, а затем проверяет состояние флага процесса Р1. Если он равен false, Р0 может немедленно входить в критический раздел, иначе Р0 обращается к переменной turn.
Если turn=0, это означает, что сейчас очередь процесса Р0 на вход в критический раздел, и Р0 периодически проверяет состояние flag[1] для Р1. Процесс Р1, в свою очередь, в некоторый момент времени обнаруживает, что сейчас не его очередь для входа в критический раздел и устанавливает свой flag в false, давая возможность процессу Р0 войти в критический раздел. После того как Р0 выйдет из критического раздела, он установит свой флаг равным false для освобождения критического раздела, и присвоит переменной turn значение 1 для передачи прав на вход в критический раздел процессу Р1.
Полный алгоритм Деккера приведен ниже. Его доказательство оставляется как упражнение.
true