동적 할당 First/Best/Worst Fit

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

본질: 동적 메모리 할당(Dynamic Storage Allocation)은 가변 분할 환경에서 새로운 프로세스가 들어오거나 malloc이 호출되었을 때, **"메모리에 흩어져 있는 여러 개의 빈 공간(Hole) 중 과연 어느 곳에 이 프로세스를 집어넣을 것인가?"**를 결정하는 알고리즘이다.

3가지 전략: 위에서부터 찾다가 첫 번째로 맞는 곳에 넣는 First-Fit(최초 적합), 남는 자투리가 가장 적은 곳에 넣는 Best-Fit(최적 적합), 오히려 남는 자투리가 가장 큰 곳에 넣는 **Worst-Fit(최악 적합)**이 있다.

실전 승자: 직관적으로는 Best-Fit이 가장 좋을 것 같지만, 실제 시스템에서는 탐색 시간이 가장 짧고(O(1)에 근접) 잉여 공간을 큼직하게 보존하는 First-Fit이 속도와 공간 효율성 양면에서 가장 우수한 것으로 증명되어 실무 메모리 할당기의 근간이 되었다.

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

개념:
- 가변 분할 (Variable Partitioning): 프로세스가 요구하는 크기만큼 메모리를 잘라서 주는 방식.
- Free List (빈 공간 리스트): 운영체제가 현재 메모리에서 사용되지 않고 비어있는 조각(Hole)들의 주소와 크기를 기록해 둔 연결 리스트.
- 동적 할당 알고리즘: Free List를 뒤져서 프로세스의 요구 크기($N$)를 만족하는 최적의 Hole을 골라내는 탐색 기법.
필요성 (파편화와의 전쟁):
- 메모리 공간에 10MB, 30MB, 20MB짜리 빈 공간(Hole)이 흩어져 있다. 새로운 15MB짜리 프로세스가 들어왔다.
- 30MB에 넣으면 15MB가 남고, 20MB에 넣으면 5MB가 남는다. 어디에 넣어야 남은 공간이 나중에 재활용되기 좋을까?
- 해결책: "탐색 속도"와 "남은 구멍의 크기(외부 단편화 비율)" 사이의 트레이드오프를 계산하여, 시스템의 성격에 맞는 검색 알고리즘(First, Best, Worst)을 적용해야 했다.
💡 비유:
- 주차장에 3칸짜리, 1칸짜리, 2칸짜리 빈 공간이 흩어져 있다. 2칸짜리 캠핑카가 들어왔다.
- First-Fit (최초 적합): 입구에서부터 쭉 돌다가 3칸짜리 빈 공간을 보자마자 "오! 들어가네!" 하고 그냥 바로 주차해 버린다. (탐색 속도 1등)
- Best-Fit (최적 적합): 주차장을 끝까지 다 돌아본다. 2칸짜리 공간을 발견하고 "내 크기랑 완벽하게 똑같네!" 하고 거기에 주차한다. (남는 칸 없음, 완벽함)
- Worst-Fit (최악 적합): 주차장을 끝까지 다 돌아본다. 가장 넓은 3칸짜리에 굳이 주차하고 1칸을 남겨둔다. (남은 1칸에 오토바이라도 댈 수 있게 하려는 의도)
발전 과정:
1. 초기 OS: 메모리가 작아서 탐색 시간이 빠른 First-Fit을 선호함.
2. Best-Fit의 함정 발견: 빈 공간을 꽉 채웠더니, 너무 작아서 아무도 못 쓰는 쓰레기 구멍(Micro-hole)들만 양산됨을 학자들이 수학적으로 증명함.
3. 현대 동적 할당기: Buddy System이나 Slab Allocator처럼 이 3가지 Fit의 한계를 넘어서는 2의 승수 분할이나 캐싱 기법으로 진화함.
📢 섹션 요약 비유: 이사를 갈 때 집에 맞는 가구를 고르는 쇼핑법입니다. 첫 번째 가게에서 대충 맞는 걸 사는 사람(First), 하루 종일 돌아다니며 1cm의 오차도 없는 가구를 찾는 사람(Best), 제일 큰 가구를 사서 남는 공간을 또 활용하려는 사람(Worst)의 성향 차이입니다.

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

