Деревянко А.С., Солощук М.Н. Операционные системы.Часть I. Построение и функционирование операционных систем

Подождите немного. Документ загружается.

281

while (1) {

section ( stack ) {

await( stack.stPtr > 0 );

memcpy ( &work, stack.buffer +

--stack.stPtr,

sizeof(portion) );

}

< обработка порции в work>

}

При реализации возможности await мы должны решить проблему

исключения. В приведенном выше примере процесс-производитель,

заблокированный в строке 10, ждет уменьшения значения указателя стека

(если стек полон). Это значение может быть уменьшено процессом-

потребителем в строке 23, но эта строка находится в критической секции

потребителя, а последний не может войти в свою критическую секцию, так

как производитель уже вошел в свою, – в строке 9. Одним из способов

разрешения этого противоречия является запрещение употребления await

где-либо, кроме самого начала критической секции, возможно, даже

включение await-условия в заголовок секции. Исключение в этом случае

начинает работать только после выхода из await. Естественно, что сама

проверка условия должна выполняться как атомарная операция

(защищаться скрытым семафором).

Можно разрешить await где угодно в критической секции, но на

время блокировки процесса в await снимать взаимное исключение.

Конечно, такой вариант дает программисту более гибкий инструмент, но

перекладывает на него ответственность за целостность, так как за время, на

282

которое исключение снимается, разделяемые данные могут быть

изменены.

Еще один вопрос, который мы должны решить при реализации

await: если процесс заблокировался, то в какие моменты следует

проверять условие разблокирования? Вопрос непраздный, так как для

вычисления условия, являющегося операндом await, необходимо

активизировать контекст заблокированного процесса. Если проделывать

это слишком часто, то накладные расходы на переключение неоправданно

возрастают. Для варианта, в котором мы жестко привязываем await к

началу критической секции, общая переменная, входящая в условие,

может быть изменена только другим процессом и ее новое значение станет

доступным при выходе этого другого процесса из его критической секции.

Выход другого процесса из критической секции – единственное событие,

по которому имеет смысл переключаться в контекст заблокированного

процесса и проверять условие в этом варианте. Если же мы разрешаем

употребление await где угодно в критической секции, то добавляется еще

один тип события – блокировка другого процесса в операторе await его

критической секции.

8.8. Мониторы

Монитор представляет собой набор информационных структур и

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

процедур являются внешними и доступны процессам пользователей, их

имена представляют входные точки монитора. Пользователь не имеет

доступа к информационным структурам монитора и может воздействовать

на них, только обращаясь к входным точкам. Монитор, таким образом,

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

283

ориентированного программирования ресурс, обслуживаемый монитором,

представляет собой объект, а входные точки – методы работы с этим

объектом. Особенностью монитора, однако, является то, что в его состав

входят так называемые "процедуры с охраной", которые не могут

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

Не являясь средством более мощным или гибким, чем

рассмотренные выше примитивы, мониторы, однако представляют

значительно более удобный инструмент для программиста, избавляя его от

необходимости формировать критические секции, обеспечивая более

высокий уровень интеграции данных и предупреждая возможные ошибки

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

Если в задаче "производители–потребители" процессы

программируются пользователем, то вид этих процессов может быть

таким:

#include <monitor.h>

/* процесс-производитель

(может быть отдельным модулем) */

