Семафор Дейкстры. Семафоры и прерывания.
Но когда ты проспишься, скрой свой испуг,
Это был не призрак, эти был только звук.
Это тронулся поезд, на который ты не попадешь.
Б. Гребенщиков
Семафор Дейкстры представляет собой целочисленную переменную, с которой ассоциирована очередь ожидающих нитей. Пытаясь пройти через сема-Фор, нить пытается вычесть из значения переменной 1. Если значение переменной больше или равно 1, нить проходит сквозь семафор успешно (семафор открыт). Если переменная равна нулю (семафор закрыт), нить останавливается и ставится в очередь.
Закрытие семафора соответствует захвату объекта или ресурса, доступ к которому контролируется этим семафором. Если объект захвачен, остальные нити вынуждены ждать его освобождения. Закончив работу с объектом (выйдя из критической секции), нить увеличивает значение семафора на единицу, открывая его. При этом первая из стоявших в очереди нитей активизируется и вычитает из значения семафора единицу, снова закрывая семафор.
Если же очередь была пуста, то ничего не происходит, просто семафор остается открытым. Тогда первая нить, подошедшая к семафору, успешно пройдет через него. Это действительно похоже на работу железнодорожного семафора, контролирующего движение поездов по одноколейной ветке (рис. 7.6)
Рис. 7.6. Железнодорожный семафор
Наиболее простым случаем семафора является двоичный семафор. Начальное значение флаговой переменной такого семафора равно 1, и вообще она может принимать только значения 1 и 0. Двоичный семафор соответствует случаю, когда с разделяемым ресурсом в каждый момент времени может работать только одна нить.
Семафоры общего вида могут принимать любые неотрицательные значения. В современной литературе такие семафоры называют семафорами-счетчиками (counting semaphore). Это соответствует случаю, когда несколько нитей могут работать с объектом одновременно, или когда объект состоит из нескольких независимых, но равноценных частей – например, несколько одинаковых принтеров. При работе с такими семафорами часто разрешают процессам вычитать и добавлять к флаговой переменной значения, большие единицы. Это соответствует захвату/освобождению нескольких частей ресурса.
Многие системы предоставляют также сервисы, позволяющие просмотреть состояние семафора без его изменения и произвести "неблокируюшуюся" форму захвата, которая возвращает ошибку в ситуации, когда нормальный захват семафора привел бы к блокировке. Теоретики не очень любят такие примитивы, но при разработке сложных сценариев взаимодействия с участием многих семафоров они бывают полезны.
Во многих современных книгах и операционных системах семафорами называются только семафоры общего вида, двоичные же семафоры носят более краткое и выразительное имя мутекс (mutex – от MUTual EXclusion, взаимное исключение). Проследить генезис этого названия автору не удалось, но можно с уверенностью сказать, что оно вошло в широкое употребление не ранее конца 80-х. Так, в разрабатывавшейся в середине 80-х годов OS/2 1.0, двоичные семафоры еще называются семафорами, а в Win32, разработка которой происходила в начале 90-х, уже появляется название mutex. Операции над мутексом называются захватом (acquire) (соответствует входу в критическую секцию) и освобождением (release) (соответствует выходу из нее).
Многие ОС предоставляют для синхронизации семафоры Дейкстры или похожие на них механизмы.
Флаги событий в RSX-11 и VMS
Так, например, в системах RSX-11 и VMS основным средством синхронизации являются флаги событий (event flags). Процессы и система могут очищать (clear) или взводить (set) эти флаги. Флаги делятся на локальные и глобальные. Локальные флаги используются для взаимодействия между процессом и ядром системы, глобальные – между процессами. Процесс может остановиться, ожидая установки определенного флага, поэтому флаги во многих ситуациях можно использовать вместо двоичных семафоров. Кроме того, процесс может связать с флагом события процедуру-обработчик AST (Asynchronous System Trap – асинхронно [вызываемый] системный обработчик).
AST во многом напоминают сигналы или аппаратные прерывания. В частности, флаги событий используются для синхронизации пользовательской программы с асинхронным исполнением запросов на ввод-вывод. Исполняя запрос, программа задает локальный флаг события. Затем она может остановиться, ожидая этого флага, который будет взведен после исполнения запроса. При этом мы получаем псевдосинхронный ввод-вывод, напоминающий синхронные операции чтения/записи в UNIX и MS DOS.
Но программа может и не останавливаться! При этом запрос будет исполняться параллельно с исполнением самой программы, и она будет оповещена о завершении операции соответствующей процедурой AST.
Асинхронный ввод-вывод часто жизненно необходим в программах реального времени, но бывает полезен и в других случаях.
Семафоры и прерывания
Большинство современных ОС предоставляют сервисы, позволяющие без вреда для остальной системы приостановить и возобновить исполнение пользовательской нити. Однако мало какая ОС предоставляет такой же сервис для обработчиков прерываний. Поэтому если ОС и разрешает использование примитивов синхронизации из прерываний, то всегда с условием, что такое использование не может приводить к блокировке обработчика.
Например, если для синхронизации используется мутекс, обработчик прерывания не может его устанавливать, а может только снимать. Это требование накладывает определенные ограничения на стиль использования семафоров. Если при синхронизации равноправных нитей каждая из них устанавливает семафор в начале критической секции и снимает его в конце, используя его и для взаимоисключения, и для синхронизации, то при взаимодействии нити с обработчиком прерывания для реализации взаимоисключения приходится использовать запрет прерываний, а мутекс – только для синхронизации.
Стандартная техника использования мутекса в обработчике прерывания состоит в следующем (порядок операций важен!): процесс захватывает мутекс, инициирует операцию на устройстве, которая должна завершиться прерыванием, и захватывает мутекс еще раз. Если к этому моменту прерывание уже произошло, мутекс будет свободен и процесс ничего не будет ждать. Если же прерывания еще не происходило, процесс заснет, ожидая его. Обработчик же прерывания только снимает мутекс.