15. Dead lock

교착상태.

 

2개의 트렌젝션 A, B가 각각 X, Y에 대한 lock 을 가지고 있을 때,

다음을 가정해보자.

 

1. A는 Y의 lock을 요구한다.

2. B는 X의 lock을 요구한다.

 

A가 Y의 lock을 받기 위해선, B가 X를 받아야 하고,

그 반대의 경우도 마찬가지다.

이렇게 서로 상대방의 lock만 보는 상황을 Dead lock, 교착 상태라 한다.

 

 

Transaction Timestamp (TS)

가장 많이 쓰는 prevention 기법

 

Transaction이 시작한 시간별로, wait를 할지, restart를 할지 결정

시간이 작으면, old 트렌젝션

시간이 크면 new 트렌젝션 으로 본다.

Ex) 오후 2시 : 14:00, 오후 4시 : 16:00

 

wait-die

Ti가 old 트렌젝션, Tj가 new 트렌젝션일 때,

Tj가 점유중인 자원이 있다면, Ti는 대기

반대로, Ti가 점유중이라면, Tj는 abort/restart

이 때 같은 Timestamp로 재시작한다.

 

wound-wait

Tj가 점유중인 자원을 Ti가 요청하면, Tj는 abort해야 함

Tj는 나중에 같은 Timestamp로 재시작

 

 

Tiimestamp를 안 쓰는 방법으로 No waiting 알고리즘이 있는데,

이거는 lock을 획득 못하면, abort시키고 나중에 재시작

 

locking과의 차이

locking은 순서가 무작위기 때문에, deadlock 발생 가능성이 있지만,

timestamp는, 오래된 트렌젝션으로 인해 starvation(기아 상태)가 발생한다.

 

 

Cautious waiting 알고리즘

불필요한 abort/restart를 줄이기 위한 방법

1. Tj가 점유중인 자원을 Ti가 요청한다.

2. Tj가 blocked되지 않은 상태라면,

3. Ti는 blocked상태가 되고, 대기한다.

4. Tj가 blocked 상태라면, Ti를 abort 시킨다.

 

blocked : 다른 item lock을 기다리는 상태

 

Multiple Granularity Locking

Granularity : locking의 단위

무엇을 그룹으로 묶냐에 따라 과부하, 세는 단위가 변한다.

 

field < record < block < file < database

순으로, locking 단위가 커질수록, 관리하기는 편하지만, 동시성엔 과부하가 커진다.

 

한 단위의 락을 얻게 되면, 하위 요소들은 암묵적으로 (implicit) lock을 얻은걸로 친다.

 

conflict

단위가 다르게 되면, 다음과 같은 문제가 발생한다.

 

1. 파일 A에 대해 lock을 얻고 작업을 하는 도중 다른 트렌젝션이 A의 레코드의 lock을 요구.

2. lock 테이블엔 파일에 대한 lock 정보만 있지, record 정보는 없음

3. 이러한 상황은 phantom 연산과 비슷

 

이러한 상황을 해결해 주는게 Multiple Granularity Locking이다.

 

특정 노드 N에 lock을 걸게 되면

상위 노드엔 intention lock(path lock) 걸음

하위 노드엔 implicit lock으로 봄