1. 프롤로그 - 4거리 교차로의 악몽

차가 꽉 막힌 좁은 사거리를 상상해보세요.

• 남쪽 차는 북쪽 차가 빠지길 기다립니다.
• 북쪽 차는 동쪽 차가 빠지길 기다립니다.
• 동쪽 차는 서쪽 차를... 서쪽 차는 남쪽 차를...

아무도 양보할 수 없고, 후진도 불가능합니다. 경찰이 와서 차 한 대를 크레인으로 들어내기 전까지는 이 상태가 영원히 지속됩니다. 이것이 바로 교착 상태(Deadlock)입니다. 컴퓨터 세상에서는 프로세스(혹은 스레드)들이 자원(메모리, 파일, DB 락)을 놓고 이런 대치 상황에 빠집니다.

---

2. 역사와 배경 (History)

• 1965년: 에츠허르 데이크스트라(Edsger W. Dijkstra)가 "식사하는 철학자 문제"를 통해 동시성 제어의 난제를 제시했습니다.
• 1971년: 에드워드 코프만(Edward Coffman) 등이 데드락의 4가지 필요 조건(Coffman Conditions)을 정립했습니다. 이 논문은 OS 교과서의 바이블이 되었습니다.
• 1980년대: 분산 데이터베이스 시스템이 등장하면서, 단일 머신을 넘어선 분산 데드락(Distributed Deadlock) 탐지 알고리즘(Chandy-Misra-Haas 등)이 연구되기 시작했습니다.

---

3. 데드락 발생의 4가지 조건 (Coffman Conditions)

데드락이 발생하려면 4가지 조건이 "동시에" 충족되어야 합니다. 역으로 말하면, 이 중 하나만 깨도 데드락은 풀립니다. (이것이 예방 기법의 핵심입니다).

1) 상호 배제 (Mutual Exclusion)

• "이 자원은 나 혼자만 쓸 거야."
• 자원은 한 번에 한 프로세스만 사용할 수 있습니다. (예: 프린터, DB의 Write Lock).
• 공유 가능한 자원(Read-only 파일 등)에서는 데드락이 발생하지 않습니다.

2) 점유 대기 (Hold and Wait)

• "왼손에 포크 쥔 채로, 오른손 포크 내놔라고 기다리기."
• 최소한 하나의 자원을 점유한 상태에서, 다른 프로세스가 가진 자원을 추가로 요구하며 대기해야 합니다.

3) 비선점 (No Preemption)

• "뺏는 건 반칙이야."
• 다른 프로세스가 자원을 다 쓰고 스스로 내놓기 전까지는 강제로 뺏을 수 없습니다. (CPU 스케줄링은 선점이 가능하지만, 락이나 프린터는 보통 비선점입니다).

4) 순환 대기 (Circular Wait)

• "꼬리에 꼬리를 무는 기다림."
• 프로세스 집합 {P0, P1, ..., Pn}에서 P0는 P1을, P1은 P2를... Pn은 P0를 기다리는 순환 고리가 있어야 합니다.

---

4. 식사하는 철학자 문제 (Dining Philosophers)

데이크스트라가 만든 이 문제는 데드락을 설명하는 가장 우아한 비유입니다.

• 상황: 원탁에 5명의 철학자가 앉아있습니다. 각자 앞에는 스파게티가 있고, 철학자들 사이에는 포크가 하나씩 놓여 있습니다. (총 5개)
• 규칙: 스파게티를 먹으려면 양손에 포크(왼쪽, 오른쪽)를 들어야 합니다.

상황 - 데드락 발생 (The Deadlock)

1. 모든 철학자가 동시에 왼쪽 포크를 집어 듭니다. (점유 대기)
2. 모든 철학자가 오른쪽 포크를 집으려고 보니 없습니다. (오른쪽 사람이 가져갔으니까)
3. 모두가 왼쪽 포크를 쥔 채로, 오른쪽 포크가 나올 때까지 영원히 기다립니다. (순환 대기)
4. 결국 모두 굶어 죽습니다. (Starvation & Deadlock)

해결책 - 순환 대기 끊기 (Resource Hierarchy)

가장 쉬운 해결책은 "자원에 순서(Hierarchy)를 매기는 것"입니다.

