[크래프톤 정글] 동적 메모리 할당기 총정리

블로그 글: 동적 메모리 할당기 총정리: Implicit/Explicit List부터 단편화까지

우리가 C언어에서 malloc과 free를 사용할 때, 그저 필요한 메모리를 요청하고 돌려주는 편리한 함수라고 생각하기 쉽습니다. 하지만 그 이면에서는 프로그램의 성능과 안정성을 좌우하는 복잡하고 정교한 동적 메모리 할당기(Dynamic Memory Allocator)가 쉴 새 없이 움직이고 있습니다.

이번 포스트에서는 동적 메모리 할당기의 기본 개념부터 대표적인 구현 방식, 그리고 메모리 관리의 영원한 숙적인 단편화(Fragmentation) 문제와 해결책까지, 그 내부 동작 원리를 총정리해 보겠습니다.

---

1. 동적 메모리 할당기의 기본 원리

동적 메모리 할당기는 프로그램 실행 중에(runtime) 사용할 메모리 공간을 힙(Heap)이라는 영역에서 동적으로 할당하고 해제하는 시스템입니다.

핵심 기능

• 할당 (Allocation): 사용자가 요청한 크기의 메모리 블록을 힙에서 찾아 주소를 반환합니다. (malloc)
• 해제 (Deallocation): 사용이 끝난 메모리 블록을 다시 사용할 수 있도록 가용 상태로 만듭니다. (free)

이를 위해 할당기는 힙의 메모리 블록들을 두 가지 상태로 관리합니다.

• 사용 중인 블록 (Allocated Block): 현재 프로그램이 사용하고 있는 메모리.
• 가용 블록 (Free Block): 할당 가능하거나, 사용 후 해제된 메모리.

그렇다면 할당기는 각 블록의 크기와 상태를 어떻게 알 수 있을까요? 바로 모든 블록의 앞뒤에 붙는 메타데이터(Metadata) 덕분입니다.

메모리 블록의 구조: 헤더와 푸터

각 메모리 블록은 순수한 데이터(Payload) 외에, 자신을 설명하는 메타데이터를 가집니다.

+-------------------------------------------------+
|   헤더 (Header)   |   데이터 (Payload) ...  |  푸터 (Footer)  |
+-------------------------------------------------+

• 헤더 (Header): 블록의 시작에 위치하며, 최소한 블록의 크기와 할당 여부 정보를 담습니다.
• 푸터 (Footer): 블록의 끝에 위치하며, 헤더의 정보를 복사해 둡니다. 푸터는 나중에 설명할 블록 병합(Coalescing) 시 매우 중요한 역할을 합니다.

---

2. 가용 블록 관리 전략

할당기는 가용 블록을 어떻게 찾아내고 관리할까요? 이 관리 방식에 따라 할당기의 성능이 결정됩니다.

2.1. 묵시적 가용 리스트 (Implicit Free List)

가장 간단한 접근법입니다. 힙에 있는 모든 블록(사용 중인 블록 + 가용 블록)을 순서대로 연결해 놓은 구조입니다.

• 구조: 모든 블록이 크기순으로 메모리에 연속적으로 위치합니다.
• 탐색: malloc 요청이 오면 힙의 처음부터 끝까지 모든 블록의 헤더를 순차적으로 확인하며 적절한 크기의 가용 블록을 찾습니다.

// 묵시적 리스트의 헤더 (최적화된 형태)
// 크기와 할당 여부를 하나의 4바이트/8바이트 정수에 저장
// 예: 32비트 시스템에서 하위 1비트로 할당 여부(1=사용중, 0=가용) 표시
typedef struct {
    size_t size_and_alloc;
} block_header;

• 장점: 구현이 매우 간단하고, 블록 내에 추가적인 포인터가 필요 없어 메모리 오버헤드가 적습니다.
• 단점: 할당할 때마다 힙 전체를 탐색해야 할 수 있어 힙이 클수록 성능이 급격히 저하됩니다.

2.2. 명시적 가용 리스트 (Explicit Free List)

묵시적 리스트의 느린 탐색 속도를 해결하기 위한 방법입니다. 이름처럼 가용 블록들만을 별도의 연결 리스트(Linked List)로 관리합니다.

• 구조: 가용 블록의 데이터(Payload) 영역에 다음 가용 블록과 이전 가용 블록을 가리키는 포인터(next, prev)를 저장합니다.
• 탐색: malloc 요청이 오면, 사용 중인 블록은 건너뛰고 이 가용 리스트만 탐색하면 되므로 속도가 매우 빠릅니다.

