KLI

여러 로크 모드를 가진 순차 트랜잭션 처리를 위한 교착상태의 연속적 검출 및 회복 기법

Metadata Downloads
Alternative Title
A Continuous Deadlock Detection and Resolution Algorithm for Sequential Transaction Processing with Multiple Lock Modes
Abstract
이 논문은 엄격한 두 단계 로킹이 직열성 보장을 위하여 적용되고 다단계 로킹규약이 다섯가지 로크 모드(IS, IX, S, SIX, 그리고 X)를 적용하는 환경에서의 순차 트랜잰션 처리에 있어서의 교착상태 문제를 다루는 알고리즘을 제시한다. 각 자원에 대하여 우리의 스캐쥴링 정책은 로크의 변경을 제외하고는 먼저온 순서대로 로크 요구를 취급한다. 교착상태의 검출과 회복을 위한 기본 착상은 H/W-TWBG라는 새로운 지향그래프의 형성에 있다. 이 그래프는 여러가지 바람직한 특성을 가지고 있어서 대기그래프를 대신하여 사용할 수 있다. 교착상태원에서 희생자들의 판별원리를 설정하고, 그리고 타당한 시간 및 면적 복잡성을 가지고 그 해결책이 거의 최적인 검출 및 회복 알고리즘을 제시한다. 우리의 교착상태 검출기법의 한 중요한 특징은 어떤 교착상태들은 어느 트랜잭션의 포기없이도 해결될 수 있다.
An algorithm for deadlock detection and resolution in the sequential transaction processing is presented, where two-phase locking is assumed for ensuring serializability, the lock requests obey th granularity locking protocol and each granule may be locked in one of the following lock modes: IS, IX, S, SIX and X. For each object, lock requests are honored according to a first-come-first served basis except for lock conversions. The basic idea for the deadlock detection and resolution is in the construction of a new directed fraph called a Holder/Waiter-Transaction Waited-By Graph. We establish guidelines for the identification of a victim in a deadlock cycle and propose a resolution algorithm whose time and space requirements are resonable and its solution is near optimal. In addition, our algorithm allows us to resolve some deadlocks without aborting any transaction.
An algorithm for deadlock detection and resolution in the sequential transaction processing is presented, where two-phase locking is assumed for ensuring serializability, the lock requests obey th granularity locking protocol and each granule may be locked in one of the following lock modes: IS, IX, S, SIX and X. For each object, lock requests are honored according to a first-come-first served basis except for lock conversions. The basic idea for the deadlock detection and resolution is in the construction of a new directed fraph called a Holder/Waiter-Transaction Waited-By Graph. We establish guidelines for the identification of a victim in a deadlock cycle and propose a resolution algorithm whose time and space requirements are resonable and its solution is near optimal. In addition, our algorithm allows us to resolve some deadlocks without aborting any transaction.
Author(s)
박영철
Issued Date
1991
Type
Research Laboratory
URI
https://oak.ulsan.ac.kr/handle/2021.oak/3868
http://ulsan.dcollection.net/jsp/common/DcLoOrgPer.jsp?sItemId=000002024433
Alternative Author(s)
Park, Young-Chul
Publisher
공학연구논문집
Language
eng
Rights
울산대학교 저작물은 저작권에 의해 보호받습니다.
Citation Volume
22
Citation Number
2
Citation Start Page
87
Citation End Page
105
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.