교착 상태 (Deadlock)

---

1. 개요

교착 상태(Deadlock) 는
여러 프로세스가 서로가 가진 자원을 기다리며 무한히 대기하는 상태를 말함
즉, 서로가 서로를 기다리느라 아무도 앞으로 진행하지 못하는 상황

---

2. 교착 상태의 예시

예시 상황

프로세스	현재 보유 자원	요청 중 자원
P1	프린터	스캐너
P2	스캐너	프린터

→ P1은 스캐너가 필요하고,
→ P2는 프린터가 필요하지만,
서로가 자원을 내놓지 않아 무한 대기 상태 발생.

---

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

교착 상태는 아래 4가지 조건이 모두 만족될 때만 발생
하나라도 깨뜨리면 교착 상태를 예방할 수 있음.

조건	설명	예시
상호 배제 (Mutual Exclusion)	자원을 한 번에 하나의 프로세스만 사용 가능	프린터 1대만 사용 가능
점유와 대기 (Hold and Wait)	자원을 보유한 채 다른 자원을 기다림	프린터를 잡고 스캐너 대기
비선점 (No Preemption)	이미 할당된 자원을 강제로 뺏을 수 없음	사용 중인 자원을 OS가 회수 불가
순환 대기 (Circular Wait)	프로세스 간 자원 대기 관계가 원형으로 연결	P1 → P2 → P3 → P1 형태

교착 상태 발생 조건 4가지 암기법:
상·점·비·순 (상호배제 / 점유대기 / 비선점 / 순환대기)

---

4. 교착 상태 해결 방법

운영체제는 교착 상태를 예방(Prevention), 회피(Avoidance), 탐지(Detection), 복구(Recovery) 네 가지 방법으로 처리

구분	방법	설명
예방 (Prevention)	발생 조건 4개 중 하나 이상을 미리 차단	상·점·비·순 조건 중 최소 하나 제거
회피 (Avoidance)	교착 상태가 발생하지 않도록 자원 할당을 조절	대표적으로 은행원 알고리즘 (Banker’s Algorithm) 사용
탐지 (Detection)	교착 상태 발생 후 탐지 알고리즘으로 확인	자원 할당 그래프(Resource Allocation Graph) 활용
복구 (Recovery)	교착 상태 프로세스를 종료하거나 자원을 회수	프로세스 강제 종료 또는 자원 선점

---

5. 교착 상태 예방 (Prevention)

교착 상태 발생 조건을 애초에 성립하지 않게 만드는 방법

조건	예방 방법	예시
상호 배제 제거	공유 가능한 자원으로 설계	프린터 대신 네트워크 프린터 공유
점유와 대기 제거	모든 자원을 한 번에 요청	프로세스 시작 시 모든 자원 미리 확보
비선점 제거	자원 선점 가능하도록 설계	자원을 뺏고 나중에 재시도
순환 대기 제거	자원 번호를 부여해 순서대로 요청	자원 우선순위 규칙 적용

단점: 시스템 자원 낭비나 대기 시간 증가 가능

---

6. 교착 상태 회피 (Avoidance)

교착 상태가 발생할 가능성이 있는 상태를 미리 피하는 방식

가장 대표적인 알고리즘은 은행원 알고리즘(Banker's Algorithm)

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

• 자원 할당 전, 시스템이 안전 상태(Safe State) 인지 검사
• 만약 안전 상태를 벗어날 가능성이 있으면 자원 할당을 보류
• “모든 프로세스가 결국 자원을 얻어 종료될 수 있다면 안전한 상태”

용어	설명
안전 상태 (Safe State)	모든 프로세스가 순차적으로 실행될 수 있는 상태
불안전 상태 (Unsafe State)	교착 상태로 발전할 수 있는 상태

---

7. 교착 상태 탐지 (Detection)

교착 상태를 허용한 뒤, 주기적으로 검사하여 탐지하는 방식

• OS가 자원 할당 그래프(Resource Allocation Graph, RAG)를 유지하며 상태를 확인
• 그래프에서 사이클(Cycle) 이 존재하면 교착 상태 발생

자원 할당 그래프 예시

P1 → R1
P2 → R2
R1 → P2
R2 → P1

→ 순환(Cycle)이 존재하므로 교착 상태 발생

---

8. 교착 상태 복구 (Recovery)

교착 상태 탐지 후, 시스템을 정상 상태로 되돌리는 단계

방법	설명	단점
프로세스 종료	교착된 프로세스 일부 또는 전부 강제 종료	작업 손실 발생
자원 선점	일부 자원을 회수하여 다른 프로세스에 재할당	상태 복원 어려움
프로세스 롤백(Rollback)	체크포인트 이전으로 되돌리기	오버헤드 큼

---

9. 교착 상태 처리 방법 요약

단계	방식	키워드	대표 알고리즘
예방	발생 조건 제거	상·점·비·순 중 하나 차단	-
회피	안전 상태 유지	자원 할당 제어	Banker’s Algorithm
탐지	발생 허용 후 감시	사이클 탐색	자원 할당 그래프
복구	탐지 후 처리	종료·선점·롤백	-