Семафоры

5.

4.

3.

2.

1.

СИНХРОНИЗАЦИЯ ПОТОКОВ В ПОЛЬЗОВАТЕЛЬСКОМ РЕЖИМЕ

5.

4.

3.

2.

1.

Одним из первых механизмов, предложенных для синхронизации поведения процессов, стали семафоры, концепцию которых описал Дейкстра (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. Тогда работа потоков с общим буферным пулом может быть описана следующим образом (рис.2). Поток-производитель прежде всего выполняет операцию Р(е), с помощью которой он проверяет, имеются ли в буферном пуле незаполненные буферы. В соответствии с семантикой операции Р, если семафор е равен 0 (т.е. свободных буферов в данный момент нет), то поток-производитель переходит в состояние ожидания. Если же значением е является положительное число, то он уменьшает число свободных буферов, записывает данные в очередной свободный буфер и после этого наращивает число занятых буферов операцией V(f). Поток-потребитель действует аналогичным образом, с той разницей, что он начинает работу с проверки наличия заполненных буферов, а после чтения данных наращивает количество свободных буферов.

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