• 규칙: "무조건 번호가 낮은 포크부터 집어라."
• 시나리오:
  • 철학자 1~4번: 낮은 번호(왼쪽) 먼저 집고 높은 번호(오른쪽) 집음.
  • 철학자 5번(마지막): 왼쪽(5번 포크)과 오른쪽(1번 포크) 중 1번 포크를 먼저 집어야 합니다.
  • 하지만 1번 포크는 이미 철학자 1번이 가져갔으므로, 철학자 5번은 1번 포크를 기다려야 합니다.
  • 이때 철학자 5번은 5번 포크를 아직 집지 않았으므로, 철학자 4번이 5번 포크를 가져가 식사를 할 수 있습니다.
  • 순환 고리가 끊깁니다!

---

5. 자원 할당 그래프 (Resource Allocation Graph, RAG)

OS는 데드락을 탐지하기 위해 RAG라는 방향 그래프를 그립니다.

• 노드(Node):
  • 프로세스(P): 원으로 표시.
  • 자원(R): 사각형으로 표시. (안에 자원의 개수를 점으로 표시).
• 엣지(Edge):
  • P -> R: 요청 (Request Edge). 내놓으라고 기다리는 중.
  • R -> P: 할당 (Assignment Edge). 이미 주고 사용 중.

판별법:

• 그래프에 사이클(Cycle)이 없다면? -> 데드락 아님.
• 그래프에 사이클이 있다면?
  • 자원 유형마다 인스턴스가 1개뿐이라면 -> 필연적 데드락.
  • 자원 인스턴스가 여러 개라면 -> 데드락일 수도 있고 아닐 수도 있음. (다른 프로세스가 자원을 반납해서 사이클을 깰 가능성이 있음).

---

6. 데드락 해결의 3가지 전략

1) 예방 (Prevention)

Coffman 조건 중 하나를 원천 봉쇄합니다. (가장 강력하지만 부작용이 큼).

• 상호 배제 부정: 모든 자원을 공유 가능하게? (현실적으로 불가능).
• 점유 대기 부정: 식사 시작 전 포크 2개를 한꺼번에 집거나, 하나도 못 집거나. (자원 효율성 저하).
• 비선점 부정: 뺏을 수 있게 만들기. (프린터 인쇄 중에 뺏으면 종이 찢어짐. 상태 저장/복구 비용 큼).
• 순환 대기 부정: Resource Ordering (철학자 해결책). 가장 현실적임.

2) 회피 (Avoidance) - 은행원 알고리즘

데드락 가능성이 보이면 아예 자원을 안 빌려줍니다.

• 은행원 알고리즘 (Banker's Algorithm):
  • OS가 "가상 시뮬레이션"을 돌려봅니다. "얘한테 빌려주면 남은 돈으로 다른 애들 다 처리하고 상환받을 수 있나?"
  • 가능하면 Safe State (승인).
  • 불가능하면 Unsafe State (거절 및 대기).
  • 단점: 모든 프로세스가 최대 자원 요구량을 미리 신고해야 하고, 계산 비용이 너무 커서 현대 OS는 잘 안 씁니다.

3) 탐지 및 복구 (Detection & Recovery)

일단 놔두고, 주기적으로 검사하다가 걸리면 죽입니다. (현대 OS와 DB의 주류 방식).

• 탐지: RAG에서 사이클 찾기 ($O(N^2)$).
• 복구:
  • Process Termination: 데드락 걸린 놈 중 하나(희생자)를 강제 종료(Kill).
  • Resource Preemption: 자원을 뺏어서 다른 놈 주기. (희생자는 롤백됨).
  • 희생자 선정 기준: 작업 진행률이 제일 낮은 놈, 자원을 제일 많이 먹은 놈 등.

참고: 타조 알고리즘 (Ostrich Algorithm) 유닉스나 윈도우 같은 범용 OS는 데드락을 무시합니다. "타조가 위험할 때 땅에 머리를 박듯이." 데드락은 드물게 발생하고, 해결 비용은 비싸므로, 그냥 "사용자가 재부팅하게 놔두는 것"이 가성비가 제일 좋다는 철학입니다.

---

7. 실제 Lab: Java & Database Deadlock

1) Java 코드로 재현하기

락 획득 순서가 꼬이면 바로 데드락입니다.

// Thread Dump를 뜨면 "Found one Java-level deadlock"이라고 나옵니다.
public class DeadlockLab {
    private static final Object LockA = new Object();
    private static final Object LockB = new Object();