3대 할당 알고리즘 시뮬레이션

메모리의 Free List에 [ 10MB ], [ 30MB ], [ 15MB ], [ 50MB ] 크기의 빈 구멍(Hole)이 순서대로 있다고 가정하자. 여기에 [ 20MB ] 크기의 새로운 프로세스 $P_1$이 도착했다.

알고리즘	탐색 과정 및 할당 위치	남은 잉여 공간	시간 복잡도
First-Fit (최초 적합)	10MB(실패) $\rightarrow$ 30MB (성공! 탐색 종료)	30 - 20 = 10MB 남음	$O(1)$ ~ $O(N)$ (평균적으로 가장 빠름)
Best-Fit (최적 적합)	리스트 끝까지 4개를 모두 검색. 20MB를 담을 수 있는 구멍(30MB, 50MB) 중 가장 크기가 비슷한 것은? $\rightarrow$ 30MB에 할당	30 - 20 = 10MB 남음	무조건 $O(N)$ (전체 스캔 필수) 또는 정렬 유지 비용 발생
Worst-Fit (최악 적합)	리스트 끝까지 4개를 모두 검색. 가장 크기가 큰 구멍은? $\rightarrow$ 50MB에 할당	50 - 20 = 30MB 남음	무조건 $O(N)$ (전체 스캔 필수)

알고리즘별 치명적 약점 (Why Best-Fit is NOT the best?)

이름만 들으면 Best-Fit이 가장 우수할 것 같지만, OS 역사상 가장 큰 배신을 안겨준 알고리즘이다.

Best-Fit의 배신 (Micro-hole 양산):
- 20MB가 필요한데 21MB 구멍에 넣었다(Best-Fit).
- 남은 1MB는? 너무 작아서 지구상의 어떤 프로세스도 들어갈 수 없는 완전한 '쓰레기 조각(External Fragmentation)'이 된다.
- Best-Fit은 이런 쓸모없는 쥐똥만 한 조각들을 메모리 전체에 수만 개씩 양산하여 시스템을 빠르게 OOM(Out of Memory)으로 몰고 간다.
Worst-Fit의 변명:
- "어차피 남길 거면, 나중에 다른 애라도 들어올 수 있게 크게 남기자!"는 철학이다. 50MB에 20MB를 넣으면 30MB가 남으므로 훌륭한 재활용 공간이 된다.
- 단점: 며칠 뒤 진짜로 50MB짜리 거대 프로세스가 들어왔을 때, 이미 Worst-Fit이 그 큰 구멍을 갉아먹었기 때문에 거대 프로세스가 들어갈 곳이 없어져 버린다.
First-Fit의 승리 (50% Rule):
- 탐색 속도가 압도적으로 빠르다. (CPU 오버헤드 최소화)
- 크기를 신경 안 쓰고 막 넣기 때문에, 남는 공간이 크지도 작지도 않게 적당히 쪼개져 메모리 파편화 방어율이 오히려 Best-Fit보다 우수함이 시뮬레이션으로 증명되었다.

📢 섹션 요약 비유: 피자를 나눌 때, 내 입 크기에 '완벽하게' 맞춰 자르다 보면 칼질이 너무 많아져서 부스러기(Micro-hole)만 잔뜩 남아 치우기 힘들어집니다. 대충 눈대중으로 처음 잡히는 큰 조각을 베어 무는 것(First-Fit)이 식사 속도와 청소 면에서 가장 효율적입니다.

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

할당 전략과 자료구조(Data Structure)의 결합

할당 속도를 높이기 위해, Free List를 어떻게 정렬(Sorting)해 두느냐가 알고리즘의 성패를 가른다.

알고리즘	Free List 최적 정렬 방식	할당 속도	해제(Free) 속도 및 병합(Merge) 비용
First-Fit	메모리 주소(Address) 순서로 정렬	매우 빠름	양옆의 빈 공간이 붙어있는지 확인하고 합치기(Merge) 매우 쉽다.
Best-Fit	크기(Size) 오름차순으로 정렬	빠름	해제 시 크기가 달라지므로, 리스트를 다시 정렬해야 하는 치명적 비용 발생.
Worst-Fit	크기(Size) 내림차순으로 정렬	매우 빠름 (항상 맨 앞)	해제 및 재정렬 비용 극심. 큰 덩어리가 박살 나서 대형 프로세스 기아 발생.

