최초 적합 (First-Fit) 알고리즘

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

본질: 최초 적합(First-Fit)은 동적 메모리 할당 시 빈 공간 리스트(Free List)를 처음부터 순차적으로 탐색하다가, 요청한 메모리 크기보다 크거나 같은 첫 번째 빈 공간(Hole)을 발견하는 즉시 탐색을 멈추고 할당하는 알고리즘이다.

가치: 가장 무식해 보이지만 최적 적합(Best-Fit)이나 최악 적합(Worst-Fit)처럼 리스트 전체를 스캔할 필요가 없어 탐색 오버헤드(시간 복잡도)가 압도적으로 적으며, 속도와 공간 활용도 측면에서 가장 현실적이고 우수한 성능을 낸다.

융합: 가변 분할 방식에서 운영체제가 채택한 사실상의 표준(Standard) 알고리즘이었으며, 메모리 주소순으로 리스트를 정렬해두면 공간 단편화를 줄이고 병합(Coalescing) 속도까지 극대화하는 시너지를 발휘한다.

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

개념: 동적 메모리 배치 문제(Dynamic Storage-Allocation Problem)를 해결하는 3대 알고리즘 중 하나로, 요구 크기를 수용할 수 있는 '최초의 충분한 틈새'에 프로세스를 쑤셔 넣고 남는 공간을 다시 빈 구멍으로 장부에 기록하는 방식이다.
필요성: 메모리 할당(Allocation)은 컴퓨터가 켜져 있는 동안 수억 번 넘게 호출되는 극도로 빈번한 운영체제 커널의 핵심 기능이다. 만약 15MB를 할당받기 위해 10만 개의 빈 공간 노드를 매번 끝까지 뒤져서 비교 계산을 한다면 CPU는 사용자 프로그램은 돌리지 못하고 메모리 장부만 뒤적거리다 끝날 것이다. 따라서 1나노초라도 빨리 검색을 종료(Early Exit)할 수 있는 탐색 최소화 철학이 절대적으로 필요했다.
💡 비유: 최초 적합은 마트 주차장에서 주차할 때의 행동과 같다. 주차장 입구부터 차를 몰고 들어가다가 내 차가 들어갈 수 있는 크기의 빈자리가 보이면, "저 안쪽 구석에 더 딱 맞는 자리가 있을까?" 고민하지 않고 1초 만에 그냥 냅다 주차해버리는 가장 효율적인 운전자의 방식이다.
등장 배경 및 설계 철학:
1. 탐색 오버헤드의 저주: 초기 컴퓨터 공학자들은 공간을 완벽하게 아끼기 위해 Best-Fit(최적 적합)을 고안했으나, 매번 리스트 전체를 스캔하는 O(N) 비용에 발목이 잡혔다.
2. 휴리스틱(Heuristic) 접근: 완벽한 최적해(Optimal)를 포기하는 대신, 연산 비용을 획기적으로 줄이는 근사해(적당히 좋은 답)를 찾는 타협안으로 First-Fit이 등장했다.
3. 통계적 역전승: 놀랍게도 시뮬레이션 결과, 대충 처음 보이는 곳에 넣는 First-Fit이 공간을 아끼려는 Best-Fit보다 악성 미세 단편화(아주 작은 쓰레기 조각)를 덜 만들어서 공간 활용률 면에서도 더 우수하거나 비슷하다는 충격적인 결론이 도출되었다.

┌──────────────────────────────────────────────────────────────────┐
│           최초 적합(First-Fit) 알고리즘의 동작 시각화            │
├──────────────────────────────────────────────────────────────────┤
│                                                                  │
│ [ 상황: 15MB 프로세스를 할당해야 함 ]                            │
│                                                                  │
│ 빈 공간 리스트 (메모리 주소 순서대로 정렬)                       │
│ ┌──────────┐  ┌──────────┐  ┌──────────┐  ┌──────────┐           │
│ │ Hole 1   │─▶│ Hole 2   │─▶│ Hole 3   │─▶│ Hole 4   │           │
│ │  10MB    │  │  20MB    │  │  16MB    │  │  30MB    │           │
│ └──────────┘  └──────────┘  └──────────┘  └──────────┘           │
│   (작아서 X)     (15MB 이상이네? 빙고! 탐색 즉시 종료)           │
│                                                                  │
│ ▶ 결과: 2번째 구멍(20MB)에 15MB 할당. 뒤에 있는 16MB나 30MB는    │
│        아예 쳐다보지도 않고 스킵함! (탐색 시간 극단적 단축)      │
│ ▶ 조각: 20MB - 15MB = 5MB의 새로운 빈 구멍(외부 단편화) 생성     │
└──────────────────────────────────────────────────────────────────┘

