외부 단편화 (External Fragmentation)

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

본질: 외부 단편화(External Fragmentation)는 프로세스들이 메모리에 동적으로 적재되고 해제되기를 반복하면서, 메모리 전체에 작은 빈 공간(Hole)들이 연속되지 않고 벌집처럼 뿔뿔이 흩어져 있는 낭비 상태를 의미한다.

가치(문제점): 남아있는 전체 빈 공간의 총합은 새로운 프로그램을 실행하기에 충분히 크지만, 이 공간들이 하나로 이어져 있지 않기 때문에(연속성 위배) OS가 프로그램 적재를 거부하여 메모리 고갈(OOM)과 동일한 시스템 정체를 유발한다.

융합: 가변 분할 방식(Variable Partition)과 세그멘테이션(Segmentation) 아키텍처의 가장 치명적인 아킬레스건이며, 이를 물리적으로 복구하는 압축(Compaction) 비용이 너무 커서 결국 현대 OS가 페이징(Paging) 아키텍처로 넘어가게 만든 핵심 원인이다.

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

개념: 외부 단편화는 메모리의 '가용 공간(Free space)'이 쪼개져 있는 현상이다. 할당된 블록 '바깥(External)'에 존재하는 남는 공간들이 너무 작게 파편화되어, 유의미한 작업을 할당받지 못한 채 버려지는 자투리 메모리들이다.
필요성(해결의 필요성): 고정 분할이 낳은 내부 낭비(내부 단편화)를 없애고자 프로세스 크기에 맞춰 칼같이 잘라주는 동적 할당(가변 분할)을 도입했다. 낭비가 0%가 된 줄 알았으나, 프로그램들이 종료되면서 이 빠진 듯 구멍이 생기자 시스템 전체의 메모리 활용률이 급전직하했다. 시스템의 신뢰성과 다중 프로그래밍 능력을 붕괴시키는 이 파편화를 반드시 극복해야만 했다.
💡 비유: 외부 단편화는 영화관의 이빨 빠진 빈 좌석과 같다. 총 100석 중 30석이 비어있지만, 전부 1자리씩 띄엄띄엄 흩어져 있어서 3명이 나란히 앉으려는 가족 손님은 표를 사지 못하고 돌아가야 하는 억울한 상황이다.
등장 배경 및 발생 원리:
1. 맞춤 재단의 모순: 30MB, 15MB, 40MB 프로세스가 순서대로 들어왔다. 이때 15MB짜리가 작업을 끝내고 나가면 중간에 15MB 틈이 생긴다.
2. 새로운 프로세스의 진입: 그 자리에 10MB짜리 프로세스가 들어오면 5MB가 남는다. 이 5MB 구멍 옆에는 사용 중인 블록이 버티고 있어 합쳐지지 못한다.
3. 재앙의 누적: 이 과정이 수천 번 반복되면 메모리는 1KB, 3MB 식의 미세한 쓰레기 조각들로 가득 찬다. 결국 빈 램은 많은데 "메모리가 부족합니다"라는 에러를 뱉는 모순적 사태가 벌어진다.

