프레임 할당 (Frame Allocation) 알고리즘

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

1. 본질: 프레임 할당(Frame Allocation)은 다중 프로그래밍 환경에서 한정된 물리 메모리(Free Frames)라는 파이를 시스템에 띄워진 여러 프로세스들에게 '몇 개씩 쪼개어 나눠줄 것인가'를 결정하는 운영체제의 거시적 자원 분배 전략이다.
2. 가치: 특정 프로세스에 프레임을 너무 적게 주면 매 클럭마다 페이지 폴트를 뿜어내는 스래싱(Thrashing)에 빠져 죽고, 너무 많이 주면 다른 프로세스가 굶어 죽으므로(Starvation), 전체 시스템의 동시 실행 효율(Degree of Multiprogramming)과 성능을 극대화할 황금 밸런스를 맞춘다.
3. 융합: 이 할당량의 크기는 균등(Equal)/비례(Proportional) 할당이라는 정적 규칙에서 출발하여, 프로세스의 활동량(Page Fault Frequency)에 따라 프레임을 뺏고 더해주는 동적 워킹 셋(Working Set) 개념과 융합되어 현대 OS의 적응형 스케줄링으로 진화했다.

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

• 개념: 물리 램(RAM)이 16GB(400만 개의 프레임)가 있다고 치자. OS가 1GB를 먹고 남은 15GB를 크롬, 워드, 롤(LoL) 세 프로세스가 나눠 써야 한다. "도대체 누구에게 램을 얼마나 할당해 줘야 할까?"라는 철학적 분배의 문제다. 페이지 교체(Replacement)가 '빈방 없을 때 누구를 죽일까?'라는 국지전이라면, 프레임 할당은 '애초에 병력을 몇 명씩 파병할까?'라는 전체 전쟁의 전략(Strategy)이다.

• 필요성: 가상 메모리는 마법이 아니다. 프로그램이 정상적으로 돌아가려면 램에 최소한으로 깔려 있어야 하는 '최소 프레임 수'라는 게 존재한다. 예를 들어 CPU의 한 명령어(MOVE [A], [B])를 처리하려면 명령어 자체(1장) + 변수 A(1장) + 변수 B(1장) 등 한 번에 최소 3장의 페이지가 무조건 램에 있어야만 에러 없이 돈다. 만약 OS가 프로세스에게 램을 달랑 2장만 할당해 주면, 3장을 모을 수가 없어서 폴트가 영원히 무한 반복되는 시스템 마비 상태가 터진다. 이 파국을 막기 위한 지능적 분배 기준이 절대적으로 필요했다.

• 💡 비유: 프레임 할당은 뷔페 식당의 테이블 크기 배정과 같다. 식당 전체에 100개의 그릇(프레임)을 놓을 공간이 있다. 혼자 온 손님에게 그릇 50개 놓을 자리를 독점하게 하면 다른 손님들이 굶어 죽는다. 반대로 10명 단체 손님(무거운 프로세스)에게 그릇을 3개밖에 안 내어주면, 반찬 1개 퍼올 때마다 다 먹고 그릇을 치워야 하는 지옥의 폴트(Page Fault) 릴레이가 터져 식당이 마비된다. 손님 덩치와 먹는 속도에 맞춰 적절한 그릇 개수를 세팅해 주는 지배인의 눈치가 바로 프레임 할당 알고리즘이다.

• 등장 배경 및 분배의 딜레마:

  1. 요구 페이징의 맹점: 요구 페이징으로 필요한 것만 올리다 보니, 어떤 앱은 끝도 없이 프레임을 요구해 램을 독식해 버렸다.
  2. 최소/최대 할당의 가이드라인 필요: 명령어 구조(Architecture)가 꼬이지 않기 위한 절대적인 최소 프레임 수를 보장해야 했다.
  3. 알고리즘의 고도화: 무식하게 1/N로 나누는 균등 할당에서 시작해, 덩치에 비례해서 주는 비례 할당을 거쳐, 런타임에 눈치껏 조절하는 동적 할당으로 뼈대가 굳어졌다.

