Distributed deadlock detection and resolution by dynamic process grouping = 동적 프로세스 집단화를 통한 분산교착상태의 검출 및 해결

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 195
  • Download : 0
The problem of detecting resource deadlocks(alos called AND-deadlock) in a distributed environment is considered in this thesis. Two algorithms based on the concept of grouping which synamically divide the transactions in the system into a set of gruops are presented. The proposed algorithms assign group label to each transcation such that the group labels contain dependency and distance information among transactions within a group. The group label for each transaction is dynamically changed during run-time according to configuration changes in the wait-for-graph(WFG). The first algorithm is based on exclusive lock model where a transcation``s request for a data item can conflict with at most one other request, which means the maximum outdegree of the WFG is 1. In this algorithm, group labels are assigned such that the group labels for any pair of transactions within a group always define their dependency. The second algorithm is based on more general model where a node in the WFG can have multiple outgoing deges. With this assumption, the second algorithm employs another distributed scheme which dynamically assigns gruop label to each transaction. The algorithm uses two-level ordering-group ordering and local ordering-to establish a total ordering among transactions in the system. Group ordering is used to effectively reduce the number of probes to detect a deadlock and local ordering is used to decide whether a transaction is deadlocked or not. Since the dependency information between transactions are updated during run-time, there is no separate "detection phase" in the proposed algorithms. The algorithms ensure that only one transaction within a cycle detects the deadlock, which simplified the problem of deadlock resolution. The deadlock resolution precedure is very simple compared to that of existing solutions. The dependency infromation remains valid after the resolution of a deadlock. Therefore, the detection of future deadlocks can be done with less ef...
Advisors
Kim, Myung-Hwanresearcher김명환researcher
Description
한국과학기술원 : 전기 및 전자공학과,
Publisher
한국과학기술원
Issue Date
1991
Identifier
61720/325007 / 000855277
Language
eng
Description

학위논문(박사) - 한국과학기술원 : 전기 및 전자공학과, 1991.2, [ vi, 109 p. ]

URI
http://hdl.handle.net/10203/36152
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=61720&flag=dissertation
Appears in Collection
EE-Theses_Ph.D.(박사논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0