#09 교착상태 (DeadLock)

서로 눈치만 보다 아무도 못 가는 상황

동기화 글에서 뮤텍스 unlock()을 빠뜨리면 교착상태가 생긴다고 했는데, 이번엔 그게 정확히 뭔지 파보자.

이미지를 보면 직관적으로 이해돼. 네 방향에서 차가 동시에 교차로에 진입해서 서로 앞을 막아버린 상황이야. 아무도 양보하지 않으면 영원히 못 빠져나와. 이게 교착상태야.

---

교착상태란?

두 개 이상의 프로세스가 서로 상대방이 가진 자원을 기다리며 무한히 대기하는 상태야. (출처: 공룡책 Silberschatz, 10th Edition)

동기화 글에서 봤던 뮤텍스를 예시로 보자.

// Thread 1
mutex1.lock();
mutex2.lock(); // Thread 2가 mutex2를 잡고 있어서 대기
// ...

// Thread 2
mutex2.lock();
mutex1.lock(); // Thread 1이 mutex1을 잡고 있어서 대기
// ...

Thread 1: mutex1 보유 → mutex2 기다림
Thread 2: mutex2 보유 → mutex1 기다림
→ 서로를 기다리며 영원히 멈춤

 

 

면접 포인트 ( •̀ ω •́ )✧

Q. 교착상태란?

두 개 이상의 프로세스가 서로 상대방이 보유한 자원을 기다리며 무한히 대기하는 상태야. 아무도 자원을 양보하지 않아서 영원히 진행이 안 돼.

---

교착상태 발생 조건 — 4가지가 동시에 충족되어야 해

공룡책에서 Coffman 조건이라고 부르는 네 가지야.

네 가지가 동시에 성립할 때만 교착상태가 발생해.

 

1. 상호 배제 (Mutual Exclusion)

자원을 한 번에 하나의 프로세스만 사용할 수 있어. 뮤텍스처럼 동시 접근이 불가능한 자원이어야 해.

 

2. 점유와 대기 (Hold and Wait)

자원을 최소 하나 보유한 채로 다른 자원을 기다리고 있어. "내 것은 놓지 않고 네 것을 달라"는 상황이야.

 

3. 비선점 (No Preemption)

프로세스가 자원을 자발적으로 놓기 전까지 강제로 빼앗을 수 없어.

 

4. 순환 대기 (Circular Wait)

프로세스들이 원형으로 서로를 기다리고 있어.

P1 → P2 → P3 → P1 (순환)
(P1이 P2가 가진 자원을 기다리고,
 P2가 P3가 가진 자원을 기다리고,
 P3가 P1이 가진 자원을 기다리는 구조)

 

 

여기서 중요한 포인트 — 이 네 가지 중 하나라도 깨면 교착상태가 발생하지 않아. 교착상태 처리 전략들이 전부 이 조건 중 하나를 깨는 방식으로 동작해.

 

 

면접 포인트 ( •̀ ω •́ )✧

Q. 교착상태 발생 조건 4가지는?

상호 배제, 점유와 대기, 비선점, 순환 대기. 네 가지가 동시에 성립해야 교착상태가 발생해. 하나라도 깨면 교착상태가 생기지 않아.

 

---

자원 할당 그래프 (Resource Allocation Graph)

교착상태를 시각적으로 표현하는 방법이야. (출처: 공룡책 Chapter 8)

P → R : 프로세스가 자원을 요청 (Request Edge)
R → P : 자원이 프로세스에 할당 (Assignment Edge)

사이클이 없으면 → 교착상태 없음

사이클이 있으면 → 교착상태 가능 (자원 인스턴스가 하나면 무조건 교착상태)

---

교착상태 처리 방법

크게 세 가지 전략이 있어. (출처: 공룡책 Chapter 8, Silberschatz 10th Edition)

---

1. 예방 (Prevention) — 조건 자체를 깨버리기

4가지 조건 중 하나라도 성립하지 않으면 교착상태가 발생하지 않아. 각 조건을 어떻게 깰 수 있는지 보면 이래.

1) 상호 배제 제거 — 자원을 공유 가능하게 만들어. 근데 프린터처럼 원래 공유가 불가능한 자원은 이 방법을 쓸 수 없어.

2) 점유와 대기 제거 — 두 가지 방법이 있어.

방법 1: 프로세스 시작 전에 필요한 모든 자원을 한 번에 요청
        → 자원 효율이 낮아져

방법 2: 자원을 요청할 때 기존에 보유한 자원을 전부 반납하고 재요청
        → Starvation 가능성이 있어

3) 비선점 제거 — 자원을 강제로 빼앗을 수 있게 해. CPU나 메모리는 가능하지만, 프린터처럼 중간에 뺏기 어려운 자원도 있어.

4) 순환 대기 제거 — 자원에 번호를 매기고, 항상 오름차순으로만 자원을 요청하게 해.

R1(1번) → R2(2번) → R3(3번) 순서로만 요청 가능
R3를 가지고 있으면 R1은 요청 불가
→ 순환 구조 자체가 불가능해짐

 

2. 회피 (Avoidance) — 안전 상태만 유지하기

