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

Понятие семафорных механизмов было введено Дейкстрой [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.

Листинг 7.9. Реализация операций Р и V для однопроцессорной системы

type Semaphore = record

счетчик :integer:

указатель :pointer; продолжение

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

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

end; var S :Semaphore;

procedure P ( var S : Semaphore); begin ЗАПРЕТИТЬ_ПРЕРЫВАНИЯ; Б.счетчик:= Б.счетчик-].: if S.счетчик < 0 then

WAIT(S); { вставить обратившийся процесс в список по S.указатель и передать

на процессор готовый к выполнению процесс } РАЗРЕШИТЬ_ПРЕРЫВАНИЯ end;

procedure V ( var S : Semaphore): begin ЗАПРЕТИТЬ ПРЕРЫВАНИЯ;

З.счетчик::= S.счетчик+1;

if S.счетчик <= 0 then RELEASE (S); { деблокировать первый процесс из списка по S.указатель }

РАЗРЕШИТЬ_ПРЕРЫВАНИЯ end:

procedure InitSem (var S ; Semaphore): begin

5.счетчик:=1;

5.указатель:=nil: end;

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

Листинг 7.10.Реализация операций Р и V для мультипроцессорной системы

type Semaphore = record

счетчик : integer;

указатель : pointer;

взаимоискл : boolean: end; var S : Semaphore;

procedure InitSem (var S : Semaphore): begin With S do begin

счетчик:=1; указатель:=nil; взаимоискл:=true: end; end:

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

procedure Р ( var S : Semaphore): var разрешено : boolean: begin

ЗАПРЕТИТЬ_ПРЕРЫВАНИЯ;

repeat ТS(разрешено, S.взаимоискл) until разрешено:

S.счетчик:=S.счетчик-1:

if S.счетчик < 0 then WAIT(S): { вставить обратившийся процесс в список по S.указатель

и передать на процессор готовый к выполнению процесс }

S.взаимоискл:=true;

РАЗРЕШИТЬ_ПРЕРЫВАНИЯ end:

procedure V ( var S : Semaphore ):

var разрешено : boolean:

begin

ЗАПРЕТИТЬ_ПРЕРЫВАНИЯ;

repeat ТS(разрешено.S.взаимоискл) until разрешено:

5.Счетчик:=5.Счетчик+1;

if S.счетчик <= 0 then RELEASE(S): { деблокировать первый процесс из списка

по S.указатель }

S. взаимоискл:=true:

РАЗРЕШИТЬ__ПРЕРЫВАНИЯ: end:

Обратите внимание, что в данном тексте команда проверки и установки — TS(pa3-решено,S.взаимоискл) — работает не с целочисленными, а с булевыми значениями. Практически это ничего не меняет, ибо текст программы и ее машинная (двоич­ная) реализация — это разные вещи.

Мьютексы

Одним из вариантов реализации семафорных механизмов для организации вза­имного исключения является так называемый мьютекс (mutex). Термин «mutex» произошел от словосочетания «mutual exclusion semaphore», что дословно перево­дится с английского как «семафор взаимного исключения». Мьютексы реализова­ны во многих операционных системах, их основное назначение — организация вза­имного исключения для задач (потоков выполнения) одного или нескольких процессов. Мьютексы — это простейшие двоичные семафоры, которые могут на­ходиться в одном из двух состояний — отмеченном и неотмеченном (открыт и за­крыт соответственно). Когда какая-либо задача, принадлежащая любому процес­су, становится владельцем объекта мьютекс, последний переводится в неотмеченное состояние. Если задача освобождает мьютекс, его состояние становится отмечен­ным.

Организация последовательного (а не параллельного) доступа к ресурсам с ис­пользованием мьютексов становится несложной, поскольку в каждый конкрет­ный момент только одна задача может владеть этим объектом. Для того чтобы мьютекс стал доступен задачам (потокам выполнения), принадлежащим разным процессам, при создании ему необходимо присвоить имя, впоследствии переда­ваемое «по наследству» задачам, которые должны его использовать для взаимо­действия. Для этого вводятся специальные системные вызовы (CreateMutex), в которых указываются начальное значение мьютекса, его имя и, возможно, атри-

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

буты защиты. Если начальное значение мьютекса равно true, считается, что зада­ча, создающая этот объект, сразу будет им владеть. Можно указать в качестве начального значение false — в этом случае мьютекс не будет принадлежать ни одной из задач, и только специальным обращением к нему удастся изменить его состояние.

Для работы с мьютексом имеется несколько функций. Помимо уже упомянутой функции создания такого объекта (CreateMutex), есть функции открытия (OpenMu-tex), ожидания событий (WaitForSingleObject и WaitForMultipleObjects) и, наконец, ос­вобождения этого объекта (ReleaseMutex).

Конкретные обращения к этим функциям и перечни передаваемых и получае­мых параметров имеются в документации на соответствующую операционную систему.