Brain은행원 알고리즘 (Banker's Algorithm)
핵심 인사이트 (3줄 요약)
- 본질: 은행원 알고리즘 (Banker's Algorithm)은 에츠허르 다익스트라 (Edsger W. Dijkstra)가 설계한 교착 상태 회피 알고리즘으로, 자원 할당 요청 시 안전 상태 유지 여부를 검사하여 불안전 상태로 이어지는 할당을 거부한다.
- 가치: 은행이 대출 전에 상환 가능 여부를 심사하듯, 시스템이 자원 할당 전에 모든 프로세스가 종료 가능한 순서(안전 순서)가 존재하는지 검증하여 교착 상태를 원천 방지한다.
- 융합: Available, Max, Allocation, Need 행렬 4개의 자료구조와 안전 상태 알고리즘 + 자원 요청 알고리즘 2개의 서브루틴으로 구성되며, 다중 인스턴스 자원 환경에서의 교착 회피 표준 해법이다.
Ⅰ. 개요 및 필요성
다중 인스턴스 자원 환경에서는 자원 할당 그래프만으로 교착 상태를 감지하기 어렵다. 프로세스가 최대 n개의 자원을 요청할 수 있고 현재 m개를 보유 중일 때, "이 요청을 들어줘도 나중에 모든 프로세스가 완료될 수 있는가?"를 미리 계산하는 알고리즘이 은행원 알고리즘이다.
이름의 유래: 은행은 예금 총액을 초과하는 대출을 해주지 않으면서도, 고객들이 돌아가며 빌리고 갚는 한 파산하지 않는다. 시스템도 마찬가지다.
💡 비유: 은행이 "지금 당신에게 이 금액을 대출해 줘도, 나머지 고객들의 대출 수요를 모두 충족하고 회수할 수 있는가?"를 확인하고 승인하는 것과 정확히 같다.
┌──────────────────────────────────────────────────────────────┐
│ 은행원 알고리즘 4개 자료구조 │
├──────────────────────────────────────────────────────────────┤
│ │
│ n = 프로세스 수, m = 자원 유형 수 │
│ │
│ Available[m] : 각 자원 유형의 현재 사용 가능 인스턴스 │
│ Max[n][m] : 각 프로세스의 최대 자원 요구량 │
│ Allocation[n][m] : 각 프로세스에 현재 할당된 자원량 │
│ Need[n][m] : 각 프로세스의 추가 필요량 │
│ │
│ 관계: Need[i][j] = Max[i][j] - Allocation[i][j] │
│ │
│ 예시 (5 프로세스, 3 자원 유형 A,B,C): │
│ │
│ Allocation Max Need Available │
│ A B C A B C A B C A B C │
│ P0: 0 1 0 7 5 3 7 4 3 │
│ P1: 2 0 0 3 2 2 1 2 2 3 3 2 │
│ P2: 3 0 2 9 0 2 6 0 0 │
│ P3: 2 1 1 2 2 2 0 1 1 │
│ P4: 0 0 2 4 3 3 4 3 1 │
│ │
│ 안전 순서: <P1, P3, P4, P2, P0> ← 존재하면 안전 상태 │
└──────────────────────────────────────────────────────────────┘
📢 섹션 요약 비유: 은행원 알고리즘은 자원 배분의 사전 심사 시스템 — "지금 이 요청을 들어줘도 미래에 모두 회수할 수 있는가"를 계산하는 안전망입니다.
Ⅱ. 아키텍처 및 핵심 원리
안전 상태 알고리즘
Safety Algorithm:
① Work = Available.copy()
② Finish[i] = false for all i
③ 반복:
i를 찾기: Finish[i] == false AND Need[i] ≤ Work
찾으면:
Work = Work + Allocation[i] // 자원 반납 받음
Finish[i] = true
못 찾으면: 종료
④ Finish[i] == true for all i → 안전 상태
그렇지 않으면 → 불안전 상태
자원 요청 알고리즘 (Resource-Request Algorithm)
프로세스 Pi가 Request[i] 요청 시:
① Request[i] ≤ Need[i]?
아니면 → 오류 (최대 요구 초과)
② Request[i] ≤ Available?
아니면 → Pi를 대기 상태로 (자원 부족)
③ 가정적 할당:
Available = Available - Request[i]
Allocation[i] = Allocation[i] + Request[i]
Need[i] = Need[i] - Request[i]
④ 안전 상태인가?
안전 → 실제로 자원 할당 완료
불안전 → 가상 할당 취소, Pi를 대기 상태로
안전 순서 탐색 과정 시각화
┌──────────────────────────────────────────────────────────────┐
│ 안전 순서 탐색 단계별 상세 예시 │
├──────────────────────────────────────────────────────────────┤
│ │
│ 초기: Work=[3,3,2], Finish=[F,F,F,F,F] │
│ │
│ 단계1: Need[1]=[1,2,2] ≤ Work=[3,3,2] → P1 완료! │
│ Work = [3,3,2] + [2,0,0] = [5,3,2] │
│ Finish = [F,T,F,F,F] │
│ │
│ 단계2: Need[3]=[0,1,1] ≤ Work=[5,3,2] → P3 완료! │
│ Work = [5,3,2] + [2,1,1] = [7,4,3] │
│ Finish = [F,T,F,T,F] │
│ │
│ 단계3: Need[4]=[4,3,1] ≤ Work=[7,4,3] → P4 완료! │
│ Work = [7,4,3] + [0,0,2] = [7,4,5] │
│ Finish = [F,T,F,T,T] │
│ │
│ 단계4: Need[2]=[6,0,0] ≤ Work=[7,4,5] → P2 완료! │
│ Work = [7,4,5] + [3,0,2] = [10,4,7] │
│ Finish = [F,T,T,T,T] │
│ │
│ 단계5: Need[0]=[7,4,3] ≤ Work=[10,4,7] → P0 완료! │
│ Finish = [T,T,T,T,T] → 안전 순서: P1,P3,P4,P2,P0 │
│ │
│ ✅ 결론: 안전 상태 │
└──────────────────────────────────────────────────────────────┘
[다이어그램 해설] 안전 순서 탐색은 욕심쟁이(Greedy) 방식으로 현재 가용 자원(Work)으로 완료 가능한 프로세스를 찾아 완료시키고 자원을 누적해가는 시뮬레이션이다. 시뮬레이션이 완전히 성공하면(Finish 모두 true) 시스템이 안전 상태다. 자원 요청 알고리즘은 먼저 가상으로 할당한 뒤 이 안전 상태 시뮬레이션을 돌려본다 — 성공하면 실제 할당하고, 실패하면 취소한다.
📢 섹션 요약 비유: 안전 순서 탐색은 퍼즐 게임처럼 "어떤 순서로 빠져나오면 모두 탈출할 수 있는가"를 미리 풀어보는 것 — 성공하면 진행, 실패하면 그 조각은 넣지 않습니다.
Ⅲ. 융합 비교 및 다각도 분석
은행원 알고리즘의 한계
┌──────────────────────────────────────────────────────────────┐
│ 은행원 알고리즘 한계 및 실무 대안 │
├──────────────────────────────────────────────────────────────┤
│ │
│ 한계 1: 사전에 Max 정보가 필요 │
│ → 실제 OS에서 프로세스의 최대 자원 요구 예측 불가 │
│ │
│ 한계 2: 프로세스 수와 자원 수가 고정 │
│ → 동적 생성/종료, 자원 추가 시 재계산 필요 │
│ │
│ 한계 3: O(n²×m) 시간 복잡도 │
│ → 수천 프로세스 환경에서 실시간 검사 비현실적 │
│ │
│ 실무 대안: │
│ ① 교착 예방 (Lock Ordering): 순환 대기 원천 차단 │
│ ② 타임아웃: 락 대기 시간 제한 후 롤백 │
│ ③ 데이터베이스: 탐지 후 희생자 롤백 │
└──────────────────────────────────────────────────────────────┘
[비교 해설] 은행원 알고리즘은 이론적으로 완벽하지만 실무에서 전면 채택은 거의 없다. 대부분의 일반 목적 OS는 Ostrich 알고리즘(무시)을 채택하는 반면, 데이터베이스는 탐지+복구를, 실시간 OS는 예방(PCP)을 채택한다. 은행원 알고리즘은 자원 수와 프로세스 수가 제한적이고 사전 정보를 알 수 있는 임베디드·실시간 환경에서 실용적이다.
📢 섹션 요약 비유: 은행원 알고리즘은 완벽한 이론 — 하지만 실제 은행은 대규모 고객에게 실시간 심사를 해주기 어렵듯이, 대규모 OS에서는 현실적 한계가 있습니다.
Ⅳ. 실무 적용 및 기술사적 판단
실무 시나리오
- 클라우드 자원 할당자: Kubernetes Admission Controller가 Pod 배치 전 노드 자원 여유분(Available) 대비 요청량을 확인하는 것은 은행원 알고리즘의 간소화 버전.
- 항공 예약 시스템: 좌석 배정 전 "이 예약을 처리해도 다른 예약 의무를 이행할 수 있는가"를 확인하는 것이 은행원 알고리즘 논리.
안티패턴
- Max 과소 설정: 프로세스가 실제로 필요한 것보다 Max를 적게 신고하면 안전 상태 판단이 잘못되어 교착 상태 발생 가능.
- N·M 크기 간과: 큰 시스템에서 O(n²m)의 반복 실행 시 스케줄러 레이턴시가 급증.
📢 섹션 요약 비유: 은행원 알고리즘의 Max 신고 오류는 대출 신청서에 잘못된 소득을 기재하는 것 — 시스템이 잘못된 판단을 내려 결국 파산(교착)에 이를 수 있습니다.
Ⅴ. 기대효과 및 결론
| 구분 | 교착 예방 | 은행원 알고리즘(회피) | 교착 탐지+복구 |
|---|---|---|---|
| 자원 이용률 | 낮음 | 중간 | 높음 |
| 교착 보장 | 100% | 100% | 탐지 주기 내 |
| 구현 복잡도 | 낮음 | 높음 | 중간 |
| 사전 정보 | 불필요 | Max 필요 | 불필요 |
📢 섹션 요약 비유: 은행원 알고리즘은 자원 관리의 완벽한 보험 상품 — 가격(오버헤드)이 비싸고 가입 조건(Max 사전 정보)이 까다롭지만, 보장(교착 방지)은 완벽합니다.
📌 관련 개념 맵
| 개념 | 관계 |
|---|---|
| 안전 상태 (Safe State) | 은행원 알고리즘이 유지하는 목표 상태 |
| 자원 할당 그래프 | 단일 인스턴스 환경의 단순화 시각화 도구 |
| Need 행렬 | 알고리즘의 핵심 입력: Max - Allocation |
| Work 벡터 | 안전 순서 탐색 중 누적 가용 자원 |
| Kubernetes ResourceQuota | 은행원 알고리즘 논리의 클라우드 구현 |
👶 어린이를 위한 3줄 비유 설명
- 선생님이 학생들에게 색종이를 나눠줄 때 "지금 이 학생에게 3장 줘도, 다른 모든 학생 프로젝트를 도울 수 있는가?"를 먼저 계산해요.
- 계산해서 "가능해요!"(안전 순서 존재) 나오면 줘요. 불가능하면 기다려 달라고 해요.
- 이것이 은행원 알고리즘 — 자원을 욕심껏 주는 게 아니라, 모두가 행복한 순서를 찾은 뒤에만 나눠줍니다!