교착 상태 복구 (Deadlock Recovery)

핵심 개념

교착 상태 복구(Deadlock Recovery)는 탐지된 교착 상태를 해소하기 위해 프로세스 종료 또는 자원 선점을 수행하는 기법입니다. 탐지 기반 전략은 반드시 복구 기법과 함께 사용해야 합니다.

동작 원리

방법 1: 프로세스/스레드 종료

전략	설명	장단점
전체 종료	교착된 모든 프로세스 중단	확실하지만 비용 큼 (부분 계산 손실)
하나씩 종료	사이클 해소될 때까지 하나씩 종료	비용 최소화 가능, 매번 탐지 재실행 필요

Victim 선택 기준

1. 프로세스 우선순위
2. 실행 시간 및 남은 작업량
3. 사용 중인 자원 종류와 수
4. 완료까지 필요한 자원 수
5. 종료 시 영향받는 프로세스 수

방법 2: 자원 선점 (Resource Preemption)

교착 프로세스로부터 자원을 강제 회수하여 다른 프로세스에 할당합니다.

이슈	설명
Victim 선택	비용 최소화 기준으로 어떤 프로세스에서 어떤 자원을 선점할지 결정
롤백 (Rollback)	선점당한 프로세스는 안전한 상태로 되돌린 후 재시작. 단순 방법은 전체 롤백
기아 방지	동일 프로세스가 반복 victim이 되지 않도록 rollback 횟수를 비용 요소에 포함

예시

교통 정체 해소와 유사합니다. 차 한 대를 견인(종료)하거나, 특정 차의 짐을 다른 차로 옮깁니다(선점).

데이터베이스 시나리오:

트랜잭션 T1, T2가 교착
→ T2를 victim으로 선택 (실행 시간 짧음)
→ T2 abort & rollback
→ T2가 보유한 락 해제
→ T1 진행 가능
→ T2 재실행

실제 시스템 적용

• 데이터베이스 (MySQL 등): 주기적으로 wait-for graph 사이클 탐지 → victim 트랜잭션 abort 및 rollback
• 운영체제: 대부분 교착 무시 (ostrich algorithm). 드물게 발생하므로 수동 재부팅으로 대응

관련 개념

• [[교착 상태 탐지 (Deadlock Detection)]]
• [[교착 상태 (Deadlock)]]
• [[은행원 알고리즘 (Banker’s Algorithm)]]