Семафорные примитивы Дейкстры

4.6 Семафорные примитивы Дейкстры.

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

Концепция

Определение 4.11. Семафор – это переменная специального типа, доступная параллельным процессам для проведения над ней только двух операций – «закрытия» и «открытия», названных соответственно Р-операцией (P – от голландского Proberen – проверить) и V-операцией (V – от голландского Verhogen – увеличить).

Эти операции неделимы и являются примитивами относительно семафора, который указывается в качестве параметра операций. 

Классическое определение этих операций выглядит следующим образом:

операция P(S):
пока S == 0 процесс блокируется;
S = S – 1;

операция V(S)
S = S + 1;

Эта запись означает следующее: при выполнении операции P над семафором S сначала проверяется его значение. Если оно больше 0, то из S вычитается 1. Если оно меньше или равно 0, то процесс блокируется до тех пор, пока S не станет больше 0, после чего из S вычитается 1. При выполнении операции V над семафором S к его значению просто прибавляется 1. В момент создания семафор может быть инициализирован любым неотрицательным значением.

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

Семафоры широко используются для синхронизации и взаимоисключения процессов.

Ссылки:
Intuit
Wikipedia