KLI

Performaance Analysis of Distributed Deadlock Detection and Resolution Algorithms based on a Hybrid Wait-for Graph and Probe Generation Scheme

Metadata Downloads
Alternative Title
대기 그래프와 프로브 생성에 기초한 교착상태의 분산 검출 및 회복 알고리즘의 성능분석
Abstract
본 논문은 분산 데이타베이스 시스템에서의 교착상태 검출 및 회복을 위한 연속 알고리즘을 제시한다. 이 알고리즘은 각 지역 사이트에 확장된 트랜잭션 대기 그래프를 유지하며 각 사이트간 메세지 전달의 수효를 최소화하기 위해 우선순위에 기초한 프로브 생성 기법을 변형하여 사용한다. 확장된 트랜잭션 대기 그래프는 로크-대기 정보 뿐만 아니라 트랜잭션 에이전트들간의 메세지-대기 정보, 수신한 프로브들, 그리고 트랜잭션 사이의 이행-대기 관계들에 관한 정보도 포함한다. 전역 교착상태는 어떤 프로브나 이행-대기 관계가 그 프로브를 개시한 트랜잭션의 어떤 에이전트로 전파될 때마다 선언된다. 교착상태의 거짓선언 확률을 최소화하기 위하여 제시한 알고리즘에 대하여 두가지 확장을 가했다. 이들은 교착상태 선언시 이의 정당성을 검증하는 부가적인 절차를 추가한 것이다. 세가지 제안한 방법의 성능을 시뮬레이션을 통하여 비교분석 하였다.
We present a continuous algorithm for deadlock detection and resolution in distributed database systems. our algorithm maintains at each local site an augmented transaction wait-for graph and used a modified priority-based probe generation scheme in order to minimize the number of intersite messages sent. The augmented transaction-wait for graph contains, in addition to lock-wait information, also information about message-wait relationships among the agents of a transaction, received probes and transitive wait-for relationships among transactions. Global deadlocks are declared whenerver a probe or transitive-wait relationship is propagated to an agent of the transaction that initiated the probe. In order to minimize the probability of false deadlocks, two extensions to the original algorithm are presented which make use of an additional validation procedure. We report on the results of simulation experiments that compare the performance of the three proposed schemes for deadlock detection and resolution.
We present a continuous algorithm for deadlock detection and resolution in distributed database systems. our algorithm maintains at each local site an augmented transaction wait-for graph and used a modified priority-based probe generation scheme in order to minimize the number of intersite messages sent. The augmented transaction-wait for graph contains, in addition to lock-wait information, also information about message-wait relationships among the agents of a transaction, received probes and transitive wait-for relationships among transactions. Global deadlocks are declared whenerver a probe or transitive-wait relationship is propagated to an agent of the transaction that initiated the probe. In order to minimize the probability of false deadlocks, two extensions to the original algorithm are presented which make use of an additional validation procedure. We report on the results of simulation experiments that compare the performance of the three proposed schemes for deadlock detection and resolution.
Author(s)
Park,Young-ChulPark,Yang-SooCheung,Young-Phil
Issued Date
1993
Type
Research Laboratory
URI
https://oak.ulsan.ac.kr/handle/2021.oak/4136
http://ulsan.dcollection.net/jsp/common/DcLoOrgPer.jsp?sItemId=000002025498
Alternative Author(s)
박영철박양수정영필
Publisher
공학연구논문집
Language
eng
Rights
울산대학교 저작물은 저작권에 의해 보호받습니다.
Citation Volume
24
Citation Number
1
Citation Start Page
167
Citation End Page
189
Appears in Collections:
Research Laboratory > Engineering Research
Authorize & License
  • Authorize공개
Files in This Item:

Items in Repository are protected by copyright, with all rights reserved, unless otherwise indicated.