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

Семафор – переменная специального типа, которая доступна параллельным процессам для проведения над ней только двух операций: «закрытии» и «открытия», названных соответственно P - и V -операциями. Эти операции являются примитивами относительно семафора, который указывается в качестве параметра операции. Здесь семафор выполняет роль вспомогательного критического ресурса, так как операции P и V неделимы при своем выполнении и взаимно исключают друг друга.

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

В настоящее время используют много различных семафорных механизмов. Варьируемыми параметрами, которые отличают различные виды примитивов, являются:

· начальное значение и диапазон изменения значений семафора;

· логика действий семафорных операций;

· количество семафоров, доступных для обработки при исполнении отдельного примитива.

Обобщенный смысл примитива P(S) состоит в проверке текущего значения семафора S (P – от голландского P roberen – проверить), и если оно не меньше нуля, то осуществляется переход к следующей за примитивом операции. В противном случае процесс снимается на некоторое время с выполнения и переводится в состояние «пассивного ожидания». Находясь в списке заблокированных, ожидающий процесс не проверяет семафор непрерывно, как в случае активного ожидания.

Операция V(S) связана с увеличением значения семафора на единицу (V – от голландского V erhogen – увеличить) и переводом одного или нескольких процессов в состояние готовности к центральному процессору.

Операции P и V выполняются операционной системой в ответ на запрос, выданный некоторым процессом и содержащий имя семафора в качестве параметра.

Допустимыми значениями семафора являются только целые числа. Двоичным семафором называют семафор, максимальное значение которого равно единице. В противном случае семафоры называют N-ичными.

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

1) семафор имеет начальное значение, равное 1. Если процессы CS ₁ и CS ₂ попытаются одновременно выполнить примитив P(S), то это удастся сделать только одному из них. Пусть это будет CS ₂:

2) процесс CS ₂ закрывает семафор S (выполняет операцию P(S)) и выполняет свой критический интервал. Процесс CS ₁ будет заблокирован на семафоре S. Тем самым гарантируется взаимное исключение;

3) после выполнения примитива V(S) процессом CS ₂ семафор S открывается, указывая на возможность захвата каким-либо процессом освободившегося критического ресурса. При этом производится перевод процесса CS ₁ из заблокированного состояния в состояние готовности.