Планирование работы диска: программные структуры

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

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

На рис. 5.3 приведена общая схема диска с подвижными головками. Он содержит не­сколько соединенных с центральным шпинделем пластин, которые вращаются с постоянной скоростью. Данные хранятся на поверхностях пластин. Пластины похожи на граммофонные пластинки, за исключением того, что дорожки на них образуют отдельные концентрические кольца, а не спираль. Дорожки с одинаковым относительным положением на пластинах об­разуют цилиндр. Доступ к данным осуществляется так: головка чтения-записи перемещается на нужную дорожку, затем ожидает, когда пластина повернется и необходимые данные прой­дут у головки. Обычно одна пластина имеет одну головку чтения-записи. Головки объедине­ны в рычаг выборки, который может двигаться по'радиусу так, что их можно перемещать на любой цилиндр и, следовательно, на любую дорожку.

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

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

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

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

Предполагается, что диск используют несколько клиентов. Например, в мультипро­граммной операционной системе это могут быть процессы, выполняющие команды пользо­вателя, или системные процессы, реализующие управление виртуальной памятью. Если дос­туп к диску запрашивает всего один клиент, то ничего нельзя выиграть, не дав ему доступ не­медленно, поскольку неизвестно, когда к диску обратится еще один клиент. Таким образом, планирование доступа к диску применяется, только когда приблизительно в одно время дос­туп запрашивают как минимум два процесса.

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


Эта стратегия называется стратегией кратчайшего времени поиска (shortest-seek-time — SST), поскольку помогает минимизировать время поиска. Однако SST— несправедливая стратегия, поскольку непрерывный поток запросов для цилиндров, находящихся рядом с те­кущей позицией головки, может остановить обработку запросов к отдаленным цилиндрам. Хотя такая остановка обработки запросов крайне маловероятна, длительность ожидания об­работки запроса здесь ничем не ограничена. Стратегия SST используется в операционной системе UNIX; системный администратор с причудами, желая добиться справедливости пла­нирования, наверное, купил бы побольше дисков .

Еще одна, уже справедливая, стратегия планирования — перемещать головки в одном на­правлении, пока не будут обслужены все запросы в этом направлении движения. Выбирается клиентский запрос, ближайший к текущей позиции головки в направлении, в котором она двигалась перед этим. Если для этого направления запросов больше нет, оно изменяется. Эта стратегия встречается под разными названиями — SCAN (сканирование), LOOK (просмотр) или алгоритм лифта, поскольку перемещения головки похожи на работу лифта, который ездит по эта­жам, забирая и высаживая пассажиров. Единственная проблема этой стратегии — запрос, которо­му соответствует позиция сразу за текущим положением головки, не будет обслужен, пока головка не пойдет назад. Это приводит к большому разбросу времени ожидания выполнения запроса.

Третья стратегия аналогична второй, но существенно уменьшает разброс времени ожида­ния выполнения запроса. Ее называют CSCAN или CLOOK (буква С взята от "circular" — циклический). Запросы обслуживаются только в одном направлении, например, от внешнего к внутреннему цилиндру. Таким образом, существует только одно направление поиска, и вы­бирается запрос, ближайший к текущему положению головки в этом направлении. Когда за­просов в направлении движения головки не остается, поиск возобновляется с внешнего ци­линдра.


Это похоже на лифт, который только поднимает пассажиров. (Вероятно, вниз они должны были бы идти пешком или прыгать!) В отношении сокращения времени поиска стра­тегия CSCAN эффективна почти так же, как и алгоритм лифта, поскольку для большинства дисков перемещение головок через все цилиндры занимает примерно вдвое больше времени, чем перемещение между соседними цилиндрами. Кроме того, стратегия CSCAN справедлива, если только поток запросов к текущей позиции головки не останавливает выполнение ос­тальных запросов (что крайне маловероятно).

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

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

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

Все три монитора-диспетчера реализуют стратегию CSCAN, но их нетрудно модифици­ровать для реализации любой стратегии планирования. Например, реализация стратегии SST приведена в главе 7.

5.3.1. Использование отдельного монитора