void producer ( void ) {

portion work;

while (1) {

< производство порции в work >

putPortion ( &work );

}

/* процесс-потребитель

(может быть отдельным модулем) */

void consumer ( void ) {

portion work;

284

while (1) {

getPortion ( &work );

< обработка порции в work>

}

Обратим внимание на то, что процессы, во-первых, никоим образом

не заботятся о разделении данных, во-вторых, не используют никакие

общие данные. Такая "беззаботная" работа процессов, однако, должна

быть поддержана монитором, входные точки которого описаны в файле

monitor.h, а определение его имеет такой вид:

/* монитор производителей-потребителей

(отдельный модуль) */

#define BSIZE ...

/* буфер */

static portion buffer [BSIZE];

/* индексы буфера для чтения и записи*/

static int rIndex = 0, wIndex = 0;

/* счетчик заполнения */

static int cnt = 0;

/* события НЕ_ПУСТ, НЕ_ПОЛОН */

static event nonEmpty, nonFull;

/* процедура занесения порции в буфер*/

void guard putPortion ( portion *x ) {

/* если буфер полон -

ожидать события НЕ_ПОЛОН */

if ( cnt == BSIZE ) wait (nonFull);

/* запись порции в буфер */

285

memcpy ( buffer + wIndex,

x, sizeof(portion) ) ;

/* модификация индекса записи */

if ( ++wIndex == BSIZE ) wIndex = 0;

cnt++; /* подсчет порций в буфере */

/* сигнализация о том,

что буфер НЕ_ПУСТ */

signal (nonEmpty);

}

void guard getPortion ( portion *x ) {

if ( cnt == 0 ) wait (nonEmpty);

memcpy ( x, buffer + rIndex,

sizeof(portion) ) ;

if ( ++rIndex == BSIZE ) rIndex = 0;

cnt++;

signal (nonFull);

}

В реализации монитора нам пришлось прибегнуть к некоторым

новым обозначениям. Во-первых, функции монитора даны с описателем

guard (охрана). Это означает, что они должны выполняться в режиме

взаимного исключения. В литературе часто употребляется образное

сравнение мониторов с комнатой, в которой может находиться только один

человек. Такая комната показана на рисунке 8.2. Если человек (процесс)

желает войти в комнату (охраняемую процедуру монитора), то он

становится во входную очередь к двери 1, в которой он ожидает

(блокируется) до тех пор, пока комната (монитор) не освободится. Дверь 1

(вход) отпирается только в том случае, если комната пуста, пропускает

286

только одного человека и запирается за ним. Дверь 2 (выход) не заперта,

когда она открывается, отпирается и дверь 1.

Рисунок 8.2 Простая модель монитора

Обратите внимание на то, что взаимное исключение обеспечивается для

всех охраняемых процедур, а не только для одноименных. В сущности,

такая процедура представляет собой ту же критическую секцию, и ее

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

скорее всего, в роли "охранника" будет выступать скрытый семафор.

Другие наши нововведения связаны с блокировками внутри

охраняемой процедуры. Мы ввели тип данных, названный нами event.

Этот тип представляет некоторое событие. Примитив wait проверяет

наступление этого события и переводит процесс в ожидание, если событие

еще не произошло. Примитив signal сигнализирует о наступлении

события. Событие является потребляемым ресурсом: если два процесса

ожидают одного и того же события, то при наступлении события

разблокирован будет только один из процессов, другой будет вынужден

ждать повторного наступления такого же события.

Примитивы ожидания-сигнализации требуют принятия решений по

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

наступлении некоторого события, то в какой момент должен быть

разблокирован процесс, ожидающий этого события? Если немедленно, то

тогда в нашей "комнате" окажется два процесса одновременно:

разблокированный процесс и процесс, выдавший сигнал, но еще не

покинувший монитор. Если позже, то за это время в монитор может войти

287

какой-то третий процесс. Если несколько процессов ожидают одного и

того же события, то какой (или какие) из них должен быть разблокирован?

Если в момент выдачи сигнала нет процессов, ожидающих этого события,

то должен ли сигнал сохраняться или его можно "потерять"?

Общий подход к решению этой проблемы иллюстрируется

расширением модели "одноместной комнаты", показанным на рисунке 8.3.

Для каждого события, которое может ожидаться в мониторе, мы вводим

свою очередь с соответствующими входными и выходными дверями для

нее. На рисунке эти очереди показаны внизу монитора. Мы вводим также

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

очередях, не считаются находящимися в мониторе. "Правила для

посетителей" комнаты-монитора следующие.

1. Новый процесс поступает во входную очередь. Новый процесс

может войти в монитор через дверь 1 только, если в мониторе нет

других процессов.

2. Если процесс выходит из монитора через дверь 2 (выход), то в

монитор входит процесс из двери 4 – из приоритетной очереди.

Если в приоритетной очереди нет ожидающих, входит процесс из

двери 1 (если есть ожидающие за ней).

3. Процесс, выполняющий операцию wait, выходит из монитора в

дверь, ведущую в соответствующую очередь (5 или 7).

4. Если процесс выполняет операцию signal, то проверяется

очередь, связанная с событием. Если эта очередь непуста, то

сигнализирующий процесс уходит в приоритетную очередь (дверь

3), а в монитор входит один процесс из очереди к событию (дверь

6 или 8). Если очередь пуста, сигнализирующий процесс остается

в мониторе.

5. Все очереди обслуживаются по дисциплине FCFS.

288

Рисунок 8.3 Расширенная модель монитора

Эти правила предполагают, что процесс будет разблокирован

немедленно (речь идет не о немедленной активизации процесса, а о его

разблокировании – перемещении в очередь готовых к выполнению).

Разблокированный процесс имеет преимущество перед процессом,

ожидающим во входной очереди.

В нашем примере производителей–потребителей мы употребляли

операцию signal в конце процедуры. Такое употребление характерно для

очень большого числа задач. Наши правила требуют перемещения

сигнализирующего процесса в приоритетную очередь. Однако, если

сигнализирующий процесс после выдачи сигнала больше не выполняет

никаких действий с разделяемыми данными, необходимости в таком

перемещении (и вообще в приоритетной очереди) нет. Жесткая привязка

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

но значительно упрощает диспетчеризацию процессов в мониторе.

Возможно решение, в котором операция signal разблокирует все

процессы, находящиеся в соответствующей очереди. Поскольку все

ожидавшие процессы не могут вместе войти в монитор, в нем остается

только один из них, успевший "подхватить" событие, а остальные

направляются в приоритетную очередь. Процесс, который

разблокировался таким образом, уже не может, однако, быть уверенным в

289

том, что его разблокирование гарантирует наступление события (событие

могло быть перехвачено другим процессом). Поэтому в проверке условия

ожидания оператор if для такой реализации должен быть заменен

оператором while, например, строки 14 - 16 последнего примера должны

выглядеть так:

/* если буфер полон -

ожидать события НЕ_ПОЛОН */

while ( cnt == BSIZE ) wait (nonFull);

Поскольку охраняемые процедуры есть критические секции, для

поддержания высокого уровня мультипрограммирования нахождение в

них процессов должно быть кратковременным. Проблема времени

может возникнуть в том случае, когда в процедуре монитора имеется

обращение к другому монитору. По нашим правилам такое обращение

не выводит процесс из первого монитора. Однако во втором

(вложенном) мониторе процесс может быть заблокирован, тогда его

пребывание в первом мониторе недопустимо затянется. Возможно

несколько вариантов решения этой проблемы:

• переложить ответственность за возникновение такой ситуации на

программиста;

• запретить вложенные вызовы вообще;

• при вхождении во вложенный монитор автоматически снимать

исключение с внешнего монитора, когда процесс возвращается из

вложенного монитора, он попадает в приоритетную очередь

внешнего монитора;

• предоставить программисту выбор из перечисленных выше

возможностей.

290

8.9. "Читатели–писатели" и групповые мониторы

Еще одна классическая задача синхронизации называется задачей

"читателей–писателей" и формулируется следующим образом. Имеется

произвольное число процессов-писателей и процессов-читателей, которые

совместно используют какие-то данные (обычно имеется в виду файл). В

любой момент процесс-читатель может потребовать прочитать данные. В

любой момент процесс-писатель может потребовать прочитать или

записать данные. Чтение и запись данных – операции длительные, но

конечные. В то время, когда процесс записывает данные, никакие другие

читатели или писатели не должны иметь доступа к данным. Любое число

процессов может читать данные одновременно. Решение должно

обеспечивать целостность данных и отсутствие бесконечного

откладывания процессов.

Существенные отличия этой задачи от задачи производителей–

потребителей состоят в следующем:

• процессы чтения и записи длительные;

• данные представляют собой повторно используемые ресурсы, а не

потребляемые, как в предыдущей задаче;

• требуются различные режимы доступа для чтения и записи.

Нам не удастся решить эту задачу при помощи мониторов,

описанных в предыдущем разделе, так как, если мы сделаем процедуры

read и write охраняемыми, то, во-первых, у нас получатся слишком

большие (длительные) критические секции, а во-вторых, мы исключим

параллельное выполнение читателей.

Решение может быть получено при помощи так называемого

группового монитора. В такой монитор входят как охраняемые, так и