A wait-for graph in

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...

is a directed graph used for

deadlock In concurrent computing, deadlock is any situation in which no member of some group of entities can proceed because each waits for another member, including itself, to take action, such as sending a message or, more commonly, releasing a loc ...

detection in

operating systems An operating system (OS) is system software that manages computer hardware, software resources, and provides common services for computer programs. Time-sharing operating systems schedule tasks for efficient use of the system and may also in ...

and

relational database A relational database is a (most commonly digital) database based on the relational model of data, as proposed by E. F. Codd in 1970. A system used to maintain relational databases is a relational database management system (RDBMS). Many relati ...

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

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. 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 A knot is a fastening in rope or interwoven lines. Knot may also refer to: Places * Knot, Nancowry, a village in India Archaeology * Knot of Isis (tyet), symbol of welfare/life. * Minoan snake goddess figurines#Sacral knot Arts, entertainme ...

in the disjunctive case. There is no simple algorithm for detecting the possibility of deadlock in the final case. The wait-for-graph scheme is not applicable to a resource allocation system with multiple instances of each resource type.

References

* {{comp-sci-stub Concurrency control Directed graphs Application-specific graphs