Реализуем диспетчер монитором, который отделен от управляемого им ресурса, т.е. диска (рис. 5.4). В решении есть три вида компонентов: пользовательские процессы, диспетчер, а так­же процедуры или процесс, выполняющие обмен данными с диском. Диспетчер реализован мо­нитором, чтобы данные планирования были доступны одновременно только одному процессу. Монитор поддерживает две операции: request (запросить) и release (освободить).



Для получения доступа к цилиндру cyl пользовательский процесс сначала вызывает про­цедуру request (cyl), из которой возвращается только после того, как диспетчер выберет этот запрос.


Затем пользовательский процесс работает с диском, например, вызывает соот­ветствующие процедуры или взаимодействует с процессом драйвера диска. После работы с диском пользователь вызывает процедуру release, чтобы диспетчер мог выбрать новый запрос. Таким образом, диспетчер имеет следующий пользовательский интерфейс.

Disk_Scheduler.request(cyl)

работа с диском

Disk_Scheduler.release()

Монитор Disk_Scheduler играет двойную роль: он планирует обращения к диску и обеспе­чивает в любой момент времени доступ к диску только одному процессу. Таким образом, пользователи обязаны следовать указанному выше протоколу.

Предположим, что цилиндры диска пронумерованы от 0 до maxcyl, и диспетчер исполь­зует стратегию CSCAN с направлением поиска от 0 до maxcyl. Как обычно, важнейший шаг в разработке правильного решения — точно сформулировать его свойства. Здесь в любой мо­мент времени только один процесс может использовать диск, а ожидающие запросы обслу­живаются в порядке CSCAN.

Пусть переменная position указывает текущую позицию головки диска, т.е. номер ци­линдра, к которому обращался процесс, использующий диск. Когда к диску нет обращений, переменной cylinder присваивается значение -1. (Можно использовать любой неправиль­ный номер цилиндра или ввести дополнительную переменную.)

Для реализации стратегии планирования CSCAN необходимо различать запросы, которые нужно выполнить за текущий и за следующий проход через диск. Пусть эти запросы хранятся в непересекающихся множествах с и N. Оба множества упорядочены по возрастанию значе-

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

ния cyl, запросы к одному и тому же цилиндру упорядочены по времени вставки в множество. Таким образом, множество с содержит запросы для цилиндров, номера которых больше или равны текущей позиции, а N — для цилиндров с номерами, которые меньше или равны текущей позиции. Это выражается следующим предикатом, который является инвариантом монитора.



DISK:   С и N являются упорядоченными множествами л все элементы множества С >= position л все элементы множества N <= position л (position ==  -1}   =>   (С == 0 л N == 0)

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

Вызывая процедуру request, процесс выполняет одно из трех действий. Если переменная position имеет значение -1, диск свободен; процесс присваивает переменной position зна­чение cyl и работает с диском. Если диск занят и выполняется условие cyl > position, то процесс вставляет значение cyl в с, иначе (cyl < position) — в N. При равенстве значе­ний cyl и position используется N, чтобы избежать возможной несправедливости плани­рования, поэтому запрос будет ожидать следующего прохода по диску. После записи значе­ния cyl в подходящее множество процесс приостанавливается до тех пор, пока не получит доступ к диску, т.е. до момента, когда значения переменных pos it ion и cyl станут равными.

Вызывая процедуру release, процесс обновляет постоянные переменные так, чтобы вы­полнялось условие DISK. Если множество с не пусто, то еще есть запросы для текущего про­хода. В этом случае процесс, освобождающий доступ к диску, удаляет первый элемент мно­жества с и присваивает это значение переменной position. Если с пусто, а N — нет, то нуж­но начать новый проход, который становится текущим. Для этого освобождающий процесс меняет местами множества с и N (N при этом становится пустым), затем извлекает первый элемент из С и присваивает его значение переменной position. Если оба множества пусты, то для индикации освобождения диска процесс присваивает переменной position значение -1.

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


Запросы в множествах С и N обслужи­ваются в порядке возрастания значения cyl. Эта ситуация похожа и на семафор FIFO: когда ос­вобождается диск, разрешение на доступ к нему передается одному ожидающему процессу. Переменной position нужно присваивать значение того ожидающего запроса, который будет обработан следующим. По этим двум причинам синхронизацию можно реализовать эффектив­но, объединив свойства мониторов Timer (см. листинг 5.7) и FIFOsemaphore (см. листинг 5.2).

