Параллельное программирование: Учебное пособие, страница 39

goto L2

end;

parend

end

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

Исключить очередность входа процессов в критическую секцию можно введением двух флажков ф1 и ф2, принимающих значения: 0 или 1. Значение ф1=0 означает нахождение процесса 1 внутри критического интервала, а ф1=1 – вне. Аналогичным образом ф2=0 определяет нахождение процесса 2 внутри, а ф2=1 – вне критического интервала.

Решение этой задачи представлено схемой алгоритма except-1 на рисунке 2.18б, а псевдокод реализации этого варианта имеет следующий вид:

begin integer ф1, ф2;   ф1:= 1; ф2:= 1;

parbegin

процесс 1: begin L1: if  ф2 = 0  then  goto  L1;

      ф1:= 0;

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

      ф1:= 1;

      остаток цикла 1; goto L1

end;

процесс 2: begin L2: if  ф1 = 0  then  goto  L2;

      ф2:= 0;

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

      ф2:= 1;

      остаток цикла 2; goto L2

end;

parend;

end

Первоначальные присваивания флажкам ф1 и ф2 значений, равных 1, связано с тем, что процессы начинаются вне своих критических интервалов. При входе первого процесса внутрь своего критического интервала будет сохраняться условие ф1=0 вплоть до момента выхода из него. Если в течение критического интервала процесса 1 к своему критическому интервалу подойдет процесс 2 и выполнит проверку занятости, то он будет выполнять ее до момента выхода процесса 1 из его критической секции. Строгая очередность входа процессов в свои критические секции в этом решении исключена, так как при выходе из критических интервалов процессы всегда оставляют для себя условия, разрешающие вход в свой критический интервал. Кроме того, реализуется взаимное исключение одновременного входа в критические интервалы.

Однако из-за различия скоростей процессов или вынужденных задержек возможна следующая ситуация. Пусть сначала процесс 1 обнаруживает, что ф2=1, а процесс 2 немедленно вслед за этим проверяет значение ф1 и тоже находит, что ф1=1. Каждый из процессов, удостоверившись, что другой процесс не находится в критическом интервале, входит в свой собственный критический интервал – и данные испорчены!

                                а)                                                                        б)

Рисунок 2.18.

Наверное, проверку допустимости входа в свою критическую секцию и установку своего флажка в ноль необходимо поменять местами? Этот вариант приведен на рисунке 2.19 со следующим фрагментом псевдокода:

begin

integer ф1, ф2;

ф1:= 1; ф2:= 1;

parbegin

пр_1: begin

A1: ф1:= 0;

B1: if ф2 = 0  then  goto  B1;

      критическая секция 1;

      ф1:= 1;

      остаток цикла 1; goto A1

end;

пр_2: begin

A2: ф2:= 0;

B2: if  ф1 = 0  then  goto  B2;

      критическая секция 2;

      ф2:= 1;

      остаток цикла 2; goto A2

end;

parend;

end 

Рисунок 2.19.

Однако и здесь обнаруживается ситуация, когда произойдет взаимная блокировка. Например, если в процессе 1 после присваивания ф1:=1, но еще до проверки флажка ф2, процесс 2 выполнит присваивание ф2:=0, то это будет означать, что оба процесса достигли своих меток В1, В2. Так как при этом флажки одновременно имеют значения, запрещающие вход в свои критические интервалы, то налицо тупиковая ситуация.

Очевидно, что длительного ожидания допуска в критическую секцию с неизменяемым состоянием собственного флажка оставлять ни в процессе 1, ни в процессе 2 нельзя. Необходимо, сделать так, чтобы синхронность входа процессов, возникающая из-за равенства скоростей процессов, нарушалась самими процессами в тот момент, когда закончилась одновременная проверка чужих флажков. Удачное решение, найденное голландским математиком Деккером, представлено на рисунке 2.20.

Рисунок 2.20.