Семафоры Дейкстры

Тип данных, именуемый семафором. Семафор представляет собой переменную целого типа S, над которой определены две операции: down(s) (или P(S)) и up(S) (или V(S)). Оригинальные обозначения P и V, данные Дейкстрой и получившие широкое распространение в литературе, являются сокращениями голландских слов proberen – проверить и verhogen – увеличить.

down(S) проверяет значение семафора, и если оно больше нуля, то уменьшает его на 1. Если же это не так, процесс блокируется, причем операция down считается незавершенной.

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

up(S) увеличивает значение семафора на 1. При этом, если в системе присутствуют процессы, блокированные ранее при выполнении down на этом семафоре, ОС разблокирует один из них с тем, чтобы он завершил выполнение операции down, т. е. вновь уменьшил значение семафора.

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

Семафоры – это низкоуровневые средства синхронизации, для корректной практической реализации которых необходимо наличие специальных, атомарных семафорных машинных команд.

Для использования двоичного семафора требуется поддержка со стороны ОС, т.к. операции up и down должны быть атомарными.

Пример.

Представим себе супермаркет, посетители которого прежде чем войти в торговый зал должны обязательно взять себе инвентарную тележку. В момент открытия магазина на входе имеется N свободных тележек – это начальное значение семафора. Каждый посетитель забирает одну из тележек (уменьшая тем самым количество оставшихся на 1) и проходит в торговый зал – это аналог операции down. При выходе посетитель возвращает тележку на место, увеличивая количество тележек на 1 – это аналог операции up. Теперь представим себе, что очередной посетитель обнаруживает, что свободных тележек нет – он вынужден блокироваться на входе в ожидании появления тележки. Когда один из посетителей, находящихся в торговом зале, покидает его, посетитель, ожидающий тележку, разблокируется, забирает тележку и проходит в зал. Таким образом, наш семафор в виде тележек позволяет находиться в торговом зале (аналоге критической секции) не более чем N посетителям одновременно. Положив N=1, получим реализацию взаимного исключения. Семафор, начальное (и максимальное) значение которого равно 1, называется двоичным семафором (т. к. имеет только 2 состояния: 0 и 1).

Использование двоичного семафора для организации взаимного исключения проиллюстрировано на рисунке.

Здесь мы видим условную переменную типа int – она здесь семафор, но на самом деле она не int, а типа данных семафор. Значит каждый из процессов, перед тем как работать с критическим ресурсом, т.е. перед тем как войти в свою критическую секцию делает операцию down() на семафор (семафор для всех один и тот же) и на выходе из своей критической секции он делает операцию up(). Представьте себе, что процесс 1 подошел к своей критической секции в то время, как семафор свободен (ресурс свободен). Он выполняет операцию down(), тем самым значение семафора становится равным 0 (т.к. вначале было равно 1), и процесс 1 получает возможность работать в своей критической секции. Если в этот момент процесс 2 захочет попасть в свою критическую секцию, т.е. тоже поработать с нашим ресурсом, то при попытке выполнить операцию down() он будет заблокирован, поскольку значение семафора 0 и уменьшиться оно уже не может. Соответственно он будет ожидать до тех пор, пока процесс 1 не выйдет из своей критической секции, после чего процесс 2 будет автоматически разблокирован в тот момент, когда процесс 1 выполнит up(), и тем самым попадет в свою критическую секцию. Понятно, что это реализует взаимное исключение.

Семафоры – это мощное средство синхронизации, но проблемы с ними тоже есть, потому что при написании программ с использованием семафоров велика вероятность возникновения ошибок (т.е. средство достаточно низкоуровневое), т.к. достаточно в одном месте перепутать местами down() и up() или поставить не в том месте down(), не в том месте up(), и получается ситуация тупика. Кроме того, семафоры являются средством, которое требует поддержки со стороны ОС. Это выражается в том, что операции down() и up() должны быть атомарными, т.е. не должно происходить переключение контекстов. Иначе возможно, что в том момент, когда процесс проверил состояние семафора, но еще не изменил его значение, в этот момент произойдет переключение контекста, другой процесс изменит значение семафора, а 1-й процесс об этом уже не узнает и будет считать, что он прав и пойдет в свою критическую секцию, в то время как там уже находится другой процесс, поэтому требование атомарности оно принципиально важно. А раз говорится о том, что должно быть запрещено переключение контекстов, это требует естественно поддержки со стороны ОС.