Методы синхронизации
В этом разделе разработаны решения пяти задач: о кольцевых буферах, читателях и писателях, планировании типа "кратчайшее задание", интервальных таймерах и спящем парикмахере. Каждая из задач по-своему интересна и иллюстрирует технику программирования с мониторами.
5.2.1. Кольцевые буферы: базовая условная синхронизация
Вернемся к задаче о кольцевом буфере (см. раздел 4.2). Процесс-производитель и процесс-потребитель взаимодействуют с помощью разделяемого буфера, состоящего из п ячеек. Буфер содержит очередь сообщений. Производитель передает сообщение потребителю, помещая его в конец очереди. Потребитель получает сообщение, извлекая его из начала очереди. Чтобы сообщение нельзя было извлечь из пустой очереди или поместить в заполненный буфер, нужна синхронизация.
В листинге 5.3 приведен монитор, реализующий кольцевой буфер. Для представления очереди сообщений вновь использованы массив buf и две целочисленные переменные front и rear, которые указывают соответственно на первую заполненную и первую пустую ячейку. В целочисленной переменной count хранится количество сообщений в буфере. Операции с буфером deposit и fetch становятся процедурами монитора. Взаимное исключение неявно, поэтому семафорам не нужно защищать критические секции. Условная синхронизация, как показано, реализована с помощью двух условных переменных.
В листинге 5.3 оба оператора wait находятся в циклах. Это безопасный способ обеспечить истинность необходимого условия перед тем, как произойдет обращение к постоянным переменным. Это необходимо также при наличии нескольких производителей и потребителей. (Напомним, что используется порядок "сигнализировать и продолжить".)
Выполняя операцию signal, процесс просто сообщает, что теперь некоторое условие истинно. Поскольку процесс-сигнализатор и, возможно, другие процессы могут выполняться в мониторе до возобновления процесса, запущенного операцией signal, в момент начала его работы условие запуска может уже не выполняться.
Например, процесс-производитель был приостановлен в ожидании свободной ячейки, затем процесс-потребитель извлек сообщение и запустил приостановленный процесс. Однако до того, как этому производителю пришла очередь выполняться, другой процесс-производитель мог уже войти в процедуру deposit и занять пустую ячейку. Аналогичная ситуация может возникнуть и с потребителями. Таким образом, условие приостановки необходимо перепроверять.
Операторы signal в процедурах deposit и fetch выполняются безусловно, поскольку в момент их выполнения условие, о котором они сигнализируют, является истинным. В действительности операторы wait находятся в циклах, поэтому операторы signal могут выполняться в любой момент времени, поскольку они просто дают подсказку приостановленным процессам. Однако программа выполняется более эффективно, когда signal выполняется, только если известно наверняка (или хотя бы с большой вероятностью), что некоторый приостановленный процесс может быть продолжен.
5.2.2. Читатели и писатели: сигнал оповещения
Задача о читателях и писателях была представлена в разделе 4.4. Напомним, что процесс-читатель может только читать записи базы данных, а процесс-писатель просматривает их и изменяет. Читатели могут обращаться к базе данных одновременно, писателям необходим исключительный доступ. Хотя база данных — общий ресурс, ее нельзя представить монитором, поскольку тогда читатели не смогут работать с ней параллельно (весь код внутри монитора выполняется со взаимным исключением). Вместо этого монитор используется для упорядочения доступа к базе данных. Сама база глобальна по отношению к читателям и писателям, она может находиться, например, в разделяемой памяти или во внешнем файле. Как будет показано ниже, такая базовая структура часто применяется в программах, основанных на мониторах.
В задаче о читателях и писателях упорядочивающий монитор дает разрешение на доступ к базе данных. Для этого необходимо, чтобы процессы информировали монитор о своем же-
Глава 5. Мониторы
ланий получить доступ и о завершении работы с базой данных. Есть два типа процессов и по два вида действий на процесс, поэтому получаем четыре процедуры монитора: ге-guest_read, release_read, request_write, release_write. Использование этих процедур очевидно. Например, процесс-читатель перед чтением базы данных должен вызвать .процедуру request_read, а после чтения — release_read.
Для синхронизации доступа к базе данных необходимо вести учет числа записывающих и читающих процессов. Как и раньше, пусть значение переменной nг — это число читателей, a nw — писателей. Это постоянные переменные монитора; при правильной синхронизации они должны удовлетворять инварианту монитора:
RW: (пг == 0 v nw == 0) л nw <= 1
В начальном состоянии пг и nw равны 0. Их значения увеличиваются при вызове процедур запроса и уменьшаются при вызове процедур освобождения.
В листинге 5.4 представлен монитор, соответствующий этой спецификации. Для обеспечения инварианта RWиспользованы циклы while и операторы wait. В начале процедуры request_read процесс-читатель должен приостановиться, пока nw не станет равной 0; эта задержка происходит на условной переменной oktoread. Аналогично процесс-писатель вначале процедуры reguest_write до обнуления переменных пг и nw должен приостановиться на условной переменной oktowrite. В процедуре release_read для процесса-писателя вырабатывается сигнал, когда значение nг равно нулю. Поскольку писатели выполняют перепроверку условия своей задержки, данное решение является правильным, даже если процессы-писатели всегда получают сигнал. Однако это решение будет менее эффективным, поскольку получивший сигнал процесс-писатель при нулевом значении nr должен сно-
178 Часть 1. Программирование с разделяемыми переменными
ва приостановиться. С другой стороны, в конце процедуры release_write точно известно, что значения обеих переменных пг и nw равны нулю. Следовательно, может продолжить работу любой приостановленный процесс.
Решение в листинге 5. 4 не устанавливает порядок чередования процессов-читателей и процессов-писателей. Вместо этого данная программа запускает все приостановленные процессы и позволяет стратегии планирования процессов определить, какой из них первым получит доступ к базе данных. Если это процесс-писатель, то приостановятся все запускаемые процессы-читатели. Если же первым получит доступ процесс-читатель, то приостановится запускаемый процесс-писатель.
5.2.3. Распределение ресурсов по схеме "кратчайшее задание": приоритетное ожидание
Условная переменная по умолчанию является FIFO-очередью, поэтому, выполняя оператор wait, процесс попадает в конец очереди ожидания. Оператор приоритетного ожидания wait (cv, rank) располагает приостановленные процессы в порядке возрастания ранга. Он используется для реализации стратегий планирования, отличных от FIFO. Здесь мы вновь обратимся к задаче распределения ресурсов по схеме "кратчайшее задание", представленной в разделе 4.5.
Для распределения ресурсов по схеме "кратчайшее задание" нужны две операции: request и release. Вызывая процедуру request, процесс либо приостанавливается до освобождения ресурса, либо получает затребованный ресурс. После получения и использования ресурса про-'•цесс вызывает процедуру release. Затем ресурс отдается тому процессу, который будет использовать его самое короткое время. Если ожидающих запросов нет, ресурс освобождается.
В листинге 5.5 представлен монитор, реализующий распределение ресурсов согласно стратегии КЗ. Постоянными переменными являются логическая переменная free для индикации того, что ресурс свободен, и условная переменная turn для приостановки процессов. Вместе они соответствуют инварианту монитора:
SJN: turn упорядочена по времени л (free => turn пуста)
Процедуры в листинге 5.5 используют метод передачи условия. Приоритетный оператор wait применяется для сортировки приостановленных процессов по количеству времени, в течение которого они будут использовать ресурс.
Функция empty используется для проверки, есть ли приостановленные процессы. Когда ресурс освобождается, при наличии приостановленных процессов запускается тот, которому нужно меньше всего времени, иначе ресурс помечается как свободный. Если процесс получает сигнал, то отметки об освобождении ресурса не делается, чтобы другой процесс не получил к нему доступ первым.
Глава 5. Мониторы
free = true; else
signal(turn); }
_}__________________________________________________________________
5.2.4. Интервальный таймер: покрывающие условия
Обратимся к новой задаче — разработке интервального таймера, который позволяет процессу перейти в состояние сна на некоторое количество единиц времени. Такая возможность часто обеспечивается операционными системами, чтобы позволить пользователям, например, периодически выполнять служебные команды. Разработаем два решения, иллюстрирующие два полезных метода. В первом решении использованы так называемые покрывающие условия; во втором (для создания компактного и эффективного механизма задержки) — приоритетный оператор wait.
Монитор, реализующий интервальный таймер, представляет собой еще один пример контроллера ресурсов. Ресурсом являются логические часы. Возможны две операции с часами: delay (interval), которая приостанавливает процесс на отрезок времени длительностью interval "тиков" таймера, и tick, инкрементирующая значение логических часов. Возможны и другие операции, например, получение значения часов или приостановка процесса до момента, когда часы достигнут определенного значения.
Прикладные процессы вызывают операцию delay (interval) с неотрицательным значением interval. Операцию tick вызывает процесс, который периодически запускается аппаратным таймером. Этот процесс обычно имеет большой приоритет выполнения, чтобы значение логических часов оставалось точным.
Для представления значения логических часов используем целочисленную переменную tod (time of day — время дня).
Вначале ее значение равно нулю и удовлетворяет простому инварианту:
CLOCK: tod >= 0 л tod монотонно увеличивается на 1
Вызвав операцию delay, процесс не должен возвращаться из нее, пока часы не "натикают" как минимум interval раз. Абсолютная точность не нужна, поскольку приостановленный процесс не может начать работу до того, как высокоприоритетный процесс, вызывающий tick, сделает это еще раз.
Процесс, вызывающий операцию delay, сначала должен вычислить желаемое время запуска. Это делается с помощью очевидного кода: wake_time = tod + interval;
Здесь переменная wake_time локальна по отношению к телу функции delay; следовательно, каждый процесс, вызывающий delay, вычисляет собственное значение времени запуска. Далее процесс должен ожидать, пока не будет достаточное число раз вызвана процедура tick. Для этого используется цикл while с условием окончания wake_time >= tod. Тело процедуры tick еще проще: она лишь увеличивает значение переменной tod и затем запускает приостановленные процессы.
Остается реализовать синхронизацию между приостановленными процессами и процессом, вызывающим tick. Один из методов состоит в использовании отдельной условной переменной для каждого условия задержки. Приостановленные процессы могут ожидать в течение разных промежутков времени, так что каждому из них нужна собственная (скрытая) условная переменная. Перед задержкой процесс записывает в постоянные переменные время, через которое он должен быть запущен. При вызове операции tick проверяются постоянные переменные, и при необходимости запуска процессов для их скрытых условных переменных вырабатываются сигналы. Описанный подход необходим для некоторых задач, но он более сложен и менее эффективен, чем необходимо для монитора Timer.
180 Часть 1. Программирование с разделяемыми переменными
Требуемую синхронизацию намного проще реализовать, используя одну условную переменную и метод так называемого покрывающего условия. Логическое выражение, связанное с условной переменной, "покрывает" условия запуска всех ожидающих процессов.
Когда какое- либо из покрываемых условий выполняется, запускаются все ожидающие процессы. Каждый такой процесс перепроверяет свое условие и возобновляется или вновь ожидает.
В мониторе Timer можно использовать одну условную переменную check, связанную с покрывающим условием "значение tod увеличено". Процессы ожидают на переменной check в теле функции delay. При каждом вызове процедуры tick запускаются все ожидающие процессы. Соответствующий этому описанию монитор Timer показан в листинге 5.6. В процедуре tick для запуска всех приостановленных процессов использована оповещающая операция signal_all.
Компактное и простое решение, представленное в листинге 5.6, не достаточно эффективно для данной задачи. Применение покрывающих условий подходит только для ситуаций, когда затраты на ложные сигналы (запускается процесс, который определяет, что его условие ложно, и сразу возвращается в состояние ожидания) меньше, чем затраты на обслуживание условий всех ожидающих процессов и запуск только того процесса, для которого условие выполняется. Именно так обычно и бывает (см. упражнения в конце главы), но в данной ситуации вероятно, что процессы задерживаются на длительное время и, следовательно, будут без нужды многократно запускаться.
Используя приоритетный оператор wait, можно преобразовать программу в листинге 5.6 в более простую и эффективную. Для этого используем приоритетный wait везде, где есть статическая упорядоченность условий для различных ожидающих процессов. В данной ситуации ожидающие процессы можно упорядочить по времени их запуска. Вызванная процедура tick использует функцию minrank, чтобы определить, пришло ли время запустить первый процесс, приостановленный на переменной check. Если да, этот процесс получает сигнал. Этим поправкам соответствует новая версия монитора Timer (листинг 5.7). В процедуре delay теперь не нужен цикл while, поскольку tick запускает процесс только при выполнении его условия запуска.
Однако операцию signal в процедуре tick нужно заключить в цикл, поскольку одного и того же времени запуска могут ожидать несколько процессов.
Итак, у нас есть три основных способа реализации условной синхронизации, при которых условия задержки зависят от переменных, локальных для ожидающих процессов. Лучше использовать приоритетное ожидание, поскольку оно дает эффективные и компактные решения, как в листингах 5.7 и 5.5. Этот способ можно применять всегда, когда условия задержки упорядочены статически.
Второй по качеству способ — использовать переменную покрывающего условия. Он также позволяет получить компактное решение, когда у приостановленных процессов есть возможность перепроверять условия своей приостановки. Однако он неприменим, когда условия ожидания процессов зависят от состояний других ожидающих процессов. Использование переменных покрывающего условия приемлемо, пока затраты на ложные сигналы ниже, чем на ведение записей об условиях ожидания в постоянных переменных.
Третий способ — записывать условия ожидания процессов в постоянные переменные и использовать скрытые переменные условий для запуска приостановленных процессов в нужное время. Этот способ приводит к более сложным решениям, но необходим, если первые два способа неприменимы или эффективность второго способа слишком низка. В упражнениях приведены задачи, демонстрирующие преимущества и недостатки всех трех способов.
5.2.5. Спящий парикмахер: рандеву
В качестве последнего базового примера рассмотрим еще одну классическую задачу синхронизации: задачу о спящем парикмахере. У нее колоритное условие, как и у задачи об обедающих философах. Она представляет практические задачи, например планирование работы головки дискового накопителя, описанное в следующем разделе. Эта задача иллюстрирует важность отношений клиент-сервер, которые часто существуют между процессами. Для нее необходим особый тип синхронизации, называемый рандеву. Наконец, она прекрасно демонстрирует необходимость систематического подхода к решению задач синхронизации.
Спе циализированные методы слишком подвержены ошибкам, чтобы использоваться для решения таких сложных задач, как эта.
(5.1) Задача о спящем парикмахере. В тихом городке есть парикмахерская с двумя дверями и несколькими креслами. Посетители входят через одну дверь и выходят через другую. Салон парикмахерской мал, и ходить по нему может только парикмахер и один посетитель. Парикмахер всю жизнь обслуживает посетителей. Когда в салоне никого нет, он спит в своем кресле. Когда посетитель приходит и видит спящего парикмахера, он будит его, садится в кресло и спит, пока тот занят стрижкой. Если парикмахер занят, когда приходит посетитель, тот садится в одно из свободных кресел и засыпает. После стрижки парикмахер открывает посетителю выходную дверь и закрывает ее за ним. Если есть ожидающие посетители, парикмахер будит одного из них и ждет, пока тот сядет в кресло парикмахера. Если никого нет, он снова идет спать до прихода следующего посетителя.
182 Часть 1. Программирование с разделяемыми переменными
Посетители и парикмахер являются процессами, взаимодействующими в мониторе — парикмахерской (рис. 5.2). Посетители — это клиенты, которые запрашивают сервис (стрижку) у парикмахера. Парикмахер — это сервер, постоянно обеспечивающий сервис. Данный тип взаимодействия представляет собой пример отношений клиент-сервер.
Для реализации описанных взаимодействий парикмахерскую можно промоделировать монитором с тремя процедурами: get_haircut (постричься), get_next_customer (позвать следующего) и f inished_cut (закончить стрижку). Посетители вызывают процедуру get_haircut; выход из нее происходит после того, как парикмахер закончит стрижку данного посетителя. Парикмахер циклически вызывает процедуру get_next_customer, приглашая клиента в свое кресло, стрижет его и выпускает из парикмахерской с помощью вызова процедуры f inished_cut. Постоянные переменные служат для хранения состояния процессов и представления кресел, в которых процессы спят.
Действия парикмахера и посетителей необходимо синхронизировать в мониторе. Во-первых, парикмахеру и посетителю необходима встреча — рандеву, т.е. парикмахер должен дождаться прихода посетителя, а посетитель — освобождения парикмахера. Рандеву аналогично барьеру для двух процессов, поскольку для продолжения работы к нему должны прийти обе стороны. Однако рандеву отличается от двухпроцессного барьера тем, что парикмахер может встретиться с любым из посетителей.
Во-вторых, посетителю необходимо ждать, пока парикмахер закончит его стричь, что определяется открытием выходной двери для посетителя. Наконец, перед тем, как закрыть выходную дверь, парикмахер должен подождать, пока уйдет посетитель. Таким образом, парикмахер и посетитель проходят через последовательность синхронизированных этапов, начинающихся с рандеву.
Самый простой способ определить подобные этапы синхронизации — использовать возрастающие счетчики для запоминания числа процессов, достигших каждого этапа. У посетителей есть два важных этапа: пребывание в кресле парикмахера и выход из парикмахерской. Для этих этапов будем использовать счетчики cinchair и cleave. Парикмахер циклически проходит через три этапа: освобождение от работы, стрижка и завершение стрижки. Используем для них счетчики bavail, bbusy и bdone. Все счетчики в начальном состоянии имеют значение нуль. Поскольку процессы проходят свои этапы последовательно, для счетчиков выполняется следующий инвариант:
Cl: cinchair >= cleave л bavail >= bbusy >= bdone
Чтобы обеспечить рандеву посетителя и парикмахера перед началом стрижки, посетитель не может садиться в кресло парикмахера чаще, чем парикмахер освобождается от работы. Кроме того, парикмахер не может начинать стрижку чаще, чем посетители садятся в его кресло. Итак, выполняется условие:
С2: cinchair <= bavail л bbusy <= cinchair
Наконец, посетители не могут выходить из парикмахерской чаще, чем парикмахер завершает стрижку:
СЗ: cleave <= bdone
Глава 5 Мониторы 183
Инвариант монитора для парикмахерской, таким образом, является конъюнкцией трех предикатов:
BARBER: С1 ^ С2 ^ СЗ
Возрастающие счетчики применимы для запоминания этапов, через которые проходят процессы, однако их значения могут возрастать неограниченно. Если синхронизация зависит только от разницы значений счетчиков, возрастания можно избежать, изменив переменные. В данной задаче есть три ключевые разности, для которых выделим три новые переменные barber, chair и open.
barber == bavail - cinchair chair == cinchair - bbusy open == bdone - cleave
Они инициализируются 0, а во время работы программы могут принимать значения 0 или 1. Значение barber равно 1, если парикмахер ожидает посетителя и сидит в своем кресле. Переменная chair имеет значение 1, если посетитель уже сел в кресло, но парикмахер еще не занят, а переменная open принимает значение 1, когда выходная дверь уже открыта, но посетитель еще не вышел.
Остается использовать эти условные переменные для реализации необходимой синхронизации между парикмахером и посетителями". Существуют четыре условия синхронизации: посетители дожидаются освобождения парикмахера; посетители ждут, когда парикмахер откроет дверь; парикмахер ждет прихода посетителя; парикмахер ждет ухода посетителя. Для представления этих условий нужны четыре условных переменных. Процессы ждут выполнения условий с помощью операторов wait, заключенных в циклы. В моменты, когда условия становятся истинными, процессы выполняют операцию signal.
Полное решение представлено в листинге 5.8. Эта задача значительно сложнее, чем рассмотренные ранее, поэтому имеет более сложное и длинное решение. Однако с помощью систематического подхода удается разделить всю синхронизацию на маленькие части, разработать решение для каждой из них и затем "склеить" решения.
184 Часть 1 Программирование с разделяемыми переменными
В приведенном мониторе мы впервые видим процедуру get_haircut, содержащую два оператора wait. Дело в том, что посетитель проходит через два этапа: сначала он ждет, пока не освободится парикмахер, потом — пока не закончится стрижка.