В. Столлингс - Операционные системы (1114679), страница 65
Текст из файла (страница 65)
~. ~ЕХАНИЗМЫ ПАРАЛжл ~')або~,~з 2ООО (Ж2К) обеспечивает синхронизацию потоков как часть объ- уры. Механизм, использованный Ж2К для реализации синхро- н"й архитект запив, и р дставляет собаи семейство следующих объектов синхронизации. Праце~ с Патон. Файл Кан нсольный ввод. Ув 'лам 'л мление об изменении Файлов. "" ° ~~л. ьвтекс Яасть 2. 6. и ° Взаимоблокировка и голодание 11ОЧЕВЫЕ ТЕРМИНЫ Перераспределение Повторно используемый ресурс Предотвращение вэаимоблокировок Расходуемый ресурс , оритм банкира имное исключение .имоблокировка ~оданпе саружение ~заимоблокировок Удержание и ожид Устранение вэаимоблокировоф" ,' Циклическое ожид" ' Л1.
РЕКОМЕНДУЕМАЯ ЛИТБРА~, ' Особый интерес представляет классическая статья 1НО1 Т72], посвя ' симоблокировкам, так же как и работа 1СОГГ71]. Неплохой обзор пс1" ее можно найти в 11Б).О80] и 1В1М198]. Обнаружению взаимоблокира мощена работа 1СОВВ96]. Механизмы синхронизации в ()Х1Х ЯЧВ4, Яо1аг1в 2.х и Ж1пс)оэсв,„ статочно полно описаны, соответственно, в 1ОВА'с 97], 1ОВАН9 ] АН95] и ~К1 ОГР71 СоХХспап Е., Е1рЫс)с М., ЯЬовЬапй А. Яувсепс Веас))ос)св.
— Солс 1'ипе 1971. ОКВ96 СогЬесс д. Еча1ссайпд Веас))ос)с Весесс(оп Мелос)в Хог ЯоХтэсаге. — ХЕЕЕ Тгалзассшиз ои ЯоХХшате Епаьпеег(пк. МагсЬ 199п-. ~1М198 В)пйто81оп О. Веас)1ос)св апс) Мелос)в Хог ТЬе(г Внес((оп, Рг Весочегу 1п Мос)егп Орега11пд Яув$еспв, — Орега((пя Яузселм Веосесз ЧЗ, . Уог)с.',. 1КАН95 ОгаЬасп Л. Яо1агХз 2.х: Хпсегпа(з апсХ АгсИ|ессиге. — Хейг зог,: Н111, 1995. 1КАу97 Огау Л.
Хпсегргосезз Соттил(еас)опз Хл УХХХс ТХзе, И;. Огапл1ез. — 1)ррег Яас)с)1е Вюег, Ь(д: Ргепс1се На11, 1997, 1О1Л72 Но)С В. Яоп1е ВеасЫос)с Ргорегс(ев оХ Сосарпсег Яувсегав. — Сотри БерсегпЬег 1972. ' зз Б1О80 1в1оог Б., Магв1апс) Т. ТЬе ВеасЦос1с РгоЬ)епп Ап Очегч1ею. — ','. ЯерсеспЬег 1980. ПСН97 В1сЫег д. АсХиаисес$ ъу(исХоиа. — Кес(пюпс), %'А: М(сговоХ1 Ртсб(с «нтрольные вопросы 1.1. Приведите примеры расходуемых и повторно используемых ресурсо "-' 1.2. Какие три условия являются необходимыми для осуществления блокировки? э.З. Выполнение каких четырех условий приводит к возникновению блокировки? э.4. Каким образом можно предотвратить условие удержания и ожида 3.5. Перечислите два способа предотвращения условия отсутствия пе деления.
6.6. Каким образом можно предотвратить циклическое ожидание? 6.7. В чем заключается разница между предотвращением, обнаружа' устранением блокировок? Текущее распределение г1 г2 гЗ Максимальные Требуется требования г4 г1 г2 гЗ г4 г1 г2 гЗ г4 Процесс 91 р2 рЗ р4 р5 а, Определите, какие ресурсы может запросить каждый из процессов, и заполните столбцы "Требуется*' таблицы. б, В каком состоянии — опасном или безопасном — находится система в настоящий момент? Обоснуйте свой ответ.
в. Заблокирована система в настоящий момент или нет? Обоснуйте свой ответ. г. Какой процесс (если таковой имеется) находится в состоянии взаимоблокировки (или может быть заблокирован)? л. Если процессом рЗ будет выполнен запрос (0,1,0,0), безопасно ли его немедленное удовлетворение? В каком именно состоянии окажется система после его немедленного удовлетворения? Какие процессы (если таковые имеются) окажутся (или могут оказаться) заблокированными при немедленном удовлетворении этого запроса? Примените алгоритм обнаружения взаимоблокировки из раздела 6.4 к приведенным данным. Доступность = (21001, 2001 1 0010 Требования = 1010 1, Распределение = 2001 2100 1 0120 6.5. С"стема буФеризации, представленная на рис. 6.10, состоит из процесса ввода ° по-ьэовательского процесса Р и процесса вывода О, соединенных с двумя бу ье уФерами, Процессы обмениваются блоками данных одинакового размера, корме оуФеризуются на диске; граница между входным и выходным буФерами линами "эмическая, зависящая от скорости работы процессов.
Используемые пропессам сами примитивы гарантируют выполнение условия !+о < шах, где ""~~ — максимальное количество блоков на диске; количество входных блоков на диске; — количество выходных блоков на диске. "' %У Опишите каждый из шести приведенных на рис. 6.3 путей так же, как это сделано для рис. 6.2 в разделе 6.1.
Кэк указывалось, в ситуации, изображенной на рис. 6.3, взаимоблокировка возникнуть не может. Обоснуйте это утверждение. Рассмотрим следующее состояние системы, в котором в данный момент не имеется никаких очередей неудовлетворенных запросов. Доступно г1 г2 гЗ г4 'Часть 2. б Взаимоблокировка и голодание О работе процессов известно следующее. 1. Пока система производит данные, процесс 1 записывает их на па диске имеется свободное место). 2. Пока на диске имеются входные данные, процесс Р считывает ит(1 каждого считанного блока выводит некоторое конечное колич ных (если на диске имеется свободное место).
3. Пока на диске имеются выходные данные. процесс О считывает Покажите, что в этой системе может возникнуть взаимоблокировка. Входной Р Выходной бУФер буФеР Рис. 6.10. Система буферизации Предложите дополнительное условие использования ресурсов, которое,:..' вращает взаимоблокировку в задаче 6.5, но при этом разрешает пе границы между входным и выходным буфером в зависимости от ' " нужд процессов. Во многозадачной системе ТНЕ 101ТК681 барабан (предшественник дисков) разделен на входные буферы, рабочую область и выходные:= подвижными границами, зависящими от скорости работы процессов=.'-"., состояние барабана можно охарактеризовать следующими парамет тах — максимальное количество страниц на барабане; т' — количество входных страниц на барабане; р — количество страниц рабочей области на барабане; о — количество выходных страниц на барабане; геэо — минимальное количество страниц, зарезервированных для в гезр — минимальное количество страниц, зарезервированных для р Сформулируйте ограничения, которые должны быть наложены на тем чтобы гарантировать, что не будет превышена емкость барабана, выходных данных и рабочей области постоянно зарезервировано и количество страниц.
1 В многозадачной системе ТНЕ возможны следующие переходы ме ниямн страницы. 1. Пустая х входной буфер (ввод данных). 2. Входной буфер — ~ рабочая область (использование яви, . 3. Рабочая область -+ выходной буфер (вывод данных) 4. Выходной буфер — х пустая (использование в 5. Пустая -+ рабочая область (Вызов процедуры) "'е 6. Рабочая область — ~ пустая (возврат из проц а.
Опипште действие этих переходов в терминах величин т, о и Р. б. Пусть процесс ввода, пользовательский и процесс вывода подчин виям задачи 6.5. Может ли в таком случае один из них привес™х.', ной блок ировкеу Рассмотрим систему с общим количеством памяти, равным 150 распределенным между процессами следующим образом: Процесс Максимум Получено 1 70 45 2 60 40 3 60 15 Примените алгоритм банкира для определения того, безопасно ли удовлетворение описанных ниже запросов, и если да — то укажите соответствующую последовательность завершения работы процессов. а.
Начинает работу четвертый процесс с максимальными требованиями к памяти, равными 60 единицам, н начальным запросом на 25 единиц памяти. б, Начинает работу четвертый процесс с максимальными требованиями к памяти, равными 60 единицам, и начальным запросом на 35 единиц памяти. Оцените применимость алгоритма банкира в реальной жизни. Алгоритм конвейера реализован таким образом, что поток элементов данных типа Т, производимых процессом Р„, проходит через последовательность процессов Р„ Р, ..., Р„„обрабатывающих проходящие данные в указанном порцдке. а, Определите обобщенный буфер сообщений, который содержит все частично использованные элементы данных, и разработайте алгоритм работы процесса Р„О <1< л — 1. Алгоритм должен иметь следующий вид: хереаг Получение информации от предшественннкат Использование полученного элементах Послать инФормацию преемнику; тоге"ех 6.10.
6 11. Для простоты считаем, что процесс Ра получает пустые элементы данных, посылаемые ему процессом Р„,. Разработанный алгоритм должен позволять процессу работать непосредственно с сообтцениями, хранящимися в буфере, не выполняя копирования элементов данных. б. Покажите, что. несмотря на работу с общим буфером, взаимоблокировка процессов в этой ситуации невозможна. быть распределены и освобождены только в отдельности.
Каждому процессу требуется не более двух единиц ресурса. Покажите, что взаимоблокировка при этом невозможна. б. М процессов совместно используют М единиц ресурса, которые могут быть распределены и освобождены только по одной единице одновременно.
Максимальное требование каждого из процессов не превышает М единиц, причем сумма максимальных требований процессов меньше, чем Ф+М. Покажите, что взаимоблокировка при этом невозможна. Рассмотрим следующие способы работы с взаимоблокировками. 1 Алгоритм банкира. 2. Обнаружение взаимоблокировки и прекращение работы потока с освобождением всех ресурсов. 3* Резервирование всех ресурсов заранее. 4. Перезапуск потока и освобождение всех ресурсов„если поток должен находиться в состоянии ожидания. 5.
упорядочение ресурсов. 6. Обнаружение взаимоблокировки и откат потока. Одним из критериев оценки различных подходов к проблеме блокироВки является оценка максимальной допустимой параллельности вычислений, иными словами, какой из методов гюзволяет работать наибольшему количеству потоков ез ожидания и возникновения взаимоблокировок? упорядочьте перечисленные р~нее методы борьбы с взаимоблокировками в порядке уменьшения обеспечиваемой ими степени параллельности и прокомментируйте ваше решение. 6.13, 6.12.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
