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

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

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

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

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

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

Листинг 7.15(продолжение)

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

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

Мониторы Хоара

Анализ рассмотренных задач показывает, что, несмотря на очевидные достоинства (простота, независимость от количества процессов, отсутствие активного ожида­ния), семафорные механизмы имеют и ряд недостатков. Эти механизмы являются слишком примитивными, так как семафор не указывает непосредственно на синх-

Мониторы Хоара____________________________________________________ 237

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

Необходимо иметь очевидные решения, которые позволят прикладным програм­мистам без лишних усилий, связанных с доказательством правильности алгорит­мов и отслеживанием большого числа взаимосвязанных объектов, создавать па­раллельные взаимодействующие программы. К таким решениям можно отнести так называемые мониторы, предложенные Хоаром [52].

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

Рассмотрим, например, некоторый ресурс, который разделяется между процесса­ми каким-либо планировщиком [17]. Каждый раз, когда процесс желает получить в свое распоряжение какие-то ресурсы, он должен обратиться к программе-плани­ровщику. Этот планировщик должен иметь переменные, с помощью которых можно отслеживать, занят ресурс или свободен. Процедуру планировщика разделяют все процессы, и каждый процесс может в любой момент захотеть обратиться к плани­ровщику. Но планировщик не в состоянии обслуживать более одного процесса одновременно. Такая процедура-планировщик и представляет собой пример мо­нитора.

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

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

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

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

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

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

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

В качестве примера рассмотрим простейший монитор для выделения одного ре­сурса (листинг 7.16).

Листинг 7.16.Пример монитора Хоара

monitor Resourse;

condition free; { условие - свободный }

var busy : boolean: { занят }

procedure REQUEST; { запрос } begin

if busy then WAIT ( free );

busy;=true:

TakeOff; { выдать ресурс } end:

Мониторы Хоара____________________________________________________ 239

procedure RELEASE; begin

TakeOn; { взять ресурс }

busy:=false:

SIGNAL ( free ) end:

begin

busy:=false: end

Единственный ресурс динамически запрашивается и освобождается процессами, которые обращаются к процедурам REQUEST (запрос) и RELEASE (освободить). Если процесс обращается к процедуре REQUEST в тот момент, когда ресурс используется, значение переменной busy (занято) будет равно true, и процедура REQUEST выпол­нит операцию монитора WAIT(free). Эта операция блокирует не процедуру REQUEST, а обратившийся к ней процесс, который помещается в конец очереди процессов, ожидающих, пока не будет выполнено условие free (свободно).

Когда процесс, использующий ресурс, обращается к процедуре RELEASE, операция монитора SIGNAL деблокирует процесс, находящийся в начале очереди, не позво­ляя исполняться никакой другой процедуре внутри того же монитора. Этот дебло­кированный процесс будет готов возобновить исполнение процедуры REQUEST сразу же после операции WAIT(free), которая его и блокировала. Если операция SIGNAL(free) выполняется в то время, когда нет процесса, ожидающего условия free, то никаких действий не выполняется.

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

Монитор является пассивным объектом в том смысле, что это не процесс; его про­цедуры выполняются только по требованию процесса.

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

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

Почтовые ящики

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

Если процесс Р1 хочет общаться с процессом Р2, то Р1 просит систему предоста­вить или образовать почтовый ящик, который свяжет эти два процесса так, чтобы они могли передавать друг другу сообщения. Для того чтобы послать процессу Р2 какое-то сообщение, процесс Р1 просто помещает это сообщение в почтовый ящик, откуда процесс Р2 может его в любое время получить. При применении почтового ящика процесс Р2 в конце концов обязательно получит сообщение, когда обратит­ся за ним (если вообще обратится). Естественно, что процесс Р2 должен знать о существовании почтового ящика. Поскольку в системе может быть много почто­вых ящиков, необходимо обеспечить доступ процессу к конкретному почтовому ящику. Почтовые ящики являются системными объектами, и для пользования та­ким объектом необходимо получить его у операционной системы, что осуществ­ляется с помощью соответствующих запросов.

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

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

¹ Название «почтовый ящик» происходит от обычного приспособления для отправки почты.

Почтовые ящики____________________________________________________ 241

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

Правила работы почтового ящика могут быть различными в зависимости от его сложности [17]. В простейшем случае сообщения передаются только в одном на­правлении. Процесс Р1 может посылать сообщения до тех пор, пока имеются сво­бодные гнезда. Если все гнезда заполнены, то Р1 может либо ждать, либо заняться другими делами и попытаться послать сообщение позже. Аналогично процесс Р2 может получать сообщения до тех пор, пока имеются заполненные гнезда. Если сообщений нет, то он может либо ждать сообщений, либо продолжать свою работу. Эту простую схему работы почтового ящика можно усложнять в нескольких на­правлениях и получать более хитроумные системы общения — двунаправленные и многовходовые почтовые ящики.

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

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

Реализация почтовых ящиков требует использования примитивных операторов низкого уровня, таких как операции Р и V или каких-либо других, но пользовате­лям может дать средства более высокого уровня (наподобие мониторов Хоара), например, такие, как представлены ниже. SEND_MESSAGE ( Получатель, Сообщение, Буфер )

Эта операция переписывает сообщение в некоторый буфер, помещает его адрес в переменную Буфер и добавляет буфер к очереди Получатель. Процесс, выдавший операцию SEND_MESSAGE, продолжит свое исполнение. WAIT_MESSAGE ( Отправитель, Сообщение, Буфер )

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

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

SEND_ANSWER ( Результат. Ответ. Буфер )

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

WAIT_ANSWER ( Результат, Ответ. Буфер )

Эта операция блокирует процесс, выдавший операцию, до тех пор, пока в буфер не поступит ответ; доступ к нему возможен через переменную Буфер. После того как ответ поступил и процесс передан на процессор, ответ, доступ к которому определяется через переменную Ответ, переписывается в память процессу, а буфер освобождается. Значение переменной Результат указывает, является ли ответ пустым, то есть выданным операционной системой, так как сообщение было адресовано несуществующему (или так и не ставшему активным) процессу.

Основные достоинства почтовых ящиков:

- процессу не нужно знать о существовании других процессов до тех пор, пока он
не получит сообщения от них;

- два процесса могут обменяться более чем одним сообщением за один раз;

- операционная система может гарантировать, что никакой иной процесс не вме­
шается во взаимодействие процессов, ведущих между собой «переписку»;

- очереди буферов позволяют процессу-отправителю продолжать работу, не об­ращая внимания на получателя.

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

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

В операционных системах компании Microsoft тоже имеются почтовые ящики (mailslots). В частности, они достаточно часто используются при создании распре­деленных приложений для сети. При работе с ними в приложении, которое долж­но отправить сообщение другому приложению, необходимо указывать класс дос­тавки сообщений. Различают два класса доставки. Первый класс (first-class delivery) гарантирует доставку сообщений; он ориентирован на сеансовое взаимодействие между процессами и позволяет организовать посылки типа «один к одному» и «один ко многим». Второй класс (second-class delivery) основан на механизме датаграмм, и он уже не гарантирует доставку сообщений получателю.