[DB] 교착상태

 

교착상태

.

 

 

교착상태란 모든 트랜잭션들이 실행을 전혀 진전시키지 못하고

무한정 기다리고 있는 상태를 말한다.

 

 

 

위의 그림은 T1과 T2가 모두 교착상태에 있는 예를 보여준다.

 

T1은 T2가 x를 unlock 시키기를 기다리고 있고

T2는 T1이 y를 unlock 시키기를 기다리고 있다.

 

이렇게 되면 다른 트랜잭션도 x와 y에 접근하지 못한다.

 

 

교착상태 필요충분조건으로는 '상호배제', '대기', '선취 금지', '순환 대기' 등

네 가지 조건이 모두 만족되어야 한다.

 

교착상태 문제에 대한 해결책은 '회피', '예방', '탐지' 등

세 가지 방법이 있다.

 

회피는 자원을 할당할 때마다 교착상태가 일어나지 않도록

실시간 알고리즘을 사용하여 검사하는 방법이다.

 

예방은 트랜잭션을 실행시키기 전에

교착상태 발생이 불가능하게 만드는 방법이다.

 

탐지는 교착상태가 일단 일어난 뒤에

교착상태 발생 조건의 하나를 제거하는 것이다.

 

 

타임스탬프

.

 

교착상태 회피를 위한 한 방법으로

각 트랜잭션은 유일하게 식별할 수 있는 식별자가 지정되는데

이것을 그 트랜잭션의 '타임스탬프'라 한다.

 

이 타임스탬프는 보통 트랜잭션이 실행을 시작하는 순서에 기초한다.

따라서 이 타임스탬프를 트랜잭션이 기다려야 할 것인지

복귀해야 할 것인지를 결정하는 데 사용할 수 있다.

 

만일 트랜잭션이 복귀해야 된다면 재시작을 위해 이 타임스탬프는 그대로 유지한다.

 

이 기법에는 두 가지가 있다.

 

wait-die 기법	트랜잭션 Ti가 이미 트랜잭션 Tj가 로크한 데이터 아이템을 요구할 때 Ti의 타임스탬프가 Tj의 것보다 작은 경우 (Ti가 고참인 경우) Ti는 기다린다. 그렇지 않으면 Ti는 복귀했다가 나중에 같은 타임스탬프를 가지고 다시 시작한다.
wound-wait 기법	트랜잭션 Ti가 이미 트랜잭션 Tj가 로크한 데이터 아이템을 요구할 때 Ti의 타임스탬프가 Tj의 것보다 클 경우 (Tj가 고참인 경우) Ti는 기다린다. 그렇지 않으면 Tj가 복귀했다가 나중에 같은 타임스탬프를 가지고 다시 시작한다.

 

 

이 두 기법은 모두 기아 문제는 일어나지 않는다.

언제든지 가장 작은 타임스탬프를 가진 트랜잭션이 있게 되고,

이 트랜잭션은 어떤 경우에도 복귀하지 않기 때문이다.

 

위에서 wait-die 기법은 Ti가 필요한 데이터를 확보할 때까지

몇 번이고 복귀할 수도 있다.

하지만 wound-wait 기법은 Ti는 기다리기만 하면 된다.

 

따라서 wound-wait 기법에서는 복귀가 덜 일어나게 된다.

 

 

타임스탬프 순서 기법

 

타임스탬프 순서 기법이란 트랜잭션을 비직렬 즉, 인터리브드 방식으로 실행한 것이

타임스탬프 순서대로 트랜잭션을 실행한 직렬 스케줄의 결과와

항상 같게 되는 것을 보장하는 것이다.

 

타임스탬프는 TS(Ti)로 나타내며, Ti에 TS(Ti)가 부여된 뒤에 새로운 Tj가 들어왔다면

TS(Ti) < TS(Tj)가 된다.

 

 

타임스탬프를 생성하는 방법 중 한가지는 논리적 계수를 사용하는 것이다.