과목 융합 관점

소프트웨어공학 / C언어 (malloc의 실체): 우리가 C언어에서 malloc(100)을 부를 때, 내부의 glibc (ptmalloc)는 위 3가지 낡은 방식을 그대로 쓰지 않는다. 대신 빈 공간의 크기별로 리스트를 따로 여러 개 파놓는 Segregated Free List(분리 가용 리스트) 방식을 쓴다. (예: 16바이트짜리 리스트, 32바이트짜리 리스트). 100바이트를 요구하면 128바이트 리스트의 첫 번째 블록(First-Fit)을 그냥 던져준다. 탐색 시간이 완벽한 $O(1)$이 된다.
클라우드 / 가상화: K8s 스케줄러가 노드에 파드(Pod)를 배치할 때도 이 개념이 쓰인다. 노드들의 남은 CPU/RAM을 보고, 꽉 차 있는 노드에 억지로 쑤셔 넣을지(Best-Fit / Bin Packing), 텅텅 빈 노드에 널찍하게 넣을지(Worst-Fit / Spread) 스케줄링 전략(Policy)을 아키텍트가 결정해야 한다.
📢 섹션 요약 비유: First-Fit은 도서관 책을 가나다순(메모리 주소순)으로 꽂는 것이라 반납할 때 주변 책과 합치기 좋습니다. Best-Fit은 책을 두께순(크기순)으로 꽂는 것이라 뺄 땐 좋지만, 얇아진 책을 다시 반납할 때 도서관 전체를 다시 뒤엎어 정렬해야 하는 지옥이 펼쳐집니다.

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

실무 시나리오

시나리오 — 레거시 임베디드 장비(Bare-metal)의 메모리 파편화 마비: RTOS가 올라간 공장 제어기에서 자체 메모리 할당기를 Best-Fit으로 구현했다. 3달간 켜놨더니 빈 메모리가 10MB나 남았는데도 1KB짜리 통신 객체 할당이 실패(OOM)하며 공장이 멈춤.
- 원인 분석: Best-Fit의 고질병인 **외부 단편화의 극한(Micro-hole)**이다. 수만 번의 할당/해제를 거치며, 남은 10MB가 100바이트짜리 구멍 10만 개로 쪼개져 버렸다. 물리적 용량은 있지만 연속된 1KB조차 없는 쓰레기장 상태가 된 것이다.
- 대응 (기술사적 가이드): 임베디드 환경에서는 외부 단편화를 유발하는 동적 할당(malloc/free) 자체를 금지(MISRA-C 규약)해야 한다. 부득이하게 써야 한다면 Best-Fit을 버리고, 메모리를 2의 승수(2, 4, 8, 16...)로 쪼개고 합치는 **버디 시스템 (Buddy System)**을 도입하여, 쪼개진 메모리가 해제될 때 즉시 옆의 짝꿍(Buddy)과 합체되어 큰 덩어리로 복구되도록 아키텍처를 갈아엎어야 한다.
시나리오 — 클라우드 노드 배치의 Bin Packing (Best-Fit의 재평가): AWS 위에서 EKS(쿠버네티스)를 돌리는데, 워커 노드 10대가 각각 CPU를 30%씩만 쓰고 있다. 남은 70%가 아까워서 새 파드를 배치하려 함.
- 아키텍처 적용: K8s 스케줄링에서는 이 빈 공간을 채우는 데 **Best-Fit (Bin Packing 전략)**이 쓰인다. 노드 1대를 CPU 99%까지 극한으로 꽉꽉 채워 넣고(Best-Fit), 아무것도 안 돌게 된 나머지 빈 노드 3대를 오토스케일링(Cluster Autoscaler)으로 통째로 꺼버리면(Scale-in) 매달 수천만 원의 클라우드 비용을 아낄 수 있다. 메모리 관리에서는 마이크로 홀을 만드는 악마였던 Best-Fit이, 클라우드 자원 관리에서는 인프라 비용을 극강으로 압축하는 천사로 재평가되는 대목이다.

