Мониторы

_______________________________Глава 5

Мониторы

Семафоры являются фундаментальным механизмом синхронизации. Как показано в гла­ве 4, их использование облегчает программирование взаимного исключения и сигнализации, причем их можно применять систематически при решении любых задач синхронизации. Од­нако семафоры — низкоуррвневый механизм; пользуясь ими, легко наделать ошибок. На­пример, программист должен следить затем, чтобы случайно не пропустить вызовы операций Р и V или задать их больше, чем нужно. Можно неправильно выбрать тип семафора или защи­тить не все критические секции. Семафоры глобальны по отношению ко всем процессам, по­этому, чтобы разобраться, как используется семафор или другая разделяемая переменная, не­обходимо просмотреть всю программу. Наконец, при использовании семафоров взаимное исключение и условная синхронизация программируются одной и той же парой примитивов. Из-за этого трудно понять, для чего предназначены конкретные Р и V, не посмотрев на дру­гие операции с данным семафором. Взаимное исключение и условная синхронизация — это разные понятия, потому и программировать их лучше разными способами.

Мониторы — это программные модули, которые обеспечивают большую структурирован­ность, чем семафоры, хотя реализуются так же эффективно. В первую очередь, мониторы яв­ляются механизмом абстракции данных. Монитор инкапсулирует представление абстракт­ного объекта и обеспечивает набор операций, только с помощью которых оно обрабатывает­ся. Монитор содержит переменные, хранящие состояние объекта, и процедуры, реализующие операции над ним. Процесс получает доступ к переменным в мониторе только путем вызова процедур этого монитора. Взаимное исключение обеспечивается неявно тем, что процедуры в одном мониторе не могут выполняться параллельно. Это похоже на неявное взаимное исключе­ние, гарантируемое операторами await. Условная синхронизация в мониторах обеспечивается явно с помощью условных переменных (condition variable).
Они аналогичны семафорам, но имеют существенные отличия в определении и, следовательно, в использовании для сигнализации.

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

В данной главе подробно описаны мониторы и на примерах показано их использование Часть примеров уже встречалась, но есть и новые. В разделе 5.1 определены синтаксис и семан­тика мониторов. В разделе 5.2 представлен ряд полезных методов программирования и приме­ров их применения: кольцевые буферы, читатели и писатели, планирование типа "кратчайшая задача", интервальный таймер и классическая задача о спящем парикмахере. В разделе 5.3 взято несколько другое направление — в нем рассматривается структура решений задач параллель­ного программирования. Для демонстрации различных методов решения используется еще одна интересная задача — планирование доступа к диску с перемещаемыми головками.

Глава 5. Мониторы                                                                                                                         169

Благодаря своей полезности и эффективности мониторы применяются в нескольких язы­ках программирования. Примечательно их использование в языке Java, описанное в разде­ле 5.4.


Лежащие в основе мониторов механизмы синхронизации (неявное исключение и ус­ловные переменные для сигнализации) реализованы также в операционной системе Unix. На­конец, условные переменные поддерживаются несколькими библиотеками программирования. В разделе 5.5 описаны соответствующие процедуры библиотеки потоков POSK (Pthreads).

5.1. Синтаксис и семантика

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

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

monitor raname {

объявления постоянных переменных операторы инициализации процедуры }

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

Монитор как представитель абстрактных типов данных обладает тремя свойствами. Во-первых, вне монитора видны только имена процедур — они представляют собой одно-единственное "окно в стене" объявления монитора. Таким образом, чтобы изменить состоя­ние ресурса, представленное постоянными переменными, процесс должен вызвать одну из процедур монитора. Вызов процедуры монитора имеет следующий вид. call mname.opname(arguments)

Здесь mnаmе — имя монитора, opname — имя одной из его операций (процедур), вызываемой с аргументами arguments. Если имя opname уникально в области видимости вызывающего процедуру процесса, то часть "mname. " в вызове процедуры не обязательна.

Во-вторых, операторы внутри монитора (в объявлениях и процедурах) не могут обращать­ся к переменным, объявленным вне монитора.



В-третьих, постоянные переменные инициализируются до вызова его процедур. Это реа­лизовано путем выполнения инициализирующих операторов при создании монитора и, сле­довательно, до вызова его процедур.

