В. Столлингс - Операционные системы (1114679), страница 60
Текст из файла (страница 60)
Парк Юрского периода состоит из музея динозавров и безвольерного зоопарка. Имеется т пассажиров и и одноместных машин. Пассажиры некоторое время проводят в музее, а затем на машине посещают зоопарк. Если имеется свободная машина, в ней Размещается один пассажир, который совершает поездку по парку в течение некоторого (случайного) времени. Если все п машин заняты, то пассажиры, желающие посетить парк, ожидают, пока машины не освободятся.„если есть свободные машины„но нет ожидающих их пассажиров, то в состоянии ожидания находятся машины. Используйте семафоры для синхронизации т процессов пассажиров и я процессов машин.
Приведенный далее набросок кода был найден на обрывке бумаги в экзаменационной аудитории. Проверьте корректность наброска, не обращая внимания на синтаксис и отсутствие объявлений переменных. Не забывайте, что Р и:з соответствуют ~а1г и а-' дпа1. 1Ье01г.(чегЬаГ1п) геаспгсе А~газа(с Раг)".() аег~ саг -= 0 саг 1а):.ег -- 0 с-г г111ес( .= 0 разэепбег ге1еаае:1: = 0; Ргосе» а раааегдег(1 :=: 1 г,с ппгп раэзеп9ега) глас -> гар(1пГ("апбсп (100»0»'масс(ег (.1пе))) Р (саг ача( 1); у (саг са)'.еп); Р (саг 1111ес)) Р (пава»ег»яег гс1еааес() сс есб раазег»9ег Ргс .езв сад ( ~ . = 1 гс и'лп сага) со ггпс -» у(саг ача!1); Р(саг гаКеп); у(саг ~111ес)) гар (1п~ (гагссп( 1000*г1се сХте) ) ) "з(раэаепйег ге1еааюс)) сЛ =.-: С) опб апгаеэ(с Раг1 'еп ',(..егЬа11тв) В комментариях к листингу 5.8 и табл. 5.2 говорится: "Простое перемещение проверки в критический раздел потребителя недопустимо, так как может привести к взаимоблокировке*'.
Продемонстрируйте это при помощи табли- цы, аналогичной табл. 5.2. Честь 3. П е ~. Параллельные вычисления: взаимоисключения... Рассмотрим решение задачи производителя)'потребителя с бескон фером, приведенное в листинге 5.9. Предположим, что скорости ра изводнтеля и потребителя примерно одинаковы. Тогда сценарий ра жет выглядеть примерно следующим образом: Производитель: аррепс(;Йдпа1;ргос1псе;...;аррас;з)дпа1;ргос)псе;...
.ф Потребитель: сопзшпе;...;1аМ;знэз1;сопзигпе;...;1а)се;жезю;... Производитель всегда ухитряется добавлять новый элемент в буфер ~~';: лизировать об этом в тот момент, когда потребитель изымает из бу ' ' дыдущий элемент. При этом производитель всегда добавляет новьгй: ' в пустой буфер, а потребитель изымает нз буфера единственный и там элемент. Хотя потребитель никогда не блокируется семафором,'='- при этом выполняется достаточно большое количество обращений, водит к существенным накладным расходам. Разработайте новую, более эффективно работающую в этих условиях пр(~' ' Указание: позвольте и принимать значение -1, означающее, что буфер потребитель распознал это состояние буфера и заблокирован до тех производитель не добавит в буфер новые данные.
Это решение не требует"' зования локальной переменной т, которая имеется в листинге 5.9. Рассмотрите листинг 5.11. Изменится ли смысл программы при замене приведенных далее инструкций? чз а. з аьс(е) ~еаз.с (а ) б. зуцпа1 (з) э1дзза1 (и) в. иа1(. (и) катг (а) '3 г.
ззопа1 (а) з(~па1 (е) Обратите внимание, что при рассмотрении задачи про ля)потребителя с ограниченным буфером наше определение алгор лало иметь не более н-1 элемента в буфере. а. Чем вызвано данное ограничение? .Ъ) б. Измените алгоритм таким образом, чтобы исправить этот недостато.-:: Ответьте на следующие вопросы„относящиеся к алгоритму парик (листинг 5. 14). а. Обеспечивает ли разработанный код то, что плату у клиента пр парикмахер, который его стриг? б. Всегда ли парикмахер использует одно и то же кресло? В решении задачи о парикмахерской имеется ряд проблем. Изме грамму из листинга 5.14 таким образом, чтобы снять следующие вон з а. Если два или три клиента ожидают возможности расплатитьсяЁ',. может принять плату у одного клиента, но отпустить из париям, другого.
К счастью, если клиент уже вынул деньги из кармана, жет положить их обратно, и в конечном итоге в кассе окаже сумма. Тем не менее хотелось бы, чтобы из парикмахерской уход но тот клиент, чей платеж был только что принят. б. Семафор 1еаз~е Ь спа1" согласно нашей идее должен защищать попыток множественного доступа к нему. К сожалению, этот семафор".'. няет свою работу не во всех случаях. Предположим, например, что рикмахера завершили стрижку и заблокированы ма1'= (1еазте Ь сйагг) . Работа двух процессов клиентов прервана н,;. венно перед вызовом 1еа"-е ЬагЬег сЬаз. г () .
Третий клиент покид. и выполняет аз.дзза1 (1еа~е Ь сЬаьг) . Какой из парикмахеров Поскольку очередь 1еаче Ь спаьг работает по принципу "первыМ первым вышел", освободится парикмахер, заблокированный первым; 5.23. это парикмахер, стригший просигналившего клиента? Возможно — да, возможно — нет. Если нет, то новый клиент придет и усядется на колени клиенту, который уже начал подниматься с кресла. в. Программа требует, чтобы клиент сел на диван даже в том случае, когда имеется пустое кресло.
Конечно, это очень небольшая гроблема, а ее решение делает и без того сумбурный код еще более запутанным. Тем не менее попытайтесь решить ее. Эта задача демонстрирует использование семафоров для согласования гропессов трех типов.1 Дед Мороз спит в своей избушке на Северном полюсе и может быть разбужен только 1) пятью сестрами-Снегурочками, вернувшимися из отпуска из Крыма, или 2) несколькими Снеговиками, у которых возникли проблемы при изготовлении игрушек. Чтобы дать Деду Морозу поспать, Снеговики будят его только в том случае, когда проблемы возникают у троих из ннх.
Когда трое Снеговиков решат свои вопросы, все остальные Снеговики, желающие посетить Деда Мороза, должны ждать, пока не вернется побывавшая у него тройка. Если проснувшийся Дед Мороз обнаруживает у дверей избушки и Снеговиков, и последнюю из Снегурочек, то он просит Снеговиков ооождать со своими проблемами до окончания празднования Нового года, поскольку куда важнее ехать поздравлять малышей. (Снегурочки не спешат вернуться из Крыма и остаются там до последнего момента.) Прибывшая последней Снегурочка идет будить Деда Мороза, пока остальные занимаются макияжем в своих комнатах.
Решите эту задачу с помощью семафоров. Покажите, что система передачи сообщений и семафоры обладают эквивалентной функциональностью„для чего выполните следующее. а, Реализуйте передачу сообщений с использованием семафоров. Указание: сделайте это с помощью совместно используемого буфера для хранения по гговых ящиков, каждый из которых представляет собой массив сообщений.
б. Реализуйте семафоры с использованием передачи сообщений. Указание: добавьте в систему синхронизирующий процесс. ',8 аРедо '8 аризнателвн длсону Трона ( уо)за Тгоио) из колледжа св. Михаила в Вермонте едоставление этой задачи. Часть 2. : а 5 Параллельные вычисления: взаимоисключения.. 317 ГЛАВА Взаимоблоки- ровка и голодание. 6.1. Принципы взаимного блокирования 6.2. Предотвращение взаимоблокировок 6.3.
Устранение взаимоблокировок 6.4. Обнаружение взаимоблокировок 6.5. Интегрированные стратегии разрешения взаимо- блокировок 6.6. Задача об обедающих философах 6.7. Механизмы параллельных вычислений в ОХАХ 6.8. Примитивы синхронизации потоков Яо1аг$з 6.9. Механизмы параллельных вычислений в Жшйочз 2000 6.10.
Резюме, ключевые термины и контрольные вопросы 6. 11. Рекомендуемая литература 6.12. Задачи ®.=~Р а) Боаиожиа аааимоблокироака рис. 6.1. Пример взаимоблокировки б) Езаииоблокироака ре1еаве р, Часть 2. а 6. Взаимоблокировка и голодание та глава продолжает рассмотрение параллельных вычислений и и двум проблемам, доставляющим основные неприятности при работ,~.:. раллельными вычислениями: взаимоблокировкам и голоданию. Гл~ с изложения основных принципов взаимоблокировок, а затем мы ~х можно предотвратить, обнаружить и устранить.
Под конец мы р " ще одну классическую задачу, иллюстрирующую вопросы синхро юблокировки, а именно — задачу об обедающих философах. Как и в главе 5, "Параллельные вычисления. взаимоисключения и мно '*, здесь мы ограничимся рассмотрением проблем в единой системе; ам си~темам посвящена глава 14, "Управление распределенными проц Взаимное блокирование (к1еао)ос11) можно определить как посто аание множества процессов, которые либо конкурируют в борьбе за " ресурсы, либо сообщаются один с другим. В отличие от других ~кающих в процессе управления параллельными вычислениями, "' ~ема в общем случае эффективного решения не имеет. Все взаимоблокировки предполагают наличие конфликта в борьбе щь ежду двумя или несколькими процессами.
Наиболее ярким прим .лужить транспортная взаимоблокировка. На рис. 6.1 показана с -. . четыре автомобиля должны примерно одновременно пересечь пе ре квадранта перекрестка представляют собой ресурсы, которые ."ссам. В частности, для успешного пересечения перекрестка всеми '., ~томобилями необходимые ресурсы выглядят следующим образом: автомобилю, движущемуся на север, нужны квадранты 1 и 2; автомобилю, движущемуся на запад, нужны квадранты 2 и 3; автомобилю, движущемуся на юг, нужны квадранты 3 и 4; автомобилю, движущемуся на восток, нужны квадранты 4 и 1.
обычное правило пересечения перекрестка состоит в том, что ен усгупить дорогу движущемуся справа. Это правило работает, к' .сток пересекают два или три автомобиля. Например, если на пере тятся автомобили, движущиеся на север и на запад, то автомоби яйся на север, уступит дорогу автомобилю, движущемуся на запад. :ресток пересекают одновременно четыре автомобиля, каждый из сно правилу воздержится от въезда на перекресток, возникнет ака. Она возникнет и в том случае, если все четыре машины проиги.. ~ло и осторожно въедут на перекресток, поскольку при этом кажд аь захватит один ресурс (один квадрант) и останется на вечной анин, когда другой автомобиль освободит следующий требующийся, ения перекрестка квадрант.
Итак, мы опять получили взаимоблок Дословно — "мертвые обвлтил*'. Н руссколзычноб литературе встреча '*туник", "клинч", однако наиболее полно отражает суть происходя кн "взаимоблокировка". — Прим. перев. Рассмотрим теперь картину взаимоблокировки с участием процессов и системных ресурсов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
