Wait-for graph

File:Http://i.msdn.microsoft.com/dynimg/IC135461.gif%7Cthumbnail%7C deadlock of resources

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 $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. 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.

A deadlock occurs when two or more tasks permanently block each other by each task having a lock on a resource which the other tasks are trying to lock. The following graph presents a high level view of a deadlock state where: Task T1 has a lock on resource R1 (indicated by the arrow from R1 to T1) and has requested a lock on resource R2 (indicated by the arrow from T1 to R2). Task T2 has a lock on resource R2 (indicated by the arrow from R2 to T2) and has requested a lock on resource R1 (indicated by the arrow from T2 to R1). Neither task can continue until a resource is available and neither resource can be released until a task continues. Therefore, a deadlock state exists.

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)

http://msdn.microsoft.com/en-IN/library/ms178104%28v=sql.105%29.aspx