Для представления множеств с и N используем массив условных переменных scan [2], индексированный целыми сип. Когда запрашивающий доступ процесс должен вставить свой параметр cyl в множество С и ждать, пока станут равны position и cyl, он просто выполняет процедуру wait(scan[c] ,cyl). Аналогично процесс вставляет свой запрос вмножество N и приостанавливается, выполняя wait(scan[n] ,cyl). Кроме того, чтобы определить, пусто ли множество, используется функция empty, чтобы вычислить наимень­шее значение в множестве — функция minrank, а для удаления первого элемента с одновре­менным запуском соответствующего процесса — процедура signal. Множества с и N меня­ются местами, когда это нужно, с помощью простого обмена значений сип. (Именно поэто­му для представления множеств выбран массив.)

Объединив перечисленные изменения, получим программу в листинге 5.9. В конце процедуры release значением с является индекс текущего множества обрабатываемых запросов, поэтому достаточно вставить только один оператор signal. Если в этот момент переменная position имеет значение -1, то множество scan [с] будет пустым, и вызов signal не даст результата.



Задачи планирования, подобные рассмотренной, наиболее трудны, какой бы механизм син­хронизации не использовался. Главное в решении— точно определить порядок обслуживания процессов. Когда порядок статичен, как здесь, можно использовать приоритетные операторы wait. Но, как отмечалось ранее, при динамическом порядке обслуживания необходимо использо­вать либо скрытые условные переменные для запуска отдельных процессов, либо покрывающие условия, позволяя приостановленным процессам осуществлять планирование самостоятельно.



5.3.2. Использование посредника

Чтобы привести структуру решения к задаче планирования и распределения, желательно реализовать монитор Disk_Scheduler или другой контроллер ресурсов в виде отдельного монитора. Поскольку диспетчер изолирован, его можно разрабатывать независимо от других компонентов. Однако чрезмерная изоляция обычно приводит к двум проблемам:

•     присутствие диспетчера видно процессам, использующим диск. Если удалить диспет­чер, изменятся пользовательские процессы;

•     все пользовательские процессы должны следовать необходимому протоколу: запрос диска, его использование, освобождение. Если хотя бы один процесс нарушает этот протокол, планирование невозможно.

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

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

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



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



В оставшейся части этого раздела показано, как преобразовать решение задачи о спящем парикмахере (листинг 5.8) в интерфейс драйвера диска, который и обеспечивает взаимодей­ствие между клиентами и драйвером диска, и реализует стратегию планирования CSCAN. Решение задачи о спящем парикмахере нужно немного изменить. Первое: переименовать процессы, монитор и процедуры монитора, как описано ниже и показано в листинге 5.10. Второе: в процедуры монитора добавить параметры для передачи запросов пользователей (посетителей) к драйверу диска (парикмахеру) и обратной передачи результатов. По сути, "кресло парикмахера" и "выходную дверь" нужно превратить в буферы взаимодействия. На­конец, нужно добавить планирование к рандеву пользователь—драйвер диска, чтобы драйвер обслуживал предпочтительный запрос пользователя. Перечисленные изменения приводят к интерфейсу диска, схема которого показана в листинге 5.10.

Листинг 5.10. Схема монитора интерфейса диска

monitor Disk_Interface   {

постоянные переменные для состояния, планирования и передачи данных

procedure use_disk(int cyl,   параметры передачи и результата)   {

ждать очереди использовать драйвер

сохранить параметры передачи в постоянных переменных



ждать завершения передачи

получить результаты из постоянных переменных

}

procedure get_next_request(someType &results)   {

выбрать следующий запрос

ждать сохранения параметров передачи

присвоить переменной results параметры передачи

}

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

procedure  finished_transfer(someType results)   { сохранить результаты в постоянные переменные ждать получения клиентом значения results }

_}_______________________________________________________________________________

Чтобы уточнить схему до полноценного решения, используем ту же базовую синхрониза­цию, что и в решении задачи о спящем парикмахере (см. листинг 5.8). К ней добавим плани­рование, как в мониторе Disk_Scheduler (см. листинг 5.9), и передачу параметров, как в кольцевом буфере (см. листинг 5.3). Инвариант монитора Disk_Interf асе становится, по существу, конъюнкцией инварианта для парикмахерской BARBER, инварианта диспетчера DISK и инварианта кольцевого буфера ВВ (упрощенного для одной ячейки).