의사결정 및 튜닝 플로우

  ┌───────────────────────────────────────────────────────────────────┐
  │                 동적 자원(메모리, 서버) 할당 전략 설계 플로우               │
  ├───────────────────────────────────────────────────────────────────┤
  │                                                                   │
  │   [요청 크기가 각기 다른 자원을 한정된 공간에 배치해야 하는 로직 작성]           │
  │                │                                                  │
  │                ▼                                                  │
  │      자원을 할당하고 해제(Free)하는 빈도가 초당 수만 번으로 극도로 높은가?     │
  │      (예: 애플리케이션 내부의 힙 메모리 관리기)                            │
  │          ├─ 예 ─────▶ [속도가 생명! First-Fit 계열 채택]              │
  │          │            (단, 순수 First-Fit은 탐색 시간이 길어질 수 있으므로, │
  │          │             크기별로 리스트를 분리한 Segregated Fit 구조 필수) │
  │          └─ 아니오 (시간 단위로 천천히 일어나는 거시적 자원 배치다)           │
  │                │                                                  │
  │                ▼                                                  │
  │      자원을 아껴서 비용을 줄이는 것(Cost Optimization)이 최우선 목표인가?    │
  │          ├─ 예 ─────▶ [Best-Fit (Bin Packing) 채택]               │
  │          │            (클라우드 인스턴스를 꽉꽉 채워 남는 서버를 꺼버림)     │
  │          │                                                        │
  │          └─ 아니오 ──▶ [Worst-Fit (Spread / Anti-Affinity) 채택]   │
  │                         (장애 발생 시 피해를 분산시키기 위해 파드들을       │
  │                          여러 노드에 최대한 듬성듬성 넓게 퍼뜨림)          │
  └───────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 하나의 알고리즘이 영원한 승자일 수는 없다. 단일 메모리(마이크로 세계)에서는 쪼개진 자원을 다시 모으기 힘들기 때문에 Best-Fit이 실패했지만, 클라우드 클러스터(매크로 세계)에서는 쪼개진 가상 자원을 꽉 채우고 물리 서버 전원을 내려버릴 수 있기 때문에 Best-Fit이 정답이 된다. 아키텍트는 스케일(Scale)에 따라 알고리즘의 유불리가 뒤집힘을 통찰해야 한다.

도입 체크리스트

50% 룰 (Fifty-Percent Rule): 수학자 크누스(Knuth)가 증명한 법칙. First-Fit을 쓸 때 할당된 메모리가 $N$개라면, 잃어버리는 빈 공간(외부 단편화)은 무조건 $0.5N$개가 된다. 즉, 램의 1/3은 무조건 파편화로 날아간다. 당신이 짠 C/C++ 서버의 메모리가 16GB라면, 실제로는 10GB만 넘어가도 파편화로 죽을 수 있음을 용량 산정(Capacity Planning) 시 고려했는가?
📢 섹션 요약 비유: 배낭에 짐을 쌀 때, 짐이 들어갈 빈틈을 끝까지 찾아서(Best-Fit) 완벽하게 싸면 기분은 좋지만, 나중에 중간에 있는 짐을 뺐다 꼈다 하면 결국 배낭 속이 엉망진창이 됩니다. 대충 손에 잡히는 대로 쑤셔 넣고(First-Fit), 차라리 배낭을 여러 칸(페이징)으로 나누는 것이 현명한 여행자입니다.

Ⅴ. 기대효과 및 결론

정량/정성 기대효과

구분	Best-Fit (최적 핏)	First-Fit (최초 핏) / 분리형 리스트	개선 효과
정량 (할당 속도)	리스트 전체 $O(N)$ 풀 스캔	즉시 발견 시 $O(1)$ 리턴	런타임 메모리 병목 극소화 (CPU 절약)
정성 (단편화 방어)	수많은 쓸모없는 마이크로 홀 양산	비교적 적당한 크기의 잉여 공간 유지	OOM 발생 주기 연장 및 시스템 수명 증가
정성 (구현 복잡도)	트리 등 복잡한 정렬 자료구조 필요	단순 연결 리스트(Linked List)로 충분	커널/라이브러리 코드 가독성 및 유지보수성 향상