[다이어그램 해설] First-Fit의 가장 아름다운 부분은 "탐색 즉시 종료(Short-circuit evaluation)"에 있다. 뒤에 16MB라는 훨씬 더 완벽하게 딱 맞는 방(Hole 3)이 대기하고 있음에도 불구하고, First-Fit은 뒤도 돌아보지 않고 Hole 2를 쪼개버린다. 이 무심함 덕분에 OS는 탐색 스레드 사이클을 아껴 사용자 프로그램에 더 많은 CPU 파워를 돌려줄 수 있다.

📢 섹션 요약 비유: 시험 문제를 풀 때 1번부터 읽어 내려가다가 확실히 정답인 보기를 발견하면, 뒤에 있는 4, 5번 보기는 쳐다보지도 않고 마킹한 뒤 다음 문제로 넘어가는 전교 1등의 스피드 풀이법입니다.

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

리스트 정렬 방식 (Ordering Strategy)

First-Fit 알고리즘의 성능은 빈 구멍들을 기록해둔 장부(Free List)를 '어떤 기준'으로 정렬해두느냐에 따라 180도 달라진다.

정렬 기준	검색 동작 및 결과	병합 (Coalescing) 오버헤드
물리적 주소 순서 (Address Order)	메모리 앞쪽 주소부터 탐색. 앞쪽에 작은 조각이 몰려 뒷부분까지 탐색이 밀리는 현상(Fragmentation) 발생 가능.	인접한 구멍이 리스트 상에서도 인접하므로, 병합 연산이 극도로 빠름. (현실적 표준)
크기 오름차순 (Size Order)	가장 작은 구멍부터 탐색하므로 사실상 Best-Fit과 동일하게 동작함.	주소 순서가 뒤죽박죽이라 양옆 구멍을 합치기 위해 전체 리스트를 뒤져야 함. (오버헤드 큼)
크기 내림차순 (Size Descending)	무조건 제일 큰 구멍부터 부딪히므로 사실상 Worst-Fit과 동일함.	의미 없음.

주소순 First-Fit의 아키텍처 및 쏠림 현상 (Splintering)

First-Fit을 메모리 주소 순서대로 운영하다 보면, 항상 리스트의 맨 앞단부터 검색을 시작하기 때문에 특이한 부작용이 발생한다.

┌────────────────────────────────────────────────────────────────────────┐
│             First-Fit의 메모리 앞부분 쏠림 현상 (Splintering)          │
├────────────────────────────────────────────────────────────────────────┤
│                                                                        │
│ [ 며칠간 서버 운영 후 메모리 레이아웃 상태 ]                           │
│                                                                        │
│ 저주소 (Low Memory) ◀────────────────────────▶ 고주소 (High)           │
│ [ ▒ 1M ▒ 2M ▒ 1M ▒ 3M ▒ 1M ▒ ... ] [ ███ 50M 거대 구멍 ███ ]           │
│ └─ 무수히 쪼개진 작은 조각들 지옥 ───┘ └─ 한 번도 안 쓰인 청정구역 ─┘  │
│                                                                        │
│ ▶ 문제: 새 프로세스(20M)가 들어오면?                                   │
│    항상 앞단부터 검색하므로, 앞에 널브러진 수백 개의 1M, 2M 조각들을   │
│    "아니네, 아니네" 하며 전부 스캔한 뒤에야 끝부분 50M에 도달함.       │
│    결국 O(N) 스캔 오버헤드가 점점 커지는 퇴화 현상이 발생!             │
└────────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 무조건 앞에서부터 찾는 성질 때문에, 메모리의 앞쪽(Low Address)은 프로그램이 들어왔다 나갔다를 반복하며 갈기갈기 찢겨 작은 자투리(Splinter)들로 붐비게 된다. 반면 뒤쪽(High Address)은 접근조차 안 되어 거대한 통짜 구멍으로 남아있다. 검색할 때마다 이 앞단의 자투리 무덤들을 지나가야 하므로 초기보다는 점점 할당 속도가 느려진다.

개선판: 다음 적합 (Next-Fit)

위의 쏠림 현상을 해결하기 위해 등장한 변형 알고리즘이다.

방식: 매번 리스트의 처음부터 검색하는 것이 아니라, 마지막으로 할당이 끝난 그 지점(포인터)을 기억해두었다가 거기서부터 이어서(Next) 탐색을 시작한다.
효과: 빈 구멍과 쪼개지는 파편들이 메모리 전 영역에 골고루 분산되어 탐색 속도가 일관되게 빨라진다. 다만 가장 거대한 통짜 구멍마저 갈가리 찢어버려 외부 단편화를 악화시키는 단점이 존재한다.
📢 섹션 요약 비유: 매번 책장 맨 왼쪽부터 책을 꽂다 보니 왼쪽만 꽉 차고 지저분해져서(쏠림 현상), 어제 꽂은 책 바로 다음 칸부터 이어서 꽂는 방식(Next-fit)으로 진화한 것입니다.

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

