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.

There is no simple algorithm for detecting the possibility of deadlock in the final case.

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.