최악 적합 (Worst-Fit) 알고리즘

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

본질: 최악 적합(Worst-Fit)은 동적 메모리 할당 시 빈 공간 장부(Free List) 전체를 뒤져서 프로세스가 들어갈 수 있는 가장 거대하게 큰 빈 공간(Largest Hole)을 의도적으로 선택하여 쪼개는 역발상 알고리즘이다.

가치: 가장 크기가 비슷한 공간을 고집하여 미세한 쓰레기 조각(악성 외부 단편화)을 양산하는 최적 적합(Best-Fit)의 부작용을 피하기 위해, "어차피 남을 거라면 아주 큼직하게 남겨서 나중에 다른 놈이 쓸 수 있게 만들자"는 재활용 철학을 담고 있다.

융합: 아이디어는 좋았으나 매번 전체 리스트를 스캔하는 O(N)의 느린 속도와, 정작 나중에 덩치 큰 VIP 프로세스가 왔을 때 줄 공간이 멸종해 버리는 치명적 단점으로 인해 실무에서는 First-Fit에 밀려 사실상 폐기된 반면교사 기법이다.

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

개념: 가변 분할 방식의 동적 메모리 할당에서 사용되는 3대 전략 중 하나로, 요구 크기를 수용할 수 있는 구멍들 중 '남는 잉여 공간(Delta)'이 가장 크게 발생하는(가장 여유로운) 구멍을 골라잡는 전략이다.
필요성: 최적 적합(Best-Fit)을 돌렸더니 메모리 곳곳에 1KB, 10KB짜리 미세 단편화(Splinter)가 수만 개 생겨났다. 이 조각들은 영원히 쓸 수 없으면서 운영체제의 탐색 장부만 길어지게 만들어 시스템을 느리게 했다. 공학자들은 이를 방어하기 위해 "차라리 30MB를 15MB 2개로 쪼개자. 남은 15MB는 쓸모가 많다!"라는 파격적인 아이디어를 내놓았다.
💡 비유: 최악 적합은 혼자 밥을 먹으러 온 손님을 가장 넓은 10인용 단체석 한가운데 앉히는 식당 주인과 같다. 이유는 "1인용 자리에 앉히면 너무 비좁아서 짐을 못 놓지만(Best-Fit의 부작용), 10인용 석에 앉히면 남는 9자리에 나중에 다른 1~2명 손님들을 계속 합석시킬 수 있을 테니까!"라는 논리다.
등장 배경 및 설계 의도:
1. Best-Fit의 패배: 공간을 아끼려던 Best-Fit이 오히려 공간의 질을 악화시킴을 목격함.
2. 재활용 가능한 조각(Usable Fragments): 구멍을 쪼갤 때 나오는 나머지 부스러기가 충분히 커야만 훗날 다른 작은 프로세스가 들어올 수 있다는 통계적 접근.
3. Worst-Fit의 제안: 전체를 스캔해서 1위(가장 큰 구멍)를 찾아 그 녀석을 계속 반토막 내는 방식으로 운영하자고 제안됨.

┌────────────────────────────────────────────────────────────────────────┐
│           최악 적합(Worst-Fit) 알고리즘의 동작 시각화                  │
├────────────────────────────────────────────────────────────────────────┤
│                                                                        │
│ [ 상황: 15MB 프로세스를 할당해야 함 ]                                  │
│                                                                        │
│ 빈 공간 리스트 (정렬 안 된 상태)                                       │
│ ┌──────────┐  ┌──────────┐  ┌──────────┐  ┌──────────┐                 │
│ │ Hole 1   │─▶│ Hole 2   │─▶│ Hole 3   │─▶│ Hole 4   │                 │
│ │  30MB    │  │  20MB    │  │  16MB    │  │  50MB    │                 │
│ └──────────┘  └──────────┘  └──────────┘  └──────────┘                 │
│   (15 남음)       (5 남음)     (1 남음)     (35 남음!)                 │
│                                                                        │
│ ▶ 탐색 과정: 4개의 구멍을 '모두' 검사하여 남는 공간 계산.              │
│ ▶ 결과 판정: 15MB를 넣었을 때 가장 많이 남는(35MB) Hole 4 선택!        │
│ ▶ 남겨진 조각: 메모리 한구석에 훌륭하게 재활용 가능한 [35MB 구멍] 생성.│
└────────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] First-Fit이나 Best-Fit이었다면 절대로 50MB라는 VIP룸(Hole 4)을 건드리지 않았을 것이다. 그러나 Worst-Fit은 가차 없이 가장 큰 방부터 썰어버린다. 50MB에서 15MB를 내어주고 남은 35MB는, 여전히 웬만한 프로그램은 다 수용할 수 있는 '우량주' 구멍이다. 1MB 찌꺼기를 만드는 Best-Fit의 오류를 완벽히 피한 것처럼 보인다.