비교 1: 최초 적합(First-Fit) vs 최적 적합(Best-Fit) vs 최악 적합(Worst-Fit)

공간(외부 단편화)과 시간(속도)의 관점에서 완벽한 비교표다.

알고리즘	시간 복잡도 (탐색 속도)	외부 단편화 발생 성향	남는 조각의 질 (재활용성)
First-Fit	O(N)이나 평균 절반 탐색 (매우 빠름)	보통 (일반적인 50% 룰 적용)	중간 크기의 적당한 찌꺼기들
Best-Fit	정렬 안 된 경우 O(N) 무조건 스캔 (느림)	찌꺼기들이 너무 작아서 최악의 단편화	사실상 재활용 불가능한 미세 조각
Worst-Fit	정렬 안 된 경우 O(N) 무조건 스캔 (느림)	거대 공간을 너무 빨리 소진해버림	재활용하기 좋게 큰 덩어리가 남음

공간 활용률의 패러독스 (Best-Fit의 배신)

직관적으로 생각하면 가장 크기가 비슷한 곳에 꽂아 넣는 Best-Fit이 공간을 가장 아낄 것 같지만, 실제 시뮬레이션에서는 First-Fit이 공간 활용률마저 Best-Fit을 이기거나 비슷한 성능을 낸다.
이유: Best-Fit은 16MB 구멍에 15MB를 넣고 1MB짜리 구멍을 만든다. 이 1MB 구멍은 훗날 그 어떤 프로세스도 들어갈 수 없어 장부만 차지하는 완전한 쓰레기(Dead wood)가 된다. 반면 First-Fit이 30MB 구멍에 15MB를 넣고 남긴 15MB 구멍은 훗날 10MB짜리 앱이 넉넉히 들어갈 수 있는 생명력 있는 구멍이다.

┌──────────┬────────────┬────────────┬─────────────────────┐
│ 평가 지표  │ First-Fit  │ Best-Fit   │ Worst-Fit         │
├──────────┼────────────┼────────────┼─────────────────────┤
│ 런타임 속도│ ⭐⭐⭐ (우수)│ ⭐ (최악)   │ ⭐ (최악)      │
│ 메모리 절약│ ⭐⭐ (보통)  │ ⭐ (오히려 독)│ ⭐⭐ (보통)  │
│ 실무 채택  │ 👑 표준 채택 │ 거의 안 씀   │ 거의 안 씀    │
└──────────┴────────────┴────────────┴─────────────────────┘

[매트릭스 해설] 컴퓨터 알고리즘의 역사에서 휴리스틱(Heuristics)이 완벽주의를 이긴 가장 대표적인 사례다. OS 커널 개발자들은 이론적으로 예쁜 것(Best-fit)보다 투박하지만 현장에서 빠르고 무난하게 돌아가는 것(First-fit)을 최종 스탠다드로 선택했다.

📢 섹션 요약 비유: 찰흙으로 인형을 만들 때, 남은 찰흙을 아끼려고 아주 미세하게 딱 맞게 떼어 쓰다 보면(Best-fit) 결국 쓸모없는 먼지 찰흙만 남아 버려지지만, 큼직하게 대충 떼어 쓰고 남은 큰 덩어리(First-fit)는 나중에 다른 인형을 만들 때 다시 뭉쳐 쓰기 훨씬 좋은 이치입니다.

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

실무 시나리오: C언어 malloc 엔진의 최적화

초기 malloc의 선택:
- 초창기 Unix/Linux의 malloc 함수는 순수하게 First-Fit을 채택했다. (때로는 Next-Fit 변형을 사용).
- 프로그램이 실행되며 수만 번의 동적 할당 요청이 들어오는데, 리스트 전체를 뒤지는 Best-Fit을 썼다간 프로그램이 기어 다니기 때문이다.
First-Fit의 한계와 Segregated Fit (격리 적합)의 등장:
- 하지만 First-Fit도 결국 O(N) 탐색이라, 오래 실행된 서버에서는 리스트 길이가 10만 개를 넘어가며 심각한 지연을 낳았다.
- 현대의 할당기(ptmalloc, jemalloc 등)는 First-Fit을 버리고, 빈 공간들을 크기별(8바이트, 16바이트, 32바이트...)로 아예 방을 여러 개 따로 나누어 관리하는 격리 적합(Segregated Fit)이나 버디 시스템으로 진화했다.
의사결정:
- 즉, First-Fit은 "크기가 섞여 있는 단일 리스트" 환경에서는 최강자지만, 실무 환경에서는 아예 리스트 자체를 크기별로 분리해두어 탐색 시간 자체를 O(1)로 만들어버리는 아키텍처로 진화했다.

