Van перекл1.Перекл2.: boolean: begin nepewil:-false;

перекл2:-false; parbegin

while true do begin

while перекл2 do begin end:

перекл!:-true;

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

PR! (* процесс ПР1 после критического интервала *) end and

while true do begin

while перекл! do begi n end; nepewi2:=true;

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

(* процесс ПР2 после критического интервала *) end pa rend end.

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

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

van перекл!. перекл2 : boolean: begin перекл!:-false; nepewi2:=false: parbegin

ПР1: while true do begin

перекл!:=true;

while перекл2 do

begin end:

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

PR! { ПР1 после критического интервала } end and

ПР2: while true do begin

перекл2:Чгие; while перекл! do

begin end;

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

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

parend end.

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

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

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

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

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

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

label 1. 2;

var перекл!. перекл2: boolean:

ОЧЕРЕДЬ : integer; Begin перекл!:=false: nepe^2:=false:

ОЧЕРЕДЬ :=!; продолжение #

Листинг 6.4 (продолжение)

parbegin

while true do

begin перекл!:-true: 1: if nepetui2-true then \

if ОЧЕРЕДЬ-! then go to 1 _;

else begin nepewil:=fa1se; while ОЧЕРЕДЬ-2 do

begin end end else begin

CS1 { Критический интервал ПР1 } ОЧЕРЕДЬ:=2: перекл!:-false end end and

while true do .

begin перекл2:-1: 2: if nepewil-true then

if ОЧЕРЕДЬ=2 then go to 2 else begin перекл2:-false; while ОЧЕРЕДЬ=1 do

begin end end else begin

CS2 ( Критический интервал ЛР2 } ОЧЕРЕДЬ:-!; nepewi2:-false end end parend end.

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

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