Wait-for graph

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

A wait-for graph is a simple tool used to find deadlocks in systems where many processes run at once and lock resources. Each process is a node. There is an arrow from process A to process B if A is waiting for a resource that B holds. If a process waits for several resources, there may be multiple arrows from that process.

In simple cases (when each resource type has a single instance), a deadlock happens exactly when the graph contains a cycle. For example, A waits for B, B waits for C, and C waits for A. Not every cycle means a separate deadlock in more complex setups.

The wait-for graph works best when resources have one copy. If resources can have many copies, the graph alone may miss some deadlocks, and other methods are needed. Deadlock detection and recovery algorithms use these graphs to break the cycle by letting one process release a resource or roll back.