Семафорные примитивы Дейкстры
Понятие семафорных механизмов было введено Дейкстрой [27]. Семафор – переменная специального типа, которая доступна параллельным процессам для проведения над ней только двух операций: «закрытия» и «открытия», названных соответственно Р- и V-операциями. Эти операции являются примитивами относительно семафора, который указывается в качестве параметра операций. Здесь семафор выполняет роль вспомогательного критического ресурса, так как операции Р и V неделимы при своём выполнении и взаимно исключают друг друга.
Семафорный механизм работает по схеме, в которой сначала исследуется состояние критического ресурса, идентифицируемое значением семафора, а затем уже осуществляется допуск к критическому ресурсу или отказ от него на некоторое время. При отказе доступа к критическому ресурсу используется режим «пассивного ожидания». Поэтому в состав механизма включаются средства формирования и обслуживания очереди ожидающих процессов. Эти средства реализуются супервизором операционной системы. Необходимо отметить, что в силу взаимного исключения примитивов попытка в различных параллельных процессах одновременно выполнить примитив над одним и тем же семафором приведет к тому, что она будет успешной только для одного процесса. Все остальные процессы будут взаимно исключены на время выполнения примитива. Основным достоинством использования семафорных операций является отсутствие состояния «активного ожидания», что может существенно повысить эффективность работы мультипрограммной вычислительной системы.
В настоящее время на практике используется много различных видов семафорных механизмов [75]. Варьируемыми параметрами, которые отличают различные виды примитивов, являются начальное значение и диапазон изменения значений семафора, логика действий семафорных операций, количество семафоров, доступных для обработки при исполнении отдельного примитива.
Обобщенный смысл примитива P(S)1 состоит в проверке текущего значения семафора S, и если оно не меньше нуля, то осуществляется переход к следующей за примитивом операции. В противном случае процесс снимается на некоторое время с выполнения и переводится в состояние «пассивного ожидания». Находясь в списке заблокированных, ожидающий процесс не проверяет семафор непрерывно, как в случае активного ожидания. Вместо него на процессоре может исполняться другой процесс, который реально совершает полезную работу.
Операция V(S)2 связана с увеличением значения семафора на единицу и переводом одного или нескольких процессов в состояние готовности к центральному процессору.
Отметим еще раз, что операции Р и V выполняются операционной системой в ответ на запрос, выданный некоторым процессом и содержащий имя семафора в качестве параметра.
Рассмотрим первый вариант алгоритма работы семафорных операций, который представлен в листинге 6.7.
Допустимыми значениями семафоров являются только целые числа. Двоичным семафором будем называть семафор, максимально возможное значение которого будет равно единице. В противном случае семафоры называют N-ичными. Есть реализации, в которых семафорные переменные не могут быть отрицательными, а есть и такие, где отрицательное значение указывает на длину очереди процессов, стоящих в состоянии ожидания открытия семафора.
Листинг 6.7. Вариант реализации семафорных примитивов
P(S): S:=S-1;
if S<0 then
{ остановить процесс и поместить его в очередь ожидания к семафору S }
V(s): if S<0 then
{поместить один из ожидающих процессов очереди семафора S в очередь
готовности};
S:=S+1
Заметим, что для работы с семафорными переменными необходимо еще иметь операцию инициализации самого семафора, то есть операцию задания ему начального значения. Обычно эту операцию называют InitSem; как правило, она имеет два параметра – имя семафорной переменной и её начальное значение; следовательно, обращение к ней имеет вид:
ImtSem (Имя_семафора, Начальное_значение_семафора);
Попытаемся на нашем примере двух конкурирующих процессов ПР1 и ПР2 проанализировать использование данных семафорных примитивов для решения проблемы критического интервала. Программа, иллюстрирующая это решение, представлена в листинге 6.8.
Листинг 6.8. Взаимное исключение с помощью семафорных операций
var S:semafor;
begin InitSem(S,1);
parbegin
ПР1: while true do
begin
P(S);
CS1 { Критический интервал процесса ПР1 }
V(S)
end
and
ПР2: while true do
begin
P(S);
CS2 { Критический интервал процесса ПР2 }
V(S)
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), то он тоже «уснет». Таким образом, возникнет так называемая тупиковая ситуация, так как «будить» процессы ПР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 можно реализовать в виде записи с двумя полями (листинг 6.9). В одном поле хранится целое значение S, во втором – указатель на список процессов, заблокированных на семафоре S.
Листинг 6.9. Реализация Р- и V-операций для однопроцессорной системы
type Semaphore = record
счетчик :integer;
указатель :pointer;
end;
var S :Semaphore;
procedure P ( var S : Semaphore);
begin ЗАПРЕТИТЬ_ПРЕРЫВАНИЯ;
S.счетчик:= S-счетчик-1;
if S.счетчик < 0 then
WAIT(S); {ВСТАВИТЬ ОБРАТИВШИЙСЯ ПРОЦЕСС В
СПИСОК ПО S.указатель и УСТАНОВИТЬ НА
ПРОЦЕССОР ГОТОВЫЙ К ВЫПОЛНЕНИЮ
ПРОЦЕСС }
РАЗРЕШИТЬ__ПРЕРЫВАНИЯ
end;
procedure V ( var S : Semaphore);
begin ЗАПРЕТИТЬ ПРЕРЫВАНИЯ;
S.счетчик:=S.счетчик+1;
if S.счетчик<= 0 then
RELEASE (S); { ДЕБЛОКИРОВАТЬ ПЕРВЫЙ ПРОЦЕСС ИЗ
СПИСКА ПО S.указатель }
РАЗРЕШИТЬ_ПРЕРЫВАНИЯ
end;
procedure InitSem (var S : Semaphore);
begin
S.счетчик:=1;
S.указатель:=nil;
end;
Реализация семафоров в мультипроцессорных системах более сложна, чем в однопроцессорных. Одновременный доступ к семафору S двух процессов, выполняющихся на однопроцессорной вычислительной системе, предотвращается запретом прерываний. Однако этот механизм не подходит для мультипроцессорных систем, так как он не препятствует двум или более процессам одновременно обращаться к одному семафору. В силу того, что такой доступ должен реализовываться как критический интервал, необходимо дополнительное аппаратное взаимное исключение доступа для различных процессоров. Одним из решений является использование уже знакомых нам неделимых команд типа «ПРОВЕРКА И УСТАНОВКА» (TS). Двухкомпонентный семафор в этом случае расширяется включением третьего компонента – логического признака ВзаимоИскл (листинг 6.10).
Листинг 6.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;
procedure P ( var S : Semaphore);
var разрешено : boolean;
begin
ЗАПРЕТИТЬ_ПРЕРЫВАНИЯ;
repeat TS(разрешено, S.взаимоискл) until разрешено;
S. счетчик:= счетчик-1;
if S.счетчик < 0 then WAIT(S); { ВСТАВИТЬ ОБРАТИВШИЙСЯ
ПРОЦЕСС В СПИСОК
ПО S.указатель И УСТАНОВИТЬ
НА CPU ГОТОВЫЙ ПРОЦЕСС }
S.взаимоискл:=true;
РАЗРЕШИТЬ_ПРЕРЫВАНИЯ
end;
procedure V ( var S : Semaphore );
var разрешено : boolean;
begin
ЗАПРЕТИТЬ_ПРЕРЫВАНИЯ;
repeat TS(разрешено, S. взаимоискл) until разрешено;
S.счетчик:=S.счетчик+1;
if S.счетчик < 0 then RELEASE(S); { ДЕБЛОКИРОВАТЬ ПЕРВЫЙ
ПРОЦЕСС ИЗ СПИСКА ПО
S.yкaзaтeль }
S.взаимоискл:=true;
РАЗРЕшИТЬ_ПРЕРЫВАНИЯ;
end;
Обратите внимание, что в данном тексте команда типа «проверка и установка» – TS(разрешено, S.взаимоискл) – работает не с целочисленными, а с булевыми значениями. Практически это ничего не меняет, ибо текст программы и её машинная (двоичная) реализация – это всё-таки разные вещи.
Мьютексы
Одним из вариантов семафорных механизмов для организации взаимного исключения являются так называемые мьютексы (mutex). Термин mutex произошёл от английского словосочетания mutual exclusion semaphore, что дословно и переводится как семафор взаимного исключения. Мьютексы реализованы во многихОС, их основное назначение – организация взаимного исключения для задач (потоков) из одного и того же или из разных процессов. Мьютексы – это простейшие двоичные семафоры, которые могут находиться в одном из двух состояний – отмеченном или неотмеченном (открыт и закрыт соответственно). Когда какая-либо задача, принадлежащая любому процессу, становится владельцем объекта mutex, последний переводится в неотмеченное состояние. Если задача освобождает мьютекс, его состояние становится отмеченным.
Организация последовательного (а не параллельного) доступа к ресурсам с использованием мьютексов становится несложной, поскольку в каждый конкретный момент только одна задача может владеть этим объектом. Для того чтобы объект mutex стал доступен задачам (потокам), принадлежащим разным процессам, при создании ему необходимо присвоить имя. Потом это имя нужно передать «по наследству» задачам, которые должны его использовать для взаимодействия. Для этого вводятся специальные системные вызовы (CreateMutex), в которых указываются начальное значение мыотекса, его имя и, возможно, атрибуты защиты. Если начальное значение мьютекса равно true, то считается, что задача, создающая этот объект, будет им сразу владеть. Можно указать в качестве начального значение false – в этом случае мьютекс не принадлежит ни одной из задач и только специальным обращением к нему можно изменить его состояние.
Для работы с мьютексом имеется несколько функций. Помимо уже упомянутой функции создания такого объекта (CreateMutex), есть функции открытия (ОреnMutex), ожидания событий (WaitForSingleObject и WaitForMultipleObjects) и, наконец, освобождение этого объекта (ReleaseMutex).
Конкретные обращения к этим функциям и перечни передаваемых и получаемых параметров нужно смотреть в документации на соответствующую ОС.
Дата добавления: 2022-02-05; просмотров: 396;