Семафоры


Концепция использования семафоров для реализации взаимоисключений предложена Дейкстрой3.
Семафор или общий семафор (semaphore) — это целая переменная, значение которой можно опрашивать и менять только при помощи специальных неделимых (как команда testandset) операций P и V. Эти операции являются примитивами относительно семафора, который указывается в качестве параметра операций. Здесь семафор выполняет роль вспомогательного критического ресурса, т.к. операции P и V неделимы при своем выполнении и взаимно исключают друг друга.
Двоичный семафор может принимать только значения 0 или 1. Считающий семафор может принимать целые неотрицательные значения.
Операция Р над семафором S записывается как P(S), алгоритм ее выполнения следующий:
if S>0 then S:=S-1 else <ожидать на S>

Операция V над семафором S , V(S), имеет следующий алгоритм выполнения:
if <один или несколько процессов ожидают на S>
then <разрешить одному из этих процессов продолжить работу>
else S:=S+1
Семафорный механизм работает по схеме, в которой сначала исследуется состояние критического ресурса, идентифицируемое значением семафора, а затем уже осуществляется допуск к критическому ресурсу или отказ от него не некоторое время. При отказе доступа к критическому ресурсу используется режим «пассивного ожидания». Поэтому в состав механизма включаются средства формирования и обслуживания очереди ожидающих процессов. Эти средства реализуются супервизором ОС. Из-за взаимного исключения примитивов попытка в различных параллельных процессах одновременно выполнить примитив над одним и тем же семафором приведет к тому, что она будет успешной только для одного процесса. Все остальные процессы будут взаимно исключены на время выполнения примитива. Основным достоинством использования семафорных операций является отсутствие состояния «активного ожидания», что может повысить эффективность работы мультипрограммной вычислительной системы. Заметим, также, что семафоры и операции над ними могут быть реализованы как программно, так и аппаратно, как правило, они реализуются в ядре.
Обобщенный смысл примитива P(S) состоит в проверке текущего значения семафора S, и если оно не меньше нуля, то осуществляется переход к следующей за примитивом операции. В противном случае процесс снимается на некоторое время с выполнения и переводится в состояние «пассивного ожидания». Находясь в списке заблокированных, ожидающий процесс не проверяет семафор непрерывно, как в случае активного ожидания. Вместо него на процессоре может исполняться другой процесс, который реально совершает полезную работу.
Операция V(S) связана с увеличением значения семафора на единицу и переводом одного или нескольких процессов в состояние готовности к ЦП.
Операции P и V выполняются ОС в ответ на запрос, выданный некоторым процессом и содержащий имя семафора в качестве параметра.

Рассмотрим на примере двух конкурирующих процессов1 и 2 использование данных семафорных примитивов для решения проблемы критического интервала. Семафор S имеет начальное значение, равное 1. если процессы1 и 2 попытаются одновременно выполнить примитив P(S), то это удастся успешно сделать только одному из них. Пусть это сделал процесс2, тогда он закрывает семафор S, после чего выполняется критический интервал. Процесс1 в рассматриваемой ситуации будет заблокирован на семафоре S, тем самым будет гарантировано взаимное исключение.
После выполнения примитива V(S) процессом2 семафор S открывается, указывая на возможность захвата каким-либо процессом освободившегося критического ресурса. При этом процесс1 из заблокированного состояния переводится в состояние готовности.
На уровне реализации возможно одно из двух решений в отношении процессов, которые переводятся из очереди ожидания в очередь готовности при выполнении примитива V:
1) процесс при его активизации вновь пытается выполнить примитив P, считая предыдущую попытку неуспешной;
2) процесс при помещении его в очередь готовности отмечается как успешно выполнивший примитив P. Тогда при его активизации управление будет передано не на повторное выполнение примитива P, а на команду, следующую за ним.

Рассмотрим первый способ реализации. Пусть процесс2 в некоторый момент времени выполняет операцию P(S). Тогда семафор S становится равным нулю. Пусть теперь процесс1 пытается выполнить операцию P(S). Процесс1 в этом случае «засыпает» на семафоре S, т.к. значение S равнялось нулю, а теперь станет равным (-1). После выполнения критического интервала процесс2 выполняет операцию V(S), при этом значение семафора S становится равным нулю, а процесс1 переводится в очередь готовности. Пусть через некоторое время процесс1 будет активизирован, т.е. выведен из состояния ожидания, и сможет продолжить свое выполнение. Он повторно пытается выполнить операцию P(S), но ему это не удается, т.к. S=0. Процесс1 «засыпает» на семафоре, а его значение становится равным (-1). Если через некоторое время процесс2 попытается выполнить P(S), то он тоже «уснет». Возникает тупиковая ситуация, т.к. «будить» процессы некому.

При втором способе реализации тупиковой ситуации не будет. Пусть все происходит до момента окончания исполнения процессом2 примитива V(S). Пусть примитив V(S) выполнен и S=0. Через некоторое время процесс1 активизировался. Согласно данному способу реализации, он сразу попадает в свой критический интервал. При этом никакой другой процесс не попадает в свой критический интервал, т.к. семафор остался закрытым. После исполнения своего критического интервала процесс1 выполнит V(S). Если за время выполнения критического интервала процесса1 процесс2 не делал попыток выполнить операцию P(S), семафор установится в единицу. В противном случае значение семафора будет не больше нуля. Но в любом варианте после завершения операции V(S) процессом1 доступ к критическому ресурсу со стороны процесса2 будет разрешен.