deadlock이란 무엇이며, 어떻게 예방·회피·탐지하는가?

Question

IT Interview Practice · Accepted Answer

**deadlock**(교착 상태)은 둘 이상의 thread가 각각 **영원히 block**된 채, 각자가 다른 쪽이 보유한 자원을 기다리는 상태다. 아무것도 진행되지 않는다.

## 네 가지 필요(Coffman) 조건

네 가지가 동시에 성립해야 한다 — 어느 하나라도 없애면 deadlock은 불가능하다:

```text
1. Mutual exclusion   → a resource is held exclusively (only one holder at a time)
2. Hold and wait      → a thread holds one resource while waiting to acquire another
3. No preemption      → resources can't be forcibly taken; only released voluntarily
4. Circular wait      → a cycle: T1 waits for R2 (held by T2), T2 waits for R1 (held by T1)
```

```text
   T1 ──holds──▶ R1        T1 wants R2 ──▶ (held by T2)
   T2 ──holds──▶ R2        T2 wants R1 ──▶ (held by T1)   ← cycle = deadlock
```

## deadlock 다루기

- **예방(Prevention)** — 어느 한 조건이 결코 성립하지 못하도록 설계한다. 가장 실용적인 방법: **전역 lock 순서**를 강제해(항상 A를 B보다 먼저 획득) **circular wait**를 없앤다. 또는 필요한 모든 lock을 한꺼번에 잡아 **hold-and-wait**를 공략한다.
- **회피(Avoidance)** — 모든 thread가 여전히 끝마칠 수 있는 "안전한" 상태를 시스템이 유지할 때만 요청을 승인한다(**Banker's algorithm**). 각 thread의 최대 자원 필요량을 미리 알아야 해서 실무에서는 거의 쓰이지 않는다.
- **탐지 & 복구(Detection & recovery)** — deadlock이 일어나게 두고, 주기적으로 **wait-for graph**에서 cycle을 스캔한 뒤, 희생자를 죽이거나 rollback해 복구한다. 데이터베이스가 정확히 이렇게 한다: deadlock을 탐지하고 "deadlock victim" 오류로 한 트랜잭션을 중단시킨다.
- **무시("ostrich algorithm")** — deadlock이 드물다면 그냥 재시작한다. 많은 OS가 일부 자원에 대해 이를 받아들인다.

## 왜 중요한가

deadlock은 고전적인 면접 주제인데, 네 조건 프레임워크가 정밀한 진단 도구이기 때문이다: 어떤 hang 상황에서 "내가 깰 수 있는 조건은 무엇인가?"를 물을 수 있다. 실제 시스템에서 즐겨 쓰는 답은 **일관된 lock 순서**(circular wait를 예방)로, lock을 둘 이상 잡을 때마다 적용하는 규칙이다. 당신의 데이터베이스가 deadlock-victim 오류를 던진다는 것을 알아채고, 그 트랜잭션을 그냥 retry하면 된다는 것을 아는 것은 직접적인 실무 적용이다.

네 가지 필요(Coffman) 조건

deadlock 다루기

왜 중요한가

관련 질문