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

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.