[Concurrency Control]Deadlock

데드락을 해결하는 방법에 대해 알아보자.

 

 

 

위와 같이 데드락이 발생할 수 있다.

해결 방법은 여러 가지가 있다. prevention, detection

 

Prevention

1. timeout을 활용

쉬운 방법이긴 하지만 timetout interval을 정하는 것이 어렵고 starvation이 발생할 수도 있다.

 

2.deadlock prevention

트랜잭션 수행하기 전에 어떤 아이템에 접근하는지 파악해서 방지하는 것이다. 이 방법은 어렵다.

pratial ordering으로 데이터에 접근하도록 하는 것이다. 이 방법은 graph-based protocol에서 살펴보았다.

 

3.wait-die/ wound-wait(preemption) 

트랜잭션이 timestamp를 가지는 것을 이용한다. timestamp는 트랜잭션이 시작한 시간이다.

wait-die sheme

Ti가 Tj에게 락을 요청할 때 Ti가 old하면 wait하고 아니면 die하는 방식이다. 

 

Ti가 Tj보다 먼저 실행한 경우를 생각해보자.

Ti         Tj

L(X)      L(Y)

W(X)     W(Y)

 ?          ?

W(Y)     W(X)

 

? 부분에서 각자 Y,X에 락을 얻으려고 할 것이다. 같은 시간에 실행되지는 않을 것이니 Ti의 L(Y) 가 먼저 수행되었다고 해보자.  Ti가 Tj보다 old 하다고 했으므로 wait이 된다. Tj의 L(X)를 할 때 Ti보다 young하므로 die한다. 따라서 Ti의 트랜잭션이 진행된다.

 

Tj의 락이 먼저 수행되면 어떻게 될까? Tj가 young하므로 Tj는 die하고 Ti는 이어서 수행된다.

 

wound-wait

상대방 트랙잭션에 상처를 입히는(롤백시키는) 방식이다. old하면 wound시키고 young하면 wait한다. 앞 선 예제에서 Ti가 old하므로 Ti가 Tj를 wound시키게 된다.

 

wait-die, wound-wait 둘 다 재실행 될 때 초기의 타임스탬프를 가진다. 즉, 가장 old해지도록 하여 우선권을 주게 된다.

 

Detection

데드락이 발생했을 때 문제를 해결하는 방식이다. 우선, 데드락이 발생한 상황인지 파악하여야 한다. 이 때 wait-for graph를 사용한다. wait를 하고 있으면 화살표를 그린다. Ti가 Tj를 기다린다면 Ti --> Tj 로 그리면 된다. 이렇게 그렸을 때 사이클이 있다면 데드락이 발생한다고 본다. 주기적으로 디텍션을 하여 데드락을 파악한다.

데드락이 감지되면 사이클을 만드는 트랜잭션 중 하나를 롤백시킨다. 트랜잭션을 선택하는 기준은 롤백을 시켰을 때 비용이 가장 적은 것이 되어야 할 것이다.

 

이 때, 롤백 방법은 total rollback과 partial rollback으로 나뉜다. 

total rollback: 트랜잭션을 전부 abort하고 다시 실행

partial rollback: 데드락을 만드는 요청 바로 전 지점으로 롤백

 

롤백 비용이 적게 되면 계속 롤백 대상이 된다. 이렇게 되면 starvation이 되므로 롤백 횟수에 따라 우선권을 주도록 해야한다.

 

락에 대한 대기가 발생할 가능성은 적고 데드락이 발생할 가능성은 더욱 적다. 데이터베이스 시스템에서 데드락 처리를 다 해주고 있음을 기억하자.