What are wait-for-graphs?Give the algorithm to construct a wait-for-graph from a given schedule of transactions? How can deadlocks be detected from wait-for-graphs? 

 Ans:  The wait-for-graph is a directed graph and consists of nodes and directed arcs; the nodes of the graph are active transactions. An arc of the graph is inserted among two nodes if there is a data-item is needed by the node at the tail of the arc that is being held by the node at the head of the arc. 

  Algorithm to construct wait-for-graph is as follows:

1.  For every transaction Ti active at the time of deadlock detection, make a node labeled T_i in the wait-for-graph.

2.  For every case, if there is a transaction T_i, waiting for a data-item that is at present allocated and held by transaction T_j, then there is a directed arc from the node for transaction T_i, to the node for transaction T_j.

3.  For every case, if there is a directed arc from the node for transaction T_i, to the node for transaction T_j and transaction T_j released the lock, after that remove the arc between them.

4.  There no deadlock if the wait-for-graph is acyclic.  

The wait-for-graph is employed for detection of deadlock in the system. If there is any cycle exits in the wait-for-graph, all the active transaction (denoted as nodes) are in deadlock that are in the cycle.