Wait-for graph

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources. Find sources: "Wait-for graph" – news · newspapers · books · scholar · JSTOR (May 2023) Some of this article's listed sources may not be reliable. Please help improve this article by looking for better, more reliable sources. Unreliable citations may be challenged and removed. (May 2023) (Learn how and when to remove this message) (Learn how and when to remove this message)

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 ${\displaystyle P_{i}}$ to ${\displaystyle P_{j}}$ implies ${\displaystyle P_{j}}$ is holding a resource that ${\displaystyle P_{i}}$ needs and thus ${\displaystyle P_{i}}$ is waiting for ${\displaystyle P_{j}}$ to release its lock on that resource. If the process is waiting for more than a single resource to become available (the trivial case), multiple edges may represent a conjunctive (and) or disjunctive (or) set of different resources or a certain number of equivalent resources from a collection. The possibility of a deadlock is implied by graph cycles in the conjunctive case, and by knots in the disjunctive case. There is no simple algorithm for detecting the possibility of deadlock in the final case.^[1]

A wait-for graph is a graph of conflicts blocked by locks from being materialized; it can be also defined as the graph of non-materialized conflicts; conflicts not materialized are not reflected in the precedence graph and do not affect serializability.

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

An arc from a transaction T1 to another transaction T2 represents that T1 waits for T2 to release a lock (i.e., T1 acquired a lock which is incompatible with a previously acquired lock from T2). A lock is incompatible with another if they are on the same object, one is a write, and they are from different transactions.

A deadlock occurs in a schedule if and only if there is at least one cycle in the wait-for graph. Not every cycle necessarily represents a distinct deadlock instance.

This computer science article is a stub. You can help Wikipedia by expanding it.

• v
• t
• e