Методы борьбы с тупиками
В настоящее время выделяются следующие основные подходы к проблеме борьбы с тупиками [,] :
n обнаружение и последующее восстановление *).
Перечисленные подходы являются универсальными и применяются как в системах с общей так и с раздельной памятью []. В каждом из типов систем имеются свои особенности реализации данных методов.
5.4.1 Предотвращение тупиков
Методы предотвращения тупиков (или как иногда говорят, самозамыкания) связаны с устранением одного или нескольких условий для их возникновения. Данный подход получил название стратегии Ханвендера, который в своей работе [] показал, что возникновение тупика не возможно, если нарушено хотя бы одно из четырех необходимых условий.
Существует три основных способа предотвращения тупиков согласно этой стратегии [,,].
При первом способе, называемом опережающим требованием, все потенциально необходимые ресурсы запрашиваются одновременно. До запроса процесс не должен удерживать какие-либо ресурсы. Система предоставляет процессу запрашиваемые ресурсы или переводит его в состояние ожидания. Тем самым устраняется условие ожидания дополнительных ресурсов.
Этот способ имеет очевидные недостатки: во-первых, он приводит к неэффективному использованию ресурсов, так как ресурсы могут удерживаться процессом задолго до их реального использования или вообще могут не потребоваться процессу в текущей реализации, во-вторых, этот путь приводит к бесконечному откладыванию.
Процесс может быть разделен на несколько задач, которые выполняются относительно независимо друг от друга. В этом случае ресурсы выделяются для каждой задачи в отдельности. Это позволяет несколько сократить «простой» ресурсов, но требует более интенсивной работы менеджера ресурсов. Кроме того процесс может периодически требовать ресурсы, использовать их и возвращать затем все занятые ресурсы системе.
Второй способ реализуется путем упорядочения ресурсов и иногда называется иерархическим распределением [md]. Ресурсы делятся на классы, каждому из которых присваивается номер. Процессы могут запрашивать ресурсы только строго с большими номерами, чем те которые они удерживают. Этот способ устраняет четвертое условие, а именно круговое ожидание. На рис. 5.2 показана именно такая ситуация. Если поместить две единицы ресурса в разные классы 1 и 2, то процесс p1, получивший ресурс с номером 1 может запросить только ресурс с номером 2, в то время как второй процесс p2 переводится в состояние ожидания 1-го ресурса. После того как первый процесс освободит первый ресурс, его получит второй процесс и запросит ресурс с номером 2 и, если он еще занят, перейдет в состояние ожидания 2-го ресурса, до его освобождения первым процессом.
Назначаемые номера ресурсов должны отражать наиболее вероятный порядок использования ресурсов. Обычно дефицитным ресурсам присваиваются большие номера.
Данный подход так же является недостаточно гибким. Вследствие невозможности получения ресурса с маленьким номером без предварительного возвращения системе ресурсов с большими номерами процессы должны запрашивать ресурсы с маленькими номерами задолго до фактической потребности в них. Некоторые процессы блокируются в очереди за процессами, которые реально еще долго им не понадобятся, но они вынуждены их запрашивать, чтобы соблюсти искусственно установленный для них порядок запросов на ресурсы.
Третий способ устраняет условие неперераспределяемости ресурсов. Если процесс в результате сделанного запроса не может получить нужный ему для продолжения выполнения ресурс, то он останавливается и все или часть занятых им ресурсов отбирается. При этом процесс теряет всю или часть сделанной им работы. Способ является простым, но может привести к бесконечному откладыванию (indefinite postponement) , выражающемуся в том, что процесс может многократно запрашивать и возвращать один и тот же ресурс [дтл]. Если выполнение такого процесса не отложить, переведя его в состояние блокировки, то это приведет к непроизводительному растрачиванию вычислительных ресурсов и резкому падению производительности системы. Откладывание или блокировка подобных процессов может оказаться слишком длительной. Процесс «зависнет» в системе.
5.4.2 Недопущение или обход тупиков
Алгоритмы недопущения или обхода тупиков можно назвать алгоритмами опережающего требования. Тупики возможны и задача состоит в таком распределении, которое не приведет к тупиком ситуациям. Требования процессов на ресурсы анализируются по специальным алгоритмам и, если ситуация безопасна относительно тупика, ресурсы выделяются.
Наиболее известным алгоритмом подобного типа является, так называемый, алгоритм банкира, предложенный Дейкстра []. Алгоритм выполняет действия аналогичные действиям банкира, имеющего некоторый капитал наличных денег. Эти деньги банкир хочет ссудить в долг на некоторый срок. Заемщики часто вынуждены брать дополнительную ссуду, чтобы вернуть хоть что-то. Заимодавец должен быть достаточно осмотрительным и так распределять кредиты, чтобы заемщики смогли вернуть ему деньги, и в то же время достаточно гибким, чтобы дать как можно больше кредитов.
В качестве банкира выступает менеджер ресурсов. Заемщики — процессы делают заявки на ресурсы. Заявки отражают максимальную потребность процессов в ресурсах данного класса. Процесс не может затребовать ресурсов больше, чем указано в заявке. Это позволяет менеджеру ресурсов проводить предварительный анализ возникающей ситуации и не допускать возникновение тупика.
Текущее распределение ресурсов может быть описано следующим образом:
Hold:array [1..n] of Process_Resource_State;
Число процессов фиксировано. Число ресурсов фиксировано. Для осуществления распределения необходимо выполнение следующих условий:
1) процесс не может требовать больше ресурсов, чем имеется в системе;
2) процесс не может получить ресурсов больше, чем указано в требовании (заявке);
3) сумма всех полей Held, отражающая количество распределенных ресурсов данного класса, не может превышать суммарного количества единиц ресурса в системе.
Менеджер ресурсов гарантирует, что тупиковая ситуация не наступит. Каждое требование проверяется по отношению к количеству ресурсов в системе, а каждый запрос проверяется относительно суммы всех заявок на ресурс. Менеджер ресурсов ищет последовательность процессов, которая может завершиться. Если такая последовательность есть, то система не находится в тупике.
Рассмотрим пример. На рис.5.4 а) показано текущее распределение единиц ресурса одного
Показанное на рис.5.4.а) состояние распределения является надежным или безопасным относительно тупика, так как здесь имеется последовательность процессов 2, 1, 3, которая может завершиться. Действительно, процесс 2 не может запросить больше двух единиц ресурса. Система имеет две свободные единицы и процесс 2 может завершиться. Завершившись процесс 2 вернет системе 5 единиц, которые затем могут быть выделены процессу 1 ( максимальная потребность которого — 4 ). Завершившись первый процесс освободит 4 единицы. Потребность третьего процесса в дополнительных единицах ресурса не превышает четырех единиц и он также может завершиться.
Однако, если текущее состояние надежно, это не значит, что все последующие состояния будут надежными. Например, если система из состояния, показанного на рис.5.4.а) перейдет в результате удовлетворения запроса первого процесса на одну единицу ресурса в состояние, показанное на рис.5.4.б), то она перейдет из надежного в ненадежное состояние. В новом состоянии нельзя гарантировать успешного завершения всех процессов. В этом состоянии отсутствует последовательность процессов, которые могут гарантированно завершиться.
Ненадежное состояние не обязательно приведет к тупику. Процессы могут не запроситть максимально заявленного количества единиц ресурса.
Итак, формально состояние является безопасным, если существует последовательность процессов такая что:
1) первый процесс в последовательности обязательно завершится, так как даже, если он запросит максимально заявленное количество единиц ресурса у системы имеется необходимое количество единиц для удовлетворения запроса;
2) второй процесс может завершиться, если первый завершится и вернет системе все занятые им единицы ресурса, что в сумме со свободными единицами позволит удовлетворить максимальную потребность второго процесса;
3) i-ый процесс в последовательности может завершиться, если все предыдущие процессы успешно завершатся и сумма освобожденных и свободных ресурсов сможет удовлетворить максимальную потребность процесса в данном ресурсе.
Таким образом, всякий раз, когда процесс делает новый запрос, менеджер ресурсов должен найти успешно завершающуюся последовательность процессов и только в этом случае запрос может быть удовлетворен. Необходимо исследовать n! последовательностей прежде, чем признать состояние безопасным. Затраты могут быть снижены пропорционально n², если отказаться от необходимости выделять запрашиваемые ресурсы согласно порядку следования в безопасной последовательности распределения.
Алгоритм называется O(n²), где O означает «order of», и работает следующим образом:
S = количество процессов;
найти процесс А в последовательности S, который может завершиться;
если нет, то состояние небезопасное — вывести процесс А из S, отобрать
у А ресурсы и добавить их пул
В этом случае ресурсы распределяются в порядке следования запросов до тех пор, пока имеется некоторая безопасная последовательность после каждого удовлетворенного запроса.
Еще менее затратный алгоритм был предложен Хаберманом []. Менеджер ресурсов поддерживает массив S[0..r-1], где r — число единиц ресурса.
Источник
Тупики
Введение
В предыдущих лекциях мы рассматривали способы синхронизации процессов, которые позволяют процессам успешно кооперироваться. Однако в некоторых случаях могут возникнуть непредвиденные затруднения. Предположим, что несколько процессов конкурируют за обладание конечным числом ресурсов . Если запрашиваемый процессом ресурс недоступен, ОС переводит данный процесс в состояние ожидания. В случае когда требуемый ресурс удерживается другим ожидающим процессом, первый процесс не сможет сменить свое состояние. Такая ситуация называется тупиком (deadlock) . Говорят, что в мультипрограммной системе процесс находится в состоянии тупика , если он ожидает события, которое никогда не произойдет. Системная тупиковая ситуация , или «зависание системы», является следствием того, что один или более процессов находятся в состоянии тупика . Иногда подобные ситуации называют взаимоблокировками . В общем случае проблема тупиков эффективного решения не имеет.
Рассмотрим пример. Предположим, что два процесса осуществляют вывод с ленты на принтер. Один из них успел монополизировать ленту и претендует на принтер, а другой наоборот. После этого оба процесса оказываются заблокированными в ожидании второго ресурса (см. рис. 7.1).
Определение. Множество процессов находится в тупиковой ситуации , если каждый процесс из множества ожидает события, которое может вызвать только другой процесс данного множества . Так как все процессы чего-то ожидают, то ни один из них не сможет инициировать событие, которое разбудило бы другого члена множества и, следовательно, все процессы будут спать вместе.
Выше приведен пример взаимоблокировки , возникающей при работе с так называемыми выделенными устройствами. Тупики , однако, могут иметь место и в других ситуациях. Hапример, в системах управления базами данных записи могут быть локализованы процессами, чтобы избежать состояния гонок (см. лекцию 5 «Алгоритмы синхронизации»). В этом случае может получиться так, что один из процессов заблокировал записи, необходимые другому процессу, и наоборот. Таким образом, тупики могут иметь место как на аппаратных, так и на программных ресурсах .
Тупики также могут быть вызваны ошибками программирования. Например, процесс может напрасно ждать открытия семафора, потому что в некорректно написанном приложении эту операцию забыли предусмотреть. Другой причиной бесконечного ожидания может быть дискриминационная политика по отношению к некоторым процессам. Однако чаще всего событие, которого ждет процесс в тупиковой ситуации , – освобождение ресурса , поэтому в дальнейшем будут рассмотрены методы борьбы с тупиками ресурсного типа.
Ресурсами могут быть как устройства, так и данные. Hекоторые ресурсы допускают разделение между процессами, то есть являются разделяемыми ресурсами . Например, память , процессор , диски коллективно используются процессами. Другие не допускают разделения, то есть являются выделенными, например лентопротяжное устройство. К взаимоблокировке может привести использование как выделенных, так и разделяемых ресурсов . Например, чтение с разделяемого диска может одновременно осуществляться несколькими процессами, тогда как запись предполагает исключительный доступ к данным на диске. Можно считать, что часть диска, куда происходит запись , выделена конкретному процессу. Поэтому в дальнейшем мы будем исходить из предположения, что тупики связаны с выделенными ресурсами , то есть тупики возникают, когда процессу предоставляется эксклюзивный доступ к устройствам, файлам и другим ресурсам .
Традиционная последовательность событий при работе с ресурсом состоит из запроса, использования и освобождения ресурса . Тип запроса зависит от природы ресурса и от ОС. Запрос может быть явным, например специальный вызов request, или неявным – open для открытия файла. Обычно, если ресурс занят и запрос отклонен, запрашивающий процесс переходит в состояние ожидания.
Далее в данной лекции будут рассматриваться вопросы обнаружения, предотвращения, обхода тупиков и восстановления после тупиков . Как правило, борьба с тупиками – очень дорогостоящее мероприятие. Тем не менее для ряда систем, например для систем реального времени, иного выхода нет.
Условия возникновения тупиков
Условия возникновения тупиков были сформулированы Коффманом, Элфиком и Шошани в 1970 г.
- Условие взаимоисключения ( Mutual exclusion ). Одновременно использовать ресурс может только один процесс.
- Условие ожидания ресурсов (Hold and wait). Процессы удерживают ресурсы , уже выделенные им, и могут запрашивать другие ресурсы .
- Условие неперераспределяемости (No preemtion). Ресурс , выделенный ранее, не может быть принудительно забран у процесса. Освобождены они могут быть только процессом, который их удерживает.
- Условие кругового ожидания ( Circular wait). Существует кольцевая цепь процессов, в которой каждый процесс ждет доступа к ресурсу , удерживаемому другим процессом цепи.
Для образования тупика необходимым и достаточным является выполнение всех четырех условий.
Обычно тупик моделируется циклом в графе, состоящем из узлов двух видов: прямоугольников – процессов и эллипсов – ресурсов , наподобие того, что изображен на рис. 7.1. Стрелки, направленные от ресурса к процессу, показывают, что ресурс выделен данному процессу. Стрелки, направленные от процесса к ресурсу , означают, что процесс запрашивает данный ресурс .
Основные направления борьбы с тупиками
Проблема тупиков инициировала много интересных исследований в области информатики. Очевидно, что условие циклического ожидания отличается от остальных. Первые три условия формируют правила, существующие в системе, тогда как четвертое условие описывает ситуацию, которая может сложиться при определенной неблагоприятной последовательности событий. Поэтому методы предотвращения взаимоблокировок ориентированы главным образом на нарушение первых трех условий путем введения ряда ограничений на поведение процессов и способы распределения ресурсов . Методы обнаружения и устранения менее консервативны и сводятся к поиску и разрыву цикла ожидания ресурсов .
Итак, основные направления борьбы с тупиками :
- Игнорирование проблемы в целом
- Предотвращение тупиков
- Обнаружение тупиков
- Восстановление после тупиков
Игнорирование проблемы тупиков
Простейший подход – не замечать проблему тупиков . Для того чтобы принять такое решение, необходимо оценить вероятность возникновения взаимоблокировки и сравнить ее с вероятностью ущерба от других отказов аппаратного и программного обеспечения. Проектировщики обычно не желают жертвовать производительностью системы или удобством пользователей для внедрения сложных и дорогостоящих средств борьбы с тупиками .
Любая ОС, имеющая в ядре ряд массивов фиксированной размерности, потенциально страдает от тупиков , даже если они не обнаружены. Таблица открытых файлов, таблица процессов , фактически каждая таблица являются ограниченными ресурсами . Заполнение всех записей таблицы процессов может привести к тому, что очередной запрос на создание процесса может быть отклонен. При неблагоприятном стечении обстоятельств несколько процессов могут выдать такой запрос одновременно и оказаться в тупике . Следует ли отказываться от вызова CreateProcess, чтобы решить эту проблему?
Подход большинства популярных ОС (Unix, Windows и др.) состоит в том, чтобы игнорировать данную проблему в предположении, что маловероятный случайный тупик предпочтительнее, чем нелепые правила, заставляющие пользователей ограничивать число процессов, открытых файлов и т. п. Сталкиваясь с нежелательным выбором между строгостью и удобством, трудно найти решение, которое устраивало бы всех.
Источник
