Deadlock

Deadlock

위와 같이 모든 트랜잭션이 다른 트랜잭션이 release 하기를 wait 하는 상황이면 deadlock 이다.

 

Deadlock Handling

Timeout-based Schemes

일정 시간이 지나도 응답이 없으면 해당 트랜잭션을 rollback

-> 구현은 쉬우나 starvation 발생한다.
-> 적절한 시간 설정이 어렵다.

Deadlock prevention protocol

트랜잭션 수행 전에 모든 데이터에 lock 을 검사한다.

모든 데이터 아이템에 부분적인 순서를 두고, 트랜젝션이 아이템들을 이 순서에 따라 lock하도록 한다. (graph-based)

 

Wait-die/Wound-wait Schemes

deadlock을 방지하기위해 트랜잭션 timestamps를 사용한다.

Wait-die scheme

- 비선점 방식

- Old 트랜잭션은 Young 트랜잭션이 데이터 아이템을 내려놓을 때 까지 기다린다. (Wait)

- Young 트랜잭션은 Old 트랜잭션을 기다리지 않고 rollback한다. (Die)

- 트랜잭션은 필요한 아이템을 얻기 위해 여러번 rollback 당할 수 있다.

Wound-wait scheme

- 선점 방식

- Old 트랜잭션은 Young 트랜잭션을 rollback 시킨다. (Wound)

- Young한 트랜잭션은 Old한 트랜잭션을 기다린다. (Wait)

- wait-die 보다 rollback이 적을 수 있다.

 

-> 두 정책에서, rollback된 트랜잭션은 기존 타임스탬프를 가지고 재시작한다.
따라서 언젠가는 가장 old 한 트랜잭션이 될 것이기 때문에 starvation 이 발생하지 않는다.

 

Deadlock Detection 

wait-for graph(prededence graph) 에 사이클이 존재한다면 deadlock 이 발생한다.

deadlock이 발생했다면 victim 트랜잭션을 선정하여 rollback시킨다.

victim은 rollback하는데 최소의 비용이 드는 트랜잭션이다.

Total / Partial rollback

Total : 트랜잭션을 abort하고 재시작한다.
Partial : deadlock을 없애기 위해 필요한 만큼만 rollback -> 더 효율적

-> 항상 같은 트랜잭션이 Victim으로 선정되면 Starvation이 일어난다.

 

사실 Lock waits 도 거의 일어나지 않으며, deadlock 은 거~의 발생하지 않는다고 봐도 무방하다.