Граф PR

Включает множество вершин V=P U R:

P={p₁, p₂, …, p_n} — множество процессов.

R={r₁, r₂, …, r_n} — множество ресурсов.

Дуги запросов Pi→Rj — i-й процесс запрашивает j-й ресурс.

Дуги распределения Rj→Pi — j-й ресурс принадлежит i-му процессу.

Если PR-граф не имеет циклов, тупиков нет.

Если имеет — возможно, тупик существует.

Цикл + тупик:

Цикл без тупика:

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

PR-граф может быть сокращен за счет процесса, все запросы которого могут быть удовлетворены. При сокращении все ресурсы выбранного процесса освобождаются. Все дуги графа, связанные с этим процессом, удаляются.

В частности,

1. Если граф полностью редуцируем, взаимоблокировка отсутствует.
2. Порядок выполнения редукций не имеет значения.