메모리 단편화와의 영원한 전쟁 (50% 규칙)

First-Fit이 아무리 훌륭해도 가변 분할 환경에 얽힌 '50퍼센트 규칙'의 저주는 피할 수 없다. 통계적으로 시스템이 균형 상태에 이르면 무조건 1/3의 메모리가 외부 단편화로 증발한다. 따라서 First-Fit 알고리즘만으로는 최신 OS를 만들 수 없으며, 결국 하드웨어적으로 주소를 찢어버리는 페이징(Paging) 아키텍처 도입이 필수적 결론이 된다.

📢 섹션 요약 비유: 동네 구멍가게(초기 OS)에서는 물건을 그냥 눈에 띄는 맨 앞줄에 막 쌓아두는 것(First-fit)이 제일 빨랐지만, 아마존 물류창고(현대 OS) 규모가 되면 아예 크기별로 선반을 철저히 분리(Slab, 크기별 리스트)해 놔야 로봇이 1초 만에 찾아올 수 있는 아키텍처 혁신이 필요합니다.

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

정량/정성 기대효과

구분	내용
할당(Allocation) 시간 최소화	조건에 맞는 첫 구멍을 찾자마자 리턴하므로 CPU 사이클 낭비를 극도로 억제함
운영체제 스케줄러 부하 경감	메모리 할당 연산이 가벼워짐에 따라 컨텍스트 스위칭 등 다른 커널 작업의 응답성 향상
병합(Coalescing) 고속화	주소순 정렬과 결합할 경우, 프로세스 종료 시 양옆의 빈 공간을 합치는 작업이 매우 직관적임

결론 및 미래 전망

최초 적합 (First-Fit) 알고리즘은 복잡하고 유동적인 자원 배분 상황에서 "적당히 좋은 해답을 가장 빠르게 찾는 것"이 시스템 전체의 성능 측면에서 최선이라는 공학적 진리를 증명한 마스터피스다. 비록 현대 운영체제는 외부 단편화 자체를 없애기 위해 물리 메모리를 페이징으로 관리하지만, 애플리케이션 레벨의 힙(Heap) 공간을 관리하는 VMA(Virtual Memory Area) 탐색이나, 디스크 파일 시스템의 빈 블록(Free Block) 탐색 같은 곳에서는 이 First-Fit의 철학이 여전히 가장 기저에 깔린 기본 스탠다드로 활약하고 있다.

📢 섹션 요약 비유: 시험 시간(CPU 리소스)이 촉박할 때, 100점(최적 적합)을 맞으려다 반도 못 풀고 시간 초과로 망하는 것보다, 빠르게 80점(최초 적합)짜리 답안을 찾고 남는 시간에 검토하는 것이 수능(시스템 운영)의 절대 승리 공식입니다.

📌 관련 개념 맵 (Knowledge Graph)

최적 적합 (Best-Fit) | 공간 낭비를 최소화하려다 오히려 미세 단편화를 양산하고 탐색 속도마저 갉아먹는 반면교사 알고리즘
외부 단편화 (External Fragmentation) | First-Fit 알고리즘을 사용하더라도 피할 수 없는 가변 분할 방식의 근본적이고 치명적인 빈 구멍 낭비 현상
다음 적합 (Next-Fit) | 메모리 앞쪽에 작은 조각이 쏠리는 First-Fit의 단점을 막고자 마지막 탐색 위치부터 이어서 찾는 변형 기법
50퍼센트 규칙 (50-Percent Rule) | First-Fit 할당 하에서 프로세스가 점유한 공간 N에 대해 항상 0.5N의 공간이 단편화로 버려지는 통계적 법칙
병합 (Coalescing) | 쪼개진 빈 공간에 First-Fit이 또 다른 구멍을 내지 못하도록, 프로세스 종료 시 인접한 빈 공간을 하나로 묶는 회수 연산

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

최초 적합이 무엇인가요? 배가 고파서 냉장고 문을 열었을 때, 제일 처음 눈에 띄는 먹음직스러운 간식을 1초 만에 꺼내 먹는 방법이에요.
왜 그렇게 하나요? 저 안쪽에 더 맛있는 게 있는지 냉장고를 끝까지 다 뒤지다 보면 시간도 너무 오래 걸리고 문을 열어놔서 전기세(CPU 낭비)가 너무 많이 나오거든요.
무엇이 좋은가요? 시간을 엄청나게 아껴서 밥 먹고 빨리 게임을 하러 갈 수 있고, 사실 눈에 띄는 걸 아무거나 먹어도 배부르기는 똑같기 때문에 제일 똑똑한 방법이랍니다.