5. Планируемое ожидание

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

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

busy.wait (p);

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

Это введение "планируемого ожидания" уступает искушению сделать понятие условия более сложным. Основные оправдания этому следующие:

1. Оно не оказывает никакого влияния на логику программы или на правила формального доказательства. Любая программа, которая работает без планируемого ожидания, будет работать и с ним, но, возможно, с лучшими временными характеристиками.
2. Автоматическое упорядочение очереди ждущих процессов - простая и быстрая методика планирования, кроме тех случаев, когда очередь является слишком длинной, а даже если это и так, то время центрального процессора не является слишком критическим ресурсом.
3. Максимальный объем требуемой памяти - одно слово на каждый процесс. Без такого встроенного метода планирования, каждому монитору, вероятно, придется выделять память пропорционально числу пользователей; альтернатива динамического выделения памяти малыми порциями непривлекательна на низком уровне операционной системы, где находятся мониторы.

Я поддамся еще одному искушению и введу булеву функцию условия:

condname.queue

которая выдает значение true, если кто-либо ожидает на condname и false - в противном случае. Очевидно, что она может быть легко реализована парой команд, и предоставляет ценную информацию, которая иначе могла бы быть получена только за счет дополнительной памяти, времени и хлопот.

Тривиально простой пример - монитор alarmclock, который дает возможность вызывающей программе задержаться на заданное количество - n - "тиков". Он имеет два входа:

procedure wakeme(n:inleger);
procodure tick;

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

now:integer;

которая подсчитывает текущее временя (первоначально - 0) и

wakeup :condition

на котором ждут "спящие" программы. Но значение alarmsetting - времени, в которое эти программы будут разбужены, известно при старте ожидания; и оно может использоваться для определения правильной последовательности пробуждения.

alarmclock:monitor
begin now:integer;     
      wakeup:condition;
  procedure wakeme(n:integer);
    begin alarmsetting:integer;
      alarmsetting := now + n;
      while now < alarmsetting do wakeup.wait(alarmsetting);
      wakeup.signal;
      comment В случае, если следующий процесс должен пробудиться в то же самое время;
    end;
  procedure tick;
    begin now := now + 1;
      wakeup.signal    
    end;
  now := 0;
end alarmclock;

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

Я благодарен A. Ballard и J. Horning за постановку этой проблемы.