Мониторы
_______________________________Глава 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 иданной книге используется порядок запуска "сигнализировать и продолжить".