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 Монитор, решающий задачу читателей и писателей.

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

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

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

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

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

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

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

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

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