В. Столлингс - Операционные системы (1114679), страница 61
Текст из файла (страница 61)
На рис. 6.2 показано выполнение двух процессов, конкурирующих в борьбе за два ресурса. Каждый из процессов требует исключительного владения обоими ресурсами на некоторое время. Процессы Р и Я имеют общий вид: Рхосевв Р Рхосввв Я Ф Э .2 ось х представляет выполнение процесса Р, а ось у — выполнеНа рнс. 6.2 о пМ "', "роцесса Ч, Т Ц. Таким образом, совместное выполнение двух процессов можно дстввить в ви е '", одно ат в северо-восточном рной системе в каждый момент времени может выполняться только процессо но Процесс т ц с, так что путь состоит из чередующихся горизонтальных и верти- Освобоидвни А Ве "~вазе д Получени В Получение Получение Освобождение Освобоидвние А В А В .::Ф Часть 2.
П б- Взанмоблокировка и голодание ьных отрезков„причем горизонтальные отрезки представляют работу , а вертикальные — процесса Я. Рис. 6.2. Пример взаимаблокировки ~ВАСОЯВ~ На рис. 6.2 показаны шесть различных путей выполнения процессов;-"' Я получает ресурс В, затем — ресурс А, затем освобождает ресурсьь,"': Когда процесс Р продолжает выполнение, он может получить оба Я получает ресурс В, а затем — ресурс А. Процесс Р начинает ра кируется при запросе ресурса А.
Ь) освобождает ресурсы В и А. КОФ цесс Р продолжает выполнение, он может получить оба ресурса. 'й получает ресурс В„затем Р получает ресурс А. Взаимоблокирав бежна, поскольку выполнение ц заблокируется при запросе выполнение процесса Р— при запросе ресурса В. Р получает ресурс А, затем Я получает ресурс В. Взаимоблокиров бежна, поскольку выполнение Я заблокируется при запросе рес выполнение процесса Р— при запросе ресурса В. Р получает ресурс А., а затем — ресурс В.
Процесс Я начинает работ)~. кируется при запросе ресурса В. Р освобождает ресурсы А и В. цесс Я продолжает выполнение, он может получить оба ресурса. Р получает ресурс А, затем — ресурс В, затем освобождает ресурсы А и В. Когда процесс Я продолжает выполнение, он может получить оба ресурса. Произойдет взаимоблокировка или нет, зависит как от динамики выполнения процессов, так и от подробностей построения приложения. Предположим, „пример, что процесс Р не требует получения обоих ресурсов одновременно и ~ест следующий вид: ргосева Р Эта ситуация изображена на рис.
6.3. Немного поразмыслив, вы можете Убедиться, что независимо от того, каким образом два процесса выполняются друг относительно друга, взаимоблокировка невозможна. ПОВ'горно используемые ресурсы Ресурсы можно разделить на две основные категории: повторно используемые (гецзаЫе) и расходуемые (сопзшпаЫе). Повторно используемые ресурсы моби~опасно использоваться одновременно только одним процессом и при этом гут безо не ист истощаться. Процесс получает ресурс, который позже освобождает для повтор„ог Рного использования другими процессами.
Примерами повторно используемых Р~~урсов могут служить процессор, каналы ввода-вывода, основная и вторичная и как я память, периферийные устройства, а также структуры данных — такие, файлы, базы данных и семафоры. Выполнение О Осеобототение А В ° ю е ° ° 4 еееее е фЬ ;Ф':: требуетс А Процессам РиО требуется А Процессам РиО требуется В олунение А $ я ееея аеее Полунение Осеобоядение Полунение Освобождение А А В В РаОХОДУЕМЫЕ РЕСУРСЫ В качестве примера взаимоблокировки с повторно используемым осмотрим два процесса, которые конкурируют за исключительный ' :сковому файлу 0 и стримеру Т.
Программа выполняет показанные н": ерации. Взаимоблокнровка осуществляется в том случае, когда к сс захватывает один ресурс и запрашивает другой. Например, вз вка произойдет нри следующем чередовании двух процессов: РортчоЯ .т показаться, что это ошибка программиста, не имеющая отношени~~ тчику операционной системы. Однако, как мы знаем, разработка '' :я параллельных вычислений — весьма сложная задача, и выявленич.", . взаимоблокировки в сложной программе — дело очень непростое,,:. ратегнй при работе с такими взаимоблокировками состоит в налоясеу мных ограничений на порядок запроса ресурсов. Процесс Ч Действие Процесс Р Действие Шаг Шаг Яо Чт ча чэ Ча Яа .'с. 6.4. Пример конкуренции двух процессов в борьбе эа повторно используеМьт .
Часть 2.:;. я 6. Взаимоблокировка и голодание :с. 6Л. Пример отсутствия ваоимоблокировки т ВАСОР83 Запрос(Т) БлокировкаЩ Запрос(Ю) Блокировка(В)-., Выполнение Ф *е Дебло кирова Деблокиров Другим примером взаимоблокировки с повторно используемыми ресурсами орут быть запросы к основной памяти. Предположим, что для распределения тупно 200 Кбайт памяти„ и выполняется такая последовательность запросов: Если оба процесса дойдут да своего второго запроса, возникнет взаимоблокировка. Если количество требуемой памяти заранее неизвестно, работать с таким типом взаимоблокировок на уровне системных ограничений (в том числе и операционной системы) очень сложно.
Наилучший способ справиться с этой конкретной проблемой заключается в использовании виртуальной памяти, о которой рассказывается в главе 8, "Виртуальная память". Расходуемыми являются те ресурсы, которые могут быть созданы (произведены) и уничтожены (потреблены). Обычно ограничений на количество расходуемых ресурсов определенного типа нет. Незаблокированный процесс- производитель может выпустить любое количество таких ресурсов; когда процесс запрашивает некоторый ресурс, последний прекращает свое существование. Примерами расходуемых ресурсов могут служить прерывания, сигналы, сообщения н информация в буферах ввода-вывода. В качестве примера взаимоблокировки с расходуемыми ресурсами рассмотРим следующую пару процессов, где каждый из процессов пытается получить сообтттеттие от другого процесса, а затем отправить сообщение своему визави.
зтттттттоблокировка осуществляется, если операция Ресехтте является бло- Рюшей (т.е. получающий процесс блокируется до тех пор, пока сообщение не буд + Разр, б. "оттучено). И вновь причиной взаимоблокировки является ошибка при уловимы Работке программы. Такие ошибки обычно довольно таинственны н трудно:доста „„ Кроме того, может оказаться, что взаимоблокировку вызывает только точно редкая комбинация событий, и тогда до того, как ошибка проявит Я„п " программа может побывать в эксплуатации многие годы, Е ~ной эффективной стратегии для работы со всеми типами вз дино" эк нет. ет.
Позже мы изучим различные подходы к решению проблемы, а рассмотрим условия возникновения взаимоблокировок. ловия возникновения взаимоблокировок для того чтобы взаимоблокировка стала возможной, требуется н . х у~лоций. ~~~ючения. Одновременно использовать один процесс. Удержание и ожидание. Процесс может удерживать выделенные ре время ожидания других ресурсов.
, Отсутствие перераспределения. Ресурс не может быть принудител бран у удерживающего его процесса. Эти условия выполняются довольно часто. Например, взаимоио ~ необходимы для гарантии согласованности результатов и цел ы данных. зь налогично.
невозможно произвольное применение .деления, в особенности при работе с данными, когда требуется обе ' ~анизм отката. Кроме перечисленных трех условий для реального осуществления,- кировки требуется выполнение четвертого условия. Циклическое ожидание. Существует замкнутая цепь процессов, к которых удерживает как минимум один ресурс, необходимый следующему в цепи после данного (см.
Рис. б.б), Рис. 6.5. Циклическое ожидание Первые три условия являются необходимыми, но не достаточи ществления взаимоблокировки. Четвертое условие в действительн вляет собой потенциальное следствие первых трех — т.е. при наличии х Условий может осуществиться такая последовательность событий* ~веДет к неРазрешимомУ циклическомУ ожиданию (что, по сУти, и Я.ч )еделением взаимоблокировки). Неразрешимость циклического ож 1овия 4 обеспечивается выполнением предыдущих трех условий. Та и, совокупность четырех перечисленных выше условий является необходимым и достаточным условием взаимоблокировки.з :6.2.
Предотврлщение взлимовлокировок Стратегия предотвращения по сути представляет собой такую разработку истомы, которая позволит исключить саму возможность взаимоблокировок. ) тоды предотвращения взаимоблокировок можно разбить на два класса. Косвенный метод состоит в предотвращении одного из первых трех условий возникновения взаимоблокировки; прямой метод предотвращает циклическое ожидание (условие 4). Рассмотрим приемы, связанные с каждым из условий, в отдельности. цзаимоисключения В общем случае избежать использования взаимоисключений невозможно. Если доступ и ресурсу должен быть исключительным„то операционная система обязана поддерживать взаимоисключения. Некоторые ресурсы, такие, как файлы, могут позволять множественный доступ для чтения и исключительный доступ для записи.
Но даже в этом случае возможно возникновение взаимоблокиРовки, если право записи в файл требуется нескольким процессам одновременно. Удерлсание и ожидание Этого условия можно избежать, потребовав, чтобы процесс запрашивал все необходимые ресурсы одновременно, и блокировать процесс до тех пор, пока такой запрос не сможет быть выполнен полностью в один и тот же момент времени. Такой подход неэффективен по двум причинам. Во-первых, процесс может длительное время ожидать одновременной доступности всех затребованных ресурсов, в то время как реально он мог бы работать и только с частью из них. Вов~орых, затребованные процессом ресурсы могут оставаться неиспользуемыми ~начительное время, в течение которого они оказываются недоступными другим процессам, Еще одна проблема состоит в том, что процессу может не быть известно заранее, какие именно ресурсы ему потребуются.
Имеется также практическая проблема, возникающая при использовании "и парадигмы модульности в программировании. Использующее описанную техно ехнологию приложение для одновременного запроса должно знать о всех необ, об -одимых ресурсах на всех уровнях или во всех модулях, что противоречит т упомянутой парадигме. г О Обычна в литературе все четыре условия. перечисляюп1ся как необходимые для осу~ ' твления взаимаблакиравки, однако такое изложение скрывает некоторые тон. иост личает данного вопроса (ЯНБВ90Х.
Условие циклического ожидания кардинально ат. сути ся от остальных грех условий. ХХервыс три исловия представляют собой, по езыблемые правила, в та время как условие 4 представляет сабои ситуацию. таран ма . вабал ден„,-, мажет осуществиться при определенной последовательности запросов и ас- ,- д "ний ресурсов процессом, Объединение все четырех условии в единый блок метало и, "'вв ески приводит к стиранию различий между предотвращением и устранением , ваимоб Часть 2. ,-.вва б Взаимоблокировка и голодание 327 тсутствие перераспределении '.у"': етого условия можно избежать несколькими путями. Например, и Унять следующим образом. если процесс удерживает некоторые ресурс казано в очередном запросе, то он должен освободить захваченные ,и необходимости запросить их вновь вместе с тем ресурсом, в доступе,' м~ ему было отказано.
С другой стороны. если процесс затребовал не рс, в настоящий момент захваченный другим процессом, то операциона' ма может вытеснить этот процесс и потребовать от него освободить з: ~е им Ресурсы. Этот метод может предотвратнть взаимоблокировку ла учае, когда процессы имеют разные приоритеты. Такой подход на практике применим только к тем ресурсам, сос рых можно легко сохранить, а позже восстановить — как, например.р учае, когда ресурс представляет собой процессор. ;иклическое ожидание Условия циклического ожидания можно избежать путем упорядо в ресурсов При этом если процесс запросил ресурс типа В, то далее просить только ресурсы, следующие согласно указанному упорядоче Чтобы убедиться в эффективности данной стратегии, свяжем с к ~м ресурса свой индекс.
Тогда ресурс В; предшествует ресурсу Вн перь предположим, что два процесса, А и В, взаимно заблокиро ольку процесс А захватил ресурс В, и запрашивает ресурс В,, а проц ' атил ресурс В, и запрашивает ресурс В,. Однако такая ситуация невоз лу того что из нее следует одновременное выполнение условий г с ~ и ": Как и в случае предотвращения удержания и ожидания, технол; ~твращения циклического ожидания может оказаться неэффективно, ающей скорость работы процесса и закрывающей доступ к ресурсам б, ' ~ то необходимости. ьЗ. 'УСТРАНЕНИЕ ВЗАИМОБЛОКИ- Другим подходом к решению проблемы взаимоблокировок является у, анмоблокировок.з В случае предотвращения взаимоблокировок мы ~релеленные ограничения на запросы к ресурсам, с тем чтобы сделать зм осуществление по крайней мере одного из необходимых условий с аимоблокировок и тем самым предотвратить саму возможность их воз сожалению, этот метод приводит к неэффективному использованию .иженню скорости работы процесса.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
