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

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

Рис.6.4. Модель взаимодействующих процессов

Проблема кажется легко решаемой, если потребовать, чтобы процессы ПР1 и ПР2 входили в свои критические интервалы попеременно. Для этого одна общая пе­ременная может хранить указатель того, чья очередь войти в критическую сек­цию. Текст такого решения на языке, близком к Pascal, приведен в листинге 6.1.

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

Var перекл : integer;

Begin перекл := 1: {при перекл=1 в CS находится процесс ПР1 }

Parbegin

While true do

Begin

while перекл = 2 do begin end;

CS1: { Критическая секция процесса ПР1 }

перекл := 2;

PR1; { оставшаяся часть процесса ПР1 }

End

And

While true do

Begin

while перекл = 1 do begin end;

CS2; { Критическая секция процесса ПР2 }

перекл := 1;

PR2; { оставшаяся, часть процесса ПР2}

End

Parend

End.

Здесь и далее конструкция следующего типа

parbegin...S11; S12; ... ; S1N₁

and... S21; S22; ... ; S2N₂

and... SK1; SK2; ... ; SKN_1k

parend.

означает параллельность К описываемых последовательных процессов. Конструкция из операторов S11; S12; ... ; S1N1 выполняется оператор за оператором, о чём свидетельствует наличие точки с запятой между операторами.

Конструкция

while true do

begin S1; S2; SN end

означает, что каждый процесс может выполняться неопределённое время. Конст­рукция типа begin end означает «пустой» оператор.

Итак, решение, представленное в листинге 6.1, обеспечивает взаимное исключение в работе критических интервалов. Однако если бы часть программы PR1 была намного длиннее, чем программа PR2, или если бы процесс ПР1 был заблокирован в секции PR1, или если бы процессор для ПР2 был с большим быстро­действием, то процесс ПР2 вскоре вынужден был бы ждать (и, может быть, чрезвычайно долго) входа в свою критическую секцию CS2, хотя процесс ПР1 и был бы вне CS1. То есть при таком решении один процесс вне своей критической секции может помещать вхождению другого в свою критическую секцию.

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

Пусть с каждым из процессов ПР1 и ПР2 будет связана переменная, по смыслу являющаяся переключателем, которая принимает значение true, когда процесс находится в своем критическом интервале, и false – в противном случае. Преж­де чем войти в свой критический интервал, процесс проверяет значение пере­ключателя другого процесса. Если это значение равно true, процессу не разре­шается входить в свой критический интервал. В противном случае процесс «включает» свой собственный переключатель и входит в критический интервал. Этот алгоритм взаимного исключения представлен в листинге 6.2.

Данный алгоритм не гарантирует полного выполнения условия нахождения толь­ко одного процесса внутри критического интервала. Отсутствие гарантий связа­но с различными, в общем случае, скоростями развития процессов. Поэтому, например, между проверкой значения переменной перекл2 процессом ПР1 и последующей установкой им значения переменной перекл1 параллельно выполняющийся процесс ПР2 может установить перекл2 в значение true, так как перекл1 ещё не успел установиться в значение true. Отсюда следует, что оба процесса мо­гут войти одновременно в свои критические интервалы.

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

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

begin перекл1=false;

перекл2:=false;

parbegin

while true do

begin

while перекл2 do

begin

end;

перекл1:=true;

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

перекл1:=false;

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

end

and

while true do

begin

while перекл1 do

begin

end;

перекл2:=true;

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

перекл2:=false;

(* процесс ПР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 перекл1=false; перекл2:=false;

ОЧЕРЕДЬ:=1;

parbegin

while true do

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

1: if nepeкл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:=false

end

end

and

while true do

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

2: if перекл1=true 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 и переклl=fa1se, то выполняется критический интервал процесса ПР2 независимо от значения переменной ОЧЕРЕДЬ. Аналогично для случая перекл2=fa1se и перекл1=true.

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

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