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

Примером программной реализации взаимного исключения является алгоритм Деккера (названный так по имени предложившего его голландского математика Деккера), позднее усовершенствованный Дейкстрой. Программа использует три общие для обоих процессов переменные (рис.4.12) : flag[1] и flag[2], устанавливающие возможность входа в критический интервал соответственно первого и второго процесса, и turn, определяющую номер выбранного процесса.

Процесс P1 уведомляет о желании войти в свой критический участок, устанавливая свой флаг. Затем он переходит к циклу, в котором проверяет, не хочет ли также войти в свой критический участок и P2. Если флаг Р2 не установлен, то Р1 пропускает тело цикла ожидания и входит в свой критический участок. Предположим, однако, что Р1 при выполнении цикла проверки обнаруживает, что флаг Р2 установлен. Это заставляет Р1 войти в тело своего цикла ожидания. Здесь он анализирует значение переменной turn, которая используется для разрешения конфликтов, возникающих в случае, когда оба процесса одновременно хотят войти в свой критический участок. Если избранным процессом является Р1, он пропускает тело своего цикла if и повторно выполняет цикл проверки в ожидании момента, когда Р2 сбросит свой флаг. (Процесс Р2 со временем должен это сделать.). Если процесс Р1 определяет, что преимущественное право принадлежит процессу Р2, он входит в тело своего цикла if, где сбрасывает свой собственный флаг, а затем блокируется в цикле ожидания, пока избранным процессом остается Р2. Сбрасывая свой флаг, Р1 дает возможность Р2 войти в свой критический интервал. Со временем Р2 выйдет из своего критического участка и обеспечит возврат преимущественного права процессу Р1 и сброс флага Р2. Теперь у Р1 появляется возможность выйти из внутреннего цикла ожидания while и установить собственный флаг. Затем Р1 выполняет внешний цикл проверки. Если флаг Р2 (недавно сброшенный) по-прежнему сброшен, то Р1 входит в свой критический участок. Если, однако, Р2 сразу же пытается вновь войти в свой критический участок, то его флаг будет установлен, и Р1 снова придется войти в тело внешнего цикла while. Однако на этот раз «бразды правления» находятся уже у процесса Р1, поскольку сейчас именно он является избранным процессом (процесс Р2, выходя из своего критического ин тервала, установил для переменной turn - номера избранного процесса - значение 1). Поэтом­у Р1 пропускает тело условной конструкции if и многократно выполняет внешний цикл проверки, пока Р2 не сбросит собственный флаг, позволяя процессу Р1 войти в свой критический интервал.

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

флаг и вновь войдет в свой критический интервал. Когда Р1 снова захватит

Program Dekker’s algorithm;

Var flag: array[1..2] of boolean;

turn: 1..2;

Procedure Process P1;

begin

repeat

flag[1] := true ;

while flag[2] do

if turn = 2 then

begin

flag[1] := false;

while turn = 2 do;

flag[1] := true

end;

< критический интервал >;

turn := 2 ;

flag[1] := false ;

< остальная часть программы >

until false

end ;

Procedure Process P2;

begin

repeat

flag[2] := true ;

while flag[1] do

if turn = 1 then

begin

flag[2] := false;

while turn = 1 do;

flag[2] := true

end;

< критический интервал >;

turn := 1 ;

flag[2] := false ;

< остальная часть программы >

until false

end ;

Begin

flag[1] := false ;

flag [2] := false ;

turn := 1 ;

Process P1 ;

Process P2

End .

Рис. 4.12. Реализация взаимного исключения согласно алгоритму Деккера

процессор, он установит свой флаг. Поскольку сейчас будет очередь процесса Р1, то Р2, если он попытается вновь войти в свой критический интервал, должен будет сбросить свой флаг и перейти на внутренний ­цикл активного ожидания, так что Р1 получит возможность входа в свой критический интервал. Этот прием позволяет решить проблему бесконечного ожидания.