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

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

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

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

- : уменьшение на 1, если это возможно. Если и невозможно уменьшить , оставаясь в области целых неотрицательных значений, то в этом случае поток, вызывающий операцию , ждет, пока это уменьшение станет возможным. Успешная проверка и уменьшение также являются неделимой операцией.

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

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

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

Введем два семафора: - число пустых буферов, и - число заполненных буферов, причем в исходном состоянии , а . Работа потоков с общим буферным пулом может быть описана следующим образом (рисунок 5.4).

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

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

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

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