[운영체제] KOCW 7 - Ch7: Deadlock

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

1) Resource Allocation Graph algorithm

▷ 점선을 포함하여, cycle이 생기지 않는 경우에만 요청 자원을 할당한다. (점선 --> 실선으로 바뀌면 deadlock이 발생할 수 있기 때문)

 

2) Banker's algorithm

: 미래에 요청 가능한 자원과, 현재 할당해줄 수 있는 자원을 비교하여 자원을 줄지 말지 결정한다.

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

1. Resource type 당 single instance인 경우 --> Resource allocation graph
2. Resource type 당 multiple instance인 경우 --> Banker's algorithm 유사한 방법

1) Resource-Allocation Graph

1) Resource-Allocation Graph: Deadlock detection -- "cycle"

• Resource allocation graph
• Corresponding wait-for graph: 자원(R)을 빼고 그린 그래프

2) Banker's algorithm 유사한 방법

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가 채택하는 방법