Двоичные семафоры Дейкстры
Совершенно иным образом подошел к проблеме взаимного исключения великий голландский ученый Э.Дейкстра (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 был открыт.