Single Instance of Each Resource Type

• Maintain wait-for graph

1. Nodes are processes.
2. Pi ® Pj if Pi is waiting for Pj.

• Periodically invoke an algorithm that searches for a cycle in the graph.
• An algorithm to detect a cycle in a graph requires an order of n2 operations, where n is the number of vertices in the graph.