┌──────────────────────────────────────────────────────────────────────┐
│        외부 단편화(External Fragmentation)의 딜레마 시각화           │
├──────────────────────────────────────────────────────────────────────┤
│                                                                      │
│ [ 현재 물리 메모리 상태: 프로세스 교체 반복 후 ]                     │
│                                                                      │
│ ┌─────┬──────────┬─────┬─────────┬─────┬──────────┐                  │
│ │ P1  │ ▒ 빈공간 ▒ │ P2  │ ▒빈공간▒ │ P3  │ ▒ 빈공간 ▒ │             │
│ │ 30M │   15MB   │ 20M │  10MB   │ 10M │   15MB   │                  │
│ └─────┴──────────┴─────┴─────────┴─────┴──────────┘                  │
│                                                                      │
│ ▶ 남은 빈 공간의 총합 = 15 + 10 + 15 = 40MB                          │
│                                                                      │
│ [ 새 프로세스 요청 ]                                                 │
│ 프로세스 P4가 30MB의 공간을 요구하며 메모리에 올라오려 함.           │
│                                                                      │
│ [ OS의 판정 ]                                                        │
│ "전체 40MB가 비어있지만, 가장 큰 연속된 구멍이 15MB밖에 없군."       │
│ "P4 너는 들어갈 수 없다. 실행 거부 (Allocation Failed)!"             │
└──────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 이 현상의 핵심은 '연속성(Contiguous)'에 대한 강박이다. 과거의 메모리 관리 기법이나 세그멘테이션은 프로세스가 메모리상에 한 덩어리(또는 큰 의미 단위)로 이어져 있어야 한다는 물리적 제약이 있었다. 전체 면적(Total Free Memory)이 아무리 넓어도, 그것이 조각나 있으면 무용지물이 되는 현상, 이것이 컴퓨터 공학을 수십 년간 괴롭힌 외부 단편화다.

📢 섹션 요약 비유: 하드디스크에 영화를 다운받으려는데, 남은 용량은 10GB지만 디스크 곳곳에 100MB씩 흩어져 있어서 2GB짜리 통짜 영화 파일을 저장할 수 없다고 에러가 나는 뼈아픈 상황입니다.

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

단편화를 통제하려는 동적 할당 알고리즘의 발버둥

외부 단편화가 생기는 것을 조금이라도 늦춰보려고 OS는 First-fit(최초 적합), Best-fit(최적 적합), Worst-fit(최악 적합) 이라는 알고리즘을 고안했다.

알고리즘	동작 방식	외부 단편화 관점에서의 결과	비유
Best-fit	요구 크기와 가장 비슷한 구멍 탐색	거의 딱 맞는 구멍을 쓰므로, 남는 자투리가 먼지 수준(수십 바이트)으로 작아져 오히려 가장 악성인 미세 외부 단편화를 양산함	딱 맞는 작은 상자 찾기
Worst-fit	가장 큰 구멍에 무조건 할당	남은 공간이 커서 다른 프로세스가 쓸 확률이 높음. 단편화 진행 속도를 조금 늦추지만 검색 오버헤드가 큼	무조건 제일 큰 상자에 담기
First-fit	처음 보이는 충분한 구멍에 할당	검색 속도가 가장 빨라 파편화 처리 비용을 상쇄함. (현실적인 승자)	눈에 띄는 첫 상자에 담기

압축 (Compaction / Defragmentation) 아키텍처

외부 단편화가 한계치에 다다르면, OS는 극약 처방인 '메모리 압축'을 실행한다. 이 아키텍처는 모든 흩어진 빈 공간을 메모리 끝으로 모아 하나의 '거대한 구멍(Big Hole)'으로 만드는 수집 연산이다.

┌──────────────────────────────────────────────────────────────────────────┐
│              외부 단편화의 물리적 해결책: 압축 (Compaction)              │
├──────────────────────────────────────────────────────────────────────────┤
│                                                                          │
│ [ 압축 전 (Before Compaction) ]                                          │
│ [P1 10M][빈 5M][P2 20M][빈 10M][P3 15M][빈 5M] (파편화 극심)             │
│                                                                          │
│     ↓↓↓ OS가 흩어진 프로세스를 복사하여 한쪽 벽으로 밀어버림 ↓↓↓         │
│                                                                          │
│ [ 압축 후 (After Compaction) ]                                           │
│ [P1 10M][P2 20M][P3 15M][ ▒▒▒▒ 합쳐진 거대 빈 공간 20M ▒▒▒▒ ]            │
│                                                                          │
│ ⚠ 압축의 치명적 대가 (Overhead)                                          │
│ 1. 20M(P2)와 15M(P3)의 데이터를 물리적으로 복사(Memory Copy)해야 함      │
│ 2. 이사 간 프로세스의 Base 레지스터 주소를 모두 재계산해서 바꿔줘야 함   │
│ 3. 이 과정 동안 CPU는 다른 일(사용자 프로그램)을 멈춰야 함 (System Stop) │
└──────────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 압축은 논리적으로 완벽한 해결책이다. 흩어진 5M, 10M, 5M 구멍이 합쳐져 20M의 온전한 덩어리가 되었으니 새 프로세스를 올릴 수 있다. 하지만 기가바이트(GB) 단위의 현대 메모리에서 이 작업을 수행하면 메모리 복사 대역폭을 모두 소모하여 시스템이 수 초간 완전히 멈추는 프리즈(Freeze) 현상이 발생한다. 즉, '해결책의 비용이 문제 자체보다 커지는' 모순에 부딪힌다. (Windows 하드디스크의 '디스크 조각 모음'이 이와 동일한 원리다)

