2. Интерпретация

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

Очевидно, что нам потребуется для каждого монитора булев семафор "mutex", чтобы гарантировать, что тела локальных процедур исключают друг друга. Семафор инициализирован значением 1; операция P(mutex) должна выполняться на входе в каждую локальную процедуру, и операция V(mutex) - на выходе из нее.

Когда процесс сигнализирует об условии, на котором другой процесс ожидает, сигнализирующий процесс должен ждать, пока восстановленный процесс разрешит ему продолжиться. Мы поэтому вводим для каждого монитора второй семафор "urgent" (инициализированный значением 0), на котором сигнализирующий процесс задерживается операцией P(urgent). Перед разрешением прерывания каждый процесс должен проверить, нет ли другого процесса, ожидающего на urgent, и, если так, должен освободить его вместо выполнения операции V(urgent). Мы поэтому должны подсчитывать число процессов, ожидающих на urgent, в целой переменной "urgentcount" (с начальным значением - 0). Так им образом, каждый выход из процедуры монитора должен кодироваться так:

if urgentcount > 0 then V(urgent) else V(mutex) 

Наконец, для каждого условия, локального в мониторе, мы вводим семафор "condsem" (инициализированный значением 0), на котором процесс, желающий ждать, задерживается операцией P(condsem). Так как процесс, сигнализирующий об этом условии должен знать, ожидает ли на нем кто-либо, нам также нужно подсчитывать число ждущих процессов, в целой переменной "condcount" (первоначально - 0). Операция "cond.wait" может теперь быть реализована следующим образом (вспомните, что ожидающая программа должна разрешить прерывание перед приостановкой):

condocunt := condcount + 1;
if urgentcount > 0 then V(urgent) else V(mutex);
P(condsem);
comment Здесь всегда будет ожидание;
condcount := condcount - 1

Операция signal может быть представлена таким кодом:

urgentcount := urgentcount + 1;
if condcount > 0 then {V(condsem); P(urgent) }; 
urgentcount := urgentcount - 1;

В этой реализации, владение монитором представлено как привилегия, которая явно передается от одного процесса другому. Только, когда никто более не хочет претендует на эту привилегию, - mutex наконец освобождается.

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

1. Когда тело процедуры монитора не содержит wait или signal, выход из процедуры может быть закодирован простой операцией V(mutex), так как urgentcount не может измениться в ходе выполнения процедуры.
2. Если cond.signal - последняя операция в теле процедуры, она может быть объединена с выходом из монитора следующим образом:

   if condcount > 0 then V(condsem) 
   else if urgentcount > 0 then V(urgent) 
                           else V(mutex)
   

3. Если не имеется других wait или signal в теле процедуры, вторая строка в приведенном выше коде, также может быть опущена.
4. Если каждый сигнал является последней операцией в теле процедуры, переменные urgentcount и urgent могут быть опущены, вместе со всеми действиями над ними. Это подобно упрощению, которое предлагает O-J. Dahl, - чтобы signal всегда был последней операцией процедуры монитора; фактически, это ограничение - очень естественное, оно невольно соблюдалось во всех примерах этой статьи.

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

1. urgentcount и condcount могут быть отменены, так как тот факт, что кто-то ожидает, может быть установлен проверкой значения семафора, которое не может измениться незаметно в пределах непрерываемого режима.
2. Многие мониторы очень коротки и не содержат вызовов других мониторов. Такие мониторы могут быть выполнены полностью в непрерываемом режиме, с использованием, как и ранее, общего механизма прерываний, обеспечиваемого аппаратными средствами. Во многих случаях это будет занимать меньше времени в непрерываемом режиме, чем установление отдельного исключения для каждого монитора.

Я благодарен J. Bezivin, J. Horning, и R.M. McKeag для помощи в нахождении этого алгоритма.