Обнаружение тупиков (detection). Графы распределения ресурсов

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

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

P1 R1

Процесс P1 запрашивает один из ресурсов R1

R2 P2

Ресурс R2 выделен процессу Р2

P3 R3 P4

Процесс Р3 запрашивает ресурс R3, который

выделен процессу P4

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

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

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

P2

R1 R1 P2

А) Б)

P3 P3

P1 R2 P1 R2

Редуцирование на процесс Р3

P2

R1 R1 P2

В) Г)

P3 P3

P1 R2 P1 R2

Редуцирование на процесс Р1 Редуцирование на процесс Р2

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