50% 규칙 (50-Percent Rule)의 수학적 절망

1960년대 Knuth의 수학적 증명에 따르면, First-fit 등 동적 할당 알고리즘으로 시스템이 평형 상태(통계적 균형)에 도달했을 때, 할당된 메모리 블록이 N개면, 평균적으로 외부 단편화로 발생한 빈 블록이 0.5N개 존재하게 된다.
즉, 메모리의 약 3분의 1(33%)이 영구적으로 흩어진 조각으로 남아 쓸 수 없게 버려진다는 뜻이다. 이 수학적 한계는 가변 분할 방식의 무덤이 되었다.
📢 섹션 요약 비유: 방을 어지럽힌 채로(외부 단편화) 놔두면 발 디딜 틈이 없고, 대청소(압축)를 하려고 맘먹으면 하루 종일 아무 일도 못 하고 청소만 해야 하는 끔찍한 가사노동의 딜레마입니다.

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

비교 1: 외부 단편화 (External) vs 내부 단편화 (Internal)

비교 항목	외부 단편화 (External Fragmentation)	내부 단편화 (Internal Fragmentation)
발생 원리	프로세스 크기에 맞춰 자르다 보니, 나간 자리에 생기는 자투리들	일정한 박스(페이지)에 담다 보니, 박스 안에 남는 잉여 공간
낭비 위치	할당된 프로세스 영역 바깥(External)의 빈 공간	할당된 프로세스 영역 안(Internal)의 빈 공간
메모리 관점	남은 공간 합은 크지만 연속적이지 않아 쓸 수 없음	공간이 이미 해당 앱 소유로 찍혀있어 남이 쓸 수 없음
해결 기법	페이징(Paging)을 통한 비연속 할당 도입으로 완벽히 제거	페이지 크기를 줄이는 것 외엔 근본적 해결 불가 (수용함)
주요 희생양	연속 메모리 가변 분할, 세그멘테이션(Segmentation)	고정 분할, 페이징(Paging)

아키텍처 진화의 역사 (단편화 극복기)

외부 단편화와 내부 단편화를 피해 온 운영체제 아키텍처의 역사는 다음과 같다.

연속 할당 (고정 분할): 내부 단편화 극심 → 버려
연속 할당 (가변 분할): 내부 단편화 0%, 그러나 외부 단편화 33% (50% 규칙), 압축 비용 폭발 → 버려
세그멘테이션 (Segmentation): 코드는 연속되게 의미 단위로 찢음. 여전히 크기가 제각각이라 외부 단편화 발생 → 버려
페이징 (Paging): 메모리를 무조건 4KB로 찢어서 흩뿌림. 외부 단편화 0% 달성. (마지막 페이지에서 내부 단편화 미세 발생) → 현대 OS의 최종 승리자

