Семафоры

Семафор – это переменная специального типа, над которой определены две операции – закрытие семафора ( P) и открытие семафора (V). Обобщ¨нный смысл операции Р состоит в декрементации числового поля семафора и в проверке значения этого поля семафора. Если это значение оказывается меньше некоторой величины (чаще всего нуля), процесс, вызвавший данную операцию блокируется и помещается в очередь к семафору.. В противном случае процесс продолжает сво¨ выполнение. Операция V связана с инкрементацией числового поля семафора. При этом, если выполняется некоторое условие, один из ранее заблокированных процессов деблокируется, т. е. покидает очередь к семафору и переходит в состояние готовности. Обычно семафор логически связывается с некоторым критическим ресурсом. Поэтому заблокированные процессы, находящиеся в очереди к семафору, косвенно ожидают доступа к критическому ресурсу.

Операции P и V являются неделимыми операциями, т. е. их выполнение не может прерываться. Действия по блокированию и деблокированию процессов реализуют  модули из состава ядра ОС.

Допустимыми значениями числовых полей семафоров являются целые числа. Различают два вида семафоров – числовые и двоичные. Числовые семафоры – это семафоры, числовые поля которых могут принимать  любые целые значения в некотором  заданном диапазоне. Двоичные семафоры – это семафоры, числовые поля которых  могут принимать только два значения : единица и ноль. Существуют различные реализации семафорных примитивов. Они отличаются друг от друга по различным параметрам ( тип семафоров, диапазон изменения значений числовых полей семафоров, логика операций, дисциплина выбора процесса при его деблокировании и т. д.). Рассмотрим некоторые алгоритмы работы семафорных примитивов. Сначала представим вариант алгоритма реализации операций P и V для числовых семафоров:

P(S): S:=S-1;

If S<0 then <заблокировать процесс, и поместить

его в очередь  к семафору>

V(S): S:=S+1;

If S<=0 then <деблокировать один из ранее заблокированных

процессов>

Алгоритм работы семафорных примитивов P и V для двоичных семаров может выглядеть следующим образом:

P(S): if S=1 then S:=0

Else

Begin

L:=L+1;

<заблокировать  процесс>;

End;  

V(S): if (S=0) and (L>0) then

Begin

<деблокировать  один из процессов>;

L:=L-1;

If L=0 then S:=1;

End;

Здесь L – длина  очереди заблокированных процессов.

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

Var s: semaphor;

Begin s:=1;

Parbegin

P1: while true do begin

… P(s); CS1; V(s); …

end;

and

P2: while true do begin

… P(s); CS2; V(s); …

end;

parend

end.

Предположим, что  первым начн¨т выполняться процесс Р1. Прежде чем войти в свой критический интервал (CS1), он вызовет операцию P(s). После е¨ выполнения значение числового поля семафора станет равным нулю, но Р1 войд¨т в свой критический интервал. Если в этот момент процесс Р2 получит управление и захочет войти в свой критический интервал (CS2), он сначала вызовет выполнение операции P(s) и заблокируется по семафору s. Если через некоторое время процесс Р1 опять получит управление и выполнит свой критический интервал до конца, а также вызовет операцию V(s), процесс Р2 деблокируется и сможет войти в свой критический интервал. Задача взаимного исключения будет решена, так как только один из двух процессов будет находиться в сво¨м критическом интервале.

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