[운영체제]데드락을 회피할 수 있는 자원할당 그래프, 은행원 알고리즘

자원할당 그래프 알고리즘(Resource-Allocation Graph Algorithm)

 자원이 하나일 때 사용하는 알고리즘. 자원 할당 그래프에 요청 간선과 할당 간선에 추가하여, 예약간선이라는 새로운 유형의 간선을 도입한다.

- 요청선 : 프로세스에서 자원으로 연결 된 섬 (나 저 자원 쓰고 싶다~라고 요청한다고 보면 됨)

 

- 할당선 : 자원에서 프로세스로 연결 된 섬 (이 자원은 이 프로세서가 쓰고 있음을 나타냄)

 

 

교착상태 확인 방법

1. 자원할당 그래프의 사이클이 존재하는 지 확인

2. 사이클이 존재한다면

  - 자원 유형에 하나의 사례만 있으면 교착상태

  - 자원 유형에 여러 사례가 있으면 교착상태 가능성

 

 

• 교착상태가 있는 자원할당 그래프 예시

 

 

 

 

• 사이클은 있지만 교착상태가 아닌 예

 

프로세스 p1이 작업을 완료하고 R3의 자원을 반환하면 p3은 p1이 반환한 자원을 할당 받으면 된다.

 

은행원 알고리즘(Banker's Algorithm)

 간단하게 교착상태를 예측하여 교착상태가 가능한 상태는 자원을 할당하지 않는 알고리즘

 

검사하여 안정상태에 있으면 자원을 할당하고 불안정상태라면 다른 프로세스들이 자원을 해제할 때까지 대기한다.

 

프로세스는 끝나면 자신이 할당하고 있는 데이터를 Available에 더해준다.

 

이러한 상태라면 

P0 -> P1 -> P2 -> P3 -> P4는 불안정 상태

 

예를 들어
P1을 보자,

available(all) > P1의 need(all)이므로 가능 (점유시켜줌)

그 후 available에 P1의 allocation을 더해준다. available : 332 -> 532

 

다음은 P2를 보자.

available(all) > P2의 need(all) 이므로 점유가 가능

작업 후, available에 P2의 allocation을 더해준다. available : 532 ->834

 

그리고 P3도 가능.

available : 834 -> 10 4 5

 

그 뒤로 P0도 가능. 마지막으로 P4도 가능 

결론 : P1->P2->P3->P0->P4는 안정된 상태이다.

 

이렇게 좋아보이지만,

 

알고리즘이 복잡하기 때문에 시스템이 과부하

할당할 수 있는 자원의 일정량을 요구한다.

사용자 프로세스가 일정해야 한다.

사용자가 최대 필요량을 미리 얄려주길 요구 하는 등의 단점이 있다.