순차 트랜잭션 처리를 위한 새로운 그래크 모델에 의한 교착상태의 주기적 검출 및 회복 기법

Abstract

이 논문은 엄격한 두 단계 로킹과 다단계 로킹규약이 다섯 가지 로크 모드(IS, IX, S, SIX 그리고 X)를 적용하는 환경에서의 순차 트랜잭션 처리에 있어서의 교착상태 문제를 다룬다. 우리의 스케쥴링 정책은 로크의 변경을 제외하고는 먼저온 순서대로 로크 요구를 취급한다. 기본 도구로, 교착상태에 대한 시스템의 정확한 상태를 파악하기 위하여, H/W-TWBG라는 새로운 ?置瘦瀏′존? 소개한다. 그 그래프는 여러가지 바람직한 특성을 가지고 있어서 대기그래프를 대신히여 사용할 수 있다. H/W-TWBG의 특성들이 제시되고 이론적인 측면들이 해석되었다. H/W-TWBG에 기초를 두고, 교착상태 원에서 희생자 후보들의 판별 원리를 설정하고, 그리고 타당한 시간 및 면적 복잡성을 가진 새로운 주기적인 교착상태의 검출 및 회복 알고리즘을 제시한다. 우리의 교착 상태 검출기법의 한 중요한 특징은 어떤 교착상태들은 어느 트랜잭션의 포기 없이도 해결될 수 있다.

This paper addresses the deadlock problem in the sequential transaction processing where the strict two-phase locking and the multiple granularity locking protocol with five lock modes (IS, IX, S , SIX and X) are employed. Our scheduling ploicy honors lock requsts in a first-in-first-out basis except for lock conversions. As a basic tool, we introduce a new directed graph model called Holder/Waiter-Transaction Waited-By Graph (H/W-TWBG) to capture precise status of systems in terms of deadlock. The graph has a number of desirabe properties which allow us to use instead of the wait-for graph. The properties of H/W-TWBGare presented and theoretical aspects of it are also analyzed. Based on H/W-TWBG, we establish the identification principles of victim candidates in a deadlock cycle, and then present a new periodic deadlock detection and resolution algorithm which has a reasonable time and storage complexity. One important feature of our deadlock resolution scheme is that some deadlocks can be resolved without aborting any transaction.

This paper addresses the deadlock problem in the sequential transaction processing where the strict two-phase locking and the multiple granularity locking protocol with five lock modes (IS, IX, S , SIX and X) are employed. Our scheduling ploicy honors lock requsts in a first-in-first-out basis except for lock conversions. As a basic tool, we introduce a new directed graph model called Holder/Waiter-Transaction Waited-By Graph (H/W-TWBG) to capture precise status of systems in terms of deadlock. The graph has a number of desirabe properties which allow us to use instead of the wait-for graph. The properties of H/W-TWBGare presented and theoretical aspects of it are also analyzed. Based on H/W-TWBG, we establish the identification principles of victim candidates in a deadlock cycle, and then present a new periodic deadlock detection and resolution algorithm which has a reasonable time and storage complexity. One important feature of our deadlock resolution scheme is that some deadlocks can be resolved without aborting any transaction.