자원 요청이 들어올 때마다 "이 요청을 들어줘도 교착상태가 생기지 않는 안전 상태인지" 미리 확인하는 방식이야.

Safe State (안전 상태) — 모든 프로세스가 순서대로 자원을 할당받아 완료할 수 있는 순서(Safe Sequence)가 존재하는 상태야.

Safe State   → 교착상태 절대 없음
Unsafe State → 교착상태 가능성 있음 (반드시 발생은 아님)
Deadlock     → 교착상태 발생

은행원 알고리즘 (Banker's Algorithm)

Edsger Dijkstra가 개발한 알고리즘이야. 은행이 돈을 빌려줄 때 파산하지 않을 때만 대출해주는 것처럼, OS가 자원을 줄 때 안전 상태가 유지될 때만 할당해.

각 프로세스가 필요한 최대 자원 수를 미리 신고
자원 요청이 들어오면:
  1. 요청을 들어줬다고 가정
  2. 이 상태에서 Safe Sequence가 존재하는지 확인
  3. 있으면 → 자원 할당
     없으면 → 안전 상태가 될 때까지 대기

단점이 있어 — 각 프로세스가 필요한 최대 자원 수를 미리 신고해야 하는데, 실제로 이게 어려운 경우가 많아. 그래서 실무에서는 잘 안 써.

 

3. 탐지 & 회복 (Detection & Recovery) — 발생 후 처리

교착상태 발생을 허용하고, 주기적으로 탐지해서 복구하는 방식이야. 실무에서 가장 많이 쓰이는 방법이야. \

탐지 방법

자원 할당 그래프에서 사이클을 탐지해. Wait-for Graph(대기 그래프)에서 사이클이 발견되면 교착상태야.

Wait-for Graph: 프로세스 → 프로세스 (기다리는 관계만 표시)
사이클 있음 → 교착상태

회복 방법 -- 두 가지 방식이 있어.

프로세스 종료 (Process Termination)
  방법 1: 교착상태 프로세스 전부 종료 → 확실하지만 손실이 큼
  방법 2: 사이클이 없어질 때까지 하나씩 종료 → 오버헤드 있음

자원 선점 (Resource Preemption)
  교착상태 프로세스에서 자원을 강제로 빼앗아 다른 프로세스에 줌
  → 피해 최소화할 프로세스 선택 필요
  → Starvation 주의 (같은 프로세스만 계속 희생되면 안 됨)

 

4. 무시 (Deadlock Ignorance)

 

 

면접 포인트 ( •̀ ω •́ )✧

Q. 교착상태 처리 방법 세 가지는?

예방(4가지 조건 중 하나를 원천 차단), 회피(안전 상태만 유지하도록 자원 할당 조절, 은행원 알고리즘), 탐지 & 회복(발생 후 사이클 탐지하고 프로세스 종료 또는 자원 선점으로 복구).

Q. 은행원 알고리즘이란?

자원 요청이 들어올 때 그 요청을 들어줬을 때도 Safe State가 유지되는지 미리 확인하는 알고리즘이야. Safe Sequence가 존재하면 할당, 없으면 대기. 단점은 각 프로세스가 최대 자원 수를 미리 신고해야 해서 실용성이 낮아.

---

실무에서는 어떻게 해?

운영체제 수준에서 교착상태를 완벽하게 예방하는 건 오버헤드가 너무 커. 그래서 실무에서는 무시하거나, 탐지 & 회복 방식을 주로 써.

• Linux, Windows — 교착상태를 OS 레벨에서 처리하지 않아. 개발자가 직접 관리해야 해
• Database — 트랜잭션 레벨에서 교착상태를 탐지하고, 하나의 트랜잭션을 롤백해서 회복해. MySQL, PostgreSQL이 이 방식이야
• Java — ReentrantLock의 tryLock(timeout) 으로 일정 시간 안에 락을 못 얻으면 포기하게 해서 교착상태를 피할 수 있어

// Java에서 교착상태 예방 — tryLock 사용
if (mutex1.tryLock(1, TimeUnit.SECONDS)) {
    try {
        if (mutex2.tryLock(1, TimeUnit.SECONDS)) {
            try {
                // 두 락 모두 획득 성공
            } finally {
                mutex2.unlock();
            }
        }
    } finally {
        mutex1.unlock();
    }
}
// 시간 안에 못 얻으면 → 포기하고 재시도 → 교착상태 방지

 

 

 

면접 포인트 ( •̀ ω •́ )✧

Q. 실무에서 교착상태를 어떻게 처리해?

OS 레벨에서는 대부분 무시하고 개발자가 관리해. DB는 탐지 & 회복 방식으로 트랜잭션 하나를 롤백해. Java에서는 tryLock(timeout)으로 일정 시간 안에 락을 못 얻으면 포기하게 해서 예방해.

---

교착상태에서 제일 중요한 건 4가지 조건이야. 면접에서 조건 하나씩 설명하면서 "이 조건을 깨는 방식이 예방 전략이고, 각각 트레이드오프가 있다"는 흐름으로 답할 수 있으면 충분해. 실무에서는 완벽한 예방보다 탐지 & 회복이 현실적이라는 것도 같이 말하면 좋아.