📢 섹션 요약 비유: 수박(거대 공간)을 아껴뒀다가 썩히느니, 누가 수박 한 조각을 달라고 하면 무조건 제일 큰 수박부터 칼을 대서 반을 잘라주고 남은 반 통을 냉장고에 보관하는 쿨한 과일 장수의 방식입니다.

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

크기 내림차순 (Size Descending) 정렬 아키텍처

Worst-Fit 역시 탐색 속도를 줄이기 위해 장부(Free List) 정렬이라는 꼼수를 부린다.

매번 O(N)으로 장부를 다 뒤지면 너무 느리므로, 구멍 크기가 가장 큰 것부터 작은 것 순으로(내림차순) 장부를 유지한다.
이렇게 하면 First-Fit 방식으로 맨 앞단만 딱 찔러도 그게 곧 Worst-Fit이 된다.

┌─────────────────────────────────────────────────────────────────────────┐
│            Worst-Fit을 위한 장부(Free List) 내림차순 정렬 구조          │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│ [ 1. 크기 내림차순 정렬된 빈 구멍 리스트 ]                              │
│ ┌────┐   ┌────┐   ┌───┐   ┌───┐   ┌───┐                                 │
│ │50MB│─▶│30MB│─▶│16MB│─▶│5MB│─▶│2MB│ (거대 구멍이 맨 앞에 노출)         │
│ └────┘   └────┘   └───┘   └───┘   └───┘                                 │
│                                                                         │
│ [ 2. 15MB 요청 시 탐색 ]                                                │
│  맨 앞의 50MB를 보고 "크네? 바로 할당!" (탐색 1번 만에 종료)            │
│                                                                         │
│ ⚠ 치명적 약점 (평준화 현상)                                             │
│ 50MB를 쪼개서 [35MB]가 됨 → 두 번째로 밀려남.                           │
│ 다음엔 35MB가 맨 앞이 되어 또 쪼개짐.                                   │
│ 결국 거대한 통짜 구멍은 순식간에 다 썰려나가고,                         │
│ 전체 시스템에 '중간 크기의 애매한 구멍'들만 가득 찬 도토리 키재기가 됨. │
└─────────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] Worst-Fit의 슬픈 결말을 보여주는 도식이다. 큰 놈부터 계속 때리기 때문에, 시간이 조금만 지나면 시스템에 50MB, 100MB짜리 웅장한 대형 룸은 온데간데없이 멸종해 버린다. 그리고 10MB, 15MB 수준의 고만고만한 중간방들만 수십 개가 나뒹구는 '평준화의 비극'이 일어난다. 이때 진짜 50MB짜리 데이터베이스 프로그램이 들어오려고 하면? 총 빈 공간은 300MB가 넘는데도 가장 큰 방이 15MB라서 OOM(Out of Memory)으로 사망해 버린다.

거대 프로세스의 굶주림 (Starvation of Large Processes)

Worst-Fit 알고리즘의 본질적 한계는 **'미래에 대한 대비가 전혀 없다'**는 점이다.

작은 프로세스들의 요청에 가장 큰 블록을 우선적으로 소비해버리므로, 정작 큰 블록을 요구하는 프로세스가 등장했을 때 이를 수용할 능력을 가장 먼저 상실한다.
Best-Fit이 자잘한 프로세스들의 배설물(미세 단편화) 때문에 망했다면, Worst-Fit은 큰 프로세스들을 굶겨 죽이는 편식 때문에 망했다.
📢 섹션 요약 비유: 부잣집에 10만 원권, 1만 원권, 1천 원권이 섞여 있을 때, 껌 한 통을 사면서 무조건 10만 원짜리 수표부터 내고 거스름돈을 받아오는 낭비벽 심한 도련님입니다. 정작 나중에 10만 원짜리 물건을 사야 할 때 지갑엔 1만 원권 잔돈만 수북해서 물건을 못 사게 됩니다.

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

3대 할당 알고리즘 최종 시뮬레이션 승패

현대 컴퓨터 공학에서 시뮬레이션으로 결론 내린 3대 알고리즘의 성적표다.

