Моделирование некоторых структур параллельного программирования. Семафоры

Одним из средств создания параллельных программ на базе стандартных языков программирования является введение специальных средств, выделяющих параллельно выполняемые участки программ. В частности, Э. Дейкстрой были предложены скобки ParBegin и ParEnd, причем первая из них разрешает начало выполнения параллельных операторов, а вторая разрешает переход к дальнейшим вычислениям. На рисунке 2.19 переходу t, соответствует скобка ParBegin, а переходу t₂ - ParEnd.

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

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

В параллельно-последовательных языках программирования для выделения параллельных ветвей используются специальныепрограммные примитивы, такие как упомянутые скобки параллельности ParBegin... ParEnd, или специальные операторы, отмечающие начало и конец параллельного сегмента. Примером могут служить операторы fork(a, b, c…) иjoin(a, b, c,..). Здесь a, b, c,... - метки, помечающие начало и конец параллельных ветвей.

Так, на рисунке 2.20 переход t₁ имеет смысл fork(a, b), переход t_l0-join(a, b). Аналогично t₂-fork(c, d), t₅- join(c, d).

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

Э. Дейкстра предложил для этих целей механизм семафоров, включающий переменные специального типа(semafore) и две операции Р и V, аргументами которых могут быть только переменные типа semafore.

Область значений семафора - целые неотрицательные числа. Если область значений сужена до двух (0 и 1), то семафор называется бинарным.

^II Операция V изменяет значения семафора s на s +1.
Действия операции Р определяются следующим образом:
если s ≠ 0, то Р замещает элемент s на s - 1;

I если s = 0, то Р не изменяет значения s и не завершается до тех пор, пока некоторая другая ветвь не изменит s с помощью операции V.

Существенным является тот факт, что операции Р и V считаются «неделимыми». По отношению к V это означает следующее.

Операция состоит из трех фаз:

- считывание значения семафора из памяти;

- увеличение значения семафора;

- помещение нового значения в память.

Неделимость V(s) заключается в том, что с самого начала выполнения этой операции к переменной s запрещен доступ всех других операций. Аналогично обстоят дела с переменной P. Обычно Р п редшествует критическому интервалу ветви, а V завершает его.

Ниже рассмотрен пример параллельной программы со скобками ParBegin... ParEnd, выделяющими сегмент с двумя параллельными ветвями рrос_1 и proc_2, разделенными запятой и семафором sem. Каждая из параллельных ветвей представляет собой бесконечный последовательный цикл, содержащий критический интервал (crit_section) и остальную часть цикла (remainder_of_cycle).

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

Var

1, 2: label;

sem: semafore;

begin

sem: =1;

parbegin

proc_l:

begin 1: P(sem);

crit_sect_l;

V(sem);

remainder_of_cycle_l; goto 1 end,

proc_2:

begin 2: P(sem);

crit_sect_2;

V(sem);

remainder_of_cycle_2; goto 2 end,

parend

end.

Соответствующая сеть Петри приведена на рисунке 2.21.

Здесь переходы Р_; соответствуют выполнению операции P, С_i - критическому интервалу ветви, V_i - операциям V, R_; -остальной части цикла (i =1, 2). Позиция Р₃ соответствует

семафору sem.

При выполнении параллельно-последовательных программ возможны ситуации, называемые взаимной блокировкой (рис. 2.22).

Пусть М₀= [1, 0, 0, 1, 0, 0, 1, 1] – начальная маркировка, показанная на рисунке. Тогда после срабатывания переходов t₁ и t₄ образуется маркировка М=[0, 1, 0, 0, 1, 0, 0, 0] и произойдет взаимная блокировка процессов, т.е. ни один процесс не сможет выполняться и не сможет вернуть захваченный ресурс.

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