본 설명은 책 “그림으로 배우는 구조와 원리 운영체제 개정 3판”를 읽으며 제 나름대로 해석하고 정리해 보았습니다.😉

은행원 알고리즘

은행가(은행원) 알고리즘은 자원의 할당 허용 여부를 결정하기 전에 미리 결정된 모든 자원의 최대 가능한 할당량을 시뮬레이션하여 안전 여부를 검사한다. 그런 다음 대기 중인 다른 모든 활동의 교착 상태 가능성을 조사하여 “안정 상태” 여부를 검사 확인한다.

은행원 알고리즘이 어디서 나온 개념인지 궁금하다면 교착상태 해결 방법 를 참고하자. 지금부터는 은행원 알고리즘에 필요한 자료가 무엇이 있는지 그리고 어떻게 계산되는지 예시를 보면서 살펴보자.

은행원 알고리즘의 자료구조

여기서 은행가 알고리즘은 다음 자료구조 들이 필요하다.

• Availabe: 각 형태별로 사용 가능한 자원 수 (사용 가능량)을 표시하는 길이가 m 인 벡터이다. Available[j] = k 이면, j 번째 자원을 k개 사용할 수 있다는 의미이다.

• Max: 각 프로세스 자원의 최대 요청량(최대 요구량)을 표시하는 n * m 행렬이다. Max[i,j] = k 이면, 프로세스 Pi는 자원 Rj를 최대 k개 까지 요청할 수 있다는 의미이다.

• Allocation : 현재 각 프로세스에 할당되어 있는 각 형태의 자원 수(현재 할당량)을 정의 하는 n*m 행렬이다. Allocation[i, j] = k 이면, 프로세스 Pi는 자원 Rj를 k 개 할당받고 있다는 의미이다.

• Need : 각 프로세스에 남아 있는 자원 요청(추가 요구량)을 표시하는 n*m 행렬이다. Need[i,j] = k 이면 프로세스 Pi는 자신의 작업을 종료하려고 Rj를 k개 더 필요하다는 의미이다.

은행원 알고리즘 동작 순서

프로세스 Pi 가 여기서 자원을 요청하게 되면 다음과 같은 동작이 일어난다.

• 1단계 : Request(i)≤ Need(i)이면 2단계로 이동하고 그렇지 않으면 프로세스가 최대 요청치를 초과하기 때문에 오류 상태가 된다.
• 2단계: Request ≤ Available 이면 3단계로 이동하고, 그렇지 않으면 자원이 부족하기 때문에 Pi는 대기한다.

• 3단계: 시스템은 상태를 다음과 같이 수정하여 요청된 자원을 프로세스 Pi에 할당한다.

  Available = Available - Request(i);

  Allocation(i) = Allocation(i) + Request(i);

  Need(i) = Need(i) - Request(i);

그리고 이제 안정 상태인지, 불안정 상태인지 검사한다. 다음 과정으로 수행된다.

• 1단계 : Work와 Finish를 각각 길이가 m과 n인 벡터라고 하자. Work = Available, Finish[i] = False, i = 1,2, … n 으로 초기화 한다.

• 2단계 : 다음 조건을 만족하는 i 값을 찾는다. i 값이 없으면 4단계로 이동한다.

  Finish[i] == False

  Need(i) ≤ Work

• 3단계 : 다음을 수행하고 2단계로 이동한다.

  Work = Work + Allocation(i)

  Finish[i] = True

• 4단계 : 모든 i 에 대하여 Finish[i] == True이면 시스템은 안정상태이다.

은행원 알고리즘 예시 문제 풀이

먼저 답부터 말하자면, 위의 예시에서는 P2 → P4 → P1 → P3 순서일때 안정상태에 있다. 그림 지금부터 어떻게 P2 → P4 → P1 → P3 순서가 성립하는지 계산을 시작해보자! (같이 종이에 써보면서 각각의 자료구조가 무엇을 의미하는지 생각하기보다는 어떤 흐름으로 계산이 되는지만 잡아봅시다 !)

Step 1

먼저 위의 그림에서 Need에 값이 작성되어있는데 주어질 때도 있고 주어지지 않을 떄도 있다. 가장 먼저 먼저 Need(i) = Maximum(i)-Allocated(i) 를 계산한다.

P1 : Need[1] = (7, 5, 3) - (0, 1, 0) = (7, 4, 3)

P2: Need[2] = (3, 2, 2) - (2, 0, 0) = (1, 2, 2)

P3: Need[3] = (9, 0, 4) - (4, 0, 1) = (5, 0, 3)

P4: Need[4] = (2, 2, 2) - (2, 1, 1) = (0, 1, 1)

이 따라서 결과 이다.

Step2