비교 항목	First-Fit (최초 적합)	Best-Fit (최적 적합)	Worst-Fit (최악 적합)
남겨진 공간의 질	적당히 섞여서 생태계 좋음	극단적인 미세 쓰레기 양산	큰 구멍 파괴 (도토리 키재기)
탐색 시간 복잡도	최고 (가장 빠름)	최악 (전체 스캔)	최악 (전체 스캔)
공간 활용률 (50% 룰)	우수함	오히려 가장 나쁨	나쁨 (큰 앱 실행 거절 잦음)
현대 OS 채택 여부	🟢 널리 쓰임	❌ 거의 폐기됨	❌ 거의 폐기됨

Worst-Fit의 기묘한 역설

"공간 활용률이 가장 나쁠 것 같은 Worst-Fit이 때로는 Best-Fit보다 낫다."

실제로 수천 개의 프로세스를 무작위로 넣고 빼는 몬테카를로 시뮬레이션을 돌려보면, 최악 적합(Worst-Fit)이 남긴 큼지막한 자투리들이 나중에 들어온 작은 앱들을 쏙쏙 잘 흡수해 주어서, 쓰레기 자투리만 양산한 베스트 핏(Best-Fit)보다 총 공간 활용률이 미세하게 좋게 나오는 현상이 발생한다.
즉 이름은 Worst(최악)이지만, 실제 성능은 Best(최적)를 이겨버리는 알고리즘의 패러독스다. 물론 그렇다 하더라도 First-Fit이라는 절대 강자를 이길 수는 없었다.

┌──────────┬────────────┬────────────┬────────────────┐
│ 평가 지표  │ First-Fit  │ Worst-Fit  │ Best-Fit     │
├──────────┼────────────┼────────────┼────────────────┤
│ 시간 효율  │ 1등        │ 2등 (정렬시)│ 3등 (꼴찌)  │
│ 공간 활용  │ 1등        │ 2등        │ 3등 (역설적) │
│ 큰 앱 수용 │ 2등        │ 3등 (최악)  │ 1등         │
└──────────┴────────────┴────────────┴────────────────┘

[매트릭스 해설] Best-Fit은 큰 블록을 지키는 데는 1등이지만 전체적인 공간 효율에서 꼴찌를 했다. Worst-Fit은 큰 블록을 다 부수어 먹어서 대형 앱 수용에서는 꼴찌지만 전체적인 공간 활용에서는 Best를 이겼다. 하지만 이 복잡한 트레이드오프의 진흙탕 싸움을 단박에 끝내버린 것이 뇌를 비우고 달리는 First-Fit의 압도적 스피드였다.

📢 섹션 요약 비유: '가장 예쁜 핏을 찾겠다(Best)'거나 '일부러 가장 안 맞는 핏을 고르겠다(Worst)'는 과도한 기교를 부리느니, 그냥 '대충 눈에 띄는 대로 입는 것(First)'이 가장 빨리 외출 준비를 마치는 지름길이라는 패션의 완성입니다.

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

실무 시나리오: Worst-Fit이 유일하게 쓰이는 특수 환경 (Buddy System)

범용 OS에서는 멸종한 Worst-Fit의 철학이 놀랍게도 Linux 커널의 핵심인 버디 시스템(Buddy System) 내부에서 부활했다.

버디 시스템의 쪼개기:
- 16KB를 요구하는 프로세스에게, 커널은 16KB 빈방을 찾지 않고 의도적으로 가장 거대한 1024KB짜리 통짜 덩어리를 골라잡는다. (Worst-Fit의 철학)
반으로 가르기:
- 1024를 512 두 개로 쪼개고, 512를 256 두 개로 쪼개고... 이 짓을 16KB가 나올 때까지 반복한다.
Worst-Fit의 우회적 성공:
- 원래 Worst-Fit은 큰 덩어리를 파괴해서 문제였지만, 버디 시스템은 "무조건 2배수 쌍둥이(Buddy)로만 쪼갠다"는 규칙을 추가했다.
- 나중에 16KB짜리가 반환되면, 옆에 있는 쌍둥이 16KB와 1나노초 만에 32KB로 합쳐지고, 다시 64KB로 연쇄적으로 병합(Coalescing)되어 순식간에 원래의 1024KB 거대 구멍으로 복구된다.
- 즉, 큰 구멍을 쪼개 쓰되(Worst-Fit), 복구가 100% 보장되는 특수 규칙을 도입하여 단점을 완벽히 소거한 현대적 융합 아키텍처다.

안티패턴: 파편화 누적으로 인한 시스템 다운

