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.

A wait-for-graph may represent processes that are waiting for a single resource to become available (the trivial case), a conjunctive (and) or disjunctive (or) set of different resources or a certain number of equivalent resources from a collection. In the conjunctive case, graph cycles imply the possibility of a deadlock, whereas in the disjunctive case knots are indicative of deadlock possibility. There is no simple algorithm for detecting the possibility of deadlock in the final case.

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.

The wait for graph scheme is applicable to a resource allocation system with multiple instances of each resource type.

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)