DBMS의 교착 상태
문제 상황
- T1은 Student 테이블의 lock을 보유하고, Grade 테이블의 lock을 얻을려 요청해 대기
- T2은 Grade 테이블의 lock을 보유하고, Student 테이블의 lock을 얻을려 요청해 대기
위의 2 트랜잭션은 서로 보유중인 lock을 계속 보유하며 서로가 가지지 못한 lock을 계속 대기합니다.
Deadlock Prevention
Deadlock이 발생할 가능성을 봉쇄
- 모든 lock을 동시에 요청 → 거부될 경우, 모두 헤재
- 데이터에 순서 부여 → 순서대로 lock 요청
| Wait-Die | Wound-Wait |
|---|---|
| 비선점적 | 선점적 |
| 오래된 트랜잭션이 A를 lock했고, 나중의 트랜잭션이 A를 요청했을 때, 나중의 트랜잭션은 rollback(die) | 오래된 트랜잭션이 A를 lock했고, 나중의 트랜잭션이 A를 요청했을 때, 요청하는 트랜잭션은 점유 중인 트랜잭션이 자원을 해제할 때까지 Wait |
| 나중의 트랜잭션이 A를 lock했고, 오래된 트랜잭션이 A를 요청했을 때, 오래된 트랜잭션은 Wait | 나중의 트랜잭션이 A를 lock했고, 오래된 트랜잭션이 A를 요청했을 때, 점유 중인 트랜잭션을 중단시키고 해당 자원을 요청하는 오래된 트랜잭션에게 할당 원래 소유하던 나중의 트랜잭션은 rollback(wound) |
| 중단 및 롤백이 더 자주 발생 | 중단 및 롤백 횟수가 비교적 적음 |
- 오래됨과 나중된 트랜잭션을 구분하기 위해서 둘다 타임스탬프가 필요
Deadlock Detection
-
Wait-For Graph:
G = (V, E)-
V: Set of transactions
-
E: Set of Tw → Th, where Tw is waiting for Th
-
이 그래프에 사이클 발생시, Deadlock으로 판단
-
Deadlock Resolution
- Selection of a victim transaction
- Victim transaction의 rollback
- Starvation의 발생 여부
예제로 보는 Deadlock
-
예제 트랜잭션 스케줄 1
-
Wait-For Graph 1
-
예제 트랜잭션 스케줄 2
트랜잭션은 4개가 있고, 자원들은 A, B, C로 총 3개가 있습니다.
-
Wait-For Graph 2
위의 트랜잭션은 사이클이 없어 deadlock이 아닙니다.