Var перекл1,перекл2: boolean;

begin перекл1:=false;

перекл2:=false;

parbegin

while true do

begin

while перекл2 do

begin end;

переклl:=true;

CS1; (* Критический интервал процесса ПР1 *)

nepeклl:=false:

PR1; (* процесс ПР1 после критического интервала *)

end

and

while true do

begin

while перекл1 do

begin end;

перекл2:=true;

CS2; (* Критический интервал процесса ПР2 *)

перекл2:=fa1se;

PR2; (* процесс ПР2 после критического интервала *)

end

parend

end.

Следующий (третий) вариант решения этой задачи (листинг 6.3) усиливает взаимное исключение, так как в процессе ПР1 проверка значения переменной перекл2 выполняется после установки переменной перекл1 в значение true (анало­гично для ПР2).

Листинг 6.3. Третий вариант попытки реализации взаимного исключения

Var перекл1,перекл2 : boolean;

begin перекл1:=false;

перекл2:=false;

parbegin

ПР1: while true do

begin

перекл1:=true:

while перекл2 do

begin end;

CS1;{ Критический интервал процесса ПР1 }

перекл1:=false;

PR1;{ ПР1 после критического интервала }

end

and

ПР2: while true do

begin

перекл2:=trueж

while перекл1 do

begin end;

CS2; { Критический интервал процесса ПР2 }

перекл2:=false;

PR2; { ПР2 после критического интервала }

end

parend

end.

Алгоритм, приведенный в листинге 6.3, также имеет свои недостатки. Действи­тельно, возможна ситуация, когда оба процесса одновременно установят свои пе­реключатели в значение true и войдут в бесконечный цикл. В этом случае будет нарушено требование отсутствия бесконечного ожидания входа в свой критиче­ский интервал. Предположив, что скорости исполнения процессов произвольны, мы получили такую последовательность событий, при которой процессы вообще перестанут нормально выполняться.

Рассмотренные попытки решить проблему критических интервалов иллюстри­руют некоторые тонкости, лежащие в основе этой проблемы.

Последний вариант решения задачи взаимного исключения, использующий только блокировку памяти, который мы рассмотрим, — это известный алгоритм, пред­ложенный математиком Деккером.

Алгоритм Деккера

Алгоритм Деккера основан на использовании трех переменных (листинг 6.4): перекл1, перекл2 и ОЧЕРЕДЬ. Пусть по-прежнему переменная перекл1=true тогда, ког­да процесс ПР1 хочет войти в свой критический интервал (для ПР2 аналогич­но), а значение переменной ОЧЕРЕДЬ указывает, чье сейчас право сделать попытку входа, при условии, что оба процесса хотят выполнить свои критические интер­валы.

Листинг 6.4. Алгоритм Деккера

label 1, 2;

var перекл1, перекл2: boolean;

ОЧЕРЕДЬ : integer;

begin пepeкл1:=false;

перекл2:=false;

ОЧЕРЕДЬ:=1;

parbegin

while true do

begin перекл1:=true;

1: if перекл2=true then

if ОЧЕРЕДЬ=1 then go to 1

else begin перекл1:=false;

while ОЧЕРЕДЬ=2 do

begin end

end

else begin

CS1; { Критический интервал ПР1 }

ОЧЕРЕДЬ:=2;

перекл1:=faIse;

end

end

and

while true do

begin перекл2:=true;

2: if перекл1=truе then

if ОЧЕРЕДЬ=2 then go to 2

else begin перекл2:=false;

while ОЧЕРЕДЬ=1 do

begin end

end

else begin

CS2; { Критический интервал ПР2 }

ОЧЕРЕДЬ:=1;

перекл2:=false

end

end

parend

end.

Если перекл2=true и перекл1=false, то выполняется критический интервал про­цесса ПР2 независимо от значения переменной ОЧЕРЕДЬ. Аналогично для случая перекл2=false и перекл1=tгue.

Если же оба процесса хотят выполнить свои критические интервалы, то есть перекл2=true и перекл1=true, то выполняется критический интервал того процесса, на который указывало значение переменной ОЧЕРЕДЬ, независимо от скоростей развития обоих процессов. Использование переменной ОЧЕРЕДЬ совместно с перекл1 и перекл2 в алгоритме Деккера позволяет гарантированно решать проблему кри­тических интервалов. Переменные перекл1 и перекл2 обеспечивают, что взаимное выполнение не может иметь места; переменная ОЧЕРЕДЬ гарантирует от взаимного блокирования. Взаимное блокирование невозможно, так как переменная не из­меняет своего значения во время выполнения программы принятия решения о том, кому же сейчас проходить свой критический интервал.

Тем не менее, реализация критических интервалов на основе описанного алго­ритма практически не используется из-за чрезмерной сложности, особенно в случаях, когда алгоритм Деккера обобщается с двух до N процессов.