데드락 — 서로가 서로를 기다리다 멈추다

앞 편의 자물쇠들은 공유 자원을 보호하지만, 여럿을 잘못 쓰면 새로운 재앙을 부른다 — **데드락(교착 상태)**이다. A가 자물쇠 1을 쥔 채 자물쇠 2를 기다리고, B가 자물쇠 2를 쥔 채 자물쇠 1을 기다리면 — 둘 다 영원히 멈춘다. 누구도 양보하지 않으니 시간이 흘러도 안 풀린다. 좁은 다리에서 마주 온 두 차가 서로 안 물러나는 것과 같다. 데드락이 언제 생기고, 어떻게 막는지를 본다.

네 가지가 모두 모일 때 — Coffman 조건

데드락은 아무 때나 생기지 않는다. 네 가지 조건이 동시에 충족돼야만 생긴다(Coffman 조건). ① 상호 배제 — 자원을 한 번에 하나만 쓸 수 있다. ② 점유와 대기(hold and wait) — 이미 하나를 쥔 채 다른 걸 기다린다. ③ 비선점(no preemption) — 쥔 자원을 강제로 뺏을 수 없다(자발적 반납만). ④ 순환 대기(circular wait) — A→B→C→A처럼 기다림이 고리를 이룬다.

중요한 건 — 이 넷이 모두 있어야 데드락이라는 점이다. 그래서 넷 중 하나만 깨도 데드락은 안 생긴다 — 이게 모든 대응의 출발점이다. (출처: Coffman conditions.)

어떻게 다루나 — 예방·회피·탐지·무시

데드락 대응은 네 갈래다. **예방(prevention)**은 네 조건 중 하나를 원천적으로 못 생기게 한다. 가장 실용적인 게 순환 대기 깨기 — 모든 스레드가 자원을 항상 같은 순서로 잠그게 하면 고리가 안 생긴다(A도 B도 락1 먼저, 락2 나중이면 서로 엇갈릴 일이 없다). *"여러 자원을 잠글 땐 락 순서를 일관되게"*가 바로 이 예방의 실천이다. **회피(avoidance)**는 실행 중에 — 이 요청을 들어주면 데드락 위험이 있나를 미리 계산해, 안전한(safe) 상태가 유지될 때만 자원을 준다(은행원 알고리즘: 모두가 최대치를 요구해도 끝낼 수 있는지 확인). **탐지(detection)**는 일단 허용하고, 주기적으로 자원 할당 그래프에 고리가 생겼나 검사해 — 발견하면 일부를 강제 종료·롤백해 푼다(DB가 흔히 이 방식: 데드락을 감지해 한 트랜잭션을 희생시킨다). 마지막으로 무시(타조 알고리즘) — 아주 드물면 그냥 두고, 나면 재시작한다(많은 OS의 현실적 선택). (출처: Deadlock prevention/avoidance/detection.)

사촌들 — 라이브락과 우선순위 역전

데드락과 헷갈리는 사촌이 둘 있다. **라이브락(livelock)**은 — 멈추진 않는데 진행도 못 하는 상태다. 좁은 복도에서 마주친 둘이 서로 같은 방향으로 비키기를 반복하며 영영 못 지나가는 것과 같다(데드락 회피를 어설프게 짜면 생긴다). **우선순위 역전(priority inversion)**은 — 높은 우선순위 작업이 낮은 우선순위 작업이 쥔 락을 기다리는데, 그 사이 중간 우선순위 작업이 낮은 작업을 선점해 — 높은 작업이 사실상 중간 작업에 막히는 역설이다(화성 탐사선 Pathfinder의 유명한 버그). 해법은 우선순위 상속 — 높은 작업이 기다리는 동안 락을 쥔 낮은 작업의 우선순위를 잠시 올려 빨리 끝내게 한다. (출처: Priority inversion.)

실무에서는 — 데이터베이스의 데드락(여러 행을 잠글 때 순서 일관·짧은 트랜잭션·재시도)이 바로 이 OS 데드락이 데이터 계층에 그대로 나타난 것이다. 임베디드·실시간 시스템(RTOS)에서는 우선순위 역전과 상속이 핵심 주제다. 결국 데드락 대응의 왕도는 — *예방(특히 락 순서 일관)*으로 애초에 고리를 안 만드는 것이고, 못 막으면 짧은 보유·재시도로 충돌을 작게 만드는 것이다.

정리하면, 데드락은 상호 배제·점유와 대기·비선점·순환 대기 네 조건이 모두 모일 때 생기는 상호 교착이다 — 그래서 넷 중 하나만 깨면 막을 수 있다(가장 실용적인 건 락 순서 일관으로 순환 대기 깨기). 대응은 예방·회피(은행원)·탐지(DB)·무시(타조) 네 갈래이고, 사촌인 *라이브락(진행 없는 분주함)*과 *우선순위 역전(상속으로 해결)*도 함께 알아 둔다. 이 모든 동시성 이야기 — 경쟁 조건·자물쇠·데드락 — 는 스레드가 자원을 공유하기에 생긴다. 다음은 그 자원 중 가장 중요한 것, 메모리를 OS가 어떻게 속이는지다.