Гордеев А.В. Операционные системы (2-е изд., 2004) (1186250), страница 60
Текст из файла (страница 60)
Тогда семафор 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 thenWAIT(S): { вставить обратившийся процесс в список no S.указатель и передатьна процессор готовый к выполнению процесс }РАЗРЕШИТЬ_ПРЕРЫВАНИЯend:procedure V ( var S : Semaphore);begin ЗАПРЕТИТЬ ПРЕРЫВАНИЯ:5.счетчик:= Б.счетчик+1;if S.счетчик <= 0 thenRELEASE ( S ) ;{ деблокировать первый процесс из списка no S.указатель }РАЗРЕШИТЬ_ПРЕРЫВАНИЯend;procedure InitSem (var S : Semaphore);beginS.C4eT4HK:=l:5.указатель:=пП;end;Реализация семафоров в мультипроцессорных системах сложнее, чем в однопроцессорных. Одновременный доступ к семафору S двух процессов, выполняющихся на однопроцессорной вычислительной системе, предотвращается запретом прерываний.
Однако этот механизм не подходит для мультипроцессорных систем, таккак он не препятствует двум или более процессам одновременно обращаться к одному семафору. В силу того что такой доступ должен реализовываться через критическую секцию, необходимо дополнительное аппаратное взаимное исключениедоступа для различных процессоров. Одним из решений является использованиеуже знакомых нам неделимых команд проверки и установки (TS). Двухкомпонентный семафор в этом случае расширяется включением третьего компонента — логического признака взаимоискл (листинг 7.10).Л и с т и н г 7 . 1 0 . Реализация о п е р а ц и й Р и V для мультипроцессорной с и с т е м ыt y p e Semaphore = recordсчетчик : i n t e g e r :указатель : p o i n t e r :взаимоискл : boolean;end:var S : Semaphore;procedure InitSem (var S : Semaphore);beginWith S dobeginсчетчик:=1;указатель:=nil;взаимоискл:=true;end;end:пг-тва синхронизации и связи взаимодействующих процессов229procedure Р ( var S : Semaphore);у а Г разрешено : boolean;beginЗАПРЕТИТЬ_ПРЕРЫВАНИЯ;repeat ТБСразрешено.
Б.взаимоискл) until разрешено;5 счетчике.счетчик-1;if S счетчик < 0 then WAIT(S): { вставить обратившийся процесс в список по S.указательи передать на процессор готовый к выполнению процесс }S взаимоискл:Чгие;РАЗРЕШИТЬ_ПРЕРЫВАНИЯend:procedure V ( var S : Semaphore );var разрешено : boolean;beginЗАПРЕТИТЬ_ПРЕРЫВАНИЯ:repeat ТЗфазрешено.З.взаимоискл) u n t i l разрешено:S.счетчик:=S.C4eT4MK+l:if S.счетчик <= 0 then RELEASE(S);{ деблокировать первый процесс из спискапо S.указатель }5.взаимоискл:Чгие:t, ,РАЗРЕШИТЬ_ЛРЕРЫВАНИЯ:end;Обратите внимание, что в данном тексте команда проверки и установки — TS(pa3решенсБ.взаимоискл) — работает не с целочисленными, а с булевыми значениями.Практически это ничего не меняет, ибо текст программы и ее машинная (двоичная) реализация — это разные вещи.МьютексыОдним из вариантов реализации семафорных механизмов для организации взаимного исключения является так называемый мъютекс (mutex). Термин «mutex»произошел от словосочетания «mutual exclusion semaphore», что дословно переводится с английского как «семафор взаимного исключения».
Мьютексы реализованы во многих операционных системах, их основное назначение — организация взаимного исключения для задач (потоков выполнения) одного или несколькихпроцессов. Мьютексы — это простейшие двоичные семафоры, которые могут находиться в одном из двух состояний — отмеченном и неотмеченном (открыт и закрыт соответственно).
Когда какая-либо задача, принадлежащая любому процессу, становится владельцем объекта мыотекс, последний переводится в неотмеченноеостояние. Если задача освобождает мыотекс, его состояние становится отмеченным.рганизация последовательного (а не параллельного) доступа к ресурсам с пользованием мьютексов становится несложной, поскольку в каждый конкрет1момент только одна задача может владеть этим объектом.
Для того чтобыТекс стал доступен задачам (потокам выполнения), принадлежащим разнымЦессам, при создании ему необходимо присвоить имя, впоследствии переда1е«по наследству» задачам, которые должны его использовать для взаимоКот В И Я ' ^ля э т о г о вводятся специальные системные вызовы (CreateMutex), вPbix указываются начальное значение мьютекса, его имя и, возможно, атри-230Глава 7. Организация параллельных взаимодействующих вычисляниг.буты защиты. Если начальное значение мыотекса равно true, считается, что задача, создающая этот объект, сразу будет им владеть. Можно указать в качественачального значение false — в этом случае мыотекс не будет принадлежать ниодной из задач, и только специальным обращением к нему удастся изменить егосостояние.Для работы с мьютексом имеется несколько функций.
Помимо уже упомянутойфункции создания такого объекта (CreateMutex), есть функции открытия (OpenMutex), ожидания событий (WaitForSingleObject и WaitForMultipleObjects) и, наконец, освобождения этого объекта (ReleaseMutex).Конкретные обращения к этим функциям и перечни передаваемых и получаемых параметров имеются в документации на соответствующую операционнуюсистему.Использование семафоров при проектированиивзаимодействующих вычислительных процессовСемафорные примитивы чрезвычайно широко используются при проектировании разнообразных вычислительных процессов. При этом некоторые задачиявляются настолько «типичными», что их детальное рассмотрение уже сталоклассическим в соответствующих учебных пособиях.
Не будем делать исключений и мы.Задача «поставщик-потребитель»Решение задачи «поставщик-потребитель» является характерным примером использования семафорных операций. Содержательная постановка этой задачи ужебыла нами описана в начале этой главы. Разделяемыми переменными здесь являются счетчики свободных и занятых буферов, которые должны быть защищены состороны обоих процессов, то есть действия по посылке и получению сообщениидолжны быть синхронизированы.Использование семафоров для решения данной задачи иллюстрирует листинг 7.11Листинг 7 .
1 1 . Решение задачи «поставщик-потребитель»var 5_свободно.5_заполнено.5_взаимоискл : semaphore;beginInitSem(S_CBo6oflHO.N):InitSem(S_3anojiHeHo,0):InitSem(S_B3aHM0ncKji,l):parbeginПОСТАВЩИК: while true dobegin{ подготовить сообщение }Р(Б_свободно);Р(5_взаимоискл):{ послать сообщение }\/(5_заполнено):У(5_взаимоискл);endandпства синхронизации и связи взаимодействующих процессов231ПОТРЕБИТЕЛЬ: while true dobegi nР(5_заполнено);Р(5_взаимоискл);{ получить сообщение }V(S_CBo6oflHO):\КБ_взаимоискл):{ обработать сообщение }endparendend.Здесь переменные 5_свободно, Б_заполнено являются числовыми семафорами,S взаимоискл — двоичный семафор. Переменная Б_свободно имеет начальное значение, равное N, где N — количество буферов, с помощью которых процессы сотрудничают.
Предполагается, что в начальный момент количество свободных буферов равно N; соответственно, количество занятых равно нулю. Двоичный семафорS взаимоискл гарантирует, что в каждый момент только один процесс сможет работать с критическим ресурсом, выполняя свою критическую секцию. СемафорыБ_свободно и Б_заполнено используются как счетчики свободных и заполненныхбуферов.Действительно, перед посылкой сообщения поставщик уменьшает значение S_CBOбодно на единицу в результате выполнения операции Р(Б_свободно), а после посылки сообщения увеличивает значение Б_заполнено на единицу в результате выполнения операции \/(Б_заполнено). Аналогично, перед получением сообщенияпотребитель уменьшает значение 5_заполнено в результате выполнения операцииР(Б_заполнено), а после получения сообщения увеличивает значение Б_свободно врезультате выполнения операции V(S_CBO6OAHO).
Семафоры Б_заполнено, Б_свободномогут также использоваться для блокировки соответствующих процессов. Еслипул буферов оказывается пустым, и к нему первым обратится процесс «потребитель», он заблокируется на семафоре 5_заполнено в результате выполнения операции Р(5_заполнено).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
