18. Семафорные примитивы Дейкстры. Задача взаимного исключения.

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

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

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

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

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

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

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

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

процессов>

Алгоритм работы семафорных примитивов 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 деблокируется и сможет войти в свой критический интервал. Задача взаимного исключения будет решена, так как только один из двух процессов будет находиться в своём критическом интервале.

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