В. Столлингс - Операционные системы (1114679), страница 59
Текст из файла (страница 59)
Рассмотрим параллельно выполняющуюся программу с двумя проц и с(, определенными так, как показано ниже. А, Б, С, 0 и Š— произ '-" атомарные (неделимые) операторы. Предположим также, что не по здесь основная программа выполняет операцию рагЬео(г. с этиМИ;-:. процессами. Приведите все возможные чередования атомарных оп "' при работе описанных процессов. чсЫ р() ча(с с() Р Г а. Определите нижнюю и верхнюю границы окончательного значе ляемой переменной Ьа11у на выходе из приведенной программы и,. ложении, что процессы могут выполняться с любой относитель стью и что значение может быть увеличено только после того, ка:н~:" гружено в регистр отдельной машинной командой. б.
Предположим, что одновременно может выполняться произволь чество процессов (при этом остаются в силе предположения о ра граммы из предыдущего задания). Как это повлияет на границы-':, тельного значения переменной са11уу Всегда ли пережидание занятости менее эффективно (с точки зрения. сорного времени)„чем блокирующее ожиданием Поясните свой ответ.'-", Рассмотрим следующую программу: Ьсо1еаг, Ь1ссКеб(2); ~пгп, по1а Р(1гс 1а) Это решение задачи взаимных блокировок предложено в (НУМА661. Найдите контрпример, демонстрирующий некорректность данно~о решения. Интересно, что даже редакция журнала Соттип1сайолз о)' Ме АСМ сочла это решение корректным. Докажите корректность алгоритма Деккера.
а. Докажите, что при этом обеспечиваются взаимные исключения. Ъ'казакие: покажите, что когда Р1 входит в критический раздел, следующее выражение истинно: й1ад(1) апб (псе 11ау(1-1) ). б. Докажите, что процесс, запрашивающий доступ к критическому разделу„ не может быть навсегда задержан. Указание: рассмотрите следующие случаи. 1) в критический раздел пытается войти единственный процесс; 2) оба процесса пытаются войти в критический раздел и при этом 2а) и си=О и ~1ад (О) =йа1зе и 2б) ~игп=О и (1ад (0) =етые. Рассмотрим алгоритм Деккера, полученный для произвольного количества процессов путем замены выполняемой при выходе из критического раздела инструкции гыгп /* РО устанавливает г.'.3хп равным 1р а Р1 — равным О */ инструкцией — (Гогг.
+ 1) % и /" и — количество працесссв */ Проследите работу алгоритма при количестве параллельных процессов, превышающем два. Алгоритм Петерсона может быть обобщен для обеспечения взаимоисключения И процессов. Предположим, что у нас есть два глобальных массива — с и '-пгп. Начальное значение Ф элементов массива о и Ф-1 элементов массива сеж равно О.
Каждый процесс имеет локальные переменные ) и )~, используемые в качестве индексов массивов. Алгоритм 1-го процесса выглядит следуюп(им образом: Я(Ь), Ьегй(К-1); /" Глобальные массивы +/ М111е ( с гне ) Параллельные вычисления: взаимоиеключения.. (й (Х (= 1) согГ1гоеу и! 11е ( (с~(Е) >= 1) (6 (Ьогп(1) =- 1) ); /* Критический раздел I Ч(1) = 0; Ост'алькой коп При рассмотрении алгоритма значение локальной переменной у и сматривать как "стадию*' алгоритма, на которой происходит в процесса у. Глобальный массив еу указывает стадию каждого проц процесс входит в критический раздел, он переходит к стадии йу. Если ц(х1> ~у(у), мы говорим, что процесс х предшествует про находится перед ним).
Мы должны показать, что этот алгоритм обес ° взаимные исключения; ° отсутствие взаимоблокировок; е невозможность голодания. Для этого докажите следу|ощие леммы. а. Лемма 1, Процесс, предшествующий остальным, может пройти' минимум к следующей стадии. Указание: пусть в седьмой ст ' ' денного кода 1-й процесс обнаруживает, что у = ~у(1) > д(Ц для всех А ~ у .
б. Лемма 2. Когда процесс переходит от стадии у к стадии у+1, в ", в точности одно из утверждений: он предшествует всем остальным процессам„ е он не единственный на стадии у. Указание: пусть процесс 1 готов увеличить д(у1; проверьте- уравнения из предыдущей леммы при этом действии, в. Лемма 3. Если имеется по меньшей мере два процесса на стадии.
ется (как минимум) один процесс на каждой из стадий Й (1 Указание: доказывается методом индукции по у. г. Лемма 4. Максимальное количество процессов. которое может на стадии у, равно Ф вЂ” у+1. 1< у<И вЂ” 1. Указание: приме шую арифметику. д. Основываясь на леммах 1 — 4, покажите, что алгоритм обесп моисключения при отсутствии взаимоблокировок и голодания. Еще одним подходом к задаче взаимоисключений является алго ной Лампорта (1.агпрогц 11.АМР741, названный так из-за того, что на практике булочных (и других магазинов), в которых каждый ц . прн входе получает нумерованный билет, позволяющий обслужитв: купателей по очереди.
Ьоо1еап сЬооэьпд(п) у ' г.г пшэЬег(г.) у кй(1е (ггое) ( сЬооэьго(1) = алое; потЬег(1) = 1+се(:пах (гшпЬег(),г); сйооз(пя(1) = ЙВ1яеу Йог (1ггб ) = 0; ) < и; ) ь+) ( кгг(1е (сйооа1го ( ) ) ) Ф-» 1е( (попЬех (3) .'= О) 66 (почЬег(,'), ) ) < (пшпЬег(1),1) /+ Критический раздел '/ пшгЬег(1) = 0; у* Остальная часть кода Массивы сйооз1по и пш.Ьег инициализируются соответственно значениями О и ба1эе. 1-й элемент каждого массива может быть прочитан и перезаписан процессом (, но другие процессы могут только читать соответствующие значения. Запись (а.о) < (е,еу) означает (а <с) или (а =с и Ь<И).
а. Опишите алгоритм словами. о. Покажите, что данный алгоритм позволяет избежать взаимоблокировок в. Покажите, что данный алгоритм обеспечивает взаимные исключения. Покажите, что следующие программные подходы к реализации взаимоисключений не зависят от элементарных взаимоисключений на уровне доступа к памяти. а. Алгоритм булочной. б.
Алгоритм Петерсона. При использовании для реализации взаимоисключений специальных машинных команд в листинге 5.4 никакой контроль над продолжительностью ожидания доступа к критическому разделу не осуществлялся. Разработайте алгоритм, который использует команду Ьеа~эес и гарантирует, что любой процесс, ожидающий входа в критический раздел, дождется своей очереди в пределах и-1 цикла, где н — количество процессов, которые могут запросить доступ на вход в кригический раздел, а "цикл" — событие, состоящее в том, что один процесс покидает критический раздел, а другой получает право входа в него. Рассмотрим следующее определение семафоров: чо(о ка1~ (э) 1х (уйзеется по крайней мере один приостановленный сема$срам а процесс) Удалить процесс Р кз з. опепе з. ПараллЕлъные вычисления: взаимоисключения...
а . сс~~пс++» ) 'Ф Сравните это определение с приведенным в листинге 5.5. Обратите иа одно отличие: в приведенном здесь определении семафор никогда нимает отрицательное значение. Насколько это отличие влияет на':: семафора? Изменится ли работа программы, если заменить в ней се листинга 5.5 семафором из данного упражнения? ;:::4- Бинарных семафоров должно быть достаточно для реализации обоб'" семафоров. Мы можем использовать для этого операции ~а1ГВ и з1. '' два бинарных семафора, бе1ау и тогах.
Рассмотрим следующий код. )' го(б ма1Г(Веймар)»ого в) ( иа1ГВ (апет.ех); Ъ (а < О) ( иа1ГВ (лыГсх); в++; 1Х (а <= О) а19па1В(с(е1ау)г а19га1В(с~п1ех); Изначально семафор э инициализирован необходимым нам значением) операция иа1" уменьшает значение а, а з(дпа1 — увеличивает. Вина фор лэзгех, инициализированный значением 1, обеспечивает взаимные ния при обновлении значения э, а бинарный семафор с)е1ау, ный нулевым значением, использован для приостановки процесса.
В приведенном коде имеется один дефект. Найдите его и предло исправления. указание; рассмотрите ситуацию, когда два процесса ют ка1~ (з) в тот момент, когда з равно О, и сразу после того, кы~. выполнит эьдга1В(гы»;ах), НО до ъа1'ВЯе1ау), вызов ча1Г.(в) процессом дойдет до той же точки. Все, что надо сделать для Ре ставленной задачи, это переместить одну строку кода. В 1978 году Дейкстра выдвинул предположение о том, что не имеется задачи взаимных исключений неизвестного, но конечного числа про пользованием конечного числа слабых семафоров, которое позволяло бы проблемы голодания. В 1979 году Моррис (д. М.
Могг(а) опроверг это жение, опубликовав решение с использованием трех слабых семафо ритм можно описать следующим образом. Если один или несколько находятся в состоянии ожидания в операции иа1г. (э), а другой про няет операцию з1дпа1(з), то значение семафора а не изменяется и, ожидающих процессов деблокируется независимо от ваьг (э) . Кроме этих трех семафоров алгоритм использует две неотрицательные целые переменные в качестве счетчиков числа процессов, находящихся в различных разделах алгоритма.
Итак, семафоры А и В инициализированы значением 1, а семафор М и счетчики 1(А и ХМ вЂ” значением О. Семафор В обеспечивает взаимоисключения при доступе к совместно используемой переменной ЫА. Процесс, пьггающийся войти в критический раздел, должен пройти через два барьера, представленные семафорами А и М. Счетчики ИА и ХМ содержат, соответственно, число процессов, готовых пересечь барьер А и пересекших А„но еще не пересекших М. Во второй части протокола КМ процессов, заблокированных семафором М, будут входить в крити еский раздел один за другим, с использованием каскадной методики, аналогичной использованной в первой части. Напишите код алгоритма, соответствующего данному описанию. Следующая задача однажды была предложена на экзамене.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