    public static void main(String[] args) {
        Thread t1 = new Thread(() -> {
            synchronized (LockA) {
                System.out.println("T1: LockA 획득");
                try { Thread.sleep(100); } catch (Exception e) {}
                System.out.println("T1: LockB 대기 중...");
                synchronized (LockB) { // A 잡고 B 요청
                    System.out.println("T1: 성공");
                }
            }
        });

        Thread t2 = new Thread(() -> {
            synchronized (LockB) {
                System.out.println("T2: LockB 획득");
                try { Thread.sleep(100); } catch (Exception e) {}
                System.out.println("T2: LockA 대기 중...");
                synchronized (LockA) { // B 잡고 A 요청 -> 순환 대기 완성
                    System.out.println("T2: 성공");
                }
            }
        });

        t1.start(); t2.start();
    }
}

• 해결: T2도 synchronized(LockA) -> synchronized(LockB) 순서로 락을 잡으면 해결됩니다.

2) Database Deadlock

웹 백엔드 개발자가 가장 자주 만나는 상황입니다.

• 시나리오: 두 트랜잭션이 서로 교차 업데이트.

  • Tx1: UPDATE Users SET ... WHERE id=1 (Lock u1)
  • Tx2: UPDATE Orders SET ... WHERE id=99 (Lock o99)
  • Tx1: UPDATE Orders ... WHERE id=99 (Wait for Tx2)
  • Tx2: UPDATE Users ... WHERE id=1 (Wait for Tx1) -> Deadlock!

• DB 엔진의 대응:

  • MySQL InnoDB 같은 엔진은 즉시 데드락을 감지합니다.
  • 둘 중 롤백 비용이 적은 트랜잭션을 강제로 에러(Deadlock found when trying to get lock)와 함께 종료시킵니다.
  • 개발자는 이 에러를 잡아서 재시도(Retry) 로직을 구현해야 합니다.

---

8. 데드락의 사촌들: Livelock & Starvation

라이브락 (Livelock) - "복도 춤 (The Hallway Dance)"

• 상황: 좁은 복도에서 두 사람이 마주쳤습니다.
  • A가 왼쪽으로 비킵니다. B도 동시에 A 기준 왼쪽(자신 기준 오른쪽)으로 비킵니다. -> 또 마주침.
  • A가 오른쪽으로 비킵니다. B도 오른쪽으로 비킵니다. -> 또 마주침.
  • 무한 반복.
• 상태: 프로세스는 계속 상태가 변하고(Running) CPU를 소모하지만, 진전(Progress)이 없습니다.
• 해결: Ethernet의 CSMA/CD처럼 충돌 발생 시 임의의 시간(Random Backoff)만큼 대기했다가 재시도합니다. (둘 다 1초 뒤에 움직이지 말고, 하나는 0.1초, 하나는 0.5초 뒤에).

기아 상태 (Starvation) - "영원한 양보"

• 상황: 우선순위 스케줄링에서, 낮은 우선순위 프로세스(P_low)가 높은 우선순위(P_high)에게 계속 밀려서 CPU를 영원히 못 받는 상황.
• 차이점: 데드락은 "0명"이 진행되는 것이고, 기아 상태는 "누군가는 잘 돌고 있는데 나만 못 도는" 것입니다.
• 해결: 에이징(Aging). 기다린 시간만큼 가산점을 줘서 우선순위를 높여줍니다. (경로우대석 원리).

---

9. 핵심 정리 (Key Takeaways)

1. Q: 교착 상태(Deadlock)란 무엇인가요?
   • A: 둘 이상의 프로세스가 서로 상대방이 가진 자원을 점유한 채로, 상대방의 자원을 요구하며 무한히 기다리는 상태입니다.
2. Q: 데드락 발생 4가지 조건은?
   • A: 상호 배제(Mutual Exclusion), 점유 대기(Hold and Wait), 비선점(No Preemption), 순환 대기(Circular Wait)입니다. 모두 만족해야 발생합니다.
3. Q: 데드락 해결 방법에는 무엇이 있나요?
   • A: 예방(4조건 중 하나 파괴/Resource Ordering), 회피(은행원 알고리즘), 탐지 및 복구(프로세스 강제 종료), 무시(타조 알고리즘)가 있습니다.
4. Q: 은행원 알고리즘의 단점은?
   • A: 프로세스가 사용할 최대 자원량을 미리 알아야 하고, 계산 오버헤드가 커서 실제 OS에는 잘 쓰이지 않습니다.
5. Q: 라이브락(Livelock)과 데드락의 차이는?
   • A: 데드락은 스레드가 멈춰 있는(Blocked) 상태지만, 라이브락은 스레드가 계속 상태를 바꾸며(Running) CPU를 쓰지만 작업 진전이 없는 상태입니다.
