Методы обнаружения тупиков

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

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

При рассмотрении задачи обнаружения тупиков применяется весьма распространённая нотация, согласно которой распределе­ние ресурсов и запросы изображаются в виде направленного гра­фа. Квадраты обозначают процессы, а большие кружки — классы идентичных ресурсов. Малые кружки, находящиеся внутри боль­ших, обозначают количество идентичных ресурсов каждого класса.

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

Графы запросов и распределения ресурсов динамично меняются по мере того, как процессы запрашивают ресурсы, получают их в своё распоряжение, а через какое-то время возвращают операционной системе.

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

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

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

На рис. 25.1 показан граф, который может быть полностью ре­дуцирован (рис. 25.2), что говорит о том, что в данном случае тупи­ковой ситуации в системе нет.

На рис. 25.3 показан типичный нередуцируемый граф.