[혼공컴운] 13. 교착 상태 (Deadlock) 정리

1. 교착 상태란?

교착 상태(Deadlock) : 일어나지 않을 사건을 기다리며 프로세스들의 진행이 영원히 멈춰버리는 현상입니다.

🍴 식사하는 철학자 문제

1. 모든 철학자가 동시에 왼쪽 포크를 집어듭니다.
2. 모든 철학자가 오른쪽 포크를 집으려 하지만, 옆 사람에 의해 이미 점유된 상태입니다.
3. 아무도 포크를 내려놓지 않고 무한히 대기합니다. → 교착 상태 발생

---

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

교착 상태를 시각적으로 파악하기 위해 프로세스와 자원의 관계를 나타낸 그래프입니다.

• 원: 프로세스
• 사각형: 자원 (사각형 안의 점은 사용 가능한 자원 수)
• 검정 화살표 (자원 → 프로세스): 현재 할당되어 사용 중인 자원
• 빨강 화살표 (프로세스 → 자원): 할당을 기다리는 중인 자원
• 💡 핵심: 그래프가 사이클(Cycle, 원 형태)을 이루고 있다면 교착 상태가 발생했거나 발생할 가능성이 큽니다.

---

3. 교착 상태 발생 조건 (4가지 필수 조건)

다음 네 가지 조건이 동시에 모두 만족될 때 교착 상태가 발생합니다.

1. 상호 배제(Mutual Exclusion): 한 번에 한 프로세스만 자원을 사용할 수 있음.
2. 점유와 대기(Hold and Wait): 자원을 할당받은 상태에서 다른 자원을 기다림.
3. 비선점(No Preemption): 다른 프로세스의 자원을 강제로 뺏을 수 없음.
4. 원형 대기(Circular Wait): 자원 할당 그래프가 원의 형태를 띰.

---

4. 교착 상태 해결 방법

🛡️ 1) 예방 (Prevention)

발생 조건 중 하나를 사전에 차단하는 방식입니다.

• 상호 배제 부정: 모든 자원을 공유 (비현실적).
• 점유와 대기 부정: 한꺼번에 다 주거나 아예 안 줌 (기아 현상 우려).
• 비선점 부정: 자원을 뺏을 수 있게 함 (CPU 등 특정 자원에만 유용).
• 원형 대기 부정: 자원에 번호를 매겨 오름차순으로만 요청 (가장 실용적).

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

자원을 무분별하게 주지 않고, 안전 상태를 유지할 때만 할당합니다.

• 안전 상태: 모든 프로세스가 종료될 수 있는 '안전 순서열'이 존재함.
• 불안전 상태: 교착 상태가 발생할 가능성이 있는 위험한 상태.

📊 은행원 알고리즘 예시 (가용 자원: 3, 3, 2 기준)

프로세스	최대 요구량	현재 할당량	필요량	할당 가능 여부
P1	7 5 3	0 1 0	7 4 3	X
P2	3 2 2	2 0 0	1 2 2	O (1순위)
P3	9 0 2	3 0 2	6 0 0	X
P4	2 2 2	2 1 1	0 1 1	O (2순위)
P5	4 3 3	0 0 2	4 3 1	O (3순위)

• 안전 순서열: P2 → P4 → P5 → P1 → P3 순으로 실행하면 교착 상태 없이 모두 완료 가능합니다.

🔍 3) 검출 후 회복 (Detection & Recovery)

교착 상태 발생을 허용하되, 발견 시 사후 조치합니다.

• 선점 회복: 해결될 때까지 다른 프로세스의 자원을 뺏음.
• 종료 회복: 프로세스를 모두 강제 종료하거나 하나씩 종료(오버헤드 발생).

🏖️ 4) 타조 알고리즘 (Ostrich Algorithm)

발생 확률이 매우 낮을 때 그냥 무시하는 방법입니다. 비용 대비 효율을 고려할 때 윈도우나 리눅스 등 범용 OS에서 간혹 사용됩니다.

---