Проанализируем использование данных семафорных примитивов. Семафор S имеет начальное значение, равное 1. Если процессы ПР1 и ПР2 попытаются одновременно выполнить примитив P(S), то это удастся успешно сделать только одному из них. Предположим, это сделал процесс ПР2, тогда он закрывает семафор S, после чего выполняется его критический интервал. Процесс ПР1 в рассматриваемой ситуации будет заблокирован на семафоре S. Тем самым будет гарантировано взаимное исключение.
После выполнения примитива V(S) процессом ПР2 семафор S открывается, указывая на возможность захвата каким-либо процессом освободившегося критического ресурса. При этом производится перевод процесса ПР1 из заблокированного состояния в состояние готовности.
На уровне реализации возможно одно из двух решений в отношении процессов, которые переводятся из очереди ожидания в очередь готовности при выполнении примитива V:
ü процесс при его активизации (выборка из очереди готовности) вновь пытается выполнить примитив Р, считая предыдущую попытку неуспешной;
ü процесс при помещении его в очередь готовности отмечается как успешно выполнивший примитив Р. Тогда при его активизации управление будет передано не на повторное выполнение примитива Р, а на команду, следующую за ним.
Рассмотрим первый способ реализации. Пусть процесс ПР2 в некоторый момент времени выполняет операцию P(S). Тогда семафор S становится равным нулю. Пусть далее процесс ПР1 пытается выполнить операцию Р(S). Процесс ПР1 в этом случае «засыпает» на семафоре S, так как значение семафора S равнялось нулю, а теперь станет равным (-1). После выполнения критического интервала процесс ПР2 выполняет операцию V(S), при этом значение семафора S становится равным нулю, а процесс ПР1 переводится в очередь готовности. Пусть через некоторое время процесс ПР1 будет активизирован, то есть выведен из состояния ожидания, и сможет продолжить свое исполнение. Он повторно пытается выполнить операцию P(S), однако это ему не удается, так как S=0. Процесс ПР1 «засыпает» на семафоре, а его значение становится равным (-1). Если через некоторое время процесс ПР2 попытается выполнить P(S), то он тоже «уснет». Таким образом, возникнет так называемая тупиковая ситуация, так как «будить» процессы ПР1 и ПР2 некому.
При втором способе реализации тупиковой ситуации не будет. Действительно, пусть все происходит также до момента окончания исполнения процессом ПР2 примитива V(S). Пусть примитив V(S) выполнен и S=0. Через некоторое время процесс ПР1 активизировался. Согласно данному способу реализации, он сразу же попадет в свой критический интервал. При этом никакой другой процесс не попадет в свой критический интервал, так как семафор остался закрытым. После исполнения своего критического интервала процесс ПР1 выполнит V(S). Если за время выполнения критического интервала процесса ПР1 процесс ПР2 не делал попыток выполнить операцию P(S), семафор S установится в единицу. В противном случае значение семафора будет не больше нуля. Но в любом варианте после завершения операции V(S) процессом ПР1 доступ к критическому ресурсу со стороны процесса ПР2 будет разрешен.
Возникновение тупиков возможно в случае несогласованного выбора механизма реактивации процессов из очереди, с одной стороны, и выбора алгоритмов семафорных операций – с другой.
Возможен другой алгоритм работы семафорных операций:
P(S):
if S >= 1 then S:= S - 1
else WAIT(S){остановить процесс и поместить в очередь ожидания к семафору S}
V(S):
if S<0 then RELEASE(S){поместить один из ожидающих процессов очереди семафора S в очередь готовности};
S:=S + l.
Здесь вызов WAIT(S) означает, что супервизор ОС должен перевести задачу в состояние ожидания, причем очередь процессов связана с семафором S. Вызов RELEASE (S) означает обращение к диспетчеру задач с просьбой перевести первый из процессов, стоящих в очереди S, в состояние готовности к исполнению.
Использование семафорных операций, выполненных подобным образом, позволяет решать проблему критических интервалов на основе первого способа реализации без вероятности возникновения тупиков. Действительно, пусть ПР2 в некоторый момент времени выполнит операцию P(S). Тогда семафор S становится равным нулю. Пусть далее процесс ПР1 пытается выполнить операцию P(S). Процесс ПР1 в этом случае «заснет» на семафоре S, так как S=0, причем значение S не изменится. После выполнения своего критического интервала процесс ПР2 выполнит операцию V(S), при этом значение семафора S станет равным единице, а процесс ПР1 переведется в очередь готовности. Если через некоторое время процесс ПР1 будет активизирован, он успешно выполнит P(S) и войдет в свой критический интервал.
В однопроцессорной вычислительной системе неделимость Р - и V - операций можно обеспечить с помощью простого запрета прерываний. Сам же семафор S можно реализовать в виде записи с двумя полями. В одном поле хранится целое значение S, во втором – указатель на список процессов, заблокированных на семафоре S.
Листинг 6.9. Реализация Р - и V - операций для однопроцессорной системы