6. Q: 식사하는 철학자 문제 해결법은?
   • A: 자원에 순서를 매겨 낮은 번호의 포크부터 집게 함으로써 순환 대기 조건을 깨뜨립니다 (Circular Wait 방지).

---

10. 용어 사전 (Glossary)

1. Deadlock (교착 상태): 두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있어 아무것도 완료되지 못하는 상태.
2. Coffman Conditions: 데드락 발생 필요충분조건 4가지.
3. Mutual Exclusion (상호 배제): 한 번에 하나의 프로세스만 자원을 사용할 수 있는 성질.
4. Hold and Wait (점유 대기): 자원을 가진 상태에서 다른 자원을 기다리는 것.
5. No Preemption (비선점): 자원을 강제로 뺏을 수 없는 성질.
6. Circular Wait (순환 대기): 대기 관계가 원형 고리를 이루는 것.
7. Livelock (라이브락): 프로세스들이 서로 양보하거나 상태를 바꾸느라 바빠서 실제 진전은 없는 상태.
8. Starvation (기아 상태): 특정 프로세스가 자원 할당 우선순위에서 계속 밀려 영원히 대기하는 현상.
9. Banker's Algorithm (은행원 알고리즘): 데드락 회피 알고리즘. 시스템을 Safe/Unsafe 상태로 나누어 관리.
10. Safe State: 데드락을 발생시키지 않고 모든 프로세스에게 자원을 할당할 수 있는 순서가 존재하는 상태.
11. RAG (Resource Allocation Graph): 자원 할당 관계를 나타낸 방향 그래프. 사이클 유무로 데드락 탐지.
12. Aging (에이징): 오랫동안 대기한 프로세스의 우선순위를 점진적으로 높여 기아 상태를 방지하는 기법.
13. Spinlock (스핀락): 락을 얻을 때까지 계속 루프를 돌며 확인하는(Busy Waiting) 락 방식. 잘못 쓰면 라이브락 유발 가능.
14. Resource Ordering: 모든 자원에 순서를 매겨 순환 대기를 원천 차단하는 데드락 예방 기법.
15. Wait-For Graph: DB에서 트랜잭션 간의 대기 관계를 나타낸 그래프. 데드락 탐지에 사용.
16. Ostrich Algorithm: 문제를 해결하는 비용보다 문제 발생 빈도가 낮을 때, 그냥 무시하는 전략.
17. Victim Selection: 데드락 복구 시 어떤 프로세스를 죽이거나 롤백할지 결정하는 기준.
18. Rollback: 트랜잭션을 취소하고 이전 상태로 되돌리는 것.
19. Distributed Deadlock: 여러 노드(서버)에 걸쳐 발생한 데드락. 탐지가 훨씬 어려움.
20. Random Backoff: 충돌이나 라이브락 상황에서 임의의 시간을 기다렸다가 재시도하여 동기화를 깨는 기법.

---

Deadlock: The Infinite Waiting Game (Definitive Guide)

1. Prologue: The Intersection Nightmare

Imagine a chaotic 4-way intersection.

• Car South waits for Car North.
• Car North waits for Car East...
• Car East waits for Car West...

No one can move. No one can reverse. This is Deadlock. In the computer world, processes (or threads) freeze waiting for resources (memory, files, DB locks) held by each other. It is the ultimate concurrency bug because it stops the system entirely, unlike race conditions which just corrupt data.

---

2. History & Background

• 1965: Edsger W. Dijkstra introduced the "Dining Philosophers Problem," highlighting the challenges of concurrency control.
• 1971: Edward Coffman formalized the 4 Coffman Conditions, proving the necessary conditions for a deadlock. This became strict gospel in OS theory.
• 1980s: With the rise of distributed systems, research shifted to Distributed Deadlock Detection (e.g., Chandy-Misra-Haas algorithm), as single-node detection wasn't enough.

---

3. The 4 Necessary Conditions (Coffman Conditions)

Coffman proved that Deadlock only happens if ALL 4 conditions are met simultaneously. Break one, and you prevent deadlock. This is the basis of all Deadlock Prevention strategies.

1) Mutual Exclusion

• "Mine alone."
• Resources cannot be shared. (e.g., Only one thread can write to a specific memory address or print at a time).
• Prevention: Use lock-free data structures (CAS) or make resources shareable (Read-Only).

2) Hold and Wait

