Detection

This scheme allows the system to enter a deadlock state, it is then capable of detecting and recovering from such a state.

When one has only single instance resources, one may implement this by maintaining a wait-for graph, where each node is a process, with $P_i\to P_j$ if $P_i$ is waiting for $P_j$.

Periodically, the system will invoke an algorithm which searches for cycles in this graph. If one exists, the system is in a deadlock. Algorithms to detect cycles in graphs run in $O(n^2)$.