The problem of detecting resource deadlocks(also called AND-deadlock) in a distributed environment is considered in this thesis. Two algorithms based on the concept of grouping which dynamically divide the transactions in the system into a set of groups are presented. The proposed algorithms assign group label to each transaction 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 transaction'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 edges. With this assumption, the second algorithm employs another distributed scheme which dynamically assigns group 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 procedure is very simple compared to that of existing solutions. The dependency information remains valid after the resolution of a deadlock. Therefore, the detection of future deadlocks can be done with less efforts.
For both schemes, proofs for correctness are given and their performances are compared to those of existing solutions through simulation. The simulation results show that both the algorithms outperform existing solutions in that deadlock computations are initiated less frequently than existing solutions. Also, since each group number implicitly contains dependency information among a set of transactions, the number of probes needed for the detection of deadlocks is significantly reduced compared to existing algorithms which explicitly maintain a set of dependency relations between two transactions. The simulation results show that the execution of the proposed algorithms does not introduce much communication overhead, which is the case for existing solutions.
본 논문은 분산처리 환경에서 나타나는 교착상태의 검출 및 해결에 관한 두가지의 방법들을 제안하였다. 이 방법들은 동적으로 시스템 내에 존재하는 트랜잭션들을 일련의 집단으로 분할하는 방법에 그 기초를 두고 있다. 제안된 방법들은 각 트랜잭션에 의존성과 거리정보를 포함하는 집단정보를 할당하며 이러한 집단정보는 대기그래프의 변화에 따라 동적으로 변화한다.
첫번째 재안된 방법은 대기그래프 내의 임의의 노드는 최대 하나의 외향에지를 가질 수 있다는 가정에 기초하여 설계되었다. 이 경우 하나의 집단 내부의 집단 정보들은 서로간의 의존성의 정보를 포함하도록 할당된다. 두번째 방법은 대기그래프에서 임의의 노드는 여러개의 외향에지를 가질 수 있도록 허용한 좀 더 일반화된 방법이다. 이 방법은 2단계의 순서화를 기초로 하나의 집단 내의 집단정보사이의 의존성을 정의하여준다. 이러한 의존정보는 분산교착상태의 검출을 위한 메세지의 갯수를 효과적으로 줄여준다.
집단정보들은 수행 중 동적으로 변화하므로 독립된 검출단계를 가지지 않는다. 이 방법들은 교착상태에 있는 트랜잭션중 단 하나만이 이를 검출하게하므로 교착상태의 해결이 간단해진다. 의존정보들은 교착상태의 해결 후에도 유지되므로 이 후의 교착상태의 검출에 필요한 정보를 제공한다.
본 논문에서는 이 두가지 방법의 정확성을 증명하였으며 모의수행을 통하여 기존의 방법들과 성능비교를 하였다. 그 결과 제안된 방법들은 기존의 방법보다 교착상태 검출을 위한 계산의 빈도가 적으며 이에따라 보내어지는 프로브 메세지의 갯수가 주어진 변수값에 대해 약 100배 정도 적음이 보여졌다. 이는 집단정보는 여러 트랜잭션의 의존정보를 포함하나 기존의 방법에서는 두개의 트랜잭션의 의존정보만을 취급하므로 생기는 결과이다.