┌─────────────────────────────────────────────────────────────────────────┐
│        프레임 할당의 극단적 실패 사례 (스래싱 유발) 시각화              │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│ [ 상황: 10,000 프레임을 가진 무거운 그래픽 편집기 실행 ]                │
│                                                                         │
│ ▶ 1. 램을 너무 조금 할당했을 때 (예: 5 프레임만 할당)                   │
│  - 프로그램 루프가 돌 때마다 10장의 페이지를 핥고 지나가야 함.          │
│  - 근데 방이 5개뿐이라, 6번째 페이지 가져올 때 1번 쫓아냄.              │
│  - 7번째 가져올 때 2번 쫓아냄... 무한 교체 지옥 발생!                   │
│  💥 결과: Page Fault Rate가 폭발하여 시스템 완전 정지 (Thrashing)       │
│                                                                         │
│ ▶ 2. 램을 너무 많이 할당했을 때 (예: 9,000 프레임 독점)                 │
│  - 그래픽 편집기는 너무나 쾌적하고 부드럽게 돌아감.                     │
│  - 하지만 뒤에 백그라운드로 띄워둔 음악 플레이어와 백신 프로그램이      │
│    프레임을 1장도 못 받아서 노래가 끊기고 튕겨버림!                     │
│  💥 결과: 다중 프로그래밍 수준(Degree)이 바닥으로 처박힘.               │
└─────────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 할당량(Allocation Size)과 페이지 부재율(Fault Rate)은 반비례 곡선을 그린다. 프레임을 많이 주면 폴트는 줄어들어 그 앱은 날아다니지만 남들이 죽고, 프레임을 아끼면 여러 앱을 띄울 순 있지만 폴트가 터져 모두가 버벅댄다. OS는 이 곡선의 변곡점(무릎)을 귀신같이 찾아내어 딱 그만큼만 램을 끊어주는 줄타기의 장인이 되어야 한다.

• 📢 섹션 요약 비유: 부모가 용돈(프레임)을 줄 때, 첫째에게 100만 원을 주면 둘째가 굶어 죽고(다중 프로그래밍 실패), 둘 다 1만 원씩 쪼잔하게 주면 둘 다 매일 돈 달라고 전화를 해대는(페이지 폴트 폭발) 극단적 상황을 막는 지혜로운 재무 설계입니다.

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

최소 프레임 수 (Minimum Number of Frames)의 하드웨어적 강제

"아무리 적게 줘도 이것보단 많이 줘야 프로그램이 터지지 않는다"는 절대 하한선이 있다. 이는 OS가 아닌 **CPU 하드웨어의 명령어 구조(ISA)**가 결정한다.

• 인텔 x86이나 MIPS 같은 CPU는 명령어 하나를 실행할 때, 명령어 자체가 여러 페이지에 걸쳐 있거나 간접 주소 지정(Indirect Addressing)을 통해 피연산자가 여러 페이지에 흩어져 있을 수 있다.
• 예를 들어, 명령어 코드가 1번, 2번 페이지에 걸쳐 있고, 가져올 데이터가 3번 페이지에, 저장할 곳이 4번 페이지에 있다면?
• 이 명령어를 한 번 치기 위해선 무조건 최소 4장의 프레임이 물리 램에 깔려 있어야 한다. OS가 3장만 할당해 주면 4번째 장을 가져올 때 1번 장을 쫓아내게 되어, 명령어가 영원히 완성되지 못하고 제자리를 맴도는 무한 페이지 폴트 재앙이 터진다.

정적 할당(Static Allocation) 알고리즘

프로세스의 실행 전 덩치(사이즈)만 보고 미리 기계적으로 파이를 나눠주는 고전적인 2가지 방식이다.

1. 균등 할당 (Equal Allocation)
   • 가용 프레임이 100개고 프로세스가 5개면, 묻지도 따지지도 않고 공산주의처럼 20개씩 칼같이 나눠준다.
   • 문제점: 10KB짜리 계산기 앱은 20개를 받아 15개를 버리고(낭비), 10GB짜리 오라클 DB도 20개를 받아 숨이 막혀 죽어버리는 최악의 비효율을 낳는다.
2. 비례 할당 (Proportional Allocation)
   • 자본주의 방식. 프로세스의 총 가상 메모리 크기에 비례하여 프레임을 준다.
   • 10GB짜리 앱에는 90프레임을, 10KB짜리 앱에는 1프레임을 준다.
   • 문제점: 10GB짜리 앱이라도 막상 켜놓고 가만히 숨만 쉬고 있으면(예: 최소화된 브라우저 창), 이 녀석에게 90프레임을 묶어두는 것 자체가 거대한 램 낭비다. (런타임의 동적 활동량을 반영하지 못함).

