Семафорные операции

Понятие семафорных механизмов было введено Дейкстрой.

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

Семафорный механизм работает по схеме, в которой сначала исследуется состояние критического ресурса, идентифицируемое значением семафора, а затем уже осуществляется допуск к критическому ресурсу или отказ от него на некоторое время. При отказе доступа к критическому ресурсу используется режим «пассивного ожидания». Поэтому в состав механизма включается средства формирования и обслуживания очереди ожидающих процессов. Эти средства реализуются супервизором операционной системы. Необходимо отметить, что в силу взаимного исключения примитивов попытка в различных параллельных процессах одновременно выполнить примитив над одним и тем же семафором приведет к тому, что она будет успешной только для одного процесса. Все остальные процессы будут взаимно исключены на время выполнения примитива.

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

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

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

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

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

Рассмотрим первый вариант алгоритма работы семафорных операций, который приведен в листинге 4.1.

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

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

If S<0 then WAIT(S); {остановить процесс и поместить его в

очередь ожидания к семафору S}

V(S): If S<0 then RELEASE(S); {поместить один из ожидающих

процессов очереди семафора S в очередь готовности};

S:=S+1;

Листинг 4.1. Вариант реализации семафорных примитивов

Заметим, что для работы с семафорными переменными необходимо еще иметь операцию инициализации самого семафора, то есть операцию задания ему начального значения. Обычно эту операцию называют InitSem; как правило, она имеет два параметра – имя семафорной переменной и ее начальное значение; следовательно, обращение к ней имеет вид:

InitSem (Имя_семафора, Начальное_значение_семафора);

Попытаемся на примере двух конкурирующих процессов Р1 и Р2 проанализировать использование данных семафорных примитивов для решения проблемы критического интервала. Схема, иллюстрирующая это решение, представлена рис.4.10.

P1 P2

InitSem (S, 1);

Рис. 4.10. Модель использования семафорных операций

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

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

На уровне реализации возможно одно из двух решений в отношении процессов, которые переводятся из очереди ожидания в очередь готовности при выполнении примитива V:

· процесс его активизации (выборка из очереди готовности) вновь пытается выполнить примитив Р, считая предыдущую попытку неуспешной;

· процесс при помещении его в очередь готовности отмечается как успешно выполнивший примитив Р.

Тогда при его активизации управление будет передано не на повторное выполнение примитива Р, а на команду, следующую за ним.

Рассмотрим первый способ реализации.

Пусть процесс Р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), то он тоже «уснет». Таким образом, возникнет так называемая тупиковая ситуация, так как «будить» процессы Р1 и Р2 некому.

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

Заметим, что возникновение тупиков возможно в случае несогласованного выбора механизма реактивации процессов из очереди, с одной стороны, и выбора алгоритмов семафорных операций – с другой.

Возможен другой алгоритм работы семафорных операций – листинг 4.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+1;

Листинг 4.2.Второй вариант реализации семафорных примитивов

Здесь вызов 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) и войдет в свой критический интервал.

Анализ рассмотренных задач показывает, что, несмотря на очевидные достоинства (простота, независимость от количества процессов, отсутствие “активного ожидания”), семафорные механизмы имеют и ряд недостатков. Семафорные механизмы являются слишком примитивными, так как семафор не указывает непосредственно на синхронизирующее условие, с которым он связан, или на критический ресурс. Поэтому при построении сложных схем синхронизации алгоритмы решения задач порой получаются весьма непростыми, ненаглядными и затруднительными для доказательства их правильности.