Одно из привлекательных свойств монитора, как и любого абстрактного типа данных, — возможность его относительно независимой разработки. Это означает, однако, что программист монитора может не знать заранее порядка вызова процедур. Поэтому полезно определить пре­дикат, истинный независимо от порядка выполнения вызовов. Инвариант монитора — это пре­дикат, определяющий "разумные" состояния постоянных переменных, когда процессы не об­ращаются к ним. Код инициализации монитора должен создать состояние, соответствующее инварианту, а каждая процедура должна его поддерживать. (Инвариант монитора аналогичен глобальному инварианту, но для переменных в пределах одного монитора.) Инварианты мони­торов включены во все примеры главы. Строка инварианта начинается символами ##.

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

170                                              Часть 1 Программирование с разделяемыми переменными

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

5.1.1. Взаимное исключение

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

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


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

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

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

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

5.1.2. Условные переменные

Условная переменная используется для приостановки работы процесса, безопасное выпол­нение которого невозможно до перехода монитора в состояние, удовлетворяющее некоторо­му логическому условию. Условные переменные также применяются для запуска приоста­новленных процессов, когда условие становится истинным. Условная переменная объявляет­ся следующим образом. cond cv;

Таким образом, cond — это новый тип данных. Массив условных переменных объявляется, как обычно, указанием интервала индексов после имени переменной. Условные переменные можно объявлять и использовать только в пределах мониторов.



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

Процесс может запросить состояние условной переменной с помощью вызова

empty(cv) ; Если очередь переменной cv пуста, эта функция возвращает значение "истина", иначе — "ложь"

Глава 5. Мониторы                                                                                                                  171

Процесс блокируется на условной переменной cv с помощью вызова wait(cv);

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

Процессы,   заблокированные   на  условных   переменных,   запускаются   операторами signal. При выполнении вызова signal(cv);

проверяется очередь задержки переменной cv. Если она пуста, никакие действия не произво­дятся. Однако, если приостановленные процессы есть, оператор signal запускает процесс вначале очереди. Таким образом, операции wait и signal обеспечивают порядок сигнализа­ции FIFO: процессы приостанавливаются в порядке вызовов операции wait, а запускаются в порядке вызовов операции signal. Позже будет показано, как добавить к очереди задерж­ки приоритеты планирования, но по умолчанию принимается порядок FIFO.

5.1.3. Дисциплины сигнализации

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


Таким образом, возможны два варианта:

• •  сигнализировать и продолжить: сигнализатор продолжает работу, а процесс, получив-

ший сигнал, выполняется позже;

•    сигнализировать и ожидать: сигнализатор ждет некоторое время, а процесс, получив­ший сигнал, выполняется сразу.

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

Порядок "сигнализировать и ожидать" имеет свойство прерывания обслуживания. Про­цесс, выполняющий операцию signal, передает управление блокировкой монитора запус­каемому процессу, т.е. запускаемый процесс прерывает работу процесса-сигнализатора. В этом случае сигнализатор переходит в очередь процессов, ожидающих на блокировке мони­тора. (Возможен вариант, когда сигнализатор помещается в начало очереди ожидающих про­цессов; это называется "сигнализировать и срочно (urgent) ожидать".)

Диаграмма состояний на рис. 5.1 иллюстрирует работу синхронизации в мониторах. Вызы­вая процедуру монитора, процесс помещается во входную очередь, если в мониторе выполняет­ся еще один процесс; в противном случае вызвавший операцию процесс немедленно начинает выполнение в мониторе. Когда монитор освобождается (после возврата из процедуры или вы­полнения операции wait), один процесс из входной очереди может перейти к работе в монито­ре. Выполняя операцию wait (cv), процесс переходит от работы в мониторе в очередь, связан­ную с условной переменной. Если процесс выполняет операцию signal (cv), то при порядке "сигнализировать и продолжить" (Signal and Continue — SC) процесс из начала очереди услов-



172                                               Часть 1 Программирование с разделяемыми переменными

ной переменной переходит во входную. При порядке "сигнализировать и ожидать" (Signal and Wait — SW) процесс, выполняемый в мониторе, переходит во входную очередь, а процесс из на­чала очереди условной переменной переходит к выполнению в мониторе.



