학습 목표
데드락 대응 4가지 전략(예방·회피·탐지+복구·무시)을 비교할 수 있다.
Banker 알고리즘이 안전 상태(safe state) 를 유지하는 방식을 설명할 수 있다.
탐지 알고리즘과 희생자 선택(victim) 복구의 트레이드오프를 설명할 수 있다.
실무에서 락 순서·타임아웃·무시(ostrich) 중 무엇을 쓰는지 판단할 수 있다.
문제 상황
- DB는 데드락 탐지 후 한 트랜잭션 롤백 — 애플리케이션은 그냥 락만 걸고 있다
- 모든 요청을 한꺼번에 자원 할당하면 데드락은 줄지만 자원 이용률이 떨어진다
- Banker는 교과서에만 있고 실제 OS는 다른 방식 — 왜 다른가
try_lock+ backoff는 데드락 예방인가 회피인가 그냥 운인가
필요조건을 봤다. 이번 편은 OS·DB가 어떻게 다루는지 전략별로 정리한다.
1. 네 가지(다섯 가지) 접근
| 전략 | 아이디어 | 예 |
|---|---|---|
| 예방 (Prevention) | 필요조건 하나를 **원천 차단** | 락 전역 순서, all-or-nothing 요청 |
| 회피 (Avoidance) | 요청 시 **안전한지 검사** 후 허용 | Banker 알고리즘 |
| 탐지 + 복구 | 주기적으로 사이클 찾고 **희생자** 중단 | DBMS, 일부 OS 옵션 |
| 무시 (Ignore) | 데드락이 드물다고 가정 | 전통적 Unix — 개발자 책임 |
- 대부분의 일반 OS는 예방·회피 비용이 커서 무시 + 개발자 가이드에 가깝다
- DBMS는 탐지·복구가 표준 — 트랜잭션 비용을 감수할 가치가 있음
2. 예방 — 실무에서 쓰는 것
| 깨는 조건 | 기법 | 실무 |
|---|---|---|
| 순환 대기 | 락 ordering | mutex A always before B |
| 점유 대기 | 모든 락을 한 번에 획득 | std::lock, pthread_mutex_timedlock 조합 |
| 상호 배제 | 읽기 공유 락(RW lock) | 읽기 많은 캐시 |
- all-or-nothing은 자원 낭비 — 잡기 전까지 아무것도 못 씀
- 타임아웃 락은 데드락을 보장 제거하진 않지만 hang을 줄임 — 재시도 로직 필요
3. 회피 — Banker 알고리즘
각 프로세스의 최대 필요량 Max, 현재 할당 Allocation, 남은 가용 Available을 추적한다.
안전 상태: 어떤 순서 <P_i, …>로 모든 프로세스가 끝날 수 있는 상태.
Need = Max - Allocation계산Available로Need ≤ Available인 프로세스 찾기- 가상 완료 → 자원 반환 → 반복
- 모두 완료 가능하면 안전 — 새 요청 허용 가능
- 불안전하면 거부 (프로세스 대기)
- 단점: 프로세스 수·자원 종류를 미리 알아야 하고, 오버헤드 큼
- 용도: 교육·이론, 일부 임베디드·자원 고정 환경
4. 탐지와 복구
탐지: RAG와 유사한 대기-for 그래프에서 사이클 검색 — 주기적 실행.
| 복구 | 방법 | 비용 |
|---|---|---|
| 프로세스 종료 | 전체 또는 희생자 하나 kill | 작업 손실 |
| 자원 선점 | 상태 롤백·체크포인트 | 구현 어려움, DB는 undo log |
- 희생자 선택 기준: 우선순위, 실행 시간, 필요 자원 수, 트랜잭션 횟수 …
- DB: 데드락 victim 트랜잭션 rollback → 애플리케이션 재시도
5. 무시 전략과 현실
Linux·Windows 커널은 범용 데드락 해결기를 돌리지 않는다.
- 개발자: 락 순서, 락 범위 최소화,
lock hierarchylint - 런타임: Go deadlock detector(개발 모드), ThreadSanitizer
- 인프라: watchdog, health check, orchestrator restart
6. 정리
- 예방은 조건 파괴, 회피는 Banker·안전 상태, 탐지·복구는 DB급
- 실무 앱: 순환 대기 제거 + 타임아웃·재시도가 현실적
- 다음: Producer-Consumer 등 동시성 패턴 사례
다음에 다룰 것
- 동시성 문제 사례
- Producer-Consumer, Readers-Writers
해당 내용은 Operating System Concepts, 10/E (Avraham Silberschatz, Peter Baer Galvin, Greg Gagne) 의 내용을 기반으로 합니다.