Приведение графов распределения ресурсов

 

Задача механизма обнаружения тупиков — определить, не возникла ли в системе тупиковая ситуация. Одним из способов обнаружения тупиков является приведение, или редукция графа,— это позволяет определять процессы, которые могут завершиться, и процессы, которые будут оставаться в тупиковой ситуации.

 

Если запросы ресурсов для некоторого процесса могут быть удовлетворены, то мы говорим, что граф можно редуцировать на этот процесс. Такая редукция эквивалентна изображению графа в том виде, который он будет иметь в случае, если данный процесс завершит свою работу и возвратит ресурсы системе. Редукция графа на конкретный процесс изображается исключением стрелок, идущих к этому процессу от ресурсов (т. е. ресурсов, выделенных дан-' ному процессу) и стрелок к ресурсам от этого процесса (т. е. текущих запросов данного процесса на выделение ресурсов). Если граф можно редуцировать на все процессы, значит, тупиковой ситуации нет, а если этого сделать нельзя, то все «нередуцируемые» процессы образуют набор процессов, вовлеченных в тупиковую ситуацию.

 

На рис. 6.4 показан ряд последовательных редукций графа, которые в конце концов позволяют убедиться в том, что для этого конкретного набора процессов тупиковой ситуации нет. На рис. 6.3(г) показана пара процессов, которые являются «нередуцируемыми» и, таким образом, представляют систему в тупиковой ситуации.

 

Здесь важно отметить, что порядок, в котором осуществляется редукция графа, не имеет значения: окончательный результат в любом случае будет тем же самым. Справедливость такого утверждения продемонстрировать относительно легко, и читатель может сам это сделать в качестве упражнения.

 

Простой пример тупика при распределении ресурсов

 

В операционных системах тупики в большинстве случаев возникают в результате обычной конкуренции за обладание выделяемыми, или закрепляемыми ресурсами (т. е. ресурсами, которые в каждый момент времени отводятся только одному пользователю и которые поэтому иногда называются ресурсами последовательного использования). На рис. 6.2 показан простой пример тупика подобного рода. На этом графе распределения ресурсов представлены два процесса (в виде прямоугольников) и два ресурса (в виде окружностей). Стрелка, направленная от ресурса к процессу, показывает,

 

 

 

Рис. 6.2 Простая тупиковая ситуация. Данная система оказалась в тупиковой ситуации, поскольку каждый процесс удерживает ресурс, запрашиваемый другим процессом, причем ни один из процессов не хочет освободить принадлежащий ему ресурс.

 

что данный ресурс принадлежит или был выделен данному процессу. Стрелка, направленная от процесса к ресурсу, показывает, что данный процесс требует, но пока еще не получил в свое распоряжение данный ресурс. На рисунке изображена система в состоянии тупика; процесс А удерживает в своем распоряжении ресурс 1, а для продолжения выполнения ему необходим ресурс 2. Процесс В удерживает ресурс 2, а для продолжения работы ему нужен ресурс 1. Каждый процесс ждет, чтобы другой процесс освободил нужный ему ресурс, причем каждый не освобождает свой ресурс до тех пор, пока другой не освободит свой ресурс, и т. д. Такое состояние кругового ожидания характерно для систем в тупиковом состоянии.

 

Алгоритмы обнаружения тупиков. Редукция графа распределения ресурсов.

Обнаружение тупиков

Обнаружение тупика — это установление факта, что возникла тупиковая ситуация, и определение процессов и ресурсов, вовлеченных в эту тупиковую ситуацию. Алгоритмы обнаружения тупиков, как правило, применяются в системах, где выполняются первые три необходимых условия возникновения тупиковой ситуации. Эти алгоритмы затем определяют, не создался ли режим кругового ожидания.

 

Применение алгоритмов обнаружения тупиков сопряжено с определенными дополнительными затратами машинного времени. Таким образом, здесь мы снова сталкиваемся с необходимостью прибегать к компромиссным решениям, столь распространенным в операционных системах. Будут ли накладные расходы, связанные с реализацией алгоритмов обнаружения тупиковых ситуаций, в достаточной степени оправданы потенциальными выгодами от локализации и устранения тупиков? В данный момент мы этот вопрос рассматривать не будем, а лучше сосредоточим свое внимание на описании алгоритмов, позволяющих обнаруживать тупики.

 

Обнаружение тупиков

 

Обнаружение взаимоблокировки сводится к фиксации тупиковой ситуации и выявлению вовлеченных в нее процессов. Для этого производится проверка наличия циклического ожидания в случаях, когда выполнены первые три условия возникновения тупика. Методы обнаружения активно используют графы распределения ресурсов.

 

Рассмотрим модельную ситуацию.

Процесс P1 ожидает ресурс R1.

Процесс P2 удерживает ресурс R2 и ожидает ресурс R1.

Процесс P3 удерживает ресурс R1 и ожидает ресурс R3.

Процесс P4 ожидает ресурс R2.

Процесс P5 удерживает ресурс R3 и ожидает ресурс R2.

 

Вопрос состоит в том, является ли данная ситуация тупиковой, и если да, то какие процессы в ней участвуют. Для ответа на этот вопрос можно сконструировать граф ресурсов, как показано на рис. 7.3. Из рисунка видно, что имеется цикл, моделирующий условие кругового ожидания, и что процессы P2,P3,P5, а может быть, и другие находятся в тупиковой ситуации.

 

 

Рис. 7.3. Граф ресурсов

 

 

Визуально легко обнаружить наличие тупика, но нужны также формальные алгоритмы, реализуемые на компьютере.

 

Один из таких алгоритмов описан в [Таненбаум, 2002], там же можно найти ссылки на другие алгоритмы.

 

Существуют и другие способы обнаружения тупиков, применимые также в ситуациях, когда имеется несколько ресурсов каждого типа. Так в [Дейтел, 1987] описан способ, называемый редукцией графа распределения ресурсов, а в [Таненбаум, 2002] – матричный алгоритм.