[OS] Deadlock Avoidance (Banker's Algorithm)

※ 질문/내용오류/공유할 내용이 있다면 jinkilee73@gmail.com으로 메일 주세요 :-)

Banker's Algorithm은 쉽게 말해서 은행원이 돈 빌려주는 것처럼 생각하면 된다.

은행원이 돈이 있으면 돈을 빌려주겠지? 돈이 없으면? 안 빌려주겠지? 그런 것이다. 예를 통해 이해해보자.

Situation

자원 A, B, C가 있다. 각각 10, 5, 7개의 Instance를 가지고 있다. 그런 상황에서 어떤 시간 t0에 다음과 같은 상황에 놓여있다고 하자.

# all resource

# Allocation, Max, Need (단, Need = Max - Allocation)

# Available resource ( = All resource - sum(Allocation))

이 상태에서 만일 P1가 추가적으로 자원 A의 Instance 하나와 자원 C의 Instance 두 개를 요구했다고 해보자. 현재 줄 수 있는 자원은 (3, 3, 2)인데 P1이 요구한 것은 (1, 0, 2)이다. 아직은 더 줄 수 있다. 

# All resource

# Allocation, Max, Need (단, Need = Max - Allocation)

# Available resource

그래서 위와 같은 상태가 된다.

위의 상태의 그래프는 <P1, P3, P4, P0, P2>순서로 수행을 하면 Safe State를 만족시킬 수 있다. 실제로 해보면 알 것이다. :=)

※ 위의 순서는 어떻게 찾아내느냐고? Safety Algorithm이라는 것이 있다. 그것을 찾아보면 알 수 있다.

마지막으로 Deadlock Detection을 다음 포스팅에서 설명하겠다.