• "I'll keep my fork while asking for yours."
• A process holding at least one resource is waiting to acquire additional resources held by other processes.
• Prevention: Require processes to request ALL resources at the very beginning (atomic allocation).

3) No Preemption

• "No stealing allowed."
• Resources cannot be forcibly removed from a process. They must be released voluntarily.
• Prevention: Allow OS to forcibly revoke resources (Context Switch).

4) Circular Wait

• "The Cycle of Doom."
• A set of processes {P0, P1, ..., Pn} exists such that P0 waits for P1, P1 waits for P2... and Pn waits for P0.
• Prevention: Resource Ordering (See Dining Philosophers).

---

4. The Dining Philosophers Problem

5 Philosophers, 5 Forks (between them). You need 2 forks (Left & Right) to eat.

The Problem (Deadlock Scenario)

1. Everyone picks up the Left Fork at the exact same time.
2. Everyone tries to pick up the Right Fork, but it's gone (held by the neighbor).
3. Everyone waits forever holding one fork. -> Deadlock & Starvation.

The Solution: Resource Hierarchy (Prevention)

The most practical solution is Resource Ordering.

• Rule: "Always pick up forks in numerical order (Low -> High)."
• Scenario:
  • Philosophers 1-4 pick up Fork i (Lower) then Fork i+1 (Higher).
  • Philosopher 5 (sitting between Fork 5 and Fork 1) wants Fork 1 (Lower) and Fork 5 (Higher).
  • He tries to pick up Fork 1 first, but Philosopher 1 has it. So he waits without holding anything.
  • This leaves Fork 5 available for Philosopher 4 to finish eating.
  • The cycle is broken!

---

5. Prevention, Avoidance, and Detection (Strategies)

1) Prevention

Invalidate one of the 4 Coffman conditions.

• Deny Mutual Exclusion: Make everything shareable (Hard).
• Deny Hold and Wait: Request all resources at start (Inefficient).
• Deny No Preemption: Allow stealing (Complex, data corruption risk).
• Deny Circular Wait: Resource Ordering (Best practical approach).

2) Avoidance (Banker's Algorithm)

The OS acts like a strict Banker.

• Before granting a resource, it simulates: "If I give this to you, is there still a sequence where everyone can finish?"
• If yes -> Safe State (Grant).
• If no -> Unsafe State (Deny/Wait).
• Cons: Requires knowing max resource needs in advance; too slow for modern OS.

3) Detection & Recovery

Let deadlock happen, find it, and kill it.

• Detection: Build a Resource Allocation Graph (or Wait-For Graph in databases) and check for cycles.
• Recovery:
  • Kill Process: Terminate the cycle-causing process.
  • Rollback: Revert specific transactions.

Ostrich Algorithm: The dominant strategy in Windows/Linux/Unix. "Pretend it doesn't exist." Deadlocks are rare enough that rebooting is cheaper than running expensive detection algorithms 24/7.

---

6. Real World: Database Deadlocks

99% of deadlocks developers face are in the Database layer.

Scenario

Two transactions updating the same rows in different orders.

• Tx A: Locks Row 1 (User). Wants Row 2 (Order).
• Tx B: Locks Row 2 (Order). Wants Row 1 (User).
• Result: Deadlock.

Solution

1. Consistent Ordering: Always lock Row 1 then Row 2 in code.
2. Retry Logic: Catch the Deadlock found exception and retry the transaction.
3. Low Timeout: Set innodb_lock_wait_timeout to fail fast.

---

7. Deadlock's Cousins

Livelock: "The Hallway Dance"

• Scenario: Two people trying to pass. A moves left, B moves left. A moves right, B moves right.
• State: Processes are Running (consuming CPU) but making zero progress. State changes constantly but loops.
• Fix: Random Backoff (Wait random time before retrying). Ethernet uses Exponential Backoff to solve this.

Starvation: "The Poor Process"

• Scenario: A low-priority process never gets the CPU because high-priority processes keep arriving.
• Difference: Deadlock stops everyone in the cycle. Starvation stops only the low-pri process.
• Fix: Aging (Increase priority the longer it waits). Linux's CFS scheduler uses complex logic to ensure fairness.

---

8. Distributed Deadlock (Advanced)

In distributed systems, Deadlock is harder to detect.

• Centralized Approach: One node collects all lock info (Single point of failure).
• Chandy-Misra-Haas Algorithm: A probe-based algorithm. If a process P is waiting for Q, it sends a probe. The probe travels along the dependency edges. If the probe returns to P, a cycle exists.