Wait-For Graph
Encyclopedia
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
to 
implies 
is holding a resource that 
needs and thus 
is waiting for 
to release its lock on that resource. A deadlock exists if the graph contains any cycles.
The wait for graph scheme is applicable to a resource allocation system with multiple instances of each resource type.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
is a directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
used for deadlock
Deadlock
A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the "chicken or the egg"...
detection in operating systems and relational database
Relational database
A relational database is a database that conforms to relational model theory. The software used in a relational database is called a relational database management system . Colloquial use of the term "relational database" may refer to the RDBMS software, or the relational database itself...
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
to implies is holding a resource that needs and thus is waiting for to release its lock on that resource. A deadlock exists if the graph contains any cycles.The wait for graph scheme is applicable to a resource allocation system with multiple instances of each resource type.