В листинге 5.1 показан монитор, реализующий семафор. Здесь представлены все компо­ненты монитора, поясняющие различия между порядком выработки сигналов SC и SW. Хотя вряд ли кому-нибудь потребуются мониторы для реализации семафоров, этот пример демон­стрирует такую возможность. В главе 6 будет показано, как реализовать мониторы с помощью семафоров. Монитор и семафор дуальны в том смысле, что с помощью одного из них можно реализовать другой, и, следовательно, их можно использовать для решения одних и тех же за­дач синхронизации. Однако мониторы являются механизмом более высокого уровня, чем се­мафоры, по причинам, описанным в начале главы.



В листинге 5.1 целочисленная переменная s представляет значение семафора. Вызывая операцию Psem, процесс приостанавливается, пока значение переменной s не станет поло­жительным, затем уменьшает его на 1. Задержка программируется с помощью цикла while, который приводит процесс к ожиданию на условной переменной роз, если s равна 0. Опера­ция Vsem увеличивает s на 1 и вырабатывает сигнал для переменной роз. Если есть приоста­новленные процессы, запускается "самый старый" из них.

Программа 5.1 корректно работает как при порядке "сигнализировать и ожидать" (SW), так и при "сигнализировать и продолжить" (SC). Под корректностью работы понимается со­хранение истинности инварианта семафора s >= 0. Порядки работы отличаются только по­следовательностью выполнения процессов. Вызывая Psem, процесс ждет, если s равна О, а после запуска уменьшает значение з. Вызывая Vsem, процесс сначала увеличивает s, после чего запускает приостановленный процесс, если такой есть.


При порядке SW запускаемый

Глава 5. Мониторы                                                                                                                         173

процесс выполняется сразу и уменьшает значение семафора s. При порядке SC запускаемый процесс выполняется через некоторое время после процесса, выработавшего сигнал. Запус­каемый процесс должен перепроверить значение семафора s и убедиться, что оно все еще по­ложительно. Это необходимо сделать, поскольку возможно, что другой процесс из очереди входа до этого вызвал действие Psem и уменьшил s. Таким образом, код в листинге 5.1 обес­печивает последовательность обслуживания FIFO для порядка SW, но не для порядка SC.

Листинг 5.1 демонстрирует еще одно различие между порядками выработки сигналов SW и SC. При порядке SW цикл while в действии Psem можно заменить простым оператором i f: if   (s  ==   0)   wait(pos);

При этом процесс, получивший сигнал, сразу начинает работу. Это гарантирует, что значение s положительно, когда данный процесс его уменьшает.

Монитор, показанный в листинге 5.1, можно изменить так, чтобы он корректно работал при обоих порядках запуска процессов (SC и SW), не использовал цикл while и реализовы­вал семафор с порядком обслуживания FIFO. Чтобы понять, как это сделать, вернемся кпрограмме в листинге 5.1. Когда процесс впервые вызывает операцию Psem, он должен при­остановиться, если значение s равно нулю. Вызывая операцию Vsem, процесс собирается за­пустить приостановленный процесс, если такой есть. Различие между выработкой сигналов в порядке SC и SW состоит в том, что если процесс-сигнализатор продолжает выполняться, то уже увеличенное на единицу значение семафора s может прочитать не тот процесс, который только что был запущен. Избежать этой проблемы можно, если вызывающий операцию Vsem процесс примет следующее решение: если есть приостановленный процесс, то нужно сигнализировать для переменной роз, не увеличивая значение семафора s, иначе увеличить s. Соответственно, если процесс, вызывающий операцию Psem, должен ожидать, то в дальнейшем он не умень­шит s, поскольку к тому времени оно не будет увеличено процессом, выработавшим сигнал.



Монитор, использующий описанный способ, представлен в листинге 5.2. Этот метод на­ зывается передачей условия, поскольку, по существу, сигнализатор неявно передает значение условия (переменная s положительна) процессу, который он запускает. Условие не делается видимым, поэтому никакой другой процесс, кроме запускаемого операцией signal, не уви­дит, что условие стало истинным и не прекратит ожидания.



174                                               Часть 1. Программирование с разделяемыми переменными

ной s в процедуре Psem и ее уменьшение в процедуре Vsem. В разделах 5.2 и 5.3 будут приведе­ны дополнительные примеры с использованием этого метода в решении задач планирования.

