교착상태 회피( 은행가 알고리즘 )

교창상태 회피

Dijkstra가 제시한 은행가 알고리즘 이용

정의 :

1.     불안정상태 or 교착상태를 피할 수 있는 자원 할당 알고리즘

안전 (Safety)알고리즘

시스템이 안전 상태인지를 발견하는 알고리즘은 다음과 같다.

1.     Work와 Finish를 각각의 값이 m과 n인 벡터라고 하면, Work = Available로 , Finish[i] = false I = 1,2,3, … , n으로 초기화한다. Work에 남아 있는 자원 수는 Available의 임시변수이다.

2.     다음과 같이 되는 i 값을 찾는다

ㄱ.   Finish[i] = false

ㄴ.   Need[i] <= Work

ㄷ.   이러한 i값이 있으면 3단계로 가고 , 없으면 4단계로 간다.

3.     자원을 할당한 후 , 해제한다

ㄱ.   Work[i] = Work[i] + Allocation[i];

ㄴ.   Finish[i] = true;

ㄷ.   2단계로 간다.

4.     모든 i에 대하여 Finish[i] = true 이면 , 이 시스템은 안정 상태이다

Ex)

안전한 수행 순서 : <p4,p2,p5,p3,p1>

은행가 알고리즘의 단점

1.     사용 가능한 일정량의 자원이 미리 존재하도록 요구된다

2.     남아 있는 사용자의 수가 수시로 변경됨

3.     모든 요청에 대하여 주어진 시간 내에서 자원을 할당할 수 있도록 강한 보장이 필요하다

4.     사전에 자기가 필요한 자원의 최대량을 제시 해야 된다.