Задачи синхронизации.

2.1 Задача «производитель-потребитель»

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

- требования задачи взаимного исключения по отношению к критическому ресурсу - обобщенной памяти для хранения сообщения;

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

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

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

2.2 Задача «читатели-писатели»

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

Имеются различные варианты взаимодействия между процессами-писателями и процессами-читателями. Наиболее широко распространены следующие:

1. Устанавливается приоритетность в использовании критического ресурса процессам-читателям. Если хотя бы один процесс-читатель пользуется ресурсом, то он закрыт для использования всем процессам-писаиелям.

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

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

2.3 Задача «обедающие философы»

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

Для примера рассмотрим случай с тремя процессами и тремя ресурсами. Пусть имеются три параллельных процесса X, Y и Z и три ресурса R₁, R₂ и R₃. Особенность развития процессов такова, что для пребывания процесса Х в активном состоянии ему требуется выделить одновременно ресурсы R₁ и R₂, для пребывания процесса Y - ресурсы R₂ и R₃, для пребывания процесса Z - ресурсы R₃ и R₁. Скорости развития процессов произвольны. Переходы из активного в другие состояния происходят в непредсказуемые моменты.

Необходимо обеспечить максимальное параллельное и правильное развитие процессов. Синхронизация в данном случае заключается в определенном упорядочении действий процессов по захвату ресурсов во избежание возможных блокировок одними процессами других /12/.

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

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

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

Процесс, желающий получить доступ к разделяемым переменным, должен обратиться к процедуре REQUEST (запрос) монитора. Если запрашиваемый ресурс свободен, то процесс получает ресурс и покидает монитор. Иначе процедура выдает команду ожидания WAIT(free) с указанием условия ожидания, которая переводит обратившийся процесс в конец очереди ожидания вне монитора.

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

Пример. Простейший монитор для выделения одного ресурса будет иметь следующий вид.

monitor Resourse;

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

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

procedure REQUEST; {запрос}

Begin

if busy then WAIT(free);

busy:=true;

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

end;

procedure RELEASE;

Begin

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

busy:=false;

SIGNAL(free);

end;

Begin

busy:=false;

end.

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

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

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

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

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

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

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

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

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

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

1 SEND_MESSAGE (Получатель, Сообщение, Буфер) - переписывает сообщение в буфер, помещает его адрес в переменную Буфер и добавляет буфер к очереди Получатель.

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

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

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

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

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

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

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

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

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