Методы синхронизации

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

5.2.1. Кольцевые буферы: базовая условная синхронизация

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

В листинге 5.3 приведен монитор, реализующий кольцевой буфер. Для представления очереди сообщений вновь использованы массив buf и две целочисленные переменные front и rear, которые указывают соответственно на первую заполненную и первую пустую ячейку. В целочисленной переменной count хранится количество сообщений в буфере. Опе­рации с буфером deposit и fetch становятся процедурами монитора. Взаимное исключе­ние неявно, поэтому семафорам не нужно защищать критические секции. Условная синхро­низация, как показано, реализована с помощью двух условных переменных.

В листинге 5.3 оба оператора wait находятся в циклах. Это безопасный способ обеспе­чить истинность необходимого условия перед тем, как произойдет обращение к постоянным переменным. Это необходимо также при наличии нескольких производителей и потребите­лей. (Напомним, что используется порядок "сигнализировать и продолжить".)

Выполняя операцию signal, процесс просто сообщает, что теперь некоторое условие ис­тинно. Поскольку процесс-сигнализатор и, возможно, другие процессы могут выполняться в мониторе до возобновления процесса, запущенного операцией signal, в момент начала его работы условие запуска может уже не выполняться.
Например, процесс-производитель был приостановлен в ожидании свободной ячейки, затем процесс-потребитель извлек сооб­щение и запустил приостановленный процесс. Однако до того, как этому производителю пришла очередь выполняться, другой процесс-производитель мог уже войти в процедуру de­posit и занять пустую ячейку. Аналогичная ситуация может возникнуть и с потребителями. Таким образом, условие приостановки необходимо перепроверять.

Операторы 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. Дело в том, что посетитель проходит через два этапа: сначала он ждет, пока не освободится парикмахер, потом — пока не закончится стрижка.


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

---

---