В. Столлингс - Операционные системы (1114679), страница 50
Текст из файла (страница 50)
Он применим к любому количеству процессов при наличии как одн и нескольких процессоров, разделяющих основную память. ° Этот подход очень прост, а потому легко проверяем. Он может использоваться для поддержки множества критических лов; каждый из них может быть определен при помощи своей со ной переменной. Однако у такого подхода имеются и серьезные недостатки. 'Ф Используется пережидание занятости. Следовательно, в то время как просс находится в ожидании доступа к критическому разделу, он продолжает потреблять процессорное время.
Возможно голодание. Если процесс покидает критический раздел, а входа в него ожидают несколько других процессов, то выбор ожидающего процесса произволен. Следовательно, может оказаться„что какой-то из процессов будет ожидать входа в критический раздел бесконечно. Возможна взаимоблокировка. Рассмотрим следующий сценарий в однопроцессорной системе. Процесс Р1 выполняет специальную инструкцию (т.е.
, евсее. или ехсйапде) и входит в критический раздел. После этого процесс Р1 прерывается процессом Р2 с более высоким приоритетом. Если Р2 попытается обратиться к тому же ресурсу, что и Р1, ему будет отказано в доступе в соответствии с механизмом взаимоисключений, и он войдет в цикл пережидания занятости. Однако в силу того что процесс Р1 имеет более низкий приоритет, он не получит возможности продолжить работу, так как в наличии имеется активный процесс с высоким приоритетом.
Из-за наличия недостатков как в случае использования программных, так и аппаратных решений нам следует рассмотреть и другие механизмы обеспечения взанмоблокнровок. Теперь мы вернемся к механизмам операционных систем и языков программирования, обеспечивающим параллельные вычисления. Этот раздел мы начнем с рассмотрения семафоров; следующие разделы будут посвящены мониторам и передаче сообщений. Первой большой работой, посвященной вопросам параллельных вычислений, стала монография Дейкстры 1?)1,1К651, который рассматривал разработку операционной системы как построение множества сотрудничающих последовательных процессов и создание эффективных и надежных механизмов ~~дд~ржки этого сотрудничества.
Эти же механизмы легко применяются и пользовательскими процессами — если процессор н операционная система Делают их общедоступными, Фундаментальный принцип заключается в том, что два или болыпее количество процессов могут сотрудничать посредством простых сигналов, так что в определенно енном месте процесс может приостановить работу до тех пор, пока не дождется событь тветстаующего сигнала. Требования кооперации любой степени сложности могут ь удовлетворены соответствующей структурой сигналов. для сигнализации иссольдч "ьзуются специальные переменные, называющиеся семафорами. Для передачи сигна, ала через семафор э процесс выполняет примитив э1дпа1 ~э), а для получения снгнв,а в--а — примитив ха1С (э~.
В последнем случае процесс приостанавливается до тех гю, Р пока не осуществится передача соответствующего сигнала.2 перемен н, ла лостижения желаемого эффекта мы можем рассматривать семафор как енную, имеющую целое значение, над которой определены три операции. 2 8 статье дейкстры и многих других источниках вместо квтс используется бук- Р,ив, место в1длв2 — - ~"; это первые буквы голландски» слов проверка ~ргооегенг' и " апе 1оегйоуеп). Часть 2. П .
о Параллельные вычисления: взаимоисключения... 267 (7оместить в~~ох~есс в а.яыеце Эаб ~окиоовать Г7роцес па1О (Ь1пагу веп~арйоге в ) ( (в.спеце в егпр';у() ) в. га1ые = 1~ Гцсл вепарЬсге . п~ соыпл; яыеыетуре я~2е~2е; 3 . со~.'пЬ 1Й (в. соыпЬ < О) 17оместить пооцесс в я.дыеые 3аодаки(вдоветь л~:~оцесс сьсх Ь'гагу зекарЬоге ( епир ( зе-о опе ) та1се ~(це~ етуре ~(Бене; (а ха1ЬБ(Ь1пагу эетарйоге в) Часть 2.
1. Семафор может быть иницизлизирован неотрицательным значение ' Операция ъа1Ь уменьшает значение семафора. Если это значение ся отрицательным, процесс, выполняющий операцию ыа1~, блоки ч, Операция в1Опа1 увеличивает значение семафора. Если это значе ложительно, то заблокированный операцией иа1Ь процесс деблокир" Не имеется никаких иных способов получения информации о знач'" ~фора илн изменения его значения, кроме перечисленных.
В листинге 5.5 приведено более Формальное определение прими ~ров. Предполагается, что примитивы ка(Ь и в1дпа1 атомарны, т.е. он" т быть прерваны, и каждая из подпрограмм может рассматриваться 1й шаг. Более ограниченная версия семафора, известная как бина >р, представлена в листинге 5.6. Бинарный семафор может принима ачения О или 1. В принципе реализация бинарного семафора должна е простой задачей; можно также показать, что все задачи, решаемые Е,.
нием обычных семафоров, могут быть решены и с использованием л рных семафоров (см, задачу 5.13). ~стинг 5.5. Определение семафорных примитивов в.соцпЬ++; (в.соыпс <= О) Уладить процесс Р из Я.циеие Поместить процесс Р в список активных стинг 5.6. Определение примитивов бинарного семафора е '.ье Удалить процесс Р ив 5. диеие Поместить процесс Р в список активных Для хранения процессов, ожидающих как обычные, так и бинарные семафоры, используется очередь.
При этом возникает вопрос о порядке извлечения процессов из данной очереди. Наиболее корректный способ — использование принципа "первым вошел — первым вышел" (Йгз$-(п-Йгв1-опав ИГО). При этом первым из очереди освобождается процесс, который был заблокирован дольше других. Семафор, использующий данный метод, называется сильным семафором (в$гопа зегпарЬоге).
Семафор, порядок извлечения процессов из очереди которого не определен, называется слабым семафором (яеа)~ зетарЬоге). На рис. 5.2 (из 10ЕИХ84]) приведен пример работы сильного семафора. Здесь процессы А, В и С зависят от результатов работы процесса 11. Изначально работает процесс А (й); процессы В, С и Р находятся в ~писке активных процессов, ожидая своей очереди. Значение семафора равно 1 это Указывает на то, что один из результатов работы процесса В имеется в наличии. Когда процесс А выполняет инструкцию иа(Ь, ои тут же получает Разрешение на дальнейшую работу и вновь становится в очередь на выполнение в списке активных процессов. Затем приступает к работе процесс В (Ф), который в конечном счете также выполняет инструкцию иа1ь, в результате чего процесс приостанавливается, давая возможность приступить к работе про е Роцессу 1) (Сз)).
Когда процесс В завершает работу над получением нового Рез л ультата, он выполняет инструкцию в1дпа1, которая позволяет процессу В перейт Рейти из списка приостановленных процессов в список активных (®). Р цесс П присоединяется к списку активных процессов, и к выполнению прист . тупеет процесс С (О~), но тут же приостанавливается при выполнении анстр к Рукции аа(Ь. Точно так же приостанавливается и выполнение процессов АиВ давая возможность процессу В приступить к работе (Ф). После того как и л . случается новый результат процесса Р, им выполняется инструкция -1 ~1Япа 1 которая и переводит процесс С из списка приостановленных в спи:: окак к акт тканых. Последующие циклы выполнения процесса 0 переведут в спиктивных процессы А и В.
5. Параллельные вычисления: взаимоисключения... Список готовых к выполнению процессов Список приостановленных процессов Семафор Я Процессор т%-: Списокготовых квыполнениюпроцессов Список пРиостановленных пРоцессов Семафор Оз Процессор 'х Список приостановленных процессов 04) Процессор Список готовых к выполнению процессов тна1т. (э'т т l+ Критический раздел +/т э1опа1(а); /* Остальной кол +~т Список готовых к выполнению процессов писак пРиостановленных пРоцессов Семафор О Процессор тго1б гпа ',и () рагЬедтп (Р (1т, Р (2), ., Р(пт ( т Список готовых к выполнению пргхтессов "%. Список приостановленных процессов О 6 Процессор Список приостановленных процессов СемаФор О 7 Процессор Часть 2.
писокприостаноеленныхпроцессов Семафор Список готовых к выполнению процессов Рис. 5.2. Пртх ттер работтн мехакиама семафоров В следующем подразделе рассматривается алгоритм взаимоисключений (лттсти ,тинг 5.7), использование сильного семафора в котором гарантирует невозттость голодания, но слабый семафор такой гарантии не дает. Далее мы бутаожтто м считать, что работают сильные семафоры, поскольку они более удобны и дем с' б,чтто именно этот вид семафоров используется операционной системой. ~чт ззаимные исключения В листинге 5.7 показано простое решение задачи взаимоисключений с использгх ль.тгхванием семафора г (сравните с листингом 5.1), Пусть у нас имеется п проессов, идентифицируемых массивом Р0).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
