Deadlock Avoidance
: 자원 요청에 대한 부가정보를 이용하여 자원 할당이 deadlock으로부터 안전(safe)한지를 조사하여, 안전한 경우에만 할당한다.
▷ 모든 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 한다.
※ safe state, safe sequence
: 프로세스의 sequence <P0, P1, ..Pn>이 safe하려면, P의 자원 요청이 "가용자원 + 모든 Pj의 보유 자원"에 의해 충족되어야 한다.
※ 2가지 경우의 avoidance 알고리즘
- Single instance per resource types --> Resource Allocation Graph algorithm
- Multiple instance per resource types --> Banker's algorithm
1) Resource Allocation Graph algorithm
▷ 점선을 포함하여, cycle이 생기지 않는 경우에만 요청 자원을 할당한다. (점선 --> 실선으로 바뀌면 deadlock이 발생할 수 있기 때문)
2) Banker's algorithm
: 미래에 요청 가능한 자원과, 현재 할당해줄 수 있는 자원을 비교하여 자원을 줄지 말지 결정한다.
- 자원 별 양은 정해져 있다.
- Allocation: 현재 프로세스에게 할당된 자원의 양
- Max: 모든 프로세스는 자원별 최대 사용량을 미리 명시한다.
- Available = 자원 별 개수 - Allocation: 할당해줄 수 있는 자원의 양
- Need = Max - Allocation: 미래에 추가 요청 가능한 자원의 양
▷ Need > Avaiable이면 자원을 주지 않고, Need < Available이면 자원을 준다.
--> 항상 safe state
Deadlock Detection and Recovery
: Deadlock 발생은 허용하되, 그에 대한 detection 루틴을 두어 deadlock 발견 시 recover한다.
▶ Deadlock Detection
- Resource type 당 single instance인 경우 --> Resource allocation graph
- Resource type 당 multiple instance인 경우 --> Banker's algorithm 유사한 방법
1) Resource-Allocation Graph
- Resource allocation graph
- Corresponding wait-for graph: 자원(R)을 빼고 그린 그래프
2) Banker's algorithm 유사한 방법
- 자원 별 양은 정해져 있다.
- Allocation: 현재 프로세스에게 할당된 자원의 양
- Request: 현재 프로세스가 요청한 자원의 양
- Available = 자원 별 개수 - Allocation: 할당해줄 수 있는 자원의 양
▷ Request > Avaiable이면 자원을 주지 않고, Request < Available이면 자원을 준다.
- Deadlock Avoidance - Banker's algorithm: 미래의 자원 요청까지 고려하는 방법
- Deadlock Detection and Recovery - Banker's algorithm 유사한 방법: 현재의 자원 요청을 고려하는 방법
▶ Deadlock Recovery
1. Process termination: deadlock과 연관된 process 죽인다.
- Abort all deadlocked process
- Abort one process at a time until the deadlock cycle is eleminated
2. Resource preemption: deadlock과 연관된 process의 자원을 빼앗는다.
- cost factor, rollback 횟수를 고려하여 victim을 선정한다.
Deadlock Ignorance
: Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않는다.
--> 만약 시스템에 deadlock이 발생한 경우, 시스템이 비정상적으로 작동하는 것을 느낀 사람이 직접 process를 죽이는 방법 등으로 대처한다.
- Unix, Windows 등 대부분의 범용 OS가 채택하는 방법
'운영체제' 카테고리의 다른 글
[운영체제] KOCW 9 - Ch8: Memory Management (0) | 2023.06.10 |
---|---|
[운영체제] KOCW 8 - Ch8: Memory Management (0) | 2023.06.09 |
[운영체제] KOCW 6.3 - Ch7: Deadlock (0) | 2023.06.09 |
[운영체제] KOCW 6.2 - Ch6: Process Synchronization (0) | 2023.06.09 |
[운영체제] KOCW 6.1 - Ch6: Process Synchronization (0) | 2023.06.09 |