[DB] 데드락

데드락

Deadlock handling

Timeout-based schemes

일정 시간이 지나도 응답이 없으면 해당 트랜잭션을 롤백하는 방법 -> 구현은 쉬우나 starvation 발생
적절한 시간 설정이 어려움

트랜잭션 수행 전에 모든 데이터의 lock 을 검사하여 방지 = 현실적으로 불가능

 

Wait-die / Wound-wait scheme

트랜잭션이 시작된 시간을 timestamp 로 삼고, 이를 기준으로 처리하는 기법

 

Wait-die scheme

Non-preemtive approach (비선점형 방식)

Ti -> Tj := Ti 가 Tj 가 선점한 자원에 lock 을 요청함

이런 상황일 때 Ti 가 Tj 보다 old -> Ti 가 wait

young -> Ti 가 die

Wound-wait scheme

Preemtive approach

Ti -> Tj, Ti 가 old 이면 wound(rollback)

Ti 가 young 이면 wait

wait-die 기법보다 더 잦은 rollback 이 일어남

 

두 방법 모두 original timestamp 를 기준으로 트랜잭션의 나이를 판단함으로서 starvation 문제를 해결함

original timestamp = die 혹은 rollback 이후에 재시작하더라도 기존의 timestamp 를 가짐

따라서 언젠가는 oldest 트랜잭션이됨

 

Deadlock detection

wait-for graph : Ti 가 Tj 의 종료를 기다리는 그래프

wait-for 그래프에 사이클이 발생하면 데드락 발생

 

해결법

사이클 내 트랜잭션(victim)을 골라 롤백

이 때 가장 코스트가 적은 victim 을 골라 롤백하는 것이 중요함 -> starvation 발생 가능 -> 비용 계산 시 롤백횟수도 고려

물론 전체를 다 롤백하는 방법도 있음