Parbegin

Begin

Begin

Begin

Begin

Begin

Begin

Begin

End.

Parend

Процесс_Y

Parbegin

Begin

Begin

while (КЛЮЧ_X) do; {ожидание пока процесс X не выйдет из критического участка}

КЛЮЧ_Y:=true;

{Критический участок Y}

КЛЮЧ_Y:=false; {признак выхода процесса Y из критического участка}

{Оставшаяся часть процесса Y}

end;

end;

КЛЮЧ_X:=false;

КЛЮЧ_Y:=false;

Процесс_Х;

Каждый из процессов представляет собой бесконечный цикл с многократным вхождением в свой критический участок. Примитив взаимоисключения реализуется в каждом процессе, как цикл while, который повторяется до тех пор, пока параллельно выполняемый процесс не выйдет из своего критического участка.

Однако заметим, что если скорости процессов произвольные, то может возникнуть ситуация, когда оба процесса получают возможность выполнять свои критические участки одновременно.

Рассмотреть этот вариант самостоятельно.

Если процесс Y заканчивает выполнение своего критического участка и устанавливает в переключателе КЛЮЧ_Y значение false,,тем самым допускает процесс Х к выполнению своего критического участка. Пусть процесс Y работает значительно быстрее процесса Х, настолько, что прежде чем процесс Х установит свой КЛЮЧ_Х в состояние true, свидетельствующее о входе этого процесса в критический участок, процесс Y уже выполнит оставшуюся часть процесса и, не обнаружив в переменной КЛЮЧ_Х значения true, также получает доступ к критическому участку. Таким образом предложенный алгоритм полностью не решает проблему критического участка.

Алгоритм Деккера (Dekker’s Algorithm)

Изящную программную реализацию механизма взаимоисключения предложил голландский математик Деккер (кроме того решению этой проблемы посвящены следующие статьи, где этот алгоритм был обобщен и для случая произвольного числа конкурирующих из-за критического ресурса процессов2).

var C1,C2,ОЧЕРЕДЬ:integer;

procedure Процесс_Х;

C1:=1;

while (C2=1) do

if ОЧЕРЕДЬ=2 then

C1:=0;

while (ОЧЕРЕДЬ=2) do;

C1:=1;

end;

end;

{Критический участок процесса Х}

C1:=0;

ОЧЕРЕДЬ:=2;

{Оставшаяся часть процесса Х}

end;

procedure Процесс_Y;

C2:=1;

while (C1=1) do

if ОЧЕРЕДЬ=1 then

C2:=0;

while (ОЧЕРЕДЬ=1) do;

C2:=1

end;

end;

{Критический участок процесса Y}

C2:=0;

ОЧЕРЕДЬ:=1;

{Оставшаяся часть процесса Y}

end;

C1:=0;

C2:=0;

ОЧЕРЕДЬ:=1;

Процесс_X;

Дата добавления: 2014-01-03