СЕМАФОРЫ

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

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

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

Эта запись означает следующее:

- при выполнении операции P над семафором S сначала проверяется его значение. Если оно больше 0, то из S вычитается 1.

Если оно меньше или равно 0, то процесс блокируется до тех пор, пока S не станет больше 0, после чего из S вычитается 1. Успешная проверка и уменьшение являются неделимой операцией.

- при выполнении операции V над семафором S к его значению просто прибавляется 1. Во время выполнения этой операции к переменной S нет доступа другим потокам.

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

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

Например. Пусть буферный пул состоит из N буферов, каждый из которых может содержать одну запись.

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

Для правильной совместной работы поток-производитель должен приостанавливаться, когда все буферы оказываются занятыми, и активизироваться при освобождении хотя бы одного буфера. Напротив, поток-потребитель должен приостанавливаться, когда все буферы пусты, и активизироваться при появлении хоти бы одной записи.

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

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

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

Семафор может находиться в сигнальном или несигнальном состоянии. ............