Мониторы

Семафоры обеспечивают достаточно мощный и гибкий инструмент для осуществления взаимных исключений и координации процессов. Однако, как вы видели в листинге 5.8, создать корректно работающую программу с использованием семафоров не всегда легко. Сложность заключается в том, что операции wait и signal могут быть разбросаны по всей программе, и не всегда можно сразу отследить их воздействие на контролируемые ими семафоры.
Монитор представляет собой конструкцию языка программирования, которая обеспечивает функциональность, эквивалентную функциональности семафоров, но легче управляется. Впервые формальное определение концепции мониторов было дано в [HOAR74]. Мониторы реализованы во множестве языков программирования, включая такие, как Concurrent Pascal, Pascal-Plus, Modula-2, Modula-З и Java. Мониторы также реализуются как программные библиотеки. Это позволяет использовать мониторы, блокирующие любые объекты. В частности, например, для связанного списка можно заблокировать все связанные списки одной блокировкой, либо иметь отдельные блокировки для каждого списка, а возможно — и для каждого элемента списка.
Рассмотрение мониторов мы начнем с версии Хоара (Ноаге).

Мониторы с сигналами

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

• Локальные переменные монитора доступны только его процедурам; внешние процедуры доступа к локальным данным монитора не имеют.
• Процесс входит в монитор путем вызова одной из его процедур.
• В мониторе в определенный момент времени может выполняться только один процесс; любой другой процесс, вызвавший монитор, будет приостановлен в ожидании доступности монитора.

Первые две характеристики сразу заставляют нас вспомнить о объектах в объектно-ориентированном программировании. Фактически объектно-ориентированные операционные системы или языки программирования могут легко реализовать монитор как объект со специальными характеристиками.
Соблюдение условия выполнения только одного процесса в определенный момент времени позволяет монитору обеспечить взаимоисключения. Данные монитора доступны в этот момент только одному процессу, следовательно, защитить совместно используемые структуры данных можно, просто поместив их в монитор. Если данные в мониторе представляют некий ресурс, то монитор обеспечивает взаимоисключение при обращении к ресурсу.
Для широкого применения в параллельных вычислениях мониторы должны включать инструменты синхронизации. Предположим, например, что процесс использует монитор и, находясь в мониторе, должен быть приостановлен до выполнения некоторого условия. При этом нам требуется некий механизм, который не только приостанавливает процесс, но и освобождает монитор, позволяя войти в него другому процессу. Позже, когда условие окажется выполненным, а монитор доступным, приостановленный процесс сможет продолжить свою работу с того места, где он был приостановлен.
Монитор поддерживает синхронизацию при помощи переменных условия, располагающихся (и доступных) только в мониторе. Работать с этими переменными могут две функции.
cwait(c): приостанавливает выполнение вызывающего процесса по условию с. Монитор при этом доступен для использования другим процессом.
csignal(c): возобновляет выполнение некоторого процесса, приостановленного вызовом cwait с тем же условием. Если имеется несколько такихпроцессов, выбирается один из них; если таких процессов нет, функция неделает ничего.
Обратите внимание на то, что операции wait/signal монитора отличаются от соответствующих операций семафора. Если процесс в мониторе передает сигнал, но при этом нет ни одного ожидающего его процесса, то сигнал просто теряется.
На рис. 5.7 показана структура монитора. Хотя процесс может войти в монитор посредством вызова любой его процедуры, мы все же будем рассматривать монитор как имеющий единственную точку входа, которая позволяет обеспечить наличие в мониторе не более одного процесса в любой момент времени. Другие процессы, которые пытаются войти в монитор, присоединяются к очереди процессов, приостановленных в ожидании доступности монитора. После того как процесс вошел в монитор, он может временно приостановиться, выполнив вызов cwait (х); после этого процесс помещается в очередь процессов, ожидающих повторного входа в монитор при выполнении условия.
Если процесс, выполняющийся в мониторе, обнаруживает изменение переменной условия х, он выполняет операцию csignal(x), которая сообщает об обнаруженном изменении соответствующей очереди.
В качестве примера использования монитора вернемся к задаче производитель/потребитель с ограниченным буфером. В листинге 5.15 показано решение задачи с использованием монитора. Модуль монитора boundedbuffer управляет буфером, использующимся для хранения и получения символов. Монитор включает две переменные условий: notfull истинно, если в буфере имеется место как минимум для одного символа, a notempty — если в буфере имеется по крайней мере один символ.

