КаталогИндекс раздела
ОглавлениеВперед

1. Введение

Основная цель операционной системы состоит в том, чтобы разделить вычислительную систему между многими программами, выполняющими непредсказуемые запросы на ресурсы. Главное внимание разработчика поэтому должно быть направлено на алгоритмы выделения ресурсов (планирования) для ресурсов различных видов (оперативная память, память на магнитных барабанах, магнитные ленты, консоли и т.д.). Чтобы упростить свою задачу, он может попробовать конструировать отдельные планировщики для каждого класса ресурса. Каждый планировщик будет состоять некоторого количества локальной управленческой информации, вместе с некоторыми процедурами и функциями, которые вызываются программами, желающими получить и освободить ресурсы. Такое собрание связанных данных и процедур известно как монитор; и соответствующая ему система обозначений может быть основана на нотации класса языка SIMULA67 [6].

monitorname: monitor
  begin ... объявление данных, локальных в мониторе;
    procedure procname ( формальные параметры ...); 
      begin ... тело процедуры ... end;
      ... объявления других процедур, локальных в мониторе;
      ... инициализация локальных данных монитора ...
end;

Заметьте, что в теле процедуры могут быть локальные данные, это обычный прием.

Чтобы вызывать процедуру монитора, необходимо задать имя монитора и имя требуемой процедуры, разделяя их точкой:

monitorname.procname(... фактические параметры ...);

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

monitor 1, monitor 2: classname;

Структура класса мониторов идентична описанной для представления данных в [13], за исключением добавления ключевого монитора слова class. Brinch-Hansen использует для той же цели слово shared [3].

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

Любая программа, динамически выделяющая ресурс, иногда должна задерживать программу, желающую получить ресурс, который в настоящее время недоступен, и возобновлять эту программу после того, как некоторая другая программа освободит данный ресурс. Мы поэтому нуждаемся в операции "wait", вызываемой изнутри процедуры монитора, которая заставит вызывающую программу быть задержанной; и в операции "signal", также вызываемой изнутри процедуры того же монитора, которая заставит только одну из ожидающих программ немедленно возобновиться. Если нет ожидающих программ, сигнал не имеет никакого эффекта. Чтобы давать возможность другим программам освободить ресурсы в течение ожидания, операция wait должна оставить возможность прерывания, иначе это предотвратило бы вход в процедуру освобождения. Однако мы устанавливаем что за операцией signal должно немедленно следовать возобновление ожидающей программы, без возможности вмешательства вызова процедуры от третьей программы. Это - единственный способ гарантировать для ожидающей программы, что она сможет получить ресурс, только что освобожденный сигнализирующей программой без риска, что третья программа вклинится в монитор и захватит ресурс вместо нее.

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

condvariable.wait; 
condvariable.signal;

Заметим, что "переменная"-условие не является ни истиной, ни ложью; она на самом деле не имеет никакого сохраняемого значения, доступного для программы. Практически, переменная условия будет представлена очередью процессов (первоначально пустой), которые в настоящее время ожидают на условии; но эта очередь невидима ни для ожидающих, ни для сигнализирующих. Такой вид переменной условия преднамеренно сохраняется настолько примитивным и элементарным насколько возможно, для того, чтобы она могло быть эффективно реализована и гибко использована и позволяла достичь широкого спектра результатов. Имеется большое искушение, ввести более комплексный примитив синхронизации, который может быть более легким для использования во многих задачах. Но мы будем некоторое время сопротивляться этому искушению.

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

procedure acquire; 
procedure release;

Переменная (1)

busy: Boolean

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

nonbusy:condition

которая сигнализирует об очередном освобождении ресурса. Начальное значение busy - false. Проектное решение приводит к следующему коду монитора:

single resource:monitor 
begin busy:Boolean; 
     nonbusy:condition;
  procedure acquire; 
     begin if busy then nonbusy.wait;
              busy := true
     end; 
  procedure release; 
     begin busy := false; 
           nonbusy.signal
     end;
  busy := false; 
  comment начальное значение;
end single resource;

Замечания

  1. В проектировании монитора, представляется естественным проектировать заголовки процедур, данные, условия и тела процедур именно в таком порядке. Все последующие примеры будут разрабатываться именно таким путем.
  2. Процедура, получающая ресурс, не должна повторно проверять, что busy имеет значение false, когда она возобновляется после ожидания, так как процедура освобождения гарантирует это; и, как упомянуто выше, никакая другая программа не может вмешаться между сигналом и продолжением только одной ожидавшей программы.
  3. Если более одной программы ожидают на условии, мы постулируем что, операция signal восстановит программу, ожидающую дольше всех. Это дает простую нейтральную дисциплину обслуживания очереди, при который каждая ожидающая программа в конечном счете получит обслуживание.
  4. Единственный монитор ресурса моделирует булев семафор [7] с операциями acquire и release, используемыми как P и V соответственно. Это - простое доказательство, того что концепции монитора / условия в принципе не менее мощны чем семафоры, и для что они могут использоваться в цех же целях.
  5. Как и в PASCAL [15], объявление переменной имеет вид: <идентификатор переменной>: <тип>;

ОглавлениеВперед
КаталогИндекс раздела