Question

Consider the following deadlock-detection algorithm. When transaction Ti, at site S1, requests a resource from Tj, at site S3, a request message with timestamp n is sent. The edge (Ti, Tj, n) is inserted in the local wait-for 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 fromTi 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.


$1.99
Sales0
Views225
Comments0
  • CreatedJanuary 29, 2011
  • Files Included
Post your question
5000