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

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

Задача «поставщик — потребитель»

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

Использование семафоров для решения данной задачи приведено в листинге 6.11.

 

Листинг 6.11. Решение задачи «поставщик — потребитель»

var S_свободно, S_заполнено, S_взаимоискл : semaphore;

begin

InitSem (S_свободно, N);

InitSem (S_заполнено, 0);

InitSem (S_взаимоискл, 1);

parbegin

ПОСТАВЩИК: while true do

begin

{ приготовить сообщение }

Р(S_свободно);

Р(S_взаимоискл);

{ послать сообщение }

V(S_заполнено);

V(S_взаимоискл);

end

and

ПОТРЕБИТЕЛЬ: while true do

begin

Р(S_заполнено);

Р(S_взаимоискл);

{ получить сообщение }

V(S_свободно);

V(S_взаимоискл);

{ обработать сообщение }

end

parend

end.

 

Здесь переменные S_свободно, S_заполнено являются числовыми семафорами, S_взаиноискл — двоичный семафор. S_свободно имеет начальное значение, рав­ное N, где N — количество буферов, с помощью которых процессы связываются. Предполагается, что в начальный момент количество свободных буферов рав­но N; соответственно, количество занятых равно нулю. Двоичный семафор S_взаимоискл гарантирует, что в каждый момент только один процесс сможет работать с критическим ресурсом, выполняя свой критический интервал. Семафоры S_свободно и S_заполнено используются как счетчики свободных и заполненных буфе­ров.

Действительно, перед посылкой сообщения «поставщик» уменьшает значение S_свободно на единицу в результате выполнения Р(S_свободно), а после посылки сообщения увеличивает значение S_заполнено на единицу в результате выпол­нения V(S_заполнено). Аналогично, перед получением сообщения «потребитель» уменьшает значение S_заполнено в результате выполнения Р(S_заполнено), а после получения сообщения увеличивает значение S_свободно в результате выполнения V(S_свободно). Семафоры S_заполнено, S_свободно могут также использоваться для блокировки соответствующих процессов. Если пул буферов оказался пустым и к нему первым обратится процесс «потребитель», он заблокируется на семафоре S_заполнено в результате выполнения Р(S_заполнено). Если пул буферов заполнен и к нему в этот момент обратится процесс «поставщик», то он будет заблокиро­ван на семафоре S_свободно в результате выполнения Р(S_свободно).

В решении задачи о «поставщике» и «потребителе» общие семафоры применены для учета свободных и заполненных буферов. Их можно также применить и для распределения иных ресурсов.

Пример простейшей синхронизации взаимодействующих процессов

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

 

Листинг 6.12. Пример синхронизации процессов

var S : Semaphore;

begin

InitSem(S,O);

ПР1: begin

ПР11; { первая часть ПР1 }

ON ( ПР2 ); { поставить на выполнение ПР2 }

P(S);

ПР12; { оставшаяся часть ПР1 }

STOP

end;

ПР2: begin

ПР2; { вся работа программы ПР2 }

V(S);

STOP

end

end

 

Начальное значение семафора S равно нулю. Если процесс ПР1 начал выпол­няться первым, то через некоторое время он поставит на выполнение процесс ПР2, после чего выполнит операцию P(S) и «заснет» на семафоре, перейдя в со­стояние пассивного ожидания. Процесс ПР2, осуществив все необходимые дей­ствия, выполнит примитив V(S) и откроет семафор, после чего процесс ПР1 бу­дет готов к дальнейшему выполнению.

Решение задачи «читатели — писатели»

Другой важной и часто встречающейся задачей, решение которой также требует синхронизации, является задача «читатели — писатели». Эта задача имеет много вариантов. Наиболее характерная область использования этой задачи — при по­строении систем управления файлами. Два класса процессов имеют доступ к не­которому ресурсу (области памяти, файлам). «Читатели» — это процессы, ко­торые могут параллельно считывать информацию из некоторой общей области памяти, являющейся критическим ресурсом. «Писатели» — это процессы, запи­сывающие информацию в эту область памяти, исключая при этом и друг друга, и процессы «читатели». Имеются различные варианты взаимодействия между «писателями» и «читателями». Наиболее широко распространены следующие условия.

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

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

Пример программы, реализующей решение данной задачи в первой постановке, представлен в листинге 6.13. Процессы «читатели» и «писатели» описаны в виде соответствующих, процедур.

 

Листинг 6.13. Решение задачи «читатели — писатели» с приоритетом в доступе к критическому ресурсу «читателей»

Var R, W : semaphore;

NR : integer;

 

procedure ЧИТАТЕЛЬ;

begin

P(R):

Inc (NR); { NR:=NR +1 }

if NR = 1 then P(W);

V(R);

Read_Data; { критический интервал }

Р(R);

Dec (NR);

if NR = 0 then V(W);

V(R)

end;

 

procedure ПИСАТЕЛЬ;

begin

P(W);

Write_Data; { критический интервал }

V(W)

end

 

begin

NR:=0;

InitSem(S, 1):

