1. Deadlock 문제
Deadlock: Block된 프로세스들의 집합에서, 각 프로세스가 자원을 보유한 채 다른 프로세스가 보유한 자원을 기다리는 상태
예시:
- 시스템에 Tape drive 2개 - P1과 P2가 각각 하나씩 보유, 나머지 하나를 요청
- Semaphore A=1, B=1 일 때: P0이 P(A)→P(B) 순서, P1이 P(B)→P(A) 순서로 요청
2. Deadlock 발생의 4가지 필요 조건
4가지가 동시에 성립해야 Deadlock이 발생할 수 있다 (Necessary conditions):
| 조건 | 설명 |
|---|---|
| Mutual Exclusion | 한 번에 하나의 프로세스만 자원을 사용 가능 |
| Hold and Wait | 자원을 보유한 프로세스가 추가 자원을 요청하며 대기 |
| No Preemption | 자원은 보유 프로세스가 자발적으로만 해제 가능. 강제 회수 불가 |
| Circular Wait | P0→P1→P2→…→Pn→P0 형태의 순환 대기 존재 |
3. Resource-Allocation Graph (RAG)
정점(V)과 간선(E)으로 구성된 그래프:
- P = {P1, P2, …, Pn}: 프로세스 집합
- R = {R1, R2, …, Rm}: 자원 유형 집합 (각 자원 유형은 여러 Instance를 가질 수 있음)
- Request edge: Pi → Rj (Pi가 Rj의 Instance를 요청)
- Assignment edge: Rj → Pi (Rj의 Instance가 Pi에 할당됨)
RAG와 Deadlock 판별
- Graph에 Cycle이 없으면 - Deadlock 없음 (확정)
- Graph에 Cycle이 있으면:
- 자원 유형당 Instance가 하나뿐이면 - Deadlock (확정)
- 자원 유형당 Instance가 여러 개이면 - Deadlock 가능성만 있음
Cycle 있고 Deadlock인 경우:
Cycle 있지만 Deadlock이 아닌 경우:
4. Deadlock 처리 방법
| 방법 | 설명 |
|---|---|
| Prevention | 4가지 필요 조건 중 하나가 성립하지 않도록 사전에 제약 |
| Avoidance | 자원 할당 시 시스템이 Safe state에 머물도록 동적으로 판단 |
| Detection & Recovery | Deadlock을 허용하되, 탐지 후 복구 |
| Ignore | Deadlock을 무시. UNIX를 포함한 대부분의 OS가 사용 |
5. Deadlock Prevention
4가지 필요 조건 중 하나라도 성립 불가능하게 만든다:
| 조건 | Prevention 전략 | 단점 |
|---|---|---|
| Mutual Exclusion | 공유 가능한 자원에는 적용 불가. 본질적으로 비공유인 자원에는 강제 불가 | 적용 범위 제한 |
| Hold and Wait | 프로세스가 자원을 요청할 때 다른 자원을 보유하지 않도록 보장 (All-or-nothing) | 낮은 자원 활용률, Starvation 가능 |
| No Preemption | 추가 자원을 즉시 할당받지 못하면 보유 자원을 모두 해제 | 이전 작업 상태 손실 |
| Circular Wait | 모든 자원 유형에 전체 순서를 부여하고, 증가 순서로만 요청하도록 강제 | 프로그래밍 제약 |
전반적 단점: 낮은 자원 활용률과 감소된 시스템 Throughput
6. Deadlock Avoidance
6.1 개념
각 프로세스가 필요한 최대 자원 수를 사전에 선언하고, 자원 할당 시 Safe state를 유지하는지 확인한다.
6.2 Safe State
- Safe state: 모든 프로세스에 대해 Safe sequence <P1, P2, …, Pn>이 존재
- 각 Pi가 필요한 자원을 현재 Available + 앞선 Pj들의 반환 자원으로 충족 가능
- Safe state → Deadlock 없음 (확정)
- Unsafe state → Deadlock 가능성 (모든 프로세스가 최대 자원을 동시에 요청하면)
- Avoidance 전략: “요청을 허가했을 때 Safe state가 유지되면 허가, 아니면 거절”
6.3 Case A: 자원 유형당 Single Instance - RAG 알고리즘
- Claim edge (점선): Pi → Rj - Pi가 Rj를 요청할 수도 있음
- 요청 시: Claim edge → Request edge → Assignment edge로 변환
- 요청을 허가했을 때 Cycle이 형성되면 → Unsafe → 거절
6.4 Case B: 자원 유형당 Multiple Instances - Banker’s Algorithm
각 프로세스가 각 자원 유형의 최대 사용량을 사전 선언해야 한다.
데이터 구조 (n = 프로세스 수, m = 자원 유형 수):
| 변수 | 크기 | 설명 |
|---|---|---|
| Available | Vector [m] | 각 자원 유형의 사용 가능한 Instance 수 |
| Max | Matrix [n x m] | 각 프로세스가 요청할 수 있는 최대 Instance 수 |
| Allocation | Matrix [n x m] | 현재 각 프로세스에 할당된 Instance 수 |
| Need | Matrix [n x m] | 각 프로세스가 추가로 필요한 Instance 수 = Max - Allocation |
Safety Algorithm:
1. Work := Available, Finish[i] := false (모든 i)
2. Finish[i]=false이고 Need_i <= Work인 i를 찾는다
(없으면 Step 4로)
3. Work := Work + Allocation_i, Finish[i] := true -> Step 2로
4. 모든 Finish[i]=true이면 -> Safe state
Resource-Request Algorithm:
1. Request_i > Need_i 이면 -> 오류 (최대 선언 초과)
2. Request_i > Available 이면 -> 대기
3. 가할당(Pretend):
Available -= Request_i
Allocation_i += Request_i
Need_i -= Request_i
-> Safety Algorithm 실행
-> Safe이면 할당 확정, Unsafe이면 원상 복구 & 대기
6.5 Banker’s Algorithm 예제
5개 프로세스 (P0~P4), 3가지 자원 (A:10, B:5, C:7):
Allocation Max Available Need
A B C A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2 7 4 3
P1 2 0 0 3 2 2 1 2 2
P2 3 0 2 9 0 2 6 0 0
P3 2 1 1 2 2 2 0 1 1
P4 0 0 2 4 3 3 4 3 1
Safe sequence: <P1, P3, P4, P2, P0> - Safe state
7. Deadlock Detection
Deadlock을 허용하되, 탐지 후 복구하는 방식.
7.1 Single Instance - Wait-for Graph
- RAG에서 자원 노드를 제거하고 프로세스 간 대기 관계만 표현
- Pk → Pj: Pk가 Pj를 기다리고 있음
- Cycle 탐지 = Deadlock 탐지
- Cycle 탐지 알고리즘: O(n^2) (n = 정점 수)
7.2 Multiple Instances - Detection Algorithm
Banker’s Algorithm과 유사하지만 Max 대신 Request(현재 요청)를 사용:
1. Work := Available
Finish[i] := false (Allocation_i != 0인 경우)
Finish[i] := true (Allocation_i = 0인 경우)
2. Finish[i]=false이고 Request_i <= Work인 i를 찾는다
3. Work := Work + Allocation_i, Finish[i] := true -> Step 2로
4. Finish[i]=false인 i가 있으면 -> 해당 Pi는 Deadlocked
- 시간 복잡도: O(m x n^2)
7.3 Detection 빈도
- 모든 요청마다? - 오버헤드 큼
- 즉시 할당 못한 요청마다? - 합리적
- 주기적으로? - Deadlock 확률이 낮으면 적합
8. Deadlock Recovery
8.1 Process Termination
- 모든 Deadlocked 프로세스를 중단
- 하나씩 중단하며 Deadlock cycle이 해소될 때까지 반복
- 중단 순서 결정 기준: Priority, 실행 시간, 사용/필요 자원, 종료까지 남은 시간, 대화형/배치 여부
8.2 Resource Preemption
- Victim 선택: 비용을 최소화하는 프로세스 선택
- Rollback: 안전한 이전 상태로 되돌린 후 재시작
- Starvation 방지: 같은 프로세스가 반복적으로 Victim이 되지 않도록 Rollback 횟수를 비용 산정에 포함
9. Avoidance vs Detection 비교
| Avoidance | Detection | |
|---|---|---|
| 가정 | 최악의 경우(Worst case) - 모든 프로세스가 최대 자원을 동시 요청 | 최선의 경우(Best case) - 어떤 프로세스도 추가 자원 요청 안 함 |
| 판단 시점 | 자원 할당 전 | 현재 상태 기준 (사후 탐지) |
| 자원 효율 | 보수적 - 자원 낭비 가능 | 낙관적 - 자원 활용 극대화 |
| 위험 | Deadlock 원천 방지 | Deadlock 발생 후 복구 비용 |