Рис. 5.7. Структура монитора

Листинг 5.15. Решение задачи производитель/потребитель с ограниченным буфером с использованием монитора

Производитель может добавить символы в буфер только из монитора при помощи процедуры append; прямого доступа к буферу у него нет. Сначала процедура проверяет условие notfull, чтобы выяснить, имеется ли в буфере пустое место. Если его нет, процесс приостанавливается, и в монитор может войти другой процесс (производитель или потребитель). Позже, когда буфер оказывается заполнен не до конца, приостановленный процесс извлекается из очереди и возобновляет свою работу. После того как процесс поместит символ в буфер, он сигнализирует о выполнении условия notempty, что разблокирует процесс потребителя (если последний был приостановлен).
Этот пример иллюстрирует разделение ответственности при работе с монитором и при использовании семафоров. Монитор автоматически обеспечивает взаимоисключение: одновременное обращение производителя и потребителя к буферу невозможно. Однако программист должен корректно разместить внутри монитора примитивы cwait и csignal, для того чтобы предотвратить размещение элемента в заполненном буфере или выборку из пустого буфера. В случае использования семафоров ответственность как за синхронизацию, так и за взаимоисключения полностью лежит на программисте.

Обратите внимание, что в листинге 5.15 процесс покидает монитор немедленно после выполнения функции csignal. Если вызов csignal осуществляется не в конце процедуры, то, по предложению Хоара, вызвавший эту функцию процесс приостанавливается, для того чтобы освободить монитор для другого процесса, помещается в очередь и остается там до тех пор, пока монитор вновь не освободится. Процесс можно поместить во входную очередь монитора вместе с другими процессами, еще не вошедшими в монитор. Однако поскольку рассматриваемый процесс уже частично выполнил свою задачу в мониторе, имеет смысл дать этому процессу приоритет перед только входящими в монитор, для чего использовать дополнительную, "срочную" очередь (см. рис. 5.7). Заметим, что один из использующих мониторы языков, а именно Concurrent Pascal, требует, чтобы вызов csignal был последней операцией процедуры монитора.
Если выполнения условия х не ожидает ни один процесс, вызов csignal (x) не выполняет никаких действий.
Как при работе с семафорами, так и с мониторами очень легко допустить ошибку в функции синхронизации. Например, если опустить любой из вызовов csignal в мониторе, то процесс, попавший в соответствующую очередь, останется там навсегда. Преимущество мониторов по сравнению с семафорами в том, что все синхронизирующие функции заключены в мониторе. Таким образом, проверить корректность синхронизации и отловить возможные ошибки оказывается проще при использовании мониторов, чем при использовании семафоров. Кроме того, при правильно разработанном мониторе доступ к защищенным ресурсам корректен независимо от запрашивающего процесса; при использовании же семафоров доступ к ресурсу корректен только в том случае, если правильно разработаны все процессы, обращающиеся к ресурсу.

Мониторы с оповещением и широковещанием

Определение мониторов, данное Хоаром [HOAR74], требует, чтобы в случае, если очередь ожидания выполнения условия не пуста, при выполнении каким-либо процессом операции csignal для этого условия был немедленно запущен процесс, находящийся в указанной очереди. Таким образом, выполнивший операцию csignal процесс должен либо немедленно выйти из монитора, либо быть приостановленным.
У такого подхода имеется два недостатка.