• 📢 섹션 요약 비유: 균등 할당은 몸무게 100kg 씨름선수와 10살 꼬마에게 똑같이 밥 한 공기씩 주는 바보 같은 배식이고, 비례 할당은 덩치가 크면 무조건 밥을 5공기 퍼주는 방식입니다. 하지만 덩치가 커도 지금 다이어트 중이거나 잠자고 있다면(동적 비활성), 그 5공기는 그대로 썩어버리는 치명적 한계가 있습니다.

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

우선순위 할당 (Priority Allocation)

크기(Size)가 아닌 프로세스의 '중요도(Priority)'에 따라 프레임을 몰아주는 기법이다.

• 비례 할당의 공식을 살짝 비틀어, 크기 대신 프로세스의 우선순위 수치로 배율을 정한다.
• 램이 모자라서 페이지 폴트가 터졌을 때, 1순위 VIP 커널 프로세스는 자기가 가진 걸 안 버리고, 우선순위가 가장 낮은 꼴찌 프로세스의 프레임을 뺏어서(강제 수용) 자기 방에 채워버린다.
• 모바일 OS(Android, iOS)에서 내가 지금 보고 있는 전면(Foreground) 앱이 날아다니고, 뒤에 숨겨둔 백그라운드(Background) 앱들이 프레임을 다 뺏기고 멈춰버리는 현상의 코어 로직이다.

전역 교체 vs 지역 교체의 배분 철학

할당(Allocation)과 교체(Replacement)는 동전의 양면이다.

┌──────────┬────────────┬────────────┬──────────────────────────────┐
│ 램 쟁탈전  │ 승자 프로세스 │ 패자 프로세스 │ 전체 시스템 스루풋   │
├──────────┼────────────┼────────────┼──────────────────────────────┤
│ 전역 교체  │ 램 쫙 빨아먹음│ 쫓겨나서 버벅댐│ 🚀 램 낭비 없이 최고│
│ 지역 교체  │ 자기 방만 씀  │ 피해 안 받음  │ 🐢 남는 램 썩음      │
└──────────┴────────────┴────────────┴──────────────────────────────┘

[매트릭스 해설] 리눅스는 지독한 능력주의(전역 교체)를 택했다. 열심히 일하는 놈이 폴트를 쳐서 램을 요구하면, 가만히 쉬고 있는 남의 프레임을 가차 없이 빼앗아 일하는 놈에게 퍼준다. 이로 인해 프로세스별 할당량은 매초마다 고무줄처럼 변하며, 이는 자연스럽게 다음 장에서 배울 동적 할당(Working Set) 아키텍처로 이어지게 된다.

• 📢 섹션 요약 비유: 전역 교체 시스템은 회사 책상이 부족할 때, 놀고 있는 직원의 빈 책상을 확 뺏어서 야근하는 에이스 직원에게 모니터 3개 세팅하라고 몰아주는 철저한 성과주의 환경입니다.

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

실무 시나리오: cgroups를 통한 프레임 할당량 하드 락(Hard Limit)

1. 클라우드의 위기:
   • 리눅스의 묻지마 전역 교체(능력주의)는 도커 컨테이너(Docker) 시대에 치명적 위기를 맞았다.
   • 서버 하나에 10개 회사 앱을 띄웠는데, 1번 회사 앱 메모리 누수 버그를 내며 미친 듯이 램을 요구(Page Fault)했다.
   • 전역 교체 논리에 의해 리눅스는 나머지 9개 회사의 프레임(램)을 다 뺏어서 1번 놈에게 줘버려 멀쩡한 9개 회사가 다 뻗어버리는 대참사(Noisy Neighbor)가 났다.
2. cgroups (Control Groups)의 구원:
   • 구글 엔지니어들은 이 야생의 전역 교체를 통제하기 위해, 리눅스 커널에 cgroups라는 철창을 만들었다.
   • 컨테이너마다 Memory Limit = 1GB 라는 하드웨어적 철창(지역 교체의 부활)을 씌웠다.
   • 1번 회사가 1GB를 다 채우면? 더 이상 남의 램을 못 뺏게 리눅스 커널이 OOM(Out of Memory) 킬러로 그 컨테이너 하나만 깔끔하게 암살해 버린다.
3. 실무의 결론:
   • 현대 백엔드 인프라(k8s)는 OS의 유연한 전역 할당(성능) 위에 cgroups라는 깐깐한 지역 할당 제한(보안/격리)을 강제로 덮어씌운 완벽한 하이브리드 경제 체제로 돌아가고 있다.

NUMA 노드별 할당의 한계

