은행원 알고리즘 자료구조 (Banker's Algorithm Data Structures)

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

본질: 에츠허르 다익스트라(Dijkstra)의 은행원 알고리즘이 데드락 회피 시뮬레이션을 돌리기 위해 실시간 메모리에 유지해야 하는 **4대 장부(Matrix)**인 Available(남은 자원), Max(최대 필요량), Allocation(현재 빌려준 양), Need(앞으로 빌려줄 양)를 의미한다.

가치: 이 네 가지 행렬의 산술 방정식인 **"Need = Max - Allocation"**과 "Need <= Available 이면 졸업 가능" 규칙만을 이용해, 그 복잡한 다중 인스턴스의 얽히고설킨 사이클(Unsafe) 확률을 오로지 숫자 매트릭스 뺄셈 몇 번으로 완벽히 증명해 내는 데이터 모델의 극치를 보여준다.

융합: 비록 순수 OS 커널 단위에선 사장되었으나, AWS나 쿠버네티스 같은 거대 클라우드 스케줄러가 노드(Node)의 자원 용량을 파드(Pod)의 Requests/Limits 선언값과 매칭시켜 빈 패킹(Bin-packing) 가용성을 점검할 때 이와 유사한 다차원 행렬 자료구조가 핵심 코어로 계승되어 사용된다.

Ⅰ. 개요 및 필요성

자원 할당 그래프(RAG)의 선 긋기 장난은 단일 인스턴스(프린터 1대)에서는 직관적이었지만, 프린터가 3대, 스캐너가 2대, CPU가 4코어인 '다중 환경'에서는 선이 엉켜 아예 시각적 증명이 불가능해진다.

이를 타파하기 위해 은행원(OS)은 복잡도를 가라앉힐 '정리된 회계 장부 4종 세트'를 만들었다. 이 장부만 있으면 지금 은행 금고에 돈이 얼마나 남았는지, 저 고객은 앞으로 얼마나 더 내놓으라 진상 부릴지(Max), 그 둘을 빼본 뒤에 지금 승인을 내릴지 기각할지를 아주 차가운 숫자로 결단할 수 있다.

💡 비유: 복잡하게 얽힌 빚쟁이 3명의 채무관계를 선 긋기로 증명하다 화가 난 회계사. 그냥 엑셀을 켜서 딱 4개의 열(Column)만 만들었다. [현재 회사 남은 현금], [A가 쓰기로 한 총예산], [A한테 지금까지 입금해 준 액수], [A한테 앞으로 더 줘야 할 남은 액수]. 이 4줄만 있으면 오늘 A한테 잔금을 치렀을 때 회사가 부도날지 안 날지 1초 만에 더하기 빼기로 증명 쌉가능!

┌───────────────────────────────────────────────────────────────┐
│         은행원 장부의 4대 자료구조 (N=프로세스, M=자원)       │
├───────────────────────────────────────────────────────────────┤
│                                                               │
│  1. Available (1 x M 벡터) : 은행 금고의 남은 시재 현황       │
│     - Available[A] = 3 (자원 A가 3개 남아있음)                │
│                                                               │
│  2. Max (N x M 행렬) : 프로세스의 '최대 대출 한도' 선언       │
│     - P1이 "나 평생 A 5개, B 3개 쓸래"라고 약정함.            │
│                                                               │
│  3. Allocation (N x M 행렬) : 현재까지 '진짜 빌려준' 수량     │
│     - P1 손에 지금 A 2개, B 1개가 쥐어져 있음.                │
│                                                               │
│  4. Need (N x M 행렬) : 'Max - Allocation' (잔여 미수금)      │
│     - P1의 Need = [5, 3] - [2, 1] = [3, 2]                    │
│     - (의미) P1을 졸업시키려면 앞으로 A 3개, B 2개가 더 필요! │
│                                                               │
│  ▶ 대원칙: Need 배열이 현재 Available 금고 상황보다 작거나    │
│             같아야만 그 스레드를 구제(졸업)시킬 수 있다.      │
└───────────────────────────────────────────────────────────────┘

📢 섹션 요약 비유: 이 4가지 장부만 있으면 복잡한 심리전 할 필요 없이 숫자로 증명됩니다. "내 호주머니(Available)에 3천 원 남았고, 쟤가 앞으로 뜯어낼 돈(Need)이 2천 원이면, 줘버리고 졸업시켜 쟤가 들고 있던 1만 원(Allocation)을 다 회수해 버리자!" 식의 회계 놀음입니다.

Ⅱ. 아키텍처 및 핵심 원리

Need 매트릭스의 '변동성' 장악

은행원 알고리즘 연산의 심장은 Need 행렬이다. 만약 P가 자원 요청 시, OS는 바로 자원을 줘버리지 않고 다음과 같은 **임시 결산(Virtual Trial)**을 한다.

승인 가정 (Trial Update): P에게 자원을 줬다고 가정하고 장부를 임시로 조작한다. Available = Available - 요청량 Allocation = Allocation + 요청량 Need = Need - 요청량
시뮬레이션 (Safety Check): 바뀐 장부 상태에서, 나머지 애들의 Need를 Available로 순차적으로 틀어막아 모두 졸업(Safe State)시킬 수 있는지 루프를 돌린다.
복원 (Rollback): 만약 졸업을 못 시키는 파산(Unsafe)이 뜨면, 장부를 원래 수치로 롤백하고(가상 임시 장부 폐기) P를 매몰차게 Block(대기) 시켜버린다.

📢 섹션 요약 비유: 은행원이 실제 돈을 넘기기 전, 메모장에서 연필로 슥슥 지우고 숫자를 올려본 뒤(가상 승인), 끝까지 장부가 흑자로 굴러가면 그제야 연필을 지우고 펜으로 확정 잉크(실 할당)를 칠하는 겁니다.

Ⅲ. 융합 비교 및 다각도 분석

자료구조	상태 범위	갱신 주체 (Update)	한계 부작용 (부하/오버헤드)
`Available`	전체 공유 자원량	OS (할당/반납 시)	공유 변수라 동시성 Lock 잡아야 함
`Max`	스레드 단위 최대 선언	사용자 코드(초기 고정)	동적/가변 스레드 환경에서 불명확 추산의 원흉
`Allocation`	스레드 단위 현재 보유	OS (할당 승인 시)	트래킹 비용 및 메모리 차지
`Need`	스레드 단위 잔여 필요치	수학 연산 (Max - Alloc)	매 요청 시마다 연산 후 Safety 비교(O(N)) 소요

📢 섹션 요약 비유: 이 엑셀 장부를 실시간 컴퓨터에 이식하면, 프로그램 1만 개가 자원을 1초에 천 번씩 달라고 할 때마다 이 거대한 행렬을 전부 뒤져가며 빼고 더해야 하니 컴퓨터가 장부 쓰다가 탈진합니다.

Ⅳ. 실무 적용 및 기술사적 판단

실무 시나리오:

Kubernetes (K8s) Resource Quota 및 Limits: K8s 매니페스트 파일에서 requests가 바로 해당 파드가 사용할 Allocation 보증이고, limits가 바로 Max를 의미한다. 스케줄러 노드의 CPU/Memory 사이즈가 Available이다. 쿠버네티스는 은행원처럼 시뮬레이션하지는 않지만, 이 4가지 매트릭스 사상을 이어받아 "이 노드의 Available이 팟의 Needs를 커버 못하면 애초에 스케줄링(할당)을 거부(Pending)" 하는 현대식 분산 회피 모델로 승화시켰다.

안티패턴:

스레드 풀의 허위 Max 선언 (Over-provisioning 방치): "내가 앞으론 얼마나 쓸지 잘 모르겠지만, 그냥 여유 있게 프린터 100대(Max) 쓸 거라고 뻥치고 시작할래." 이렇게 보수적으로 신고해 버리면 Need 배열이 미친 듯이 커져서, OS의 Available 금고는 아무 프로세스도 졸업시킬 수 없다는 절망(Unsafe)에 빠진다. 결국 돈이 썩어 넘쳐나는데도 아무도 자원을 배급받지 못하는 거대한 락 대단원 마비(아사)가 벌어진다.

📢 섹션 요약 비유: 은행 대출 서류 쓸 때, "1천만 원만 빌려주면 무조건 졸업할게" 할 걸 쫄아서 "혹시 모르니 10억까지 빌려간다고 쓸게(Max 뻥튀기)"를 해버리면, 은행은 쫄아서 단돈 100원도 안 빌려주고 당신을 대기열에 박아 버립니다.

Ⅴ. 기대효과 및 결론

기준	장부(Matrix)가 없는 원시 OS	4대 장부를 탑재한 Banker OS
자원 얽힘 파악	그냥 터지면 패닉 롤백 (오리무중)	숫자 놀음으로 수학적 예측 명확성 확보
메모리 비용	없음 (속도 극대화)	n×m 배열 유지 및 안전 루틴 부하 극대

운영체제 전담 부서에 회계사 4명을 고용해 Available, Max, Allocation, Need 라는 치밀한 수학적 행렬 감시 장부를 도입한 다익스트라의 시도는, 다중 자원 생태계를 수학적으로 증명할 수 있는 완벽한 판을 짰다는 의의를 가진다.

비록 이 행렬의 유지 보수 코스트(O(MN^2))가 범용 컴퓨터에 감당되지 않아 폐기되었으나, **"현재 용량과 최대 한도를 비교하여 미래 할당을 미리 심판한다"**는 자료구조적 철학은 현대의 트래픽 라우팅, 클라우드 빈 패킹 스케줄러의 아키텍처에 불멸의 유산으로 자리 잡았다.

📌 관련 개념 맵

개념	관계
안전 상태 (Safe State)	이 4대 장부 연산식을 끝까지 가상 시뮬레이션 돌려 전원 구제 성공이 증명된 최종 목표 상태
은행원 알고리즘의 한계	`Max` 배열을 초반에 신고하게 만든 강제 규정이 역설적으로 알고리즘 전체를 붕괴시킨 가장 큰 단점
Bin Packing (빈 패킹)	짐(Need)과 박스(Available)의 크기를 맞춰 빈틈없이 채워 넣는 현대 클라우드의 확장 기술

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

은행장(OS)은 데드락을 막으려 커다란 엑셀 장부를 펼쳐 놓고 딱 4가지 열만 만들었어요.
"우리 금고 남은 돈(Available)", "네가 평생 꿔갈 빚 한도(Max)", "지금까지 빌려간 돈(Allocation)", "앞으로 빌려줄 남은 빚(Need)".
누가 돈 빌려달라고 할 때마다 남은 금고(Available)에서 남은 빚(Need)을 까 보고, "아 이 정도면 얘한테 줘서 무사히 과자 사 먹게 졸업시킬 수 있겠네!" 할 때만 허락 버튼을 누른답니다!