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

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

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

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

Использование семафоров для решения данной задачи приведено в листинге 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

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