은행가 (Banker’s) 알고리즘

1. 교착상태 대표 회피 알고리즘, 은행가 알고리즘

(1) 은행가 알고리즘의 개념

• 작업에 필요한 자원 수에 따라 프로세스 수행에 필요한 자원이 충분한지 검사하는 교착상태 회피 알고리즘

(2) 은행가 알고리즘의 자료구조

자료구조	설명
Max	– 프로세스 별 최대 자원의 요구
Available	– 사용 가능 자원의 수
Need	– 프로세스 별 남아있는 자원 수
Allocation	– 현재 프로세스 별 할당 자원 수

2. 은행가 알고리즘 사례

• 사전 가정

(1) 현재 사용 가능한 리소스의 양을 구한다.

• Available = 리소스 총량 – Allocation 합산

(2) 추가 요구량을 구한다

• Request = Max – Allocation

(3) 추가 요구 자원이 현재 여유 자원보다 적은 프로세스(i)를 찾는다.

• 수행을 끝내기 위한 충분한 자원을 확보한 프로세스 검사
  [ (Request(i) ← Available(i) ]

(4) 수행 가능한 프로세스가 점유한 자원을 여유 자원으로 바꿈

• (끝내고 반환한 경우로 가정) 이후 3번부터 반복
  (Available = Available + Allocation)

3. 은행가 알고리즘 분산 시스템 사용 방법 및 문제점

구분	설명
분산 시스템에서 사용방법	– 시스템 내 프로세스 중 하나를 은행원 알고리즘 수행 시 유지 프로세스(은행원)으로 지정하여 분산 시스템에서 사용
은행가 알고리즘 문제점	– 쉽게 구현 가능하지만 추가 비용 소요 – 은행원이 Bottleneck 발생 가능 – 할당할 자원량 일정량 존재 필요 – 최대 자원 요구량을 알아야 함