Семафорные примитивы Дейкстры

Понятие семафорных механизмов было введено Дейкстрой [10]. Семафор (sema­phore) — это переменная специального типа, которая доступна параллельным процес­сам только для двух операций — закрытия и открытия, названных соответственно операциями Р и V¹. Эти операции являются примитивами относительно семафора, который указывается в качестве параметра операций. Здесь семафор играет роль вспомогательного критического ресурса, так как операции Р и V неделимы при сво­ем выполнении и взаимно исключают друг друга.

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

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

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

' Р — от голландского Proberen (проверить), V — от голландского Verhogen (увеличить).

Средства синхронизации и связи взаимодействующих процессов____________ 225

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

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

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

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

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

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

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

if S<0 then { остановить процесс и поместить его в очередь ожидания к семафору S }:

V(s): if S<0 then { поместить один из ожидающих процессов очереди семафора S в очередь готовности }; S:=S+1;

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

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

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

Листинг 7.8.Взаимное исключение с помощью семафорных операций

var S:semafor;

begin InitSem(S, 1); продолжение

¹ Двоичные семафоры иногда называют мьютексами (см. далее).

226Глава 7. Организация параллельных взаимодействующих вычислений

Листинг 7.8(продолжение)

parbegin

ПР1: while true do begin P(S):

CS1 : { критическая секция процесса ПР1 } V(S) end and

ПР2: while true do begin PCS);

CS2 ; { критическая секция процесса ПР2 } VCS) end

parend end.

Семафор 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), то он тоже заблокируется. Таким образом, возникнет

Средства синхронизации и связи взаимодействующих процессов________________ 227

так называемая тупиковая ситуация, так как разблокировать процессы ПР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+1.

Здесь вызов 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 можно реализовать в виде записи с двумя полями (листинг 7.9.). В одном поле будет хра­ниться целое значение S, во втором — указатель на список процессов, заблокиро­ванных на семафоре S.