Двоичные семафоры Дейкстры

Совершенно иным образом подошел к проблеме взаимного исключения великий голландский ученый Э.Дейкстра (E.Dijkstra, 1966). Он предложил использовать новый вид программных объектов — семафоры. Здесь мы рассмотрим их простейший вариант — двоичные семафоры, они же мьютексы (mutex, от слов MUTual EXclusion — взаимное исключение).

Двоичным семафором называется переменная S, которая может принимать значения 0 и 1 и для которой определены только две операции.

 P(S) — операция занятия (закрытия) семафора. Она ожидает, пока значение S не станет равным 1, и, как только это случится, присваивает S значение 0 и завершает свое выполнение. Очень важно: операция P по определениюнеделима, т.е. между проверкой и присваиванием не может вклиниться другой процесс, который бы изменил значение S.

 V(S) — операция освобождения (открытия) семафора. Она просто присваивает S значение 0.

Чем переменная-семафор отличается от обычной булевой переменной? Тем, что для нее недопустимы никакие иные операции, кроме P и V. Нельзя написать в программе S:=1 или if(S)then..., если S определена как семафор.

Чем операция P отличается от варианта с проверкой и присваиванием, который мы выше признали неудовлетворительным? Неделимостью. Но это «по определению», а как на практике добиться этой неделимости? Это отдельный, вполне решаемый вопрос.

Заслуга Дейкстры как раз в том, что он разделил проблему взаимного исключения на две независимые проблемы разных уровней:

 на уровне реализации: как обеспечить работу семафоров в соответствии с их определением;

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

Решать эти две задачи по отдельности легче, чем обе вместе, при этом решать их обычно должны разные люди: первую — разработчики ОС, а вторую — разработчики прикладной программы.

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

Системная функция P(S) должна проверить, свободен ли семафор S. Если свободен (S = 1), то система занимает его (S:= 0) и на этом функция завершается. Если же семафор занят, то система блокирует процесс, вызвавший функцию P, и запоминает, что этот процесс блокирован по ожиданию освобождения семафора S. Таким образом, при реализации семафоров удается избежать активного ожидания.

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

Системная функция V(S) — это, конечно, не просто присваивание S:= 1. Кроме этого, система должна проверить, нет ли среди спящих процессов такого, который ожидает освобождения семафора S. Если такой процесс найдется, система разблокирует его, а переменная S в этом случае сохраняет значение 0 (семафор снова занят, теперь уже другим процессом).

Может ли случиться так, что несколько спящих процессов ждут освобождения одного и того же семафора? Да, так вполне может быть. Какой из этих процессов должен быть разбужен системой? С точки зрения корректности работы и соответствия определениям функций P и V — любой, но только один. С точки зрения эффективности работы — вероятно, надо разбудить самый приоритетный процесс, а в случае равенства приоритетов… ну, видимо, тот, который спит дольше.

Теперь, когда мы разобрались с реализацией семафоров, можно о ней забыть^[9] и помнить только, что семафоры существуют и могут быть использованы при необходимости.

Рассмотрим теперь вторую половину задачи — использование семафоров для управления взаимодействием процессов. Как можно реализовать корректную работу процессов с критическими секциями, если использовать двоичный семафор? Да очень просто.

Процесс A:	Процесс B:
... P(S);

 

(критическая секция A)

V(S);

...

...

P(S);

(критическая секция B)

V(S);

...

И все. Сложности ушли в реализацию семафоров. Надо только проследить, чтобы до начала работы процессов семафор S был открыт.