Использование блокировки памяти при синхронизации параллельных процессов

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

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

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

Пусть имеются два (или более) циклических процесса, в которых есть абстракт­ные критические секции, то есть каждый из процессов состоит из двух частей: некоторого критического интервала и оставшейся части кода, в которой нет рабо­ты с общими (критическими) переменными. Пусть эти два процесса асинхронно разделяют во времени единственный процессор либо выполняются на отдель­ных процессорах, каждый из которых имеет доступ к некоторой общей области памяти, с которой и работают критические секции. Проиллюстрируем эту ситуа­цию с помощью рис. 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_k

parend

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

Конструкция

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;

перекл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 и войдут в бесконечный цикл. В этом случае будет нарушено требование отсутствия бесконечного ожидания входа в свой критиче­ский интервал. Предположив, что скорости исполнения процессов произвольны, мы получили такую последовательность событий, при которой процессы вообще перестанут нормально выполняться.

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

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