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

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

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

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

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

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

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

InitSem(S_свободно.N); InitSem(S_заполнено.O); InitSem(S_взаимоискл.1): parbegin

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

{ подготовить сообщение } Р(S_свободно); Р(S_взаимоискл);

{ послать сообщение } V(S_заполнено): V(S_взаимоискл); end and

Средства синхронизации и связи взаимодействующих процессов_______________ 231

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

Р(S_заполнено); Р(5__взаимоискл);

{ получить сообщение } V(S_свободно); V(S_взаимоискл);

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

parend end.

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

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

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

Синхронизация взаимодействующих процессов с помощью семафоров

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

232________ Глава 7. Организация параллельных взаимодействующих вычислений

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

var S : Semaphore: begin InitSem(S.O);

ПР1: begin

ПРИ; { первая часть ПР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 будет готов к дальней­шему выполнению.

Задача «читатели-писатели»

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

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

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

Средства синхронизации и связи взаимодействующих процессов_______________ 233

ся с пульта кассира, когда он оформляет для нас тот или иной билет. Имеется боль­шое количество как читателей, так и писателей.

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

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

var R, W : semaphore:

N_R : integer: procedure ЧИТАТЕЛЬ: begin

P(R):

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

if NR = 1 then P(W):

V(R):

Read_Data: { критическая секция }

P(R):

Dec(NR);

if N_R = 0 then V(W):

VCR) end;

procedure ПИСАТЕЛЬ; begin

P(W);

Write_Data; { критическая секция }

V(W) end

begin NR:=0;

InitSem(S.l): InitSem(W.l); 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, предназначенная для подсчета текущего числа процессов типа «читатели», находящихся в критической секции. Доступ к разделяемой области памяти осу-

234 Глава 7. Организация параллельных взаимодействующих вычислений

ществляется через семафор W. Семафор R требуется для взаимного исключения процессов типа «читатели».

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

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

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

var S, W, R : semaphore;

NR : integer; procedure ЧИТАТЕЛЬ; begin

P(S): P(R):

Inc(NR):

if NR = 1 then P(W);

V(S): VCR):

Read_Data: { критическая секция }

P(R):

Dec(NR);

if NR = 0 then V(W);

VCR) end;

procedure ПИСАТЕЛЬ; begin

PCS): P(W);

Write_Data; { критическая секция }

V(S): V(W) end;

begin NR:=0;

InitSem(S.l); InitSem(W.l); InitSem(R.l): parbegin

Средства синхронизации и связи взаимодействующих процессов________________ 235

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 имеет место только при входе в критическую секцию. После выполнения чтения уже категорически нельзя использовать этот семафор, ибо он тут же заблокирует первого же читателя, если хотя бы один писатель захочет вой­ти в свою критическую секцию. И получится так называемая тупиковая ситуация, ибо писатель не сможет войти в критическую секцию, поскольку в ней уже нахо­дится читатель. А читатель не сможет покинуть критическую секцию, потому что писатель желает войти в свою критическую секцию.

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

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

Var VI. V2 : integer;

Procedure ПИСАТЕЛЬ: Begin

Inc(Vl):

Write_Data:

V2:=V1
End: продолжение