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

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

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

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

Листинг 7.1. Текст программы для первого решения

Var перекл : integer;

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

Parbegin

Средства синхронизации и связи взаимодействующих процессов_______________ 217

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...Sll:S12; ... : S1N1 and... S21; S22; ... ; S2N2

and... SK1: SK2: ... : SKN1k parend

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

Следующая языковая конструкция означает, что каждый процесс может выпол­няться неопределенно долгое время фактически бесконечное количество раз:

while true do begin S1; S2: SN end

Наконец, конструкция типа begin end означает просто «пустой» оператор. Итак, решение, представленное в листинге 7.1, обеспечивает нам взаимное ис­ключение в работе критических секций. Однако если бы фрагмент программы PR1 был намного длиннее, чем фрагмент PR2, или если бы процесс ПР1 был за­блокирован в секции PR1, или если бы процессор для ПР2 обладал более высо­ким быстродействием, то процесс ПР2 вскоре вынужден был бы ждать входа в свою критическую секцию CS2, хотя процесс ПР1 и был бы вне CS1. Такое ожи­дание могло бы оказаться слишком долгим, то есть для этого решения один про­цесс вне своей критической секции может помешать другому войти в свою кри­тическую секцию.

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

218 Глава 7. Организация параллельных взаимодействующих вычислений

дет в критическую секцию. Этот алгоритм взаимного исключения представлен в листинге 7.2.

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

Var перекл1.перекл2.: boolean: begin перекл1:=false;

neperкп:=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:

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

PR2 { процесс ПР2 после критической секции } end

parend end.

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

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

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

var перекл1. перекл2 : boolean; begin перекл1:=false; nepeкп2:=false: parbegin

ПР1: while true do begin перекл1:=true;

Средства синхронизации и связи взаимодействующих процессов____________ 219

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.

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

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

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

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

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

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

label 1. 2;

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

ОЧЕРЕДЬ : integer:

Begin перекл 1 :=faIse: перекп2:=false; ОЧЕРЕДЬ:=1: parbegin

while true do
begin перекл1:true: продолжение

220________ Глава 7. Организация параллельных взаимодействующих вычислений

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

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

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

CS1 { критическая секция ПР1 } ОЧЕРЕДЬ: =2: перекл1:=false end end and while true do

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

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

CS2 { критическая секция ПР2 } 0ЧЕРЕДЬ:=1; перекл2:=false end end

parend end.

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

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

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