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

Рис.6 Граф запросов и распределения ресурсов

Ранее мы привели на рис.5 вариант “кругового ожидания”, типичного для системы в состоянии тупика.
Графы запросов и распределения ресурсов динамично меняются по мере того, как процессы запрашивают ресурсы и получают их в свое распоряжение, а по истечении некоторого времени возвращают системе.
Одним из способов обнаружения тупиков, является приведение, или редукция графа — это позволяет определить процессы, которые могут завершиться, и процессы, которые будут оставаться в тупиковой ситуации.
Редукция графа на конкретный процесс изображается исключением стрелок, идущих к процессу от ресурсов и стрелок к ресурсам этого процесса, такая редукция эквивалентна такой ситуации, когда данный процесс завершился и возвратил ресурсы системе. Если граф можно редуцировать на все процессы, значит тупиковой ситуации нет, а если этого сделать нельзя, то все “нередуцируемые” процессы образуют набор процессов, вовлеченных в тупиковую ситуацию. Заметим, что порядок, в котором осуществляется редукция графа, не имеет значение.
Редуцирование на процесс Р1 Редуцирование на процесс Р2

Рис.7 Редукция графа

На рис.7 показана ситуация, в которой для конкретного набора процессов тупиковой ситуации нет. Если же мы попытаемся редуцировать граф, приведенный на рис.5, то легко обнаружим, что система находится в тупиковой ситуации.

Самостоятельно привести примеры нередуцируемых графов (минимальное количество процессов 4, минимальное количество классов идентичных ресурсов 3 по два идентичных ресурса в каждом классе}.