Элементарные приемы синхронизации на верхнем уровне.

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

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

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

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

Аналогично Р2 может получать сообщения до тех пор, пока имеются заполненные гнезда.

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

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

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

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

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

Монитор можно представить себе как комнату, от которой есть только один ключ.

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

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

Рассмотрим, например, ресурс, который распределяет некоторая программа – планировщик.

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

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

Следует подчеркнуть, что монитор – это пассивный объект, как комната. Это не процесс. Монитор оживает только тогда, когда какой-либо процесс решает воспользоваться его услугами. Особенностью программы-монитора состоит в том, что в любой момент ее может выполнить только один процесс.

Использование монитора иллюстрирует Пример 1, на котором изображена реализация операций P и V над семафором S. Выражение вида ИМЯ УСЛОВИЯ.ЖДАТЬ и ИМЯ УСЛОВИЯ.СИГНАЛ относятся к операциям “ждать” и ”сигнал”, связанным с условием ИМЯ УСЛОВИЯ.

Пример 1.

ДВОИЧНЫЙ_СЕМАФОР : monitor;

S: integer;

Begin

condition СЕМАФОР ПОЛОЖИТЕЛЬНЫЙ;

Procedure P;

Begin

if S<1 then СЕМАФОР ПОЛОЖИТЕЛЬНЫЙ.ЖДАТЬ;

S:=S-1;

end;

Procedure V;

Begin

S:=S+1;

if S=1 then СЕМАФОР ПОЛОЖИТЕЛЬНЫЙ.СИГНАЛ;

end;

end.

Обращение к операциям P и V записываются как ДВОИЧНЫЙ СЕМАФОР.Р и ДВОИЧНЫЙ СЕМАФОР.V. Условие СЕМАФОР ПОЛОЖИТЕЛЬНЫЙ указывает, когда заблокированный процесс может безопасно продолжать работу. На примере два процесса взаимно исключаются из критического участка с помощью двоичного семафора, реализованного в мониторе.

Begin

Parbegin

P1: begin do while (True);

call ДВОИЧНЫЙ СЕМАФОР.P;

Критический участок P1;

call ДВОИЧНЫЙ СЕМАФОР.V;

Оставшаяся часть P1;

end;

end;

P2: begin do while (True);

call ДВОИЧНЫЙ СЕМАФОР.P;

Критический участок P2;

call ДВОИЧНЫЙ СЕМАФОР.V;

Оставшаяся часть P2;

end;

end;

parend;

end.

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

По сравнению с семафорами мониторы имеют преимущества в том, что

· Мониторы – очень гибкий инструмент. Например, почтовый ящик можно реализовать с его помощью

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

Тупики.

Ситуация, когда процессы ждут друг друга неопределенно долго, называется тупикомили дедлоком (deadlock).

Существует три основных направления политики избежания тупиков:

· предотвращение тупиков;

· автоматическое обнаружение;

· обнаружение при участии оператора.

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

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