A performance study of deadlock resolution in distributed systems

Distributed deadlock is a state where there exists among some processes running on different computers a cyclic wait to acquire some resources such that no process can proceed. Since a deadlock is a state that persists unless it is solved by some method, and the number and size of deadlocks increase substantially as the concurrency level or number of sites in a distributed system grows, we need an efficient approach to solve this problem.Distributed deadlock resolution consists of choosing a victim, aborting and restarting it. There has been no detailed study of resolution, despite the fact that deadlock detection does not complete its task without resolution. The performance analysis of different resolution strategies that have been proposed and new approaches for distributed deadlock resolution are the subject of this study.Different heuristic strategies (rules) to choose victims to break deadlocks are discussed and the direct and indirect goals that the rules were hypothesized to achieve are described. Various simulation runs (experiments) were conducted to analyze in depth the performance of the rules. The system throughput and the overhead of running the rules are evaluated and the effectiveness of each rule in achieving its goals are compared.The assessment of each rule under different system conditions is used to evaluate the possibility of incorporating more than one rule in deadlock resolution. This leads to the suggestion for use of a first-principles expert system to monitor and diagnose distributed systems, including the resolution of problems such as deadlocks. The rule base of such an expert system would include rules to choose the optimum victim to resolve a distributed deadlock.U of I OnlyETDs are only available to UIUC Users without author permissio