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

⇐ ПредыдущаяСтр 34 из 50Следующая ⇒

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

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

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

Пример программы, реализующей решение данной задачи в первой постановке, представлен в листинге 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 (Результат, Ответ, Буфер)

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

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

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

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

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

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

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

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

⇐ Предыдущая 29 30 31 32 333435 36 37 38 Следующая ⇒