트랜잭션이 시스템에 들어올 때마다 계수를 하나씩 증가시키는 것이다.

 

또 다른 방법은 시스템 클록의 값을 사용하는 것인데

트랜잭션이 시스템에 들어오면 시스템 클록의 값을 타임스탬프 값으로 부여하는 것이다.

 

즉, 트랜잭션들의 타임스탬프가 직렬 가능성을 결정한다.

 

만약 TS(Ti) < TS(Tj)라고 할 때,

두 트랜잭션을 비직렬로 실행한 스케줄은 트랜잭션 Ti가 트랜잭션 Tj보다

반드시 먼저 나오는 직렬 스케줄과 동등하다는 것을 보장해 준다.

 

이 기법을 '타임스탬프 순서(TSO)'라 한다.

 

 

타임스탬프 순서와 동등한 스케줄을 보장하기 위해서는

각 데이터 아이템 x에 대해 두 개의 타임스탬프 값을 유지한다.

 

read_TS(x)	x의 판독 타임스탬프로서 read(x)를 성공적으로 수행한 트랜잭션의 타임스탬프 중에서 제일 큰 타임스탬프
write_TS(x)	x의 기록 타임스탬프로서 write(x)를 성공적으로 수행한 트랜잭션의 타임스탬프 중에서 제일 큰 타임스탬프

 

 

타임스탬프 순서 규약

 

타임스탬프 순서 규약(TSOP)은 충돌되는 read나 write 연산을

타임스탬프 순서대로 실행되게 보장하는 것이다.

 

규약은 다음과 같다.

 

1	트랜잭션 Ti가 read(x)를 수행하려 할 때
	1) TS(Ti) < write_TS(x)이면, read(x)를 거부하고 Ti를 취소시켜 복귀 : TS(Ti)보다 타임스탬프가 큰 어떤 트랜잭션이 Ti가 접근하기 전에 이미 x의 값을 변경시켰기 때문에 2) TS(Ti) >= write_TS(x)이면 read(x)를 허용하고 read_TS(x)는 TS(Ti)와 현재의 read_TS(x) 중 큰 것으로설정
2	트랜잭션 Ti가 write(x)를 수행하려 할 때
	1) TS(Ti) < read_TS(x)이면, write(x)를 거부하고 Ti를 취소시켜 복귀 : TS(Ti)보다 타임스탬프가 큰 어떤 트랜잭션이 x의 값을 이미 기록하였기 때문에 2) (TS(Ti) >=read_TS(x)  ∧ TS(Ti) >= write_TS(x))이면 write(x)를 허용하고 write_TS(x)의 값은 TS(Ti)로 고정

 

 

기록 연산이나 판독 연산을 수행하려다 실패하고 복귀된 트랜잭션은

새로운 타임스탬프를 부여받아 재실행을 시도해야 한다.

 

 

 

위의 스케줄은 TS(T1) < TS(T2)가 되고

모든 연산들은 타임스탬프 규약을 위반하지 않으므로 직렬이 가능하다.

 

 

대기 그래프

.

 

교착상태 탐지하는 가장 간단한 방법은 '대기 그래프'를 구축하는 것이다.

대기 그래프에 사이클이 생성되기만 하면 교착상태가 발생했다고 판단한다.

 

시스템이 교착상태에 있다는 것이 탐지되면

교착상태에 관련된 트랜잭션 하나를 선정하여 취소시키고

그 트랜잭션에 의해 변경된 데이터 아이템들을 원상태로 복귀나 회복시켜야 한다.

 

이때 취소시킬 트랜잭션은 작업이 가장 적게 수행된 트랜잭션이 선정되는 것이 효율적이다.

 

 

 

 

 

 

 

 

* 해당 글은 '데이터베이스 시스템' 책을 참고하여 작성하였습니다. 출처: 데이터베이스 시스템 (이석호)