Wait-For Graph

데드락 탐지는 사이클을 찾고, 해결은 그 사이클을 한 군데 끊는 것입니다.

DBMS는 누가 누구의 락 해제를 기다리는지 추적합니다. 그 대기 관계가 원으로 닫히면 더 이상 스스로 풀리지 않으므로, 트랜잭션 하나를 강제로 ROLLBACK해 전체 대기를 해소합니다.

1. 대기 그래프에서 사이클 확인

각 간선은 “내가 가진 락이 아니라, 상대 트랜잭션이 가진 락을 기다린다”는 뜻입니다.

T1 락 A는 보유, 락 B를 기다림 T2가 B를 놓아야 다음 UPDATE 가능
T1 -> T2
T2 락 B는 보유, 락 A를 기다림 T1이 A를 놓아야 다음 UPDATE 가능
T2 -> T1 서로가 서로를 기다리면 원형 대기가 완성되고, 이것이 데드락입니다.
중요: 단순한 대기는 잠시 후 풀릴 수 있지만, 사이클이 있는 대기는 외부 개입 없이는 끝나지 않습니다.

2. 사이클을 끊어 다시 진행

탐지의 목적은 “문제가 생겼다”를 알리는 것이 아니라, 락 하나를 풀어 남은 작업을 이어가게 만드는 것입니다.

01
주기적으로 그래프 검사 대기 중인 트랜잭션 관계를 모아 사이클이 생겼는지 확인합니다.
02
희생자 1개 선택 사이클에 포함된 트랜잭션 중 하나를 강제로 중단해 교착을 끊습니다.
03
ROLLBACK으로 락 해제 선택된 트랜잭션이 점유하던 락이 풀리면, 다른 트랜잭션이 바로 진행할 수 있습니다.
다음 절과 연결되는 포인트: 모든 DBMS가 공통으로 하는 일은 사이클을 찾아 한쪽을 되돌리는 것입니다. 차이는 언제 탐지하는지, 그리고 얼마나 롤백하는지에 있습니다.