• Если выполнивший операцию csignal процесс не завершил свое пребывание в мониторе, то требуются два дополнительных переключения процессов: одно для приостановки данного процесса и второе для возобновления его работы, когда монитор станет доступен.
• Планировщик процессов, связанный с сигналом, должен быть идеально надежен. При выполнении csignal процесс из соответствующей очереди должен быть немедленно активизирован, причем планировщик должен гарантировать, что до активизации никакой другой процесс не войдет в монитор (в противном случае условие, в соответствии с которым активизируется процесс, может успеть измениться). Так, например, в листинге 5.15, когда выполняется csignal (notempty), процесс из очереди nonempty должен быть активизирован до того, как новый потребитель войдет в монитор. Вот и другой пример: сбой процесса производителя может произойти непосредственно после того, как он добавит символ к пустому буферу, так что операция csignal не будет выполнена. В результате процессы в очереди notempty окажутся навечно заблокированными.

Лэмпсон (Lampson) и Ределл (Redell) разработали другое определение монитора для языка Mesa [LAMP80]. Их подход позволяет преодолевать описанные проблемы, а кроме того, предоставляет ряд полезных расширений концепции мониторов. Структура монитора Mesa использована и в языке программирования Modula-3 [NELS91]. В языке программирования Mesa примитив csignal заменен примитивом cnotify, который интерпретируется следующим образом. Когда процесс, выполняющийся в мониторе, вызывает cnotify(х), об этом оповещается очередь условия х, но выполнение вызвавшего cnotify процесса продолжается. Результат оповещения состоит в том, что процесс в начале очереди условия возобновит свою работу в ближайшем будущем, когда монитор окажется свободным. Однако поскольку нет гарантии, что некий другой процесс не войдет в монитор до упомянутого ожидающего процесса, при возобновлении работы наш процесс должен еще раз проверить, выполнено ли условие. В случае использования такого подхода процедуры монитора boundedbuffer будут иметь следующий вид (листинг 5.16).
Листинг 5.16. Код монитора boundedbuffer

Инструкции if заменены циклами while; таким образом, будет выполняться как минимум одно лишнее вычисление переменной условия. Однако в этом случае отсутствуют лишние переключения процессов и не имеется ограничений на момент запуска ожидающего процесса после вызова cnotify.

Одной из полезных особенностей такого рода мониторов может быть связанное с каждым примитивом условия cnotify предельное время ожидания. Процесс, который прождал уведомления в течение предельного времени, помещается в список активных независимо от того, было уведомление о выполнении условия или нет. При активизации процесс проверяет, выполнено ли условие, и если да, то продолжает свою работу. Такая возможность предотвращает бесконечное голодание процесса в случае, когда другие процессы сбоят перед уведомлением о выполнении условия.
При использовании правила, согласно которому происходит уведомление процесса, а не его насильственная активизация, в систему команд можно включить примитив cbroadcast, который вызывает активизацию всех ожидающих процессов. Это может быть удобно в ситуациях, когда процесс не осведомлен о количестве ожидающих процессов. Предположим, например, что в программе производитель/потребитель функции append и take могут работать с символьными блоками переменной длины. В этом случае, когда производитель добавляет в буфер блок символов, он не обязан знать, сколько символов готов потребить каждый из ожидающих процессов. Он просто выполняет инструкцию cbroadcast, и все ожидающие процессы получают уведомление о том, что они могут попытаться получить свою долю символов из буфера.

Кроме того, широковещательное сообщение может использоваться в том случае, когда процесс не в состоянии точно определить, какой именно процесс из ожидающих должен быть активизирован. Хорошим примером такой ситуации может служить диспетчер памяти. Допустим, у нас имеется байт свободной памяти, и некоторый процесс освобождает дополнительно h байт. Диспетчеру не известно, какой именно из ожидающих процессов сможет работать с k+j байт свободной памяти; следовательно, он должен использовать вызов cbroadcast, и все ожидающие процессы сами проверят, достаточно ли им освободившейся памяти.

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