범용 힙 메모리(C malloc)를 직접 구현할 때 절대 Worst-Fit을 메인 로직으로 쓰면 안 된다. 하루만 돌려도 힙 공간이 믹서기에 갈린 것처럼 잘게 부서지며, 게임 서버나 DB에서 1MB짜리 패킷 버퍼 하나 할당받지 못해 "Memory Allocation Failed" 패닉 로그를 뿜으며 서버가 즉사한다.

📢 섹션 요약 비유: 수박을 마구잡이로 파먹어서 껍질만 남기는 것(Worst-fit의 실패)은 나쁘지만, 수박을 정확히 반의반의 반으로 쪼개어 밀폐 용기에 담아 보관했다가 다시 합치는 것(Buddy System)은 완벽한 냉장고 정리 기술이 됩니다.

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

정량/정성 기대효과

구분	내용
미세 단편화(Splinter) 억제	Best-Fit의 치명적 단점이었던 수십 바이트짜리 악성 빈 구멍 쓰레기들이 생성되는 것을 방지
자투리 공간의 재활용성	할당 후 남겨진 조각이 상대적으로 커서, 이후 들어오는 작은 프로세스들이 충분히 재활용 가능
반면교사로서의 가치	큰 블록 보존의 중요성을 역설적으로 증명하여, 이후 Slab이나 Buddy 할당기의 설계 철학에 기여

결론 및 미래 전망

최악 적합 (Worst-Fit)은 이름부터가 자신의 운명을 암시하듯, 범용 메모리 할당의 메인 무대에서는 철저히 실패한 전략이다. 1MB를 위해 100MB를 쪼개버리는 맹목적인 파괴 행위는 '대형 프로세스 기아 상태'라는 치명상을 낳았다. 하지만 이 실패는 컴퓨터 과학자들에게 "크기가 제각각인 메모리를 하나의 장부로 관리하는 것 자체가 미친 짓이다"라는 뼈저린 교훈을 주었다. 결국 Worst-Fit의 패배를 기점으로, 인류는 메모리를 규격화된 블록(페이징)으로 자르거나, 크기별로 방을 따로 관리하는(슬랩 캐시) 방향으로 거대한 아키텍처 전환을 이루어냈다.

📢 섹션 요약 비유: 소를 잡을 때 쓰는 거대한 식칼(Worst-fit)로 파 한 뿌리를 썰다가 도마까지 다 망가뜨려 본 뒤에야, 파 써는 과도와 고기 써는 식칼을 따로 구비해야(크기별 격리 할당) 한다는 주방의 진리를 깨달은 셈입니다.

📌 관련 개념 맵 (Knowledge Graph)

최초 적합 (First-Fit) | 동적 할당의 3대장 중 최후의 승리자로, 탐색 즉시 할당하여 속도가 가장 빠름
최적 적합 (Best-Fit) | 공간을 딱 맞춰 아끼려다 오히려 가장 치명적인 쓰레기 파편을 양산한 완벽주의 알고리즘
버디 시스템 (Buddy System) | Worst-Fit처럼 큰 블록을 쪼개 쓰지만, 2의 승수로 쪼개고 합치는 규칙으로 단점을 완벽히 극복한 리눅스의 핵심 할당기
외부 단편화 (External Fragmentation) | 어떤 배치 알고리즘을 쓰더라도 가변 분할 환경에서 필연적으로 발생하는, 흩어진 빈 공간의 낭비 현상
OOM (Out Of Memory) | 전체 메모리 공간은 남아있음에도, Worst-Fit 때문에 큰 덩어리가 멸종하여 큰 프로세스를 띄우지 못하고 시스템이 죽는 에러

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

최악 적합이 무엇인가요? 종이접기를 하려고 가위를 들었을 때, 무조건 새 스케치북(가장 큰 종이) 한가운데를 뻥 뚫어서 작은 별 모양 하나를 오려내는 방법이에요.
왜 그런 짓을 하나요? 쓰다 남은 작은 종이 쪼가리에 별을 딱 맞춰 오리려다(최적 적합) 너무 힘들어서, 차라리 새 스케치북을 자르면 큼직하게 남은 종이에 나중에 달이나 달팽이도 오릴 수 있을 거라 생각했거든요.
무엇이 문제인가요? 나중에 진짜 거대한 코끼리를 오리려고 보니까, 새 스케치북들이 전부 별 모양으로 구멍이 뻥뻥 뚫려 있어서 코끼리를 그릴 수가 없게 돼버렸답니다.