2019년 3월 13일
은행가 (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 발생 가능 – 할당할 자원량 일정량 존재 필요 – 최대 자원 요구량을 알아야 함 |
About The Author
도리
2 Comments
2) 추가요구량(Need) 계산 시 P2의 R2 자원은 2가 되어야 하지 않을까요?
–> 최대요구량(Max = 1, 4) – 할당량(Allocation = 1, 2) = 추가요구량(Need = 0, 2)
말씀하신 것과 같이 (2) 추가 요구량 산정식을 통해 P2 프로세스의 R2 추가 요구 자원(Request)은 최대 요구량(4) – 현재 점유량(2) = 2가 맞습니다.
본문에서 잘못된 부분을 올바르게 수정하였습니다. 잘못된 부분 지적 감사드립니다.