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