[제138회 정보관리기술사 1교시 11번] 은행가 알고리즘(Banker’s Algorithm) — 교착상태 회피의 핵심

출제 의도 분석

운영체제의 교착상태(Deadlock) 파트에서 단골 출제됩니다. 회피(Avoidance) 기법으로서의 핵심 메커니즘인 안전 상태 개념과 실제 계산 과정을 단계별로 보여주면 완성도가 높습니다. Deadlock의 4대 조건과 연결하면 추가 점수를 기대할 수 있습니다.

1. 교착상태 처리 방법

방법	전략	대표 알고리즘
예방(Prevention)	4대 조건 중 하나 제거	자원 선점, 총체적 순서
회피(Avoidance)	안전 상태 유지	은행가 알고리즘
탐지(Detection)	발생 후 탐지·복구	자원할당 그래프
무시(Ignorance)	드문 경우 무시	Ostrich Algorithm

2. 은행가 알고리즘 개념

은행이 대출 시 자금이 항상 부족하지 않도록 관리하듯, OS가 프로세스에 자원 할당 시 시스템이 안전 상태(Safe State)를 유지할 수 있는 경우에만 자원을 할당하는 알고리즘입니다.

안전 상태: 모든 프로세스가 최대 자원 요구량을 순차적으로 만족받아 실행 완료될 수 있는 안전 순서열(Safe Sequence)이 존재하는 상태

3. 주요 데이터 구조

• Available[m]: 현재 사용 가능한 각 자원의 수
• Max[n×m]: 각 프로세스의 최대 자원 요구량
• Allocation[n×m]: 현재 각 프로세스에 할당된 자원
• Need[n×m]: 각 프로세스가 추가로 필요한 자원 (= Max – Allocation)

4. 안전성 검사 알고리즘

1. Work = Available, Finish[i] = false for all i
2. Find i: Finish[i]=false AND Need[i] ≤ Work
3. Work += Allocation[i], Finish[i] = true
4. Goto 2
5. Finish[i]=true for all i → Safe State
   else → Unsafe State (자원 할당 거부)

5. 한계점

• 각 프로세스의 최대 자원 요구량을 사전에 알아야 함 → 현실적 어려움
• 프로세스 수와 자원 종류가 고정되어야 함
• 계산 오버헤드 발생 (O(n² × m))

핵심 정리

은행가 알고리즘은 이론적으로 완벽한 교착상태 회피 방법이지만, 실제 운영체제에서는 사전 정보 확보의 어려움으로 잘 사용되지 않습니다. 대부분의 실용 OS는 탐지 후 복구 방식을 채택합니다.