Решение задачи «читатели – писатели»

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

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

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

Пример программы, реализующей решение данной задачи в первой постановке, представлен в листинге 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 VI, 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 равны, то, очевидно, что получена правильная версия данных. Если же дан­ные обновлялись за время чтения, то операция повторяется. Данный алгоритм может быть использован в случае, если нежелательно заставлять процесс «писатель» ждать, пока «читатели» закончат операцию чтения, или если вероятность повторения операции чтения достаточно мала и обусловленное повторными операциями снижение эффективности системы меньше потерь, связанных с избыточностью решения при использовании взаимного исключения. Однако необхо­димо иметь в виду ненулевую вероятность зацикливания чтения при высокой интенсивности операций записи. Наконец, если само чтение представляет собой достаточно длительную операцию, то оператор V1:=V2 для процесса «читатель» может быть заменён на оператор

repeat V:= V2 until V1 = V

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

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

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

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

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

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

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

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

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

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

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

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

monitor Resourse;

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

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

procedure REQUEST; {запрос}

begin

if busy then WAIT ( free);

busy:=rtrue;

TakeOff; { ВЫДАТЬ РЕСУРС }

end;

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.

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

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

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

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

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

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

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

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

1 SEND_MESSAGE (Получатель, Сообщение, Буфер)

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

2 WAIT_MESSAGE (Отправитель, Сообщение, Буфер)

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

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

записывает Ответ в тот Буфер, из которого было получено сообщение, и добавляет буфер к очереди отправителя. Если отправитель ждёт ответ, он деблокируется.

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

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

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

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

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

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

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

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

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