wait(имяycлoвия)

Signal(имяусловия)

Переменные-условия совершенно не похожи на "обычные" пере­менные, с которыми мы привыкли иметь дело.

Когда определяется такая переменная:

Ø заводится очередь.

Ø Процесс, выдавший команду ожидания, включается в эту очередь,

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

Простое распределение ресурсов при помощи мониторов

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

monitor распределительресурсов;

var ресурсзанят: логический;

ресурссвободен: условие;

procedure захватитьресурс;

Begin

if ресурсзанят then

wait(pecypccвoбoдeн);

ресурсзанят:= истина

End;

procedure возвратитьресурс;

Begin

ресурсзанят:= ложь;

signal(ресурссвободен)

End;

 

Begin

ресурсзанят:= ложь

End;

Рис. 5.1 Простое распределене ресурса при помощи монитора.

Достоинство подобного распределителя ресурсов заключается в том, что он работает точно так же, как двоичный семафор: команда "захватитьресурс" выполняет функцию Р-оператора, а команда "возвратитьресурс" – V-оператора. Поскольку с помощью такого простого монитора с одним ресурсом можно реализовать семафор, мониторы по меньшей мере обладают той же логической мощностью, что и семафоры.

5.4 Пример монитора: кольцевой буфер

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

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

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

Поскольку размер кольцевого буфера ограничен, процесс-про­изводитель в какой-то момент может столкнуться с тем, что все элементы массива окажутся занятыми; в этом случае процессу-производителю необходимо будет подождать, пока потребитель не прочитает и тем самым не освободит хотя бы один элемент массива. Аналогично может возникнуть ситуация, когда потребитель хотел бы прочитать данные, а массив оказывается пустым; в этом случае потребитель должен будет ждать, пока процесс-производитель не поместит данные в массив. На рис. 5.2 приведен монитор под назва­нием "мониторкольцевогобуфера", который реализует кольцевой буфер и соответствующий механизм синхронизации для обеспечения взаимодействия в паре "производитель-потребитель" (базовую вер­сию этого монитора предложил Хоор (Но 74)).

 

monitor мониторкольцевогобуфера;

var кольцевойбуфер: array [0.. размербуфера – 1] of тип;

текущая позиция: 0.. размербуфера;

очереднаязаполняемаяпозиция: 0.. размербуфера – 1;

очереднаяосвобождаемаяпозиция: 0..размербуфера – 1;

буфернепуст, буфернезаполнен: условие;

procedure заполнитьпозицию(данные: тип);

Begin

if текущая позиция = размербуфера

then wait(буфернезаполнен);

кольцевойбуфер [очереднаязаполняемаяпозиция]: = данные;

текущаяпозиция:= текущая позиция + 1;

очереднаязаполняемаяпозиция:= (очереднаязаполняемая­позиция + 1) mod размербуфера;

signal(бyфepнeпycт)

End;

procedure освободитьпозицию(var данные:тип);

Begin

if текущаяпозиция = 0 then wait(буфернепуст);

данные:= кольцевойбуфер [очереднаяосвобождаемаяпози­ция];

текущаяпозиция:= текущаяпозиция – 1;

очереднаяосвобождаемаяпозиция:= (очереднаяосвобождае­мая-

позиция + 1) mod размербуфера;

signal (буфернезаполнен)

End;

 

Begin

текущаяпозиция:= 0;

очереднаязаполняемаяпозиция:= 0;

очереднаяосвобождаемаяпозиция:= 0

End;

Рис. 5.2 Реализация кольцевого буфера при помощи монитора.

 

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

Условие "буфернезаполнен" является признаком, которого ждет процесс-производи­тель, если обнаружит, что кольцевой буфер целиком заполнен; этот признак устанавливается по сигналу процесса-потребителя о том, что он только что освободил позицию.

Условие "буфернепуст" является признаком, которого ждет процесс-потребитель, если об­наружит, что кольцевой буфер пуст; этот признак устанавливается по сигналу процесса-производителя о том, что он только что по­местил данные в некоторую позицию.

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

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

Другой процесс читает строки данных из кольцевого буфера и выдает их на принтер. Однако этот второй процесс, обычно называемый деспулером, работает с гораздо меньшей скоростью – со скоростью принтера.

Кольцевой буфер должен иметь достаточно большой размер, чтобы "выбирать слабину", которая возникает из-за несоответствия скоростей работы спулера и деспулера.

5.5 Пример монитора: читатели и писатели

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

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

Проблему проектирования параллельной программы для управ­ления доступом процессов-читателей и писателей к базе данных впер­вые сформулировали и решили Куртуа, Хейманс и Парнас (Со71).

На рис. 5.3 представлен монитор, решающий задачу читателей и писателей и разработанный на основе алгоритма, который предложили Хоор и Горман (Но74).

monitor читателииписатели;

Var

читатели: целое;

ктотопишет: логический;

читатьразрешается, писатьразрешается: условие;

procedure началочтения;

Begin

if ктотопишет or очередь(писатьразрешается)

then wait(читатьразрешается);

читатели:= читатели + 1;

signal(читaтьpaзpeшaeтcя)

End;

procedure конецчтения;

Begin

читатели:= читатели – 1;

if читатели = 0 then signal(пиcaтьpaзpeшaeтcя)

End;

 

procedure началозаписи;

Begin

if читатели > 0 or ктотопишет

then wait(писатьразрешается);

ктотопишет:= истина

End;

 

procedure конецзаписи

Begin

ктотопишет:= ложь;

if очередь(читатьразрешается)

then signal(читaтьpaзpeшaeтcя)

else signal(пиcaтьpaзpeшaeтcя)

End

Begin

читатели:= 0;

ктотопишет:= ложь

End;

Рис. 5.3 Монитор, решающий задачу читателей и писателей.

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

Когда процессу-читателю нужно произвести чтение, он вызывает процедуру монитора под названием "началочтения", а после за­вершения чтения – процедуру "конецчтения".

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

От­метим, что процедура "началочтения" завершается выдачей сигнала "читатьразрешается", чтобы следующий ожидающий очереди чита­тель мог начать чтение. В этом случае следующий процесс-читатель активизируется и выдает находящемуся после него в очереди чита­телю сигнал о возможности продолжить выполнение. Фактически подобная "цепная реакция" будет идти до тех пор, пока не активи­зируются все ожидающие процессы-читатели. Во время выполнения такой цепочки действий все вновь приходящие процессы включают­ся в очередь ожидания. Цепная активизация процессов-читателей – весьма рациональное решение. Поскольку процессы-читатели не мешают друг другу и поскольку они могут выполняться в мульти­процессорных системах параллельно, это эффективный способ об­служивания подобных процессов. Отметим, что во время выполне­ния цепочки активизации процессов даже вновь приходящие про­цессы-читатели не могут войти в монитор, поскольку мы соблюдаем правило, согласно которому процессы, уже получившие сигнал активизации, обслуживаются раньше новых процессов.

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

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

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

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

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