Из листингов 5.1 и 5.2 видно, что условные переменные аналогичны операциям Р и V с семафорами. Операция wait, подобно Р, приостанавливает процесс, а операция signal, как и V, запускает его. Однако есть два существенных отличия. Первое — операция wait всегда приостанавливает процесс до последующего выполнения операции signal, тогда как операция Р вызывает остановку процесса, только если текущее значение семафора равно нулю. Второе — операция signal не производит никаких действий, если нет процессов, приостановленных на условной переменной, тогда как V либо запускает приостановленный процесс, либо увеличивает значение семафора, т.е. факт выполнения операции signal не запоминается. Из-за этих отли­чий условная синхронизация с мониторами программируется не так, как с семафорами.

В оставшейся части данной главы будем предполагать, что мониторы используют порядок "сигнализировать и продолжить". Первым для мониторов был предложен порядок "сигнали­зировать и ожидать", однако SC был принят в операционной системе Unix, языке програм­мирования Java и библиотеке Pthreads. Порядку SC было отдано предпочтение, поскольку он совместим с планированием процессов на основе приоритетов и имеет более простую фор­мальную семантику. (Эти вопросы обсуждаются в исторической справке.)



5.1.4. Дополнительные операции с условными переменными

До сих пор с условными переменными использовались три операции: empty, wait и signal. Полезны еще три: приоритетная wait, minrank и signal_all. Все они имеют простую семантику и могут быть эффективно реализованы, поскольку обеспечивают лишь дополнительные действия над очередью, связанной с условной переменной. Все шесть опе­раций представлены в табл. 5.1.

Таблица 5.1. Операции над условными переменными

wait(cv)                       Ждать в конце очереди

waitlcv,   rank)           Ждать в порядке возрастания значения ранга (rank)

signal (cv)                   Запустить процесс из начала очереди и продолжить

signal_all (cv)           Запустить все процессы очереди и продолжить

empty (cv)                     Истина, если очередь ожидания пуста, иначе — ложь

minrank (cv)                 Значение ранга процесса в начале очереди ожидания

С помощью операций wait и signal приостановленные процессы запускаются в том же порядке, в котором они были задержаны, т.е. очередь задержки является FIFO-очередью. Приоритетный оператор wait позволяет программисту влиять на порядок постановки про­цессов в очередь и их запуска. Оператор имеет вид:

wait(cv,   rank)

Параметр cv— это условная переменная, a rank— целочисленное выражение. Процессы приостанавливаются на переменной cv в порядке возрастания значения rank и, следова­тельно, в этом же порядке запускаются. При равенстве рангов запускается процесс, ожидав­ший дольше всех. Во избежание потенциальных проблем, связанных с совместным примене­нием обычного и приоритетного операторов wait для одной переменной, программист дол­жен всегда использовать только один тип оператора wait.

Для задач планирования, в которых используется приоритетный оператор wait, часто по­лезно иметь возможность определить ранг процесса в начале очереди задержки. Из вызова minrank(cv)

175

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


В противном случае возвращается некоторое произвольное целое число. Оповещающая операция signal — последняя с условными переменными. Она использу­ется, если можно возобновить более одного приостановленного процесса или если процесс-сигнализатор не знает, какие из приостановленных процессов могли бы продолжать работу (поскольку им самим нужно перепроверить условия приостановки). Эта операция имеет вид: signal_all(cv)

Выполнение оператора signal_all запускает все процессы, приостановленные на условной переменной cv. При порядке "сигнализировать и продолжить" он аналогичен коду: while   (.'empty (cv) )   signal(cv);

Запускаемые процессы возобновляют выполнение в мониторе через некоторое время в соот­ветствии с ограничениями взаимного исключения. Как и оператор signal, оператор sig-nal_al 1 не дает результата, если нет процессов, приостановленных на условной переменной cv. Процесс, выработавший сигнал, также продолжает выполняться в мониторе.

Операция signal_all вполне определена, когда мониторы используют порядок "сигнализировать и продолжить", поскольку процесс, выработавший сигнал, всегда продол­жает работать в мониторе. Но при использовании порядка "сигнализировать и ожидать" эта операция определена не точно, поскольку становится возможным передать управление более, чем одному процессу, и дать каждому процессу исключительный доступ к монитору. Это еще одна причина, по которой в операционной системе Unix, языке Java, библиотеке Pthreads иданной книге используется порядок запуска "сигнализировать и продолжить".


Содержание раздела

---

---