은행원 알고리즘의 4대 자료구조 (Max, Allocation, Need, Available)

핵심 인사이트 (3줄 요약)

본질: 은행원 알고리즘이 데드락 회피 시뮬레이션을 돌리기 위해 운영체제 메모리 내부에 실시간으로 유지하는 4가지 핵심 행렬(Matrix) 및 벡터(Vector) 데이터 구조다.

가치: Available(가용량)과 Need(추가 필요량)를 비교하여 시스템이 안전 상태(Safe State)인지 판별하는 수리적 근간이 되며, 이 4개의 엑셀 표(장부)가 있어야만 다중 인스턴스(Multi-instance) 환경에서 교착 상태를 완벽히 예측할 수 있다.

융합: 각 프로세스가 태어날 때 신고하는 Max 값에서, 현재 빌려간 Allocation 값을 빼면 앞으로 더 필요한 Need 값이 도출되는 유기적인 연동 구조를 가지며, 이 장부들은 자원이 할당/반납될 때마다 실시간으로 갱신(Update)되어야 한다.

Ⅰ. 개요 및 필요성 (Context & Necessity)

개념: 에츠허르 데이크스트라의 은행원 알고리즘(Banker's Algorithm)이 시스템의 안전성을 검증하기 위해 사용하는 4가지 필수 변수 그룹이다. (프로세스 수를 $n$, 자원 종류의 수를 $m$이라 한다.)
필요성: 은행에서 대출을 내어주려면 "은행 금고에 돈이 얼마 남았나?(Available)", "저 고객은 예전에 얼마를 빌려갔나?(Allocation)", "앞으로 얼마나 더 빌릴 한도가 남았나?(Need)"를 보여주는 회계 장부가 필수적이다. OS 역시 자원(CPU, 메모리, 프린터)을 떼먹히지(데드락) 않기 위해 이 장부를 커널 레벨에서 1비트의 오차도 없이 관리해야 했다.
💡 비유: 가계부를 쓸 때 **'1. 내 통장 잔고(Available)', '2. 친구별 총 빌려주기로 한 약속 금액(Max)', '3. 지금까지 실제로 빌려준 돈(Allocation)', '4. 앞으로 더 빌려달라고 할 수 있는 남은 금액(Need)'**을 엑셀로 정리해 두는 것과 완벽히 일치한다.
등장 배경: 자원이 1개뿐이라면 그래프(RAG) 선 긋기로 데드락을 찾을 수 있지만, A자원 10개, B자원 5개, C자원 7개처럼 다중 인스턴스 환경이 되자 기하학적 그래프로는 한계에 부딪혔다. 이를 선형 대수학의 행렬(Matrix) 구조로 변환하여 수리적 시뮬레이션을 가능케 하기 위해 고안되었다.

  [은행원 알고리즘 4대 자료구조의 유기적 관계도]

  [ 1. Available (가용 벡터) ]
    - 현재 시스템에 남아있는 '대출 가능한' 잉여 자원들
    - 크기: 길이 m 짜리 1차원 배열 (예: A자원 3개, B자원 2개 남음)

  [ 2. Max (최대 요구 행렬) ]
    - 프로세스가 평생 쓸 자원의 한도액 (초기 계약금)
    - 크기: n x m 2차원 배열 (예: P1은 A를 5개, B를 3개 쓸 거임)

  [ 3. Allocation (할당 행렬) ]
    - 현재 프로세스가 이미 쥐고 있는 자원
    - 크기: n x m 2차원 배열 (예: P1이 A를 2개, B를 1개 쥐고 있음)

  [ 4. Need (추가 요구 행렬) ] ⭐ 가장 중요!
    - 앞으로 프로세스가 더 요구할 수 있는 잠재적 빚
    - 공식: Need[i][j] = Max[i][j] - Allocation[i][j]
    - (예: P1은 A를 3개(5-2), B를 2개(3-1) 더 요구할 수 있음)

[다이어그램 해설] 이 4개의 장부는 철저하게 연동되어 있다. 누군가 자원을 새로 받아 가면(Allocation 증가), 그 즉시 금고 잔고(Available)는 깎이고, 앞으로 더 요구할 양(Need)도 깎인다. 이 3단 콤보 갱신이 원자적으로(Atomic) 이루어지는 것이 회피 알고리즘의 대전제다.

📢 섹션 요약 비유: 마이너스 통장(Max)을 1,000만 원 뚫어놓고, 현재 400만 원을 빼서 쓰고 있습니다(Allocation). 그럼 은행은 "아 저 고객이 언제든 600만 원(Need)을 더 빼갈 수 있겠구나"라고 인지하고, 은행 전체의 현금 보유량(Available)이 600만 원 밑으로 떨어지지 않게 방어해야 부도를 막을 수 있습니다.

Ⅱ. 아키텍처 및 핵심 원리 (Deep Dive)

4대 자료구조의 수학적 정의 및 크기(Size)

$n$ = 프로세스의 수 (예: P0, P1, P2 ... 3명) $m$ = 자원의 종류 수 (예: CPU, 프린터, 디스크 ... 3종류)

1. Available (가용 자원 벡터)

타입: int Available[m] (1차원 배열)
의미: 각 자원 타입별로 현재 할당 가능한 인스턴스(개수)의 수.
예시: Available[0] = 3 이면, 0번 자원(CPU)이 현재 3개 남아있다는 뜻이다.

2. Max (최대 자원 요구 행렬)

타입: int Max[n][m] (2차원 행렬)
의미: 각 프로세스 $i$가 자원 $j$를 평생 동안 최대 몇 개까지 요구할 것인지 나타낸다.
특징: 이 값은 프로세스가 시작할 때(Creation) 무조건 시스템에 제출해야 하며, 런타임에 이 값을 초과하여 요구하면 즉시 에러(Abortion)가 난다.

3. Allocation (할당 행렬)

타입: int Allocation[n][m] (2차원 행렬)
의미: 각 프로세스 $i$가 현재 쥐고 있는 자원 $j$의 개수.
성질: $\sum Allocation[i][j] + Available[j] = \text{시스템의 총 자원 } j\text{의 개수}$ (질량 보존의 법칙)

4. Need (추가 요구 행렬)

타입: int Need[n][m] (2차원 행렬)
의미: 프로세스 $i$가 작업을 끝내기 위해 미래에 추가로 요구할 수 있는 자원 $j$의 개수.
핵심 공식: Need[i][j] = Max[i][j] - Allocation[i][j]

  ┌────────────────────────────────────────────────────────────────────────┐
  │         자원 할당 및 반환 시 4대 자료구조의 동기화 업데이트 연산       │
  ├────────────────────────────────────────────────────────────────────────┤
  │                                                                        │
  │   [ 시나리오: 프로세스 P(i)가 자원(Request)을 추가로 요청함 ]          │
  │                                                                        │
  │   1. 할당(대출) 승인 시 OS 커널 내부 업데이트 로직:                    │
  │      Available = Available - Request;                                  │
  │      Allocation[i] = Allocation[i] + Request;                          │
  │      Need[i] = Need[i] - Request;                                      │
  │      (※ Max 행렬은 변하지 않음. 불변의 계약서임)                       │
  │                                                                        │
  │   2. 프로세스 P(i) 종료 후 자원 반납(상환) 시 로직:                    │
  │      Available = Available + Allocation[i];                            │
  │      Allocation[i] = 0;                                                │
  │      Need[i] = 0;                                                      │
  │                                                                        │
  │   ✅ 결론: Available(금고)이 줄어들었다 늘어나는 완벽한 복식부기 회계! │
  └────────────────────────────────────────────────────────────────────────┘

📢 섹션 요약 비유: 이 4개의 구조체는 기업의 '대차대조표'입니다. 돈이 나가고 들어올 때마다 자산(Available), 부채(Allocation), 자본(Need)이 톱니바퀴처럼 한 번에 맞물려 돌아가야 장부에 빵꾸가 나지 않습니다.

Ⅲ. 융합 비교 및 다각도 분석 (Comparison & Synergy)

안전 상태 검사 (Safety Algorithm)의 핵심: Need vs Available

은행원 알고리즘이 "안전하다(Safe State)"고 판별하는 1순위 조건은 무조건 이것이다.

모든 자원에 대해 Need[i] <= Available 인 프로세스를 찾아라!

상황 (Need와 Available의 대결)	해석 및 조치
`Need <= Available`	"지금 은행 잔고로 쟤가 땡깡 부리는(Max) 걸 다 막을 수 있네!" ─▶ 합격. 얘를 살려주면 나중에 갖고 있던 돈(Allocation)까지 뱉어내므로 잔고가 더 풍족해짐.
`Need > Available`	"은행 잔고가 부족해서 쟤가 돈 내놓으라 하면 파산이네!" ─▶ 불합격. 얘는 일단 제쳐두고, 잔고가 적어도 살릴 수 있는 다른 만만한 놈부터 찾아야 함.

만약 1,000명의 고객(N)이 있는데 단 한 명도 Need <= Available을 만족하지 못한다면? 그 순간 시스템은 **불안전 상태(Unsafe State)**로 확정되며, 아까 시뮬레이션용으로 빌려줬던 자원을 취소(Rollback)하고 대출을 거절하게 된다.

자료구조의 공간 복잡도 오버헤드

자원 종류(M)가 10개, 프로세스(N)가 1,000개일 때:

Max: 1,000 x 10 = 10,000개의 int (40KB)
Allocation: 10,000개의 int (40KB)
Need: 10,000개의 int (40KB)
메모리 용량 자체는 120KB 수준으로 깃털처럼 가볍다. 하지만 이 $1,000 \times 10$ 행렬을 락(Lock)을 요청할 때마다 이중 for문($O(N^2 \times M)$)으로 덧셈 뺄셈하며 스캔해야 하는 CPU 연산 오버헤드가 범용 OS를 미치게 만든다.
📢 섹션 요약 비유: 데이터 저장 공간(행렬 메모리)은 엑셀 파일 1개 용량이라 문제 될 게 없습니다. 하지만 락을 달라고 할 때마다 OS가 "잠깐만!" 하고 엑셀을 켜서 함수를 수백만 번 갱신하고 검증하는 시간(CPU 오버헤드)이 너무 오래 걸려서 뒤에 줄 선 사람들이 화병이 나는 것입니다.

Ⅳ. 실무 적용 및 기술사적 판단 (Strategy & Decision)

실무 시나리오

은행원 알고리즘 행렬의 K8s 클라우드 매핑: 이 4대 자료구조는 단일 OS 스케줄러에서는 버려졌지만, 놀랍게도 현대 클라우드 오케스트레이션(Kubernetes)의 핵심 철학에 100% 매핑되어 그대로 살아남았다.
- Max[i] = K8s 파드(Pod)의 Resources.Limits (나 이거 넘게 쓰면 OOM 킬러로 날 죽여도 좋다는 계약서)
- Allocation[i] = K8s 파드(Pod)의 Resources.Requests (내가 최소한 무조건 점유하고 시작해야 하는 고정 자원)
- Available = K8s 노드(Node)의 Allocatable 자원 (전체 자원에서 시스템 데몬 몫을 뺀 잉여 자원)
- 아키텍트 설계: K8s 스케줄러(Kube-scheduler)는 새 파드가 뜰 때 Requests(Alloc) 값이 Available을 초과하는지 필터링(Filtering)하여 배치를 거부한다. 이것이 바로 데이크스트라의 4대 자료구조를 분산 환경에 적용한 현대판 클라우드 회피 알고리즘이다.
사전 지식(A Priori Knowledge)의 불가능성과 한계: 왜 일반 자바/C++ 애플리케이션 개발자는 이 4대 장부를 쓰지 않을까?
- 원인: Max 행렬 때문이다. 어떤 스레드가 new Object()를 몇 번 할지, 커넥션을 몇 개 맺을지 코드를 짜는 개발자 본인조차 알 수 없다. 트래픽에 따라 동적으로 변하기 때문이다.
- 실무 결단: 애초에 Max를 모르니 Need를 계산할 수 없고, 알고리즘 자체가 시작도 못 한다. 따라서 개발자는 이 완벽한 예방 공식을 포기하고, tryLock 타임아웃이나 Circuit Breaker(서킷 브레이커) 같은 런타임 방어막(Reactive)에 의존하는 아키텍처를 짤 수밖에 없다.

  ┌──────────────────────────────────────────────────────────────────┐
  │     K8s 스케줄링에서 4대 자료구조를 활용한 파드(Pod) 배치 결정   │
  ├──────────────────────────────────────────────────────────────────┤
  │                                                                  │
  │   [ 워커 노드 1의 잔고 (Available) = CPU 4코어, Mem 8GB ]        │
  │                                                                  │
  │   [ 1. 신규 파드 A 배포 요청 ]                                   │
  │     ▶ Request(Alloc) = CPU 2, Mem 4G                             │
  │     ▶ Limit(Max) = CPU 4, Mem 8G                                 │
  │     ▶ 검증: Alloc(2,4) <= Available(4,8) 이므로 ✅ 배포 승인!    │
  │     ▶ 갱신 후 Available = CPU 2, Mem 4G 남음.                    │
  │                                                                  │
  │   [ 2. 신규 파드 B 배포 요청 ]                                   │
  │     ▶ Request(Alloc) = CPU 3, Mem 2G                             │
  │     ▶ Limit(Max) = CPU 3, Mem 4G                                 │
  │     ▶ 검증: Alloc의 CPU(3) > Available의 CPU(2) 🚨 초과!         │
  │     ▶ 결론: 배포 거부 (Pending 상태 돌입). 다른 노드 탐색.       │
  └──────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 클라우드 엔지니어가 밥 먹듯이 짜는 YAML 파일의 Request와 Limit가 바로 은행원 알고리즘의 Allocation과 Max 행렬의 클라우드 버전이다. 이 수치를 대충 "에라 모르겠다" 하고 빼놓고 배포하면 스케줄러가 장부(행렬)를 못 써서 데드락(Node OOM)이 터져버리므로, 이 값을 정교하게 산정하는 것이 데브옵스(DevOps)의 핵심 역량이다.

📢 섹션 요약 비유: 은행원 알고리즘의 장부는 완벽하지만 "미래에 돈을 얼마나 쓸지 완벽한 사업계획서(Max)를 가져와라"고 요구합니다. 스타트업(일반 프로그램)은 미래를 몰라서 이 대출을 못 받습니다. 하지만 이미 규모가 확정된 대기업 부서(K8s 컨테이너)는 예산안(Limit)을 정확히 가져올 수 있으므로 이 장부 시스템이 완벽하게 들어맞습니다.

Ⅴ. 기대효과 및 결론 (Future & Standard)

기대효과

이 4가지 자료구조를 시스템 자원 관리 테이블로 채택하면, 어떠한 다중 자원 경합 상태에서도 시스템이 안전 지대(Safe State)를 이탈하려 할 때 100%의 확률로 미리 브레이크를 걸어 운영체제 레벨의 교착 상태(Deadlock)를 영구적으로 회피할 수 있다.

결론 및 미래 전망

Max, Allocation, Need, Available 이 4개의 엑셀 표는 컴퓨터 과학 역사상 "시스템의 자원 상태를 가장 수학적으로 우아하게 추상화한 모델"이다. 비록 단일 코어 OS에서는 미래 예측 불가능성(Max) 때문에 사장되었지만, 이 개념은 죽지 않고 **클러스터 자원 스케줄링(Mesos, YARN, K8s)**으로 웅장하게 부활했다. 미래의 분산 시스템에서는 사용자가 Max 값을 수동으로 하드코딩하지 않고, AI 머신러닝 모듈이 과거의 트래픽 패턴을 분석하여 프로세스의 Max와 Need 행렬을 실시간으로 자동 예측 및 동적 갱신(Auto-prediction)해주는 AI 기반 스마트 회피 시스템으로 진화하여 은행원 알고리즘의 태생적 한계를 완벽히 부숴버릴 것이다.

📢 섹션 요약 비유: 이 4개의 장부는 1965년에 만들어진 낡은 가계부지만, 그 "자산과 부채의 논리적 뼈대"가 너무나 완벽하여 60년이 지난 지금도 클라우드라는 거대한 글로벌 은행의 회계 시스템 근간을 그대로 지탱하고 있는 위대한 발명품입니다.

📌 관련 개념 맵 (Knowledge Graph)

개념 명칭	관계 및 시너지 설명
은행원 알고리즘 (Banker's)	이 4개의 자료구조를 덧셈 뺄셈하며 $O(N^2)$ 번 뺑뺑이 돌려 안전 상태를 찾는 깐깐한 심사역이다.
안전 상태 (Safe State)	`Need <= Available` 조건을 만족하는 놈들을 찾아서 징검다리를 끝까지 건너면 도달하는 데드락 0%의 천국이다.
교착 상태 회피 (Avoidance)	이 자료구조들을 유지/관리하면서 자원 할당을 기각(Deny)하여 데드락을 요리조리 피해 가는 정책이다.
자원 할당 그래프 (RAG)	다중 인스턴스를 위해 4대 장부를 쓰는 은행원과 달리, 자원이 딱 1개일 땐 복잡한 장부 없이 그림(RAG)으로 퉁치는 가벼운 도구다.
쿠버네티스 Requests/Limits	OS 커널에서 쫓겨난 `Allocation`과 `Max` 행렬이 클라우드 시대에 이름만 바꿔서 완벽히 부활한 현대적 매핑 모델이다.

👶 어린이를 위한 3줄 비유 설명

은행원 아저씨가 데드락(파산)을 막으려면 4개의 비밀 장부가 필요해요.
첫 번째는 "은행 금고에 남은 돈(Available)", 두 번째는 "손님이 평생 최대로 빌릴 돈(Max)", 세 번째는 "지금 당장 빌려준 돈(Allocation)"이에요.
가장 중요한 마지막 장부는 바로 **"앞으로 더 빌려줘야 할 돈(Need)"**이에요! 이걸 알아야 은행 금고에 남은 돈으로 막을 수 있을지 없을지 계산할 수 있답니다!