┌──────────┬────────────┬────────────┬────────────────────┐
│ 아키텍처   │ 공간 연속성  │ 외부 단편화  │ 내부 단편화  │
├──────────┼────────────┼────────────┼────────────────────┤
│ 가변 분할  │ 강제함      │ ☠️ 치명적   │ 발생 안 함     │
│ 페이징     │ 완전히 찢음  │ 🟢 발생 안함 │ 🟡 미세 발생 │
└──────────┴────────────┴────────────┴────────────────────┘

[매트릭스 해설] 컴퓨터 과학은 딜레마 상황에서 더 싼 비용을 선택하는 학문이다. 외부 단편화를 해결하기 위해 치러야 할 '메모리 압축(Compaction)' 비용은 시스템 멈춤이라는 끔찍한 결과를 낳았다. 반면 내부 단편화는 기껏해야 4KB당 2KB를 버리는 푼돈 수준이다. 인류는 "그냥 메모리를 아주 잘게 조각내어(페이징) 아무 빈 곳에나 뿌리고 외부 단편화를 멸종시키자. 내부 낭비 조금 생기는 건 램을 하나 더 사서 꽂는 게 싸다"라는 결론에 도달했다.

📢 섹션 요약 비유: 큰 종이에서 원하는 모양을 계속 오려내다 보면 결국 종이 전체가 너덜너덜해져서(외부 단편화) 못 쓰게 되는데, 아예 처음부터 색종이를 정사각형 모자이크 타일(페이징)로 만들어 조립하면 버리는 종이가 없어지는 원리입니다.

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

실무 시나리오: C언어 malloc과 Heap 단편화 (STW)

현대 OS의 물리 메모리 관리에서는 페이징 덕분에 외부 단편화가 사라졌지만, 놀랍게도 애플리케이션(프로세스) 내부의 힙(Heap) 메모리 영역에서는 여전히 이 외부 단편화가 매일 밤 개발자들을 괴롭힌다.

상황: C++이나 Java로 개발된 24시간 도는 게임 서버가 있다. 게임 특성상 작은 몬스터 객체(20바이트)와 거대한 보스 객체(1MB)가 수없이 생성(new/malloc)되고 소멸(delete/free)된다.
힙 파편화 (Heap Fragmentation):
- 앱 내부의 가상 메모리(Heap) 공간이 옛날 가변 분할 시절처럼 이빨 빠진 쓰레기 조각(외부 단편화)으로 가득 찬다.
가비지 컬렉터 (GC)의 극약 처방:
- 빈 구멍이 너무 많아져서 새 객체를 생성할 수 없으면, 자바의 GC(Garbage Collector)가 발동하여 살아있는 객체들을 한쪽으로 쫙 밀어버리는 **'압축(Compaction)'**을 수행한다.
- 이때 앱이 멈추는 현상이 바로 그 악명 높은 **Stop-The-World (STW)**다. 게임 서버 렉의 가장 흔한 원인이다.
실무적 해결 (메모리 풀링):
- 외부 단편화를 원천 차단하기 위해, 실무 게임 서버는 힙을 실시간으로 쪼개 쓰지 않고 부팅 시 같은 크기의 객체를 담을 **오브젝트 풀(Object Pool / Slab Allocator)**을 미리 만들어두어 '고정 분할' 방식으로 회귀하는 최적화를 수행한다.

플래시 메모리(SSD)와 TRIM

하드디스크 시절에는 디스크 내부의 파일 외부 단편화를 해결하기 위해 '디스크 조각 모음'을 돌렸다. 하지만 SSD 환경에서는 외부 단편화로 흩어져 있어도 접근 속도가 빛처럼 빠르므로 조각을 모을(압축) 필요가 없다. 오히려 쓰기(Write) 횟수를 늘려 수명을 깎으므로 금기시된다. 대신 파일이 지워진 흩어진 구멍들을 컨트롤러에 알려주는 TRIM 명령어가 그 자리를 대체했다.