미래 전망

머신러닝 기반 메모리 예지 할당 (Predictive Allocation): 현재의 할당기(Allocator)는 멍청하게 "지금 달라는 크기"만 보고 구멍을 찾는다. 차세대 할당기는 "이 코드는 항상 100바이트를 할당한 뒤 1초 뒤에 50바이트를 추가로 요구하더라"라는 런타임 패턴을 AI가 학습하여, 아예 처음부터 150바이트짜리 구멍(Worst-Fit 변형)에 프로세스를 배치하여 미래의 파편화를 선제적으로 막아내는 연구가 도입되고 있다.

결론

First, Best, Worst Fit은 컴퓨터 공학도들이 메모리 관리를 배울 때 가장 먼저 접하는 3가지 고전 철학이다. 인간의 직관은 낭비가 없는 'Best-Fit'을 승자로 지목했지만, 컴퓨터의 차가운 현실은 잦은 탐색 비용과 쪼개진 마이크로 조각의 저주를 견디지 못하고 대충 빨리 꽂아 넣는 'First-Fit'의 손을 들어주었다. 이 역설적인 결론은 시스템 설계에 있어 **"국소적인 완벽함(로컬 최적화)이 전체 시스템의 파멸(글로벌 단편화)을 부를 수 있다"**는 뼈아픈 교훈을 남겼으며, 이는 오늘날 MSA 설계와 클라우드 자원 할당에서도 변하지 않는 진리로 작용하고 있다.

📢 섹션 요약 비유: 완벽한 짝(Best-Fit)을 찾기 위해 평생을 기다리다 결국 아무것도 못 하고 늙어버리는 것보다, 적당히 맞는 사람(First-Fit)을 빨리 만나 남은 삶(CPU 시간)을 가치 있게 채워가는 것이 훨씬 더 성공적이고 훌륭한 시스템(인생) 운영 방식입니다.

📌 관련 개념 맵 (Knowledge Graph)

개념 명칭	관계 및 시너지 설명
External Fragmentation (외부 단편화)	이 3가지 할당 알고리즘이 죽어라 막아보려 했지만 결국 실패해서 페이징(Paging)에게 자리를 내주게 된 근본적인 메모리 조각화 현상
Buddy System (버디 시스템)	이 3가지 Fit의 한계를 부수기 위해, 메모리를 무조건 2의 승수(2, 4, 8, 16)로만 쪼개고 합치도록 만들어 단편화와 속도를 모두 잡은 리눅스 커널의 핵심 할당 기법
Slab Allocator (슬랩 할당기)	객체 크기가 고정되어 있다면 굳이 Fit 알고리즘으로 빈 구멍을 찾지 말고, 똑같은 크기의 빵틀을 미리 수만 개 만들어두고 찍어내자는 커널 캐싱 기술
Compaction (메모리 압축)	빈 구멍을 찾다 찾다 도저히 안 나오면, 프로세스들을 한쪽으로 싹 밀어버려 빈 공간을 큰 덩어리로 합치는 최후의 수단 (하지만 너무 느려서 버려짐)
Bin Packing (빈 패킹 알고리즘)	Best-Fit 알고리즘이 가상 메모리에서는 망했지만, 클라우드 서버에 컨테이너를 꽉꽉 채워 넣어 서버 비용을 줄이는 현대적 아키텍처로 화려하게 부활한 이름

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

캠핑장에 텐트를 칠 수 있는 빈자리가 '좁은 곳, 딱 맞는 곳, 엄청 넓은 곳' 이렇게 3군데 흩어져 있어요.
텐트를 들고 들어온 첫 번째 친구(First)는 걷기 귀찮아서 입구에서 제일 가까운 '엄청 넓은 곳'에 대충 텐트를 쳐버렸어요 (제일 빠름).
두 번째 친구(Best)는 캠핑장을 끝까지 다 뒤져서 자기 텐트 크기에 '딱 맞는 곳'에 쳤어요. 완벽해 보이지만, 그 옆에 남은 1cm 빈틈에는 이제 아무도 텐트를 칠 수 없는 쓰레기 공간이 되어버렸답니다!