// 명시적 리스트의 가용 블록 구조
typedef struct block {
    size_t size_and_alloc;  // 헤더
    struct block* next;     // 다음 가용 블록 포인터
    struct block* prev;     // 이전 가용 블록 포인터
    // ... 데이터 ...
    // ... 푸터 ...
} free_block;

• 장점: 탐색 성능이 묵시적 리스트에 비해 월등히 뛰어납니다.
• 단점: 가용 블록 내에 포인터를 저장할 추가 공간이 필요해 메모리 오버헤드가 발생하며, 리스트 관리 로직이 복잡해집니다.

2.3. 버디 할당기 (Buddy Allocator)

메모리를 2의 거듭제곱 크기로 나누어 관리하는 방식입니다. 분할과 병합이 매우 빠르지만, 요청 크기가 2의 거듭제곱이 아닐 경우 메모리 낭비(내부 단편화)가 발생할 수 있습니다.

---

3. 메모리의 숙적, 단편화 (Fragmentation)

동적 할당기의 성능을 저해하는 가장 큰 문제입니다. 단편화는 크게 두 종류로 나뉩니다.

3.1. 내부 단편화 (Internal Fragmentation)

할당된 블록 내부에 사용되지 않고 낭비되는 공간이 생기는 문제입니다.

• 예시: 10바이트를 요청했는데, 할당기가 최소 블록 크기인 16바이트를 할당했을 때 남는 6바이트.

• 해결책: 블록 분할 (Splitting)

  • 요청한 크기보다 큰 가용 블록을 찾았을 때, 블록을 정확히 요청한 만큼만 잘라내어 할당하고, 남은 부분을 새로운 가용 블록으로 만드는 기법입니다.

    // 분할 전
    [ 가용 블록 500B ]
    
    // 100B 할당 요청 후 분할
    [ 할당된 블록 100B ] [ 새로운 가용 블록 400B ]

3.2. 외부 단편화 (External Fragmentation)

가용 메모리 총량은 충분하지만, 그 공간이 여러 곳에 작은 조각으로 흩어져 있어 정작 요청된 크기의 연속된 블록을 할당하지 못하는 문제입니다.

• 예시: 힙에 50B, 80B 크기의 가용 블록이 흩어져 있어 총 130B의 여유 공간이 있지만, 100B 크기의 할당 요청은 실패합니다.

• 해결책: 블록 병합 (Coalescing)

  • 메모리를 해제(free)할 때, 인접한 가용 블록이 있다면 즉시 하나로 합쳐 더 큰 가용 블록을 만드는 기법입니다.

  • 이때 푸터가 결정적인 역할을 합니다. 어떤 블록을 해제할 때, 그 블록의 헤더를 보고 이전 블록의 위치를 계산한 뒤, 이전 블록의 푸터를 읽어 그 블록이 가용 상태인지 즉시 확인할 수 있습니다.

    // 병합 전
    [ 블록 1 ] [ 해제할 블록(가용) ] [ 블록 3(가용) ]
    
    // 병합 후: 해제할 블록과 블록 3을 합친다.
    [ 블록 1 ] [       하나의 큰 가용 블록       ]

---

4. 최적의 블록을 찾는 방법: 배치 정책 (Placement Policy)

가용 리스트에서 어떤 블록을 선택할 것인지 결정하는 알고리즘입니다.

• First Fit (최초 적합): 가용 리스트의 처음부터 탐색하여 크기가 맞는 첫 번째 블록을 할당합니다. 빠르지만, 리스트 앞쪽에 작은 조각들이 남기 쉽습니다.
• Next Fit (다음 적합): 마지막으로 할당했던 위치부터 탐색을 시작합니다. First Fit보다 힙을 골고루 사용하는 경향이 있습니다.
• Best Fit (최적 적합): 요청한 크기와 가장 비슷한(가장 작은 차이의) 가용 블록을 할당합니다. 내부 단편화를 줄이지만, 전체 리스트를 탐색해야 해서 느릴 수 있습니다.

---

결론: 보이지 않는 곳에서의 치열한 최적화

C언어의 표준 malloc은 보통 이 개념들이 혼합된 분리형 리스트(Segregated List)와 같은 고도화된 기법을 사용합니다. 이는 다양한 크기별로 가용 리스트를 여러 개 두어 탐색 성능과 메모리 효율을 극대화하는 방식입니다.

동적 메모리 할당기는 단순한 기능 제공을 넘어, 성능, 메모리 오버헤드, 단편화 문제 사이에서 끊임없이 줄다리기하는 시스템 공학의 정수입니다. malloc 한 줄 뒤에 숨겨진 이러한 원리를 이해한다면, 메모리를 더욱 효율적으로 사용하는 프로그램을 작성하는 데 큰 도움이 될 것입니다.