📢 섹션 요약 비유: 운영체제라는 큰 나라는 페이징이란 마법으로 외부 단편화 전염병을 없앴지만, 아직도 그 나라 안의 각 동네(프로세스 힙)에서는 옛날 방식대로 쓰레기를 치우느라 매번 대청소(Stop The World)를 하고 있는 아이러니한 현실입니다.

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

정량/정성 기대효과

구분	내용
페이징(Paging)의 당위성 부여	외부 단편화라는 막대한 비효율(33% 낭비)은 비연속 메모리 할당 아키텍처로의 전환을 강제한 역사적 원동력임
압축(Compaction) 알고리즘 발전	파편화된 공간을 모으는 로직은 현대 프로그래밍 언어의 가비지 컬렉터(GC) 코어 엔진으로 계승됨
메모리 풀(Memory Pool) 패턴 확산	런타임 단편화를 막기 위해 규격화된 메모리를 사전 할당하는 성능 최적화 패턴(Slab)의 기원이 됨

결론 및 미래 전망

외부 단편화 (External Fragmentation)는 연속 메모리 할당이라는 경직된 틀 안에서 '완벽한 맞춤 할당(가변 분할)'을 추구했을 때 필연적으로 마주하게 되는 복잡계의 재앙이다. 조각을 아무리 모아도 연속되지 않으면 쓸 수 없다는 맹점은, 결국 주소를 비연속적으로 매핑하는 가상 메모리와 페이지 테이블이라는 위대한 추상화 기술을 탄생시켰다. 오늘날 OS 커널 레벨에서 외부 단편화는 완전히 정복된 과거의 망령이지만, 그 그림자는 여전히 유저 레벨의 힙(Heap) 메모리와 데이터베이스 스토리지 엔진 내부 깊숙한 곳에서 개발자들이 평생 싸워나가야 할 영원한 숙제로 남아 있다.

📢 섹션 요약 비유: 퍼즐 조각을 억지로 원래 판의 빈칸(연속성)에 맞추려다 보니 안 들어가서 끙끙댔지만, 아예 판이라는 개념을 없애고 4KB짜리 블록들을 아무렇게나 조립해도(페이징) 하나의 그림이 되게 만드는 발상의 전환으로 해결한 난제입니다.

📌 관련 개념 맵 (Knowledge Graph)

내부 단편화 (Internal Fragmentation) | 할당된 방 안에서 남아도는 공간으로, 외부 단편화와는 발생 위치와 원인이 완전히 다름
메모리 압축 (Compaction) | 외부 단편화로 생긴 수많은 빈 구멍을 하나의 거대한 구멍으로 합치기 위해 메모리 내용을 복사하며 옮기는 작업
페이징 (Paging) | 프로세스를 연속으로 두어야 한다는 강박을 버리고 4KB 크기로 잘라 빈 곳 아무 데나 분산 적재하여 외부 단편화를 없앤 기법
50퍼센트 규칙 (50-Percent Rule) | 가변 분할 환경에서 메모리의 1/3은 항상 조각나서 영구적으로 버려진다는 수학적 한계 증명 법칙
가비지 컬렉션 (Garbage Collection, GC) | Java 같은 언어에서 힙 메모리의 외부 단편화를 해결하기 위해 살아있는 객체를 모으고 압축(Compaction)하는 메커니즘

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

외부 단편화가 무엇인가요? 주차장에 자리가 10개 남았는데, 차들이 듬성듬성 주차해놔서 전부 한 자리씩만 떨어져 비어있는 상태예요.
무엇이 문제인가요? 아빠의 커다란 캠핑카는 3자리가 쭉 붙어있어야 주차할 수 있는데, 자리가 총 10개나 남았음에도 불구하고 붙어있는 곳이 없어서 집에 돌아가야 한답니다.
어떻게 해결하나요? 주차된 차들을 전부 한쪽 끝으로 바짝 밀착시켜서(압축), 커다란 빈 공간 10자리를 통째로 하나로 만들어버리면 캠핑카가 들어갈 수 있어요.