Пользовательский процесс ждет очереди на доступ к диску, выполняя те же действия, что и процедура request монитора Disk_Scheduler (см. листинг 5.9). Аналогично процесс драйвера показывает, что он доступен, выполняя те же действия, что и процедура release монитора Disk_Scheduler. В начальном состоянии, однако, переменной position будет присваиваться значение -2, чтобы показать, что диск недоступен и не используется до того, как драйвер впервые вызовет процедуру get_next_request. Следовательно, пользователи должны ждать начала первого прохода.

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


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





С помощью двух сравнительно простых изменений этот интерфейс между пользователем и драйвером диска можно сделать еще эффективнее. Во-первых, драйвер диска может быстрее на­чать обработку следующего пользовательского запроса, если в процедуре f inished_transf er исключить ожидание извлечения результатов предыдущей передачи. Но это нужно делать осто­рожно, чтобы область результатов не была перезаписана, когда драйвер завершает следую­щую передачу данных, а результаты предыдущей еще не извлечены. Во-вторых, можно объе­динить две процедуры, вызываемые драйвером диска. Тогда при обращении к диску эконо­мится один вызов процедуры монитора. Реализация этих преобразований требует изменить инициализацию переменной results. Внесение обеих поправок предоставляется читателю.

5.3.3. Использование вложенного монитора

Если диспетчер доступа к диску является отдельным монитором, пользовательские процес­сы должны следовать протоколу: запрос диска, работа с ним, освобождение. Сам по себе диск управляется процессом или монитором. Когда диспетчер доступа к диску является посредни­ком, пользовательский интерфейс упрощается (пользователю достаточно сделать всего один за­прос), но монитор становится значительно сложнее, как видно из сравнения листингов 5.9 и 5.11. Кроме того, решение в листинге 5.11 предполагает, что диском управляет процесс драйвера.

Третий способ состоит в объединении двух стилей с помощью двух мониторов: одного для планирования и одного для доступа к диску (рис. 5.6). Однако при использовании такой структуры необходимо, чтобы вызовы из монитора диспетчера освобождали исключение в мониторе доступа. Ниже мы исследуем это свойство вложенных вызовов мониторов и раз­работаем схему решения задачи планирования доступа к диску.



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


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

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

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

Задача планирования доступа к диску является конкретным примером, в котором возникают описанные проблемы. Как уже отмечалось, решение задачи можно изменить в соответствии с рис. 5.6. Монитор Disk_Scheduler из программы в листинге 5.9 заменен двумя мониторами. Пользовательский процесс делает один вызов операции doIO монитора Disk_Access. Этот мо­нитор планирует доступ, как в листинге 5.9. Когда приходит очередь процесса на доступ к диску, он делает второй вызов операции read или write монитора Disk_Transf er. Этот второй вы­зов происходит из монитора Disk_Access, имеющего следующую структуру, monitor Disk_Access {

постоянные переменные такие же, как в мониторе Disk_Scheduler ;

procedure doIOfint cyl;   аргументы передачи и результата)   { действия процедуры  Disk_Scheduler.


request; вызов Disk_Transfer. read или Disk_Transf er .write ; действия процедуры Disk_Scheduler. release; } >

Вызовы монитора Disk_Transf er являются вложенными. Для планирования доступа к диску они должны быть открытыми, иначе в процедуре doIO не смогут одновременно находиться не­сколько процессов, и действия request и release станут ненужными. Здесь можно использо­вать открытые вызовы, поскольку в качестве аргументов для монитора Disk_Transf er пе­редаются только локальные переменные (параметры процедуры doIO), а инвариант диспет­чера доступа DISK перед вызовом операций read или wr i te остается истинным.

