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 Ti in the wait-for-graph.
2. For every case, if there is a transaction Ti, waiting for a data-item that is at present allocated and held by transaction Tj, then there is a directed arc from the node for transaction Ti, to the node for transaction Tj.
3. For every case, if there is a directed arc from the node for transaction Ti, to the node for transaction Tj and transaction Tj 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.