운영체제 Deadlock Avoidance ( 은행원 알고리즘, Banker's Algorithm, Safety Algorithm, Resource-Request Algorithm )

Deadlock 처리

deadlock을 처리하는 방법으로는 3가지 정도 볼 수 있다.
1. Deadlcok Prevention
2. Deadlcok Avoidance
3. Detection and recovery 

그중에 Deadlock Avoidance에 대해 알아보자

 

Deadlock Avoidance

 

Prevention과 마찬가지로 criculer wait를 무효화하는 방법이다. 하지만 다른 점이라면 자원의 상태(state)를 판단하여 할당할지 안 할지를 판단한다. 이때 상태라고 함은 3가지 상태를 판단한다.

 

1. the number of available ( 사용 가능한 자원의 수 )

2. allocated resources ( 할당된 자원의 수 )

3. the maximum demands of the processes ( 프로세스가 요구한 최대 자원의 수 ) 

 

우린 safe state라는 상태를 찾는 것이 목표이다. 간단히 말해 프로세스의 동작 순서를 정해서 criculer wait를 만들지 않는 상태를 말한다. 

 

하지만 criculer wait을 만들더라고 Deadlock이 아닌 상태가 있지만 여기선 criculer wait를 만든다면 무조건 safe state라고 판단하지 않는다. 굉장히 보수적인 알고리즘이다. 

 

자세히 알아보자, 

 

먼저 instance가 1개라고 했을 때, 자원을 할당하기 위해서 Claim edge라는 상태를 추가했는데, 뭘 의미하냐면, 당장 자원이 필요하지 않지만 가까운 미래에 요청할 것이란 걸 알려준다. 그림에선 검은 점선을 나타낸다.

 

 

예를 들어보자, 다음과 같은 상황이라면 R2는 어느 프로세스에 할당돼야 할까??

 

 

만약 P2에 먼저 할당된다면 P1은 동작하지 못하고 계속 기다린다. 즉, Deadlock에 빠진다 ( not safe ) 그래서 P1에 먼저 R2를 할당하고 P1이 끝나면 그때 P2가 동작한다. 

정리하면 자원을 할당할 때 Claim edge도 고려하여 할당해야 한다.

 

그렇다면 만약 자원의 instance가 여러 개라면 어떻게 할까?? Banker's 알고리즘을 이용하여 구현한다.

 

 

Banker's Algorithm

 

여러 개의 instnace가 있다고 했을 때 어떻게 자원을 할당할 것인가에 대한 알고리즘이다. 프로세스와 자원을 matrix형태로 나타낼 수 있다.

 

확인해야 할 사항들이 4가지 있다.

Availlable : 사용 가능한 자원의 수

Max : 프로세스가 요청한 최대 자원 수  

Allocation : 이미 할당된 자원의 수

Need : 필요한 자원의 수 (Max - Allocation)

 

Banker's 알고리즘은 2가지 알고리즘으로 합쳐져 있는데 먼저 그중  하나인 Safety Algorithm을 보자. 

 

 

1. Safety Algorithm

 

- 예를 들어보면, Work (m개)와 Finish (n개)라는 변수를 만든다. 

Work = Available

Finish = Fasle로 초기화한다.

 

하나의 프로세스 i에 대해서 다음과 같은 동박을 반복한다.

Finish [i] = False

Need [i] <= Work

무슨 말이냐면, Finish [i] = False는 아직 자원을 할당받지 못했다는 의미고, Need <= Work는 필요한 자원의 수가 이용 가능한 자원의 수보다 작거나 같으면 할당할 수 있다는 의미니 만족한다면 (Finish [i] == True)로 safe state로 본다.

 

만약 만족하지 못한다면. 

Work = Work + Allocation [i]

Finish [i] = True로 업데이트하고 다시 반복한다.

 

 

2. Resource-Request Algorithm 

 

- Requset라는 프로세스가 동작하기 위해 요청한 자원의 수를 의미하는 변수를 가지고 state를 판단한다.

 

Request <= Need (필요한 자원의 수보다 요청한 자원의 수가 적거나 같으면 다음으로 이동), 

Reques <- Available (이용 가능한 자원의 수보다 요청한 자원의 수가 적거나 같으면 상태를 업데이트해준다)

 

Available = Available - Request;

Allocation = Allocation + Request;

Need = Need - Request;

 

이렇게 했을 때, 만약 safe state라면 프로세스에게 자원을 할당해주고 아니라면 대기한다.

 

 

위에 두 알고리즘을 조합하여 Banker's 알고리즘이 구현된다. 예를 들어보면서 이해하면 더욱 좋을 것이다.

5개의 프로세스가 있고 3가지 타입의 자원이 있는데, 각각 A( 10 instance ), B( 5 instance ), C( 7 instance )를 가지고 있다고 하자.

 

 

Need는 Max - Allocation으로 알 수 있다.

 

P0

- Work = [ 3, 3, 2 ]

Finish = [ False, False, False, False, False, ] (P0~P4)

 

P0는 [ 7 4 3 ]이 필요하지만 현재 가능한 자원은 [ 3, 3, 2 ]뿐이라 대기해야 한다. ( Need <= Work ) 

 

P1

- Work = [ 3, 3, 2 ]

Finish = [ False, False, False, False, False, ] (P0~P4)

 

P1은 [ 1 2 2 ]가 필요한데 현재 가능한 자원은 [ 3, 3, 2 ]이니 할당 가능하다. 그러니 P1에게 자원을 주고 동작이 끝나면 회수한다. 즉, Work = [ 5, 3, 2 ]가 되고 Finish [1] = True로 변경된다.

 

이런 식으로 진행하다 보면 safe sequence는 < P1, P3, P4, P0, P2 >와 같은 순서로 진행된다. 단, 우선순위를 고려하진 않는다.