다중 코어 서버에서는 프레임의 '개수'만 할당해 줘선 안 된다. "어느 노드(CPU 소켓) 쪽에 붙어있는 프레임인가?"라는 물리적 위치가 속도를 좌우한다. 아무리 1000개의 프레임을 넉넉히 할당받았어도, 내 코어(Node 0)에서 저 멀리 다리를 건너야 하는 Node 1의 프레임으로만 1000개를 받았다면 성능은 반토막이 난다(리모트 페널티). 프레임 할당 알고리즘은 이제 '양'뿐만 아니라 '위치'까지 고려해야 하는 차원으로 진화했다.

• 📢 섹션 요약 비유: 방목형 농장(전역 교체)에서 소들이 자유롭게 남의 구역 풀까지 다 뜯어 먹으며 살찌게 놔두다가, 미친 소 한 마리가 농장 전체 풀을 다 박살 내자, 농장주(쿠버네티스)가 튼튼한 울타리(cgroups)를 쳐서 "딱 이 구역 풀만 먹어라!" 하고 강제 배급제로 돌려버린 클라우드 목장의 현실입니다.

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

정량/정성 기대효과

결론 및 미래 전망

프레임 할당 (Frame Allocation) 알고리즘은 컴퓨터 과학에서 "유한한 재화를 어떻게 분배하는 것이 가장 정의로우면서도 동시에 효율적인가?"라는 정치경제학적 물음을 0과 1의 세계에 던진 철학적 명제다. 초기 공학자들은 고정된 크기(균등/비례)를 미리 떼어주는 통제 경제를 시도했으나 참담하게 실패했다. 결국 "필요할 때마다 남의 것을 빼앗아 쓰는 야생의 시장 경제(전역 교체)"가 전체 시스템 처리량을 우주 끝까지 올려준다는 것을 깨달았다. 하지만 그 야생성이 이웃 앱을 죽이는 부작용(Noisy Neighbor)을 낳자, 현대에 와서는 다시 cgroups라는 보이지 않는 손을 개입시켜 통제하는 나선형적 진화를 거치고 있다. 앞으로 AI 시대의 무지막지한 GPU VRAM 할당 전쟁에서도 이 분배와 통제의 변증법은 동일하게 반복될 것이다.

• 📢 섹션 요약 비유: 중앙에서 똑같이 식량을 배급하던 공산주의(균등 고정 할당)가 굶주림(비효율)에 무너지고, 능력껏 밥을 뺏어 먹는 자본주의(전역 교체)가 풍요를 가져왔지만, 독점의 폐해가 커지자 결국 복지 규제(cgroups 제한)를 통해 밸런스를 맞추게 된 인류 경제 시스템의 완벽한 램(RAM) 버전 거울입니다.

📌 관련 개념 맵 (Knowledge Graph)

• 페이지 부재율 (Page Fault Rate) | 프레임 할당량을 조금만 줄여도 지수함수적으로 폭발하여 서버를 박살 내는 절대적 성능 모니터링 지표
• 전역 교체 (Global Replacement) | 빈방이 없을 때 내 방 안에서 안 지우고, 만만한 남의 프로세스 램을 후려쳐서 뺏어오는 현대 OS의 주력 정책
• 스래싱 (Thrashing) | 프로세스에게 할당된 프레임 수가 너무 적어, 밥 먹을 틈도 없이 남의 방 뺏고 내 방 뺏기느라 CPU가 기절하는 현상
• 워킹 셋 (Working Set) | 어떤 프로세스가 폴트 없이 평온하게 돌기 위해 "최소한으로 꼭 쥐고 있어야 하는 램 프레임의 뭉치(할당 하한선)"
• cgroups (Control Groups) | 도커 컨테이너 환경에서 리눅스의 전역 교체 폭주를 막기 위해 인위적으로 메모리 할당(Limit) 상한선을 그어버리는 철창

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

1. 프레임 할당이 뭔가요? 배고픈 아이들 5명에게 피자(메모리) 10조각을 몇 조각씩 나눠줄지 결정하는 엄마의 고민이에요.
2. 어떻게 나눠주나요? 무조건 2조각씩 평등하게(균등) 줄 수도 있고, 덩치 큰 형아한테 5조각, 막내한테 1조각(비례) 줄 수도 있어요.
3. 무엇이 문제인가요? 덩치가 커도 지금 형아가 자고 있다면 피자 5조각은 다 식어서 버리게 돼요. 그래서 요즘 엄마(운영체제)는 일단 1조각씩 입에 넣어주고, 빨리 다 먹고 "더 줘!" 하는 아이한테 피자를 더 몰아주는 아주 똑똑한 눈치 방식을 쓴답니다.