요약
Deadlock: 프로세스들이 서로가 가진 자원을 기다리며 무한 대기에 빠지는 상황
발생 조건은 4가지(Mutual Exclusion / Hold & Wait / No Preemption / Circular Wait) 가 있으며 4조건을 모두 만족해야 발생함
해결 전략은 Prevention / Avoidance / Detection & Recovery 세 가지이며, 실무 OS는 대부분 Detection 기반으로 동작한다.
Avoidance의 대표 알고리즘은 Banker’s Algorithm이며, Safe/Unsafe state 개념이 핵심
개념 등장 배경
운영체제는 CPU 시간, 메모리, I/O 장치 같은 자원을 여러 프로세스에 동시에 제공해야 한다.
하지만 프로세스들이 서로의 자원을 기다리며 영원히 멈추는 순간, 시스템 전체가 더 이상 진행되지 않는다.
이 정지 상태가 바로 Deadlock 이며 OS는 이를 다루기 위해 자원 할당 정책을 철저히 설계해야 한다.
주요 개념 설명
1) Deadlock 정의
둘 이상의 프로세스가 서로가 보유한 자원을 기다리며 종료되지 않는 상태.
P1: R1 필요 → R2 대기
P2: R2 필요 → R1 대기
→ 서로 기다림 → 교착상태Deadlock이 발생하면 시스템 일부가 아니라 전체 실행 흐름이 정지한다.
2) Deadlock 발생의 4가지 필요조건
Deadlock은 아래 네 조건이 모두 동시에 만족할 때만 발생한다.
-
Mutual Exclusion (상호 배제)
- 자원을 동시에 여러 프로세스가 사용할 수 없음.
-
Hold & Wait (보유한 채 대기)
- 이미 자원을 가진 프로세스가 새로운 자원을 기다리는 상태.
-
No Preemption (비선점)
- OS가 자원을 강제로 빼앗을 수 없음.
-
Circular Wait (순환 대기)
- 자원 요청이 원형 고리 형태로 얽혀 있음.
P1 → P2 → P3 → … → P1하나라도 깨면 Deadlock은 절대 발생하지 않는다. (Prevention 핵심 논리)
3) 그래프로 표현하기 — Resource Allocation Graph (RAG)
[Process] → (request) → [Resource]
[Resource] → (assignment) → [Process]RAG에서 cycle이 발견되면 Deadlock 가능성이 존재한다.
특히 자원 인스턴스가 1개인 경우 → Cycle = Deadlock 확정.
4) Deadlock Handling 전략 3가지
1) Prevention
4조건 중 하나를 시스템 정책으로 제거.
가장 단순하지만 비효율 극심.
| 제거하는 조건 | 방법 | 문제점 |
|---|---|---|
| Mutual Exclusion | 자원 공유 | 현실적으로 불가능 |
| Hold & Wait | 필요한 자원을 한 번에 전부 요구 | 자원 낭비, starvation 가능 |
| No Preemption | 자원 강제 회수 | 구현 어려움 |
| Circular Wait | 자원에 순서를 강제 | 실제 시스템에서 가장 현실적인 Prevention |
2) Avoidance (회피)
Deadlock에 빠질 위험이 있는 Unsafe state로 들어가지 않도록 사전에 차단.
핵심 개념:
-
Safe State
모든 프로세스가 어떤 순서로든 정상 종료 가능한 상태. -
Unsafe State
Deadlock은 아니지만 Deadlock이 발생할 수 있는 위험 상태.
Avoidance는 항상 시스템을 Safe 상태에 유지하는 것이 목표.
→ 대표 알고리즘: Banker’s Algorithm
3) Detection & Recovery (검출 + 복구)
Deadlock을 허용한 뒤,
주기적으로 검사해 Deadlock이 생기면 해결.
방법:
-
Deadlocked 프로세스 중 일부 종료
-
자원을 강제로 회수(Preemption)
-
체크포인트 후 Rollback
→ 실제 OS(Linux/Windows)는 이 방식을 사용.
5) Deadlock Avoidance — 핵심 알고리즘 2가지
(1) Resource Allocation Graph + Claim Edge
Request를 허용했을 때 Cycle이 생기면 거부.
(2) Banker’s Algorithm
multiple instance 자원에 대한 Deadlock Avoidance 알고리즘.
프로세스의 Max를 알고 있는 상황에서 각 요청이 들어올때 요청을 허용한다고 가정한 뒤 시스템이 안전 상태인지 확인해 자원 요청을 승인/거부한다.
필요한 표 구성 요소 4가지
- Available : 현재 남은 자원 수
- Max : 프로세스가 필요로 하는 최대치
- Allocation : 현재 할당된 자원
- Need = Max - Allocation : 앞으로 더 필요한 자원
Safe State 검사
- 남아있는 자원 available로 실행할 수 있는 프로세스를 하나 찾는다. (need <= available)
- 그 프로레스를 완료했다고 가정, allocation을 available에 다시 반환
- 다시 다른 프로세스를 실행할 수 있는지 반복함
모든 프로세스를 완료할 수 있다면 상태는 safe
동작 원리 다이어그램
[Request 발생]
│
▼
[Need ≤ Request ?] → 아니면 즉시 거부
│
[Request ≤ Available ?] → 아니면 대기
│
▼
[임시로 자원 할당 후 Safe State 검사]
│
┌────┴─────┐
│ │
Safe Unsafe
│ │
Grant Deny핵심 개념 요약
- Deadlock의 4조건은 동시에 성립해야만 Deadlock이 발생한다.
- Avoidance의 핵심은 Safe State 유지 여부.
- Banker’s Algorithm의 4개 구성 요소 available, max, allocation, need
- Detection은 사이클 또는 완료 가능한 프로세스가 없는 것으로 판단.
- 복구 시 전체 프로세스를 죽일 필요 없이 사이클을 만드는 프로세스만 중단하면 된다.
cf.
| 개념 | 설명 |
|---|---|
| Deadlock vs Starvation | Deadlock은 상호 기다림, Starvation은 계속 우선순위에서 밀림 |
| Unsafe != Deadlock | Unsafe는 Deadlock 가능성만 있음 |
| Cycle != Deadlock | 자원 인스턴스가 1개일 때만 확정 |
| Prevention vs Avoidance | Prevention = 조건 제거 / Avoidance = Safe 유지 |