그럼 이제 Work, Finish 를 초기화해줍시다. Work의 초기값은 Available 값과 같고 Finish 는 프로세스의 갯수만큼의 길이를 같고 각각의 값은 False 로 초기화합니다.

즉, Work = (3, 3, 2)

​ Finish = (False, False, False, False)

Step 3

이제 계산하기전의 준비는 끝났다. 그럼 이제 P1 부터 차례로 자원이 할당 가능한지를 판별해보자.

만족하는 조건은 Finish[i] = False 이고 Need[i] <= Work 여야한다.

먼저 편의상 P1 -> P4 부터 차례로 검사해보자.

Finish[1] = False

Need[1] = (7, 4, 3) 이고 Work = (3, 3, 2) 로

(7, 4, 3) <= (3, 3, 2) 로 Need[1]의 A와 B자원의 부등호가 성립하지 않는다. 따라서 가장 처음에 P1에 자원을 할당할 수 없다.

그럼 P2 를 보자.

(1, 2, 2) <= (3, 3, 2) 로 만족한다! 따라서 가장 처음에 자원을 할당해줄 프로세스는 P2 이다. 그런데 여기서 “어, P4 도 되는데?” 라고 생각할 수 있다. 그렇다 P4도 된다! 여러가지 순서로 안정 조건이 성립할 수 있다. 일단 계산을 끝까지 해봐야하니까, 계속 진행해보자.

그럼 P2에 자원을 할당해주었다. 그럼 이제

Work = Work + Allocation[i] (표에서는 Allocated)

Finish[i] = True 로 계산해주자면

Work = (3, 3, 2) + (2, 2, 0) = (5, 5, 2) 이다.

그럼 이제 다시 같은방법으로 P1 부터 확인해보자.

Finish[1] = False

Need[1] (7, 5, 5) <= Work (5, 5, 2) 땡이다. 그럼 P1말고 P3을 봐보자

Finish[3] = False

Need[3] (5, 0, 3) <= Work (5, 2, 2) 역시 땡이다. C자원이 모자르다. 그럼 이제 P4를 봐보자.

Finish[4] = False

Need[4] (0, 1, 1) <= Work (5, 2, 2) 만족한다!

그럼 Finsih[4] = True, Work = (5, 2, 2) + Allocation[i] (2, 1, 1) = (6, 3, 3) 이다.

이 과정을 반복하게 되면 초기에 말했던 정답인 P2 → P4 → P1 → P3 순서로 안정조건이 성립할 수 있음을 알 수 있다!

자, 그럼 이제 은행원알고리즘 계산을 어떻게 하는지는 대충 감을 잡았을 것이다. 그렇다면 왜 이러한 방식으로 계산을 했는지 다시 짚어보자.

먼저, Allocation (Allocated)는 각 프로세스가 지금 현재 사용하고 있는 자원의 개수이다. 그리고 Maximum(Max)는 각 프로세스가 최대 요구 할 수 있는 자원의 개수이다. 따라서 프로세스가 어떤 특정 시간 상황에 따라서 Maximum의 개수만큼 자원을 요구할 수 도 있는 것이다. 그렇기 때문에 프로세스가 지금 현재 갖고있는 자원 + Need(더 요구할 수도 있게되는 자원의 개수) 즉, Maximum의 상황을 고려해줘야 하는것이다. Available은 프로세스 P1, P2, P3, P4가 쓰고 있는 자원 외에 지금 시스템에서 갖고있는 자원의 개수이다. 즉 여분의 자원, 누구든 사용할 수 있는 자원의 개수인 것이다. 따라서 Work라는 값을 두고 현재 사용 가능한 자원의 개수를 두고 각 프로세스가 끝나면 자원을 해제 하게 되면서 Allocation (Allocated) 자원들을 시스템이 갖게되는 것이다. 따라서, Work = Work + Allocation[i] 가 되는 것이다. 그리고 Finish 는 말그대로 해당 프로세스를 수행했는지의 여부를 체크하는 것이다.

즉, OS는 각각의 프로세스가 지금 갖고 있는 자원에서 최대 자원 요구량의 상황까지 고려하면서 데드락이 일어나지 않도록 위의 같은 은행원 알고리즘으로 교착상태를 회피하고자 하는 것이다.

이렇게 은행가 알고리즘은 교착 상태를 회피하려고 교착 상태가 일어나지 않을 때만 작업을 진행시킨다. 그러나 다음 단점이 있다.

• 일정하게 남아있는 자원 수를 파악하기가 매우 어렵다.
• 다중 프로그래밍 시스템에서는 사용자 수가 항상 변한다.
• 교착 상태 회피 알고리즘을 실행하면 시스템 과부하가 증가한다.
• 프로세스는 자원을 보유한 상태로 끝낼 수 없다.
• 항상 불안정 상태를 방지해야하므로 자원 이용도가 낮다.