Consider the following deadlock-detection algorithm. When transaction Ti, at site S1, requests a resource from Tj, at site S3, a request message with time-stamp n is sent. The edge (Ti, Tj, n) is inserted in the local wait-for graph of S1. The edge (Ti, Tj, n) is inserted in the local wait-for graph of S3 only if Tj has received the request message and cannot immediately grant the requested resource. A request from Ti to Tj in the same site is handled in the usual manner; no timestamps are associated with the edge (Ti, Tj). A central coordinator invokes the detection algorithm by sending an initiating message to each site in the system. On receiving this message, a site sends its local wait-for graph to the coordinator. Note that such a graph contains all the local information that the site has about the state of the real graph. The wait-for graph reflects an instantaneous state of the site, but it is not synchronized with respect to any other site. When the controller has received a reply from each site, it constructs a graph as follows: • The graph contains a vertex for every transaction in the system. • The graph has an edge (Ti, Tj) if and only if: ° There is an edge (Ti, Tj) in one of the wait-for graphs. ° An edge (Ti, Tj, n) (for some n) appears in more than one wait-for graph. Show that, if there is a cycle in the constructed graph, then the system is in a deadlock state, and that, if there is no cycle in the constructed graph, then the system was not in a deadlock state when the execution of the algorithm began.
Consider the following deadlock-detection
On receiving this message, a site sends its local wait-for graph to the coordinator. Note that such a graph contains all the local information that the site has about the state of the real graph. The wait-for graph reflects an instantaneous state of the site, but it is not synchronized with respect to any other site. When the controller has received a reply from each site, it constructs a graph as follows:
• The graph contains a vertex for every transaction in the system.
• The graph has an edge (Ti, Tj) if and only if:
° There is an edge (Ti, Tj) in one of the wait-for graphs.
° An edge (Ti, Tj, n) (for some n) appears in more than one wait-for graph.
Show that, if there is a cycle in the constructed graph, then the system is in a deadlock state, and that, if there is no cycle in the constructed graph, then the system was not in a deadlock state when the execution of the algorithm began.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
