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

Для этого понадобилось объединить вместе установку очередности входа процессов в свои критические секции с помощью общего флажка ф (см. рис. 2.18а) и сохранить в каждом процессе управление состоянием собственного флажка, ограждающего свою критическую секцию, как это было на рисунке 2.19. Теперь после проверки чужого ограждающего флажка вместо ожидания осуществляются действия по установке очередности входа.

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

proc except_3(...)

begin integer ф1, ф2, ф;

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

parbegin

пр_1: begin

А1: ф1: = 0;

B1: if ф2 = 0 then

begin

if ф = 1 then goto B1;

ф1:= 1;

C1: if ф = 2 then goto C1;

  gotoА1

end;

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

ф:= 2; ф1:= 1;

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

goto А1

end;

пр_2: begin

A2: ф2: = 0;

B2: if ф1=0 then

begin

if ф = 2 then goto B2;

ф2 = 1;

C2: if ф = 1 then goto C2;

 goto A2

end;

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

ф: = 1; ф2: = 1;

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

goto A2

end;

parend;

end

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

Взаимное исключение входа в критический интервал может быть распространено на множество параллельно выполняемых процессов, стремящихся овладеть общими ресурсами, например разделяемой областью памяти. Для этого случая достаточно одного целочисленного флажка, которому может присваиваться значение от нуля до числа, равного числу взаимодействующих процессов. Каждый из процессов для ограждения собственного входа в критическую секцию должен иметь пару собственных флажков, подобных ф1 и ф2 на рис. 2.20. Флажки можно поместить в два общедоступных одномерных массива ф1[0:n] и ф2[0:n]. Схема алгоритма одного из параллельных процессов приведена на рисунке 2.21.

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

При подходе k–го процесса к своему критическому интервалу его флагу ф1(k) присваивается значение 0. Это дает возможность объявить другим процессам присвоением ф2[k]:=1, что k–й процесс еще не вошел в критический интервал, и общему флагу ф, если он не равен нулю, присвоить свой номер. Как только общий флаг получил значение номера процесса, второй флажок процесса получает значение нуль. Этот флажок будет просматриваться другими процессами, когда k–й процесс войдет в критический интервал.

Следующим шагом перед входом в критический интервал служит просмотр вторых флажков (ф2[ j ] = 0 ?) процессов-конкурентов: нет ли среди них уже находящихся в критическом интервале? Если есть, то вход в критический интервал откладывается, пока не станут все флажки ф2[ j ] =1. На выходе всем флагам присваивают начальные значения .                     Рисунок 2.21.

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