Файл: А. В. Гордеев А. Ю. Молчанов системное программное обеспечение электронный вариант книги издательства Питер СанктПетербург Челябинск юургу каф. Автоматика и управление 2002 2 Предисловие Настоящий учебник.pdf

302
выполняет операцию 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
в очередь готовности};

303
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 ЗАПРЕТИТЬ_ПРЕРЫВАНИЯ;

304
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 двух процессов, выпол- няющихся на однопроцессорной вычислительной системе, предотвращается запре- том прерываний. Однако этот механизм не подходит для мультипроцессорных сис- тем, так как он не препятствует двум или более процессам одновременно обра- щаться к одному семафору. В силу того, что такой доступ должен реализовываться как критический интервал, необходимо дополнительное аппаратное взаимное ис-

305
ключение доступа для различных процессоров. Одним из решений является ис- пользование уже знакомых нам неделимых команд типа «ПРОВЕРКА И УСТА-
НОВКА» (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); { ВСТАВИТЬ ОБРАТИВШИЙСЯ
ПРОЦЕСС В СПИСОК

306
ПО 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, что дословно и перево- дится как семафор взаимного исключения. Мьютексы реализованы во многих ОС,
их основное назначение – организация взаимного исключения для задач (потоков)
из одного и того же или из разных процессов. Мьютексы – это простейшие двоич-

307
ные семафоры, которые могут находиться в одном из двух состояний – отмеченном или неотмеченном (открыт и закрыт соответственно). Когда какая-либо задача,
принадлежащая любому процессу, становится владельцем объекта mutex, послед- ний переводится в неотмеченное состояние. Если задача освобождает мьютекс, его состояние становится отмеченным.
Организация последовательного (а не параллельного) доступа к ресурсам с использованием мьютексов становится несложной, поскольку в каждый конкрет- ный момент только одна задача может владеть этим объектом. Для того чтобы объ- ект mutex стал доступен задачам (потокам), принадлежащим разным процессам,
при создании ему необходимо присвоить имя. Потом это имя нужно передать «по наследству» задачам, которые должны его использовать для взаимодействия. Для этого вводятся специальные системные вызовы (CreateMutex), в которых указыва- ются начальное значение мыотекса, его имя и, возможно, атрибуты защиты. Если начальное значение мьютекса равно true, то считается, что задача, создающая этот объект, будет им сразу владеть. Можно указать в качестве начального значение false – в этом случае мьютекс не принадлежит ни одной из задач и только специ- альным обращением к нему можно изменить его состояние.
Для работы с мьютексом имеется несколько функций. Помимо уже упомяну- той функции создания такого объекта (CreateMutex), есть функции открытия
(ОреnMutex), ожидания событий (WaitForSingleObject и WaitForMultipleObjects) и,
наконец, освобождение этого объекта (ReleaseMutex).
Конкретные обращения к этим функциям и перечни передаваемых и получае- мых параметров нужно смотреть в документации на соответствующую ОС.
Использование семафоров при
проектировании взаимодействующих
вычислительных процессов
Семафорные примитивы чрезвычайно широко используются при проектиро- вании разнообразных вычислительных процессов. При этом некоторые задачи яв- ляются настолько «типичными», что их детальное рассмотрение уже стало класси- ческим в соответствующих учебных пособиях. Не будем делать исключений и мы.

308
Задача «поставщик – потребитель»
Решение задачи «поставщик – потребитель» является характерным примером использования семафорных операций. Содержательная постановка этой задачи уже была нами описана в первом разделе данной главы. Разделяемыми переменными здесь являются счётчики свободных и занятых буферов, которые должны быть за- щищены со стороны обоих процессов, то есть действия по посылке и получению сообщений должны быть синхронизированы.
Использование семафоров для решения данной задачи приведено в листинге
6.11.
Листинг 6.11. Решение задачи «поставщик – потребитель»
var S_свободно, S_заполнено, S_взаимоискл : semaphore;
begin initSem(S_свободно,N);
initSem(S_заполнено,0);
initSem(S_взаимоискл,1);
parbegin
ПОСТАВЩИК: while true do begin
…{ приготовить сообщение }
Р(S_свободно);
Р(S_взаимоискл);
…{послать сообщение }
V(S_заполнено);
V(S_взаимоискл);
end and
ПОТРЕБИТЕЛЬ: while true do begin
Р(S_заполнено);
Р(S_взаимоискл);

309
…{ получить сообщение }
V(S_свободно);
V(S_взаимоискл);
…{ обработать сообщение }
end parend end.
Здесь переменные S_свободно, S_заполнено являются числовыми семафо- рами, S_взаимоискл – двоичный семафор. S_свободно имеет начальное значе- ние, равное N, где N – количество буферов, с помощью которых процессы связы- ваются. Предполагается, что в начальный момент количество свободных буферов равно N; соответственно, количество занятых равно нулю. Двоичный семафор
S_взаимоискл гарантирует, что в каждый момент только один процесс сможет работать с критическим ресурсом, выполняя свой критический интервал. Семафо- ры S_свободно и S_заполнено используются как счётчики свободных и запол- ненных буферов. Действительно, перед посылкой сообщения «поставщик» умень- шает значение S_свободно на единицу в результате выполнения Р(S_свободно),
а после посылки сообщения увеличивает значение S_заполнено на единицу в ре- зультате выполнения V(S_заполнено). Аналогично, перед получением сообщения
«потребитель» уменьшает значение S_заполнено в результате выполнения
Р(S_заполнено), а после получения сообщения увеличивает значение
S_свободно в результате выполнения V(S_свободно). Семафоры S_заполнено,
S_свободно могут также использоваться для блокировки соответствующих про- цессов. Если пул буферов оказался пустым и к нему первым обратится процесс
«потребитель», он заблокируется на семафоре S_заполнено в результате выпол- нения Р(S_заполнено). Если пул буферов заполнен и к нему в этот момент обра- тится процесс «поставщик», то он будет заблокирован на семафоре S_свободно в результате выполнения Р(S_свободно).

310
В решении задачи о «поставщике» и «потребителе» общие семафоры приме- нены для учёта свободных и заполненных буферов. Их можно также применить и для распределения иных ресурсов.
Пример простейшей синхронизации взаимодействующих процессов
Можно использовать семафорные операции для решения таких задач, в кото- рых успешное завершение одного процесса связано с ожиданием завершения дру- гого. Предположим что существуют два процесса ПР1 и ПР2. Необходимо, чтобы процесс ПР1 запускал процесс ПР2 с ожиданием его выполнения, то есть ПР1 не продолжал бы выполняться до тех пор, пока процесс ПР2 до конца не выполнит свою работу. Программа, реализующая такое взаимодействие, представлена в лис- тинге 6.12.
Листинг 6.12. Пример синхронизации процессов var S : Semaphore;
begin initSem(S,0):
ПР1: begin
ПР11; { первая часть ПР1 }
ON ( ПР2 ); { поставить на выполнение ПР2 }
P(S);
ПР12; { оставшаяся часть ПР1 }
STOP
end;
ПР2: begin
ПР2; { вся работа программы ПР2 }
V(S);
STOP
end end.

311
Начальное значение семафора S равно нулю. Если процесс ПР1 начал выпол- няться первым, то через некоторое время он поставит на выполнение процесс ПР2,
после чего выполнит операцию P(S) и «заснёт» на семафоре, перейдя в состояние пассивного ожидания. Процесс ПР2, осуществив все необходимые действия, вы- полнит примитив V(S) и откроет семафор, после чего процесс ПР1 будет готов к дальнейшему выполнению.
Решение задачи «читатели – писатели»
Другой важной и часто встречающейся задачей, решение которой также тре- бует синхронизации, является задача «читатели – писатели». Эта задача имеет мно- го вариантов. Наиболее характерная область использования этой задачи – при по- строении систем управления файлами. Два класса процессов имеют доступ к неко- торому ресурсу (области памяти, файлам). «Читатели» – это процессы, которые мо- гут параллельно считывать информацию из некоторой общей области памяти, яв- ляющейся критическим ресурсом. «Писатели» – это процессы, записывающие ин- формацию в эту область памяти, исключая при этом и друг друга, и процессы «чи- татели». Имеются различные варианты взаимодействия между «писателями» и
«читателями». Наиболее широко распространены следующие условия.
Устанавливается приоритет в использование критического ресурса процессам
«читатели». Это означает, что если хотя бы один «читатель» пользуется ресурсом,
то он закрыт для использования всем «писателям» и доступен для использования всем «читателям». Во втором варианте, наоборот, больший приоритет у процессов
«писатели». При появлении запроса от «писателя» необходимо закрыть дальней- ший доступ всем тем процессам «читателям», которые выдадут запрос на критиче- ский ресурс после него.
Другим типичным примером для задачи «читатели – писатели» помимо сис- тем управления файлами может служить система автоматизированной продажи би- летов. Процессы «читатели» обеспечивают нас справочной информацией о нали- чии свободных билетов на тот или иной рейс. Процессы «писатели» запускаются с

312
пульта кассира, когда он оформляет для нас тот или иной билет. Имеется большое количество как «читателей», так и «писателей».
Пример программы, реализующей решение данной задачи в первой постанов- ке, представлен в листинге 6.13. Процессы «читатели» и «писатели» описаны в ви- де соответствующих процедур.
Листинг 6.13. Решение задачи «читатели–писатели» с приоритетом в доступе к критическому ресурсу «читателей»
Var R, W : semaphore;
NR : integer;
procedure ЧИТАТЕЛЬ;
begin
P(R);
Inc(NR); { NR:=NR +1 }
if NR = 1 then P(W);
V(R);
Read_Data: { критический интервал }
Р(R);
Dec(NR);
if NR = 0 then V(W);
V(R)
end;
procedure ПИСАТЕЛЬ;
begin
P(W);
Write_Data; { критический интервал }
V(W)
end begin
NR:=0;
initSem(S,1); InitSem(W,1);
parbegin while true do ЧИТАТЕЛЬ
and while true do ЧИТАТЕЛЬ
and