Независимо от семантики вложенных вызовов, остается проблема взаимного исключения внутри монитора. При последовательном выполнении процедур монитора параллельный доступ к его постоянным переменным невозможен. Однако это не всегда обязательно для исключения взаимного влияния процедур. Если процедура считывает, но не изменяет постоянные перемен­ные, то ее разные вызовы могут выполняться параллельно. Или, если процедура просто возвра­щает значение некоторой постоянной переменной, и оно может читаться неделимым образом, . з эта процедура может выполняться параллельно с другими процедурами монитора. Значение, возвращенное вызвавшему процедуру процессу, может не совпадать с текущим значением по­стоянной переменной, но так всегда бывает в параллельных программах. К примеру, можно до­бавить процедуру read_clock к монитору Timer в листинге 5.6 или 5.7. Независимо от того, выполняется процедура read_clock со взаимным исключением или нет, вызвавший ее про­цесс знает лишь, что возвращаемое значение не больше текущего значения переменной tod.

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


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



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

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

Указанный выше пример можно запрограммировать иначе, используя ключевое слово synchronized для операторов внутри метода.

class Interfere {

private int data = 0; public void update() {

synchronized (this) {  // блокировка данного объекта

data+ " } } }

Ключевое слово this ссылается на объект, для которого был вызван метод update, и, следо­вательно, на блокировку этого объекта. Синхронизированный оператор (с ключевым словом synchronized), таким образом, аналогичен оператору await, а синхронизированный метод — процедуре монитора.

Язык Java поддерживает условную синхронизацию с помощью операторов wait Hnotify; они очень похожи на операторы wait и signal, использованные ранее в этой главе. Но операторы wait и notify в действительности являются методами класса Object, родительского для всех классов языка Java. И метод wait, и метод notify должны выпол­няться внутри кода с описанием synchronized, т.е. при заблокированном объекте.

Метод wait снимает блокировку объекта и приостанавливает выполнение потока. У каж­дого объекта есть одна очередь задержки. Обычно (но не обязательно) это FIFO-очередь.


Язык Java не поддерживает условные переменные , но можно считать, что на каждый синхро­низированный объект приходится по одной (неявно объявленной) условной переменной.

Метод notify запускает поток из начала очереди задержки, если он есть. Поток, вызвав­ший метод notify, продолжает удерживать блокировку объекта, так что запускаемый по­ток начнет работу через некоторое время, когда получит блокировку объекта. Это значит, что метод notify имеет семантику "сигнализировать и продолжить". Язык Java также поддерживает оповещающий сигнал с помощью метода noti f yAll, аналогичного процедуре signal_all. Поскольку у объекта есть только одна (неявная) переменная, методы wait, not i f у и not i f yAl 1 не имеют параметров.

Если синхронизированный метод (или оператор) одного объекта содержит вызов метода в другом объекте, то блокировка первого объекта во время выполнения вызова удерживается. Таким образом, вложенные вызовы из синхронизированных методов в языке Java являются закрытыми. Это не позволяет для решения задачи планирования доступа к диску с вложен­ными мониторами использовать струк^ру, изображенную на рис. 5.6. Это также может при­вести к зависанию программы, если изсинхронизированного метода одного объекта вызыва­ется синхронизированный метод другого объекта и наоборот.

5.4.3. Читатели и писатели с параллельным доступом

В данном и следующих двух подразделах представлен ряд примеров, иллюстрирующих ас­пекты параллелизма и синхронизации программ на языке Java, использование классов, дек­лараций и операторов. Все три программы являются завершенными: их можно откомпилиро­вать компилятором javac и выполнить с помощью интерпретатора Java. (За подробностями использования языка Java обращайтесь к своей локальной инсталляции; на Web-странице этой книги также есть исходные коды программ.)

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

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


Хотя в этой программе возможно взаимное влияние процессов, она служит для иллюстрации структуры программ на языке Java и использования потоков.

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



Членами класса являются поле data и два метода, read и write. Поле data объявлено с ключевым словом protected, т.е. оно доступно только внутри класса или в подклассах, на­следующих этот класс (или в других классах, определенных в том же модуле). Методы read и write объявлены с ключевым словом public; это значит, что они доступны везде, где дос­тупен класс. Каждый метод при запуске выводит одну строку, которая показывает текущее значение поля data; метод write увеличивает его значение.

Следующие классы в нашем примере — Reader и Writer. Они содержат коды процессов читателя и писателя и являются расширениями класса Thread. Каждый из них содержит ме­тод инициализации с тем же именем, что и у класса; этот метод выполняется при создании нового экземпляра класса. Каждый класс имеет метод run, в котором находится код потока. Класс Reader определен так.





Когда создается экземпляр любого из этих классов, новый объект получает два параметра: число циклов выполнения rounds и экземпляр класса RWbasic. Методы инициализации со­храняют параметры в постоянные переменные rounds и RW. Внутри методов инициализации имена переменных предваряются ключевым словом this, чтобы различать постоянную пе­ременную и параметр с тем же именем.

Три определенных выше класса Rwbasic, Reader и Writer — это "строительные блоки" программы для задачи о читателях и писателях, в которой читатели и писатели могут парал­лельно обращаться к одному экземпляру класса RWbasic. Чтобы закончить программу, ну­жен главный класс, который создает по одному экземпляру каждого класса и запускает пото­ки Reader и Writer на выполнение.





Программа начинает выполнение с метода main, который имеет параметр args, содержащий аргументы командной строки. Здесь это один аргумент, задающий число циклов, которые должен выполнить каждый поток. Программа выводит последовательность строк со считан­ными и записанными значениями. Всего выводится 2*rounds строк, поскольку работают два потока и каждый выполняет rounds итераций цикла.

5.4.4. Читатели и писатели с исключительным доступом

Приведенная выше программа позволяет потокам параллельно работать с полем data. Изменим ее, чтобы обе|спечить взаимно исключающий доступ к этому полю. Сначала опреде­лим новый класс RWexclusive, который расширяет класс RWbasic для использования син­хронизированных методов read и write.





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

while   (nr >  0)   //приостановка,   если есть  активные  потоки Reader

try   {  wait();   }

catch   (InterruptedException ex)   {return;} data++;

System.out.println("записано:   "   + data); notify();   //  запустить  еще  один ожидающий Writer } }

Нужно также изменить классы Reader, Writer и Main, чтобы они использовали этот класс вместо RWexclusive, но больше ничего менять не нужно. (Это одно из преимуществ объект­но-ориентированных языков программирования.)

В классе ReadersWriters появились два новых локальных (с ключевым словом pri­vate) метода: startRead и endRead. Их вызывает метод read перед обращением к базе данных и после него. Метод startRead увеличивает значение скрытой переменной nr, ко­торая учитывает число активных потоков-читателей. Метод endRead уменьшает значение переменной nr. Если она становится равной нулю, то для запуска ожидающего писателя (если он есть) вызывается процедура notify.

Методы startRead, endRead и write синхронизированы, поэтому в любой момент времени может выполняться только один из них. Следовательно, когда активен метод star­tRead или endRead, поток писателя выполняться не может.


Метод read не синхронизиро­ван, поэтому его одновременно могут вызывать несколько потоков. Если поток писателя вы­зывает метод write, когда поток читателя считывает данные, значение nr положительно, по­этому писатель перейдет в состояние ожидания. Писатель запускается, когда значение nr становится равным нулю. После работы с полем data писатель запускает следующий ожи­дающий процесс-писатель с помощью метода notify. Поскольку метод notify имеет се­мантику "сигнализировать и продолжить", писатель не сможет выполняться, если еще один читатель увеличит значение nr, поэтому писатель перепроверяет значение nr.

В приведенном выше методе write вызов wait находится внутри так называемого операто­ра try. Это механизм обработки исключений языка Java, который помогает программисту об­рабатывать нештатные ситуации. Поскольку ожидающий поток может быть остановлен или за­вершен ненормально, оператор wait необходимо использовать внутри оператора try, обрабаты­вающего исключительную ситуацию InterruptedException. В данном коде просто происходит выход из метода wr i te, если во время ожидания потока возникла исключительная ситуация.

Преимущество приведенного решения задачи о читателях и писателях по отношению к показанному ранее в листинге 5.4 состоит в том, что интерфейс потоков писателей органи­зован в одну процедуру write, а не в две, request_write () и release_write (). Тем не менее в обоих решениях читатели имеют преимущество перед писателями. Подумайте, как изменить приведенное решение, чтобы отдать преимущество писателям или сделать решение справедливым (см. упражнения в конце главы).


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

---

---