Wait-for graph

A Wait-For Graph in computer science is a directed graph used for deadlock detection in operating systems and relational database systems.

In Computer Science, a system that allows concurrent operation of multiple processes and locking of resources and which does not provide mechanisms to avoid or prevent deadlock must support a mechanism to detect deadlocks and an algorithm for recovering from them.

One such deadlock detection algorithm makes use of a Wait-For Graph to track which other processes a process is currently blocking on. In a Wait-for Graph, processes are represented as nodes, and an edge from process $P_{i}$ to $P_{j}$ implies $P_{j}$ is holding a resource that $P_{i}$ needs and thus $P_{i}$ is waiting for $P_{j}$ to release its lock on that resource.

References

Silberschatz, Abraham (2003). Operating System Concepts. John Wiley & Sons, INC. p. 260. ISBN 0-471-25060-0. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)