Семафоры. Обобщением блокирующих переменных являются так называемые семафоры Дийкстры

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

Для работы с семафорами вводятся два примитива, традиционно обозначаемых Р и V. Пусть переменная S представляет собой семафор. Тогда действия V(S) и P(S) определяются следующим образом.

* V(S): переменная S увеличивается на 1 единым действием. Выборка, наращи­вание и запоминание не могут быть прерваны. К переменной S нет доступа другим потокам во время выполнения этой операции.

* P(S): уменьшение S на 1, если это возможно. Если 5=0 и невозможно умень­шить S, оставаясь в области целых неотрицательных значений, то в этом случае поток, вызывающий операцию Р, ждет, пока это уменьшение станет возможным. Успешная проверка и уменьшение также являются неделимой операцией.

Никакие прерывания во время выполнения примитивов V и Р недопустимы.

В частном случае, когда семафор S может принимать только значения 0 и 1, он превращается в блокирующую переменную, которую по этой причине часто на­зывают двоичным семафором. Операция Р заключает в себе потенциальную воз­можность перехода потока, который ее выполняет, в состояние ожидания, в то время как операция V может при некоторых обстоятельствах активизировать дру­гой поток, приостановленный операцией Р.

Рассмотрим использование семафоров на классическом примере взаимодействия двух выполняющихся в режиме мультипрограммирования потоков, один из ко­торых пишет данные в буферный пул, а другой считывает их из буферного пула. Пусть буферный пул состоит из N буферов, каждый из которых может содержать одну запись. В общем случае поток-писатель и поток-читатель могут иметь раз­личные скорости и обращаться к буферному пулу с переменой интенсивностью. В один период скорость записи может превышать скорость чтения, в другой — наоборот. Для правильной совместной работы поток-писатель должен приоста­навливаться, когда все буферы оказываются занятыми, и активизироваться при освобождении хотя бы одного буфера. Напротив, поток-читатель должен приос­танавливаться, когда все буферы пусты, и активизироваться при появлении хотя бы одной записи.

Введем два семафора: е — число пустых буферов, и f — число заполненных буфе­ров, причем в исходном состоянии е = N, a f = 0. Тогда работа потоков с общим буферным пулом может быть описана следующим образом (рис. 4.20).

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

Рис. 4.20. Использование семафоров для синхронизации потоков

В данном случае предпочтительнее использовать семафоры вместо блокирующих переменных. Действительно, критическим ресурсом здесь является буферный пул, который может быть представлен как набор идентичных ресурсов — отдель­ных буферов, а значит, с буферным пулом могут работать сразу несколько пото­ков, и именно столько, сколько буферов в нем содержится. Использование дво­ичной переменной не позволяет организовать доступ к критическому ресурсу более чем одному потоку. Семафор же решает задачу синхронизации более гиб­ко, допуская к разделяемому пулу ресурсов заданное количество потоков. Так, в нашем примере с буферным пулом могут работать максимум N потоков, часть из которых может быть «писателями», а часть — «читателями».

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

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

Рис. 4.21. Использование двоичного семафора