2024. 1. 31. 12:16ㆍ프로그래밍 공부/OS
교착상태
Deadlock Resolution
Deadlock
길거리에서 교통체증이 심해 차들이 꼬인 상태
Deadlock의 개념
Processor
Running
↘ event
ready blocked 자원
Blocked/Asleep state
- 프로세스가 특정 이벤트를 기다리는 상태
- 프로세스가 필요한 자원을 기다리는 상태
Deadlock state
- 프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우
* 프로세스가 deadlock 상태에 있음
- 시스템 내에서 deadlock에 빠진 프로세스가 있는 경우
* 시스템이 deadlock 상태에 있음
Deadlock vs Starvation 기아상태
Deadlock의 개념
running → terminated
dispatch ↗ sleep
(schedule) ↙ timerunnout (block)↘
(preemption)
ready ↔ asleep
↗ wakeup
created
running → terminated
dispatch sleep ↘
(schedule) ↗ ↙ timerunnout (block)
(preemption)
ready ↔ asleep
starvation ↖ wakeup deadlocked 자원 Event
↗ ↘ CPU 새치기 X ↙
created transition
impossible 가능성 zero
자원의 분류 Deadlock
일반적인 분류
- Hardeware resources vs Software resources
다른 분류법
- 선점 가능 여부에 따른 분류
- 할당 단위에 따른 분류
- 동시 사용 가능에 따른 분류
- 재사용 가능 여부에 따른 분류
① 선점 가능 여부에 따른 분류
Preemptible resources
- 선점 당한 후, 돌아와도 문제가 발생하지 않는 자원
- Processor, memory 등
CPU → Swap-device
→ context switch
→ saving
restoring
Non-preemptible resources
- 선점 당하면, 이후 진행에 문제가 발생하는 자원
* Rollback, restart등 특별한 동작이 필요
- E.g., disk drive 등
disk 뽑아버리기
usb 뽑아버리기
여권 → 아들
선점
write
② 할당 단위에 따른 분류
Total allocation resources 전체를 O
- 자원 전체를 프로세스에게 할당
- E.g., Processor, disk drive 등
CPU
core
R
Partitioned allocation resources P1 P2 P3 P4
- 하나의 자원을 여로 조작으로 나누어, 여러 프로세스들에게 할당
- E.g., Memory 등
③ 동시 사용 가능 여부에 따른 분류
Exclusive allocation resources
- 한 순간에 한 프로세스만 사용 가능한 자원
- E.g., Processor, memory, disk drive 등
→ P1 P2
↑P2
Shared allocation resource
- 여러 프로세스가 동시에 사용 가능한 자원
- E.g., Program(sw), shared data 등
Source code exe
WP
?
Pi ← R → Pj
④ 재사용 가능 여부에 따른 분류
SR (Serially-reusable Resources)
- 시스템 내에 항상 존재하는 자원
- 사용이 끝나면, 다른 프로세스가 사용 가능
- E.g., Processor, memory, disk drive, program 등
CR (Consumable Resources)
- 한 프로세스가 사용한 후에 사라지는 자원
- E.g., signal, message 등
S ↙
P1 -M→ P2
Deadlock과 자원의 종류
Deadlock을 발생시킬 수 있는 자원의 형태
- Non-preemptible resources
- Exclusive allocation resources P1 → shared ← P2
- Serially reusable resources
* 할당 단위는 영향을 미치지 않음
CR을 대상으로 하는 Deadlock model
- 너무 복잡!
O(2^n)
Deadlock 발생의 예
2개의 프로세스 (P1, P2)
2개의 자원 (R1, R2) 발생 X
| 프로세스 P1 | 시간 | 프로세스 P2 |
| ... request R2 ← ① ... request R1 ← ③ ... ... release R1 ← ... release R2 ← ... ... |
t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 |
... ... request R1 ← ② ... request R2 ← ④ ... ... release R1 ← ... release R2 ← ... |
Deadlock Model (표현법)
Graph Model
State Transition Model
Graph Model
Node
- 프로세스 노드(P1, P2), 자원 노드(R1, R2)
☆Edge
- Rj → Pi : 자원 Rj이 프로세스 Pi에 할당 됨
- Pi → Rj : 프로세스 Pi가 자원 Rj을 요청 (대기 중)
③요청 ①할당
-- P1 ←
↓ |
R1 R2
| ↑
→ P2--
② ④
State Transition Model
예제 RA 2개
- 2개의 프로세스와 A type의 자원 2개(unit) 존재
- 프로세스는 한번에 자원 하나만 요청/반납 가능
State
| P1 state |
현재 자원 수 # of R units allocated |
요청 Request |
| 0 | 0 | x |
| 1 | 0 | o |
| 2 | 1 | x |
| 3 | 1 | o |
| 4 | 2 | x |
5 x 5개 가능
State Transition Model
P2
S 0 1 →
↗ ↖ P2 P2 P2 P2 P2
P1 P2 hold 0, hold 0, hold 1, hold 1, hold 2,
need 0 need 1 need 0 need 1 need 0
P1 holds 0, S00 ---P2--→S01----2--→S02----2--→S03----2--→S04
P1↓ needs 0 | ↑←----------|↑-------2-- |↑←--------|↑--------2- |
P1↓ | 1↓| 1↓ | 1↓ | 1↓
P1 holds 0, S10 |---2--→ S11 |----2--→S12 |---2--→S13|---2--→S14
needs 1 | |←----------| |-------2-- | |←--------| |-------2--
1↓ |1 1↓|1 1↓ |1 1↓|1
P1 holds 1, S20 ----2--→S21----2--→S22----2--→S23
needs 0 | ↑←----------|↑-------2-- | |
1↓ | 1↓ | 1↓ 1↓
P1 holds 1, S30 |---2--→ S31 |----2--→S32----2--→S33 deadlock
needs 1 | |←----------| |-------2--
1↓ |1 1↓|1
P1 holds 2, S40 |---2--→ S41
needs 0
Deadlock 발생 필요 조건
아래 4가지 모두 성립해야 한다
자원의 특성
Exclusive use of resources 혼자
Non-premptible resources 선점 X
프로세스의 특성
Hold and wait (Partial allocation)
- 자원을 하나 hold하고 다른 자원 요청
Circular wait ○
Deadlock 해결 방법
Deadlock prevention methods
-☆ 교착상태 예방
Deadlock avoidance method
- 교착상태 회피
Deadlock detection and deadlock recovery methods
- 교착상태 탐지 및 복구
Deadlock Prevention 예방
4개의 deadlock 발생 조건 중 하나를 제거
- Exclusive use of resources
- Non-premptible resources
- Hold and wait (Partial allocation)
- Circular wait
Deadlock이 절대 발생하지 않음
Deadlock Prevention
↗ 1
예방 → 2
↘ 3
↘ 4
shared
1. 모든 자원을 공유 허용
- Exclusive use of resources 조건 제거
- 현실적으로 불가능
2. 모든 자원에 대해 선점 허용
- Non-premptible resources 조건 제거
- 현실적으로 불가능
- 유사한 방법
* 프로세스가 할당 받을 수 없는 자원을 요청한 경우,
기존에 가지고 있던 자원을 모두 반납하고 작업 취소
이후 처음 (또는 check-point)부터 다시 시작
* 심각한 자원 낭비 발생 → 비현실적
P2
↗
Rj
↑(X) ↗ 무용지물
P1. |------→| |
(X) ↙ ↘(X)→ X
R1 R2←-----
3. 필요 자원 한번에 모두 할당 (Total allocation)
- Hold and wait 조건 제거 반납x
- 자원 낭비 발생 P1→R1....n 1초 독점
* 필요하지 않은 순간에도 가지고 있음 ↑ ↗
- 무한 대기 현상 발새 가능 P2
P3↗ 엄청 wait
4. Circular wait 조건 제거 ○
- Totally allocation을 일반화 한 방법. P1
- 자원들에게 순서를 부여
- ☆프로세스는 순서의 증거 방향으로만 자원 요청 가능
- 자원 낭비 발생
__ →
|X ↓ R1 R2 R3 R4
P1 → O → O → O → O
(1,2,3,4) ↗ ----→ O O
P2 / ----/ O
(1,3)
Deadlock Prevention
☆4개의 deadlock 발생 조건 중 하나를 제거
Deadlock이 절대 발생하지 않음
심각한 자원 낭비 발생
- Low device utilization
- Reduced system throughput
☆비현실적
회피
detection recover
Deadlock 해결 방법
Deadlock prevention methods
- 교착상태 예방
Deadlock avoidance method
- 교착상태 회피
Deadlock detection and deadlock recovery methods
- 교착상태 탐지 및 복구
Deadlock Avoidance
시스템의 상태를 계속 감시
시스템이 deadlock 상태가 될 "가능성"이 있는 자원 할당 요청 보류
☆시스템을 항상 safe state로 유지
안전한 상태
Deadlock Avoidance
Safe state
-☆ 모든 프로세스가 정상적으로 종료 가능한 상태
- safe sequence가 존재
* Deadlock 상태가 되지 않을 수 있음을 보장
Unsafe state
- Deadlock 상태가 될 가능성이 있음
- 반드시 발생한다는 의미는 아님
☆가정
- 프로세스의 수가 고정됨
- 자원의 종류와 수가 고정됨
- 프로세스가 요구하는 자원 및 최대 수량을 알고 있음
- 프로세스는 자원을 사용 후 반드시 반납한다
↓
Not practical
Deadlock Avoidance
1. Dijkstra's algorithm
- Banker's algorithm
2. Habermann's algorithm
Edsger Wybe Dijkstra
Deadlock Avoidance
영감
Dijkstra's banker's algorithm
- Deadlock avoidance를 위한 간단한 이론적 기법
- 가정
* ☆ 한 종류(resource type)의 자원이 여러 개(unit)
- 시스템을 항상 safe sate로 유지
은행원
Deadlock Avoidance
Dijkstra's banker's algorithm |R| = 10
- 1 resource type R, 10 resource units, 3 processes
- ☆Safe sate example
나 10만원 = 2만원 → 3만원 → 5만원
↗ ↑ ↖
① ② ③
→ 1 5 2
→ 2 4 3
* 가정: 다 믿을 수 있는 친구
돈을 갚는다
State-1
Process-ID |
최대 필요 수 Max. Claim |
현재 할당 Cur. Alloc. |
MAX(앞으로 필요한 수) Additional Need |
| P1 | 3 | 1 | (3-1=)2 |
| P2 | 9 | 5 | (9-5=)4 |
| P3 | 5 | 2 | (5-2=)3 |
→
Available resource units : 2 순서
실행 종료 순서 : P1 → P3 → P2 ("Safe sequence") 하나만 존재! → "Safe state"
현재 상태에서 안전 순서가 하나 이상 존재하면 안전 상태임
Deadlock Avoidance
Dijkstra's banker's algorithm
- 1 resource type R, 10 resource units, 3 processes
- Unsafe state example
State-2
R = 2
Safe Sequence
| Process-ID | Max. Claim | Cur. Alloc. | Additional Need |
| P1 | 5 | 1 | 4 |
| P2 | 9 | 5 | 4 |
| P3 | 7 | 2 | 5 |
→
Available resource units : 3
No safe sequence
임의의 순간에 새 프로세스들이 모두 세 개 이상의 단위 자원을
요청하는 경우 시스템은 교착상태에 놓이게 됨
Deadlock Avoidance
Dijkstra's banker's algorithm (example)
- 1 resource type R, 10 resource units, 3 processes
R = 2
State-1
| Process-ID | Max. Claim | Cur. Alloc. | Additional Need |
| P1 | 3 | 1 → 2 | 2 |
| P2 | 9 | 5 | 4 |
| P3 | 5 | 2 | 3 |
→
R = 1 요청!
When the process P1 requests a resource unit in State-1,
- There exists safe sequence P1 → P3 → P2, after allocation
Accept the request, because State-1-1 is also safe state
State - 1-1
P1 → P3 → P2, R = 1
safe sequence
| Process-ID | Max. Claim | Cur. Alloc. | Additional Need |
| P1 | 3 | 2 | 1 |
| P2 | 9 | 5 | 4 |
| P3 | 5 | 2 | 3 |
Deadlock Avoidance
Dijkstra's banker's algorithm (example)
- 1 resource type R, 10 resource units, 3 processes
State-1
| Process-ID | Max. Claim | Cur. Alloc. | Additional Need |
| P1 | 3 | 1 | 2 |
| P2 | 9 | 5 → 6 | 4 |
| P3 | 5 | 2 | 3 |
→
(가정)
When the process P2 requests a resource unit in State-1,
- No safe sequence, after allocation
Reject the request, because State-1-2 is unsafe
Simmulation → safe sequence O → ok
X → reject!
State - 1-2
R = 1 safe sequence X
unsafe state
| Process-ID | Max. Claim | Cur. Alloc. | Additional Need |
| P1 | 3 | 1 | 2 |
| P2 | 9 | 6 | 3 |
| P3 | 5 | 2 | 3 |
Deadlock Avoidance
B R1
↓
여러개
Habermann's algorithm
- Dijkstra's algorithm의 확장
- 여러 종류의 자원 고려
* Multiple resource types
* Multiple resource units for each
- ☆ 시스템을 항상 safe state로 유지
Deadlock Avoidance
Habermann's algorithm (Example)
- 3 types of resources: Ra, Rb, Rc a b c
- Number of resource units for each type: (10, 5, 7)
- 5 processes
Max. claim of each process
| Process-ID | Max. claim |
| Ra Rb Rc | |
| P1 | 7 5 3 |
| P2 | 3 2 2 |
| P3 | 9 0 2 |
| P4 | 2 2 2 |
| P5 | 4 3 3 |
(10, 5, 7)
State-2
| Process-ID | 최대 필요 수 Max. claim |
현재 가진 수 Cur. Alloc. |
추가 필요 수 Additional Need |
| Ra Rb Rc | Ra Rb Rc | Ra Rb Rc | |
| P1 | 7 5 3 | 0 1 0 | 7 4 3 |
| P2 | 3 2 2 | 2 0 0 | 1 2 2 |
| P3 | 9 0 2 | 3 0 2 | 6 0 0 |
| P4 | 2 2 2 | 2 1 1 | 0 1 1 |
| P5 | 4 3 3 | 0 0 2 | 4 3 1 |
| 자원의 수의 합 | 7 2 5 |
→
Available resource units : "(3, 3, 2)"
Safe sequence : P2 → P4 → P1 → P3 → P5
- Safe state because there exist a safe sequence
Deadlock Avoidance
Habermann's algorithm (Example)
When the process P2 requests (1, 0, 2) in State-2,
- There exists a safe sequence (P2 → P4 → P1 → P3 → P5)
Accept the request, because State-2-1 is safe
State-2-1
(3, 3, 2) → (2, 3, 0)
| Process-ID | Max. claim | Cur. Alloc. | Additional Need |
| Ra Rb Rc | Ra Rb Rc | Ra Rb Rc | |
| P1 | 7 5 3 | 0 1 0 | 7 4 3 |
| P2 | 3 2 2 | 3→4 0 2→4 | 0 2 0 |
| P3 | 9 0 2 | 3 0 2 | 6 0 0 |
| P4 | 2 2 2 | 2 1 1 | 0 1 1 |
| P5 | 4 3 3 | 0 0 2 | 4 3 1 |
Deadlock Avoidance
Habermann's algorithm (Example)
When the process P1 requests (0, 3, 0) in State-2,
- No safe sequence, after allocation
Reject the request, because State-2-2 is unsafe
State-2-1
R = (3, 0, 2) → (2, 3, 0)
Additional Need: 요구할 수 있다! 반드시 필요 X
| Process-ID | Max. claim | Cur. Alloc. | Additional Need |
| Ra Rb Rc | Ra Rb Rc | Ra Rb Rc | |
| P1 | 7 5 3 | 0 4→7 0 | 7 1 3 |
| P2 | 3 2 2 | 2 0 0 | 1 2 2 |
| P3 | 9 0 2 | 3 0 2 | 6 0 0 |
| P4 | 2 2 2 | 2 1 1 | 0 1 1 |
| P5 | 4 3 3 | 0 0 2 | 4 3 1 |
Deadlock Avoidance
Deadlock의 발생을 막을 수있음
High overhead
- 항상 시스템을 감시하고 있어야 한다
Low resource utilization
- "Safe state" 유지를 위해, 사용 되지 않는 자원이 존재
☆Not practical
- 가정
* 프로세스의 수, 자원 수가 고정
*. 필요한 최대 자원 수를 알고 있음
- 프로세스는 자원을 사용 후 반드시 반납한다
Deadlock 해결 방법
Deadlock prevention methods
- 교착상태 예방
Deadlock avoidance method
- 교착상태 회피
Deadlock detection and deadlock recovery methods
- 교착상태 탐지 및 복구
Deadlock Detection 검출
Deadlock 방지를 위한 사전 작업을 하지 않음
- Deadlock이 발생 가능
주기적으로 deadlock 발생 확인
- 시스템이 deadlock 상태인가?
- 어떤 프로세스가 deadlock 상태인가?
"Resource Allocation Graph (RAG)" 사용
Deadlock Detection
Resource Allocation Graph (RAG)
- Deadlock 검출을 위해 사용
2
- Directed, bi/partite Graph
→ U P V R
○ → ○ ○ ╲
↖ ↕ ○ ╲ ●
○ ○⧹ ╲ ╱ ●
○ ╱ ╲ ●
○ ⧹ ●
Deadlock Detection
Resource Allocation Graph (RAG)
- Directed graph G = (N, E)
N: Node P: Process R: resource
* N = { Np, Nr } where
Np is the set of processes = {P1, P2, ..., Pn}
and Nr is the set of resources = {R1, R2, ..., Rn}
Processor Resource
Np Rr
P1 R1
P2 R1
... ...
Pn Rm
Deadlock Detection
Resource Allocation Graph (RAG)
- Edge는 Np와 Nr 사이에만 존재
* e = (Pi, Rj): 자원 요청
* e = (Pi, Rj): 자원 할당
P1 -요청(P1, R1)→ R1
P2 ←(R2, P2)할당- R2
... ...
Pn Rm
Deadlock Detection
Resource Allocation Graph (RAG)
- Rk : k type의 자원
- tk : Rk의 단위 자원 수 |Rk|
* For each Rk ∈ Nr, ∃ tk which is the number of units of Rk
갯수
- |(a, b)|: (a, b) edge의 수
→
t1 = 2
P1 ← ●● R1
|(R2, P2)| = 2
P2 → ●● t2 = 4
→ ●● R2
... ...
Pn ●
●● Rm
Deadlock Detection
RAG example
Deadlock?
P1 요청
↗ ↗ ↘
R1 ●● t1 = 3 t2 = 2 ●● R2
●
↘↖ 요청 ↙↗
P2 요청
Deadlock Detection Method
Graph reduction 줄인다
- 주어진 RAG에서 edge를 하나씩 지워가는 방법
- Completely reduced 다 지워짐!
* 모든 edge가 제거됨
* Deadlock에 빠진 프로세스가 없음
x
- Ir/reducible
* 지울 수 없는 edge가 존재
* 하나 이상의 프로세스가 deadlock 상태
o
Deadlock Detection Method
Graph reduction
- Unblocked process edge 지운다!
* 필요한 자원을 모두 할당 받을 수 있는 프로세스
(Pi → Rj) 개수 = 요청 수
The process Pi is unblocked if it satisfies 요청 ≤ 남은수
→ ∀ j (|Pi,→ Rj)| ≤ tj - ∑ all k |(Rj, Pk)| ) → 남은 수
모든 ↑ 전체 사용중 ∑ all k |(Ri → Pj)| → Rj가 할당된 수
모든자원 ↑ tj
Pi 요청하는 모든 자원 전체 Rj의 수
Deadlock Detection Method
Graph reduction procedure
① Unblocked process에 연결된 모든 edge를 제거
② 더 이상 unblocked process가 없을 때까지 ① 반복
- 최종 Graph에서
* 모든 edge가 제거 됨 (Completely reduced)
현재 상태에서 deadlock이 없음
X
* 일부 edge가 남음 (irreducible) => 자원 할당 받을 수 없는 P 존재
현재 deadlock이 존재
O
Graph reduction (example 1)
unblocked Pi
X X P1
↗ ↗ ↘ ↖
R1 ●● t1 = 3 t2 = 2 ●● R2
●
↘↖ ↙↗
P2
(a) Initial state
unblocked
P1
R1 ●● t1 = 3 t2 = 2 ●● R2
● X X
↘↖↘ ↙↗↙
X X P2
(b) Reduction by process P1
모든 edge X
P1
R1 ●● t1 = 3 t2 = 2 ●● R2
●
P2
(c) Reduction by process P2
Graph reduction (example 2)
unblocked process
P1
↗ ↗↙ ↖ ↘
R1 ●● ●● R2
●
↓ ↗↗ ↓X
P2 P3
↘ X↙↗X
●●
R3
(a) Initial state
unblocked process
P1
↗ ↗↙ ↖ ↘
R1 ●● ●● R2
●
↓ ↗↗
P2 P3
↘
●●
R3
(b) Reduction by process P3
→ deadlock
Deadlock Detection Method
Graph reduction
- High overhead
* 검사 주기에 영향을 받음
* Node의 수가 많은 경우
- Low overhead deadlock detection methods
(Special case)
* Case-1) Single-unit resources
Cycle detection
* Case-2) Single-unit request in expedient state
Knot detection
Deadlock Avoidance vs Detection
회피 탐지
- Deadlock avoidance
* 최악의 경우를 생각
앞으로 일어날 일을 고려
* Deadlock이 발생 하지 않음
- Deadlock detection
* 최선의 경우를 생각
현재 상태만 고려
* Deadlock 발생 시 Recovery 과정이 필요
O →
Deadlock Recovery
A(X) B C
누구를?
Random
Process termination
- Deadlock 상태인 프로세스 중 일부 종료
- Termination cost model
* 종료 시킬 deadlock 상태의 프로세스 선택
* Termination cost
우선순위 / Process priority ↙ ↘
종류 / Process type System User 100 1 (X)
총 수행 시간 / Accumulated execution time of the process
남은 수행 시간 / Remaining time of the process
종료 비용 / Accounting cost
Etc.
- 종료 프로세스 선택
* Lowest-termination cost process first
장점
Simple O(n) P1 ... Pn
Low overhead
단점
불필요한 프로세스들이 종료될 가능성이 높음
2x2x ... 2
* Minimum cost recovery "최고의 선택" P1 P2 ... Pn
최소 비용으로 deadlock 상태를 해소 할 수 있는 process 선택 x x x
모든 경우의 수를 고려해야 함
Complex
High overhead
O(2^k)
Deadlock Recovery
→
↑↓
P2 R1 R2 R3
↓ ↖ ↑ ↗
종료! P1
Resource preemption
- Deadlock 상태 해결을 위해 선점할 자원 선택
- 해당 자원을 가지고 있는 프로세스를 종료시킴
* ☆deadlock 상태가 아닌 프로세스가 종료 될 수 있음
* 해당 프로세스는 이후 재시작 됨
- 선점할 자원 선택 ←|기준
* Preemption cost model이 필요
* Minimum cost recovery method 사용
O(r)
1 ... r
↖ ↑ ↗
P1
Deadlock Recovery
Deadlock을 검출한 후 해결하는 과정
Deadlock recovery methods
- Process termination
* Deadlock 상태에 있는 프로세스를 종료시킴
* 강제 종료된 프로세스는 이후 재시작 됨
- Resource termination
* Deadlock 상태 해결을 위해 선점할 자원 선택
* 선점된 자원을 가지고 있는 프로세스에서 자원을 빼앗음
자원을 빼앗긴 프로세스는 강제 종료됨
Deadlock Recovery
Pi → 종료
| | |
←
"save point"
게임
Checkpoint-restart method
- 프로세스의 수행 중 특정 지점(checkpoint)마다 context를 저장
- Rollback을 위해 사용
* 프로세스 강제 종료 후 가장 최근의 checkpoint에서 재시작
start
- checkpoint-1 (context saved)
- checkpoint-2 (context saved)
|
- checkpoint-k (context saved)
|
- abnormally terminated
|
finish
요약
Deadlock의 개념
Deadlock의 model(표현법)
Deadlock의 해결 방법들
- Deadlock prevention
- Deadlock avoidance
- Deadlock detection and recovery
'프로그래밍 공부 > OS' 카테고리의 다른 글
| 9 Virtual Storage (Memory) (0) | 2024.02.05 |
|---|---|
| 8 메모리(주기억장치) 관리 (0) | 2024.02.02 |
| 6 프로세스 동기화 & 상호배제 (0) | 2024.01.24 |
| 5 프로세스 스케줄링 (0) | 2024.01.22 |
| 4 스레드 관리 (0) | 2024.01.21 |