InitSem(W,1);

parbegin

while true do ЧИТАТЕЛЬ

and

while true do ЧИТАТЕЛЬ

and

. . .

while true do ЧИТАТЕЛЬ

and

while true do ПИСАТЕЛЬ

and

while true do ПИСАТЕЛЬ

and

. . .

 

while true do ПИСАТЕЛЬ

parend

end.

 

При решении данной задачи используются два семафора R и W и переменная NR, предназначенная для подсчета текущего числа процессов типа «читатели», нахо­дящихся в критическом интервале. Доступ к разделяемой области памяти осу­ществляется через семафор W. Семафор R используется для взаимоисключения процессов типа «читатели».

Если критический ресурс не используется, то первый появившийся процесс при входе в критический интервал выполнит операцию P(W) и закроет семафор. Если процесс является «читателем», то переменная NR будет увеличена на единицу и последующие «читатели» будут обращаться к ресурсу, не проверяя значение семафора W, что обеспечивает параллельность их доступа к памяти. Последний «читатель», покидающий критический интервал, является единственным, кто выполнит операцию V(W) и откроет семафор W. Семафор R предохраняет от некорректного изменения значения NR, а также от выполнения «читателями» операций P(W) и V(W). Если в критическом интервале находится «писатель», то на семафоре W может быть заблокирован только один «читатель», все остальные будут блоки­роваться на семафоре R. Другие «писатели» блокируются на семафоре W.

Когда «писатель» выполняет операцию V(W), неясно, какого типа процесс войдет в критический интервал. Чтобы гарантировать получение процессами «читате­лями» наиболее свежей информации, необходимо при постановке в очередь го­товности использовать дисциплину обслуживания, учитывающую более высо­кий приоритет «писателей». Однако этого оказывается недостаточно, ибо если в критическом интервале продолжает находиться, по крайней мере, один «чита­тель», то он не даст обновить данные, но и не воспрепятствует вновь приходя­щим процессам «читателям» войти свою критическую секцию. Необходим до­полнительный семафор. Пример правильного решения этой задачи приведен в листинге 6.14.

 

Листинг 6.14. Решение задачи «читатели — писатели» с приоритетом в доступе к критическому ресурсу первых с дополнительным семафором

var S, W, R : semaphore;

NR : integer:;

 

procedure ЧИТАТЕЛЬ;

begin

P(S); P(R);

Inc(NR):

if NR=1 then P(W);

V(S); V(R);

Read_Data; { критический интервал }

P(R);

Dec(NR);

if NR=0 then V(W);

V(R)

end;

 

procedure ПИСАТЕЛЬ;

begin

P(S); P(W);

Write_Data; { критический интервал }

V(S); V(W)

end;

 

begin

NR:=0;

InitSem (S, 1); InitSem (W, 1); InitSem (R, 1);

parbegin

while true do ЧИТАТЕЛЬ

and

while true do ЧИТАТЕЛЬ

and

. . .

while true do ЧИТАТЕЛЬ

and

while true do ПИСАТЕЛЬ

and

while true do ПИСАТЕЛЬ

and

. . .

while true do ПИСАТЕЛЬ

parend

end.

 

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

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

 

Листинг 6.15. Синхронизация процессов «читатели» и «писатель» без взаимного исключения

Var V1, V2 : integer;

 

Procedure ПИСАТЕЛЬ;

Begin

Inc(V1);

Write_Data;

V2:=V1

End;

 

Procedure ЧИТАТЕЛЬ;

Var V: integer;

Begin

Repeat V:= V2;

Read_Data

Until V1 = V

End;

 

begin

V1:= 0; V2 := 0;

parbegin

while true do ЧИТАТЕЛЬ

and

while true do ЧИТАТЕЛЬ

and

. . .

while true do ЧИТАТЕЛЬ

and

while true do ПИСАТЕЛЬ

parend

end.

 

Этот алгоритм использует для данных два номера версий, которым соответству­ют переменные V1 и V2. Перед записью порции новых данных процесс «писатель» увеличивает на 1 значение переменной V1, а после записи — переменную V2. «Чи­татель» обращается к V2 перед чтением данных, а к V1 — после. Если при этом V1 и V2 равны, то очевидно, что получена правильная версия данных. Если же дан­ные обновлялись за время чтения, то операция повторяется. Данный алгоритм может быть использован в случае, если нежелательно заставлять процесс «писа­тель» ждать, пока «читатели» закончат операцию чтения, или если вероятность повторения операции чтения достаточно мала и обусловленное повторными опе­рациями снижение эффективности системы меньше потерь, связанных с избы­точностью решения при использовании взаимного исключения. Однако необхо­димо иметь в виду ненулевую вероятность зацикливания чтения при высокой интенсивности операций записи. Наконец, если само чтение представляет собой достаточно длительную операцию, то оператор V:=V2 для процесса «читатель» может быть заменен на оператор

Repeat V:=V2 Until V1 = V

Это предотвратит выполнение «читателем» операции чтение, если «писатель» уже начал запись.