A new algorithm which detects deadlock in distributed computing system is proposed. This algorithm is called DGR (Distributed Graph Reconstruction) algorithm, because it extracts informations about deadlock condition from reconstructed wait-for graph. The main goal of the algorithm is how to detect deadlock with less communication messages in fully distributed manner. The approach of this algorithm is completely new. The communication model is used as an abstraction of a distributed system. It detects all existing deadlock with smaller number of messages than known algorithms. DGR algorithm does not detect any flase deadlock and it detects disjoint cycles within wait-for graph separately. Therefore, the resolution of detected deadlock can be done more easily. The hypercube computer architecture is used as a basis of distributed system and the hypercube simulator is used for performance analysis of the algorithm.
분산 처리 시스템에서 발생할수 있는 제 문제중의 하나가 교착상태에 관한것이다. 이러한 교착상태는 시스템 운영상 성능및 신뢰성에 지대한 영향을 미치는 문제이므로, 분산 처리 시스템에서는 반드시 교착상태를 다룰수 있는 방책이 필요하게 된다.
본 논문에서는 분산 처리 시스템에서 발생할 수 있는 교착상태를 검출하는 알고리즘을 제안하였다. 이 알고리즘은 DGR (Distrdbuted Graph Reconstruction) 알고리즘이라 부르는데, 이 알고리즘이 교착상태에 관한 정보를 재구성된 wait-for-graph로 부터 추출해 내기 때문이다. 이 알고리즘의 주된 목적은 완전히 분산적인 방법으로써 어떻게 좀 더 적은 통신 메세지를 가지고 교착상태를 검출하느냐에 있다. 본 논문에서 제안된 알고리즘은 그 접근방법 자체가 기존의 알고리즘과는 근본적으로 다르다. 이 알고리즘은 존재하는 모든 교착상태를 검출해 내며, 존재하지 않는 교착상태를 검출하지도 않는다. 또한 서로 관련성이 없는 교착상태를 분리해서 검출하므로 후에 제기되는 교착상태의 해소 방안도 간단해 질수 있다.
분산 처리 시스템에 대한 모델은 통신 모델을 사용하였으며, 하이퍼큐브 컴퓨터 구조가 분산 처리 시스템으로 사용되었다. 알고리즘의 성능 분석을 위해 하이퍼큐브 컴퓨터의 시뮬레이터를 이용하였다.
