[OS] 운영체제 메모리 관리: Free-Space Management

malloc()과 free()는 단순한 함수가 아니다. 그 뒤에는 복잡한 공간 관리 전략이 숨어 있다.

 

Free-Space Management란 무엇인가

운영체제(OS)는 CPU, 메모리, 저장장치 등 여러 자원을 효율적으로 관리한다. 그중에서도 메모리 관리(memory management) 는 프로그램 실행의 핵심 요소이다.

 

Free-Space Management란, 프로세스가 요청한 동적 메모리를 어떻게 배분하고, 해제된 공간을 다시 재활용할 것인지를 결정하는 기술이다.

 

즉,

malloc()으로 요청한 메모리를 어디에 줄지, free()로 반환된 공간을 어떻게 관리할지를 다루는 것이 바로 이 장의 핵심이다.

 

 

---

 

정적 할당과 동적 할당

	정적할당	동적할당
시점	컴파일 타임	실행 타임
크기	고정	가변
예시	char name[16];	malloc(), free()
특징	빠르고 단순하지만 유연성 부족	실행 중 크기 조절 가능

정적 할당은 프로그램이 실행되기 전에 크기가 고정된다. 반면 동적 할당은 런타임에 메모리를 요청하거나 반환할 수 있다.
대부분의 현대 프로그램은 입력 크기나 데이터 구조가 가변적이므로 동적 메모리를 사용한다.

 

 

---

 

 

malloc()이 어려운 이유: 단편화(Fragmentation)

동적 메모리 관리의 가장 큰 어려움은 단편화(Fragmentation) 이다.

 

외부 단편화 (External Fragmentation)

전체 여유 공간은 충분하지만, 연속된 블록이 없어서 큰 요청을 처리하지 못하는 현상이다.
예를 들어 아래와 같은 메모리 상태를 가정한다.

 

총 20바이트의 여유 공간이 있지만, 연속된 15바이트 공간이 없어 15바이트 요청은 실패한다.

 

내부 단편화 (Internal Fragmentation)

요청한 크기보다 조금 더 큰 블록을 할당하여 내부에 낭비가 생기는 경우이다. 외부 단편화는 메모리 바깥이 쪼개지는 현상이고, 내부 단편화는 블록 내부의 낭비를 의미한다.

 

 

가장 중요한 사항은 fragment를 효율적으로 다뤄서 최소화하는 것이다.

 

 

---

 

 

Free Space Management Overview

이 장에서는 메모리 관리의 세부적인 동작 원리를 단계적으로 다룬다.

핵심은 "메모리를 어떻게 나누고, 병합하고, 추적하며, 어떤 전략으로 선택할 것인가"이다.

 

구성 요소

1. Low-level Mechanisms
   • Splitting: 큰 블록을 작은 블록으로 나누어 할당한다.
   • Coalescing: 인접한 free 블록을 병합하여 단편화를 줄인다.
   • Tracking & Embedding: 블록 내에 헤더 정보를 기록하여 관리한다.
2. Allocation Strategies
   • Best Fit
   • Worst Fit
   • First Fit
   • Next Fit
   • Buddy Allocator
   • Slab Allocator

이 메커니즘과 전략들을 조합하여, 운영체제는 동적 메모리 요청을 가능한 효율적으로 처리한다.

 

 

기본 전제 조건

일반적인 malloc()/free() 기반의 힙 관리 시스템을 가정한다. 이를 바탕으로 Free-Space Management의 특성과 제약을 정의한다.

1. 관리 대상은 힙(Heap)이다.
   • malloc()과 free()가 관리하는 영역은 heap이라 부른다.
   • 이 영역은 운영체제가 제공한 연속된 바이트 공간이다.
2. Free List로 빈 공간을 관리한다.
   • 힙 내의 빈 영역들은 연결 리스트 형태의 Free List로 추적한다.
3. 외부 단편화(External Fragmentation)가 주요 문제이다.
   • 내부 단편화도 존재하지만, 힙 관리에서는 일반적으로 외부 단편화가 더 큰 문제로 취급된다.
4. 이미 할당된 블록은 이동할 수 없다.
   • 한 번 할당된 메모리는 이동(compaction)할 수 없으며, 잘못된 위치 선택이 영구적인 단편화를 유발할 수 있다.
5. 힙은 고정된 연속 메모리 구역이다.
   • 관리자는 단일 연속 공간을 대상으로 동작하며, 비연속적인 다중 힙은 고려하지 않는다.

이러한 전제를 기반으로, Free List를 관리하고 다양한 전략을 비교하게 된다.

 

 

---

 

 

Low-level Mechanisms

 

Free List: 빈 공간을 추적하는 구조

동적 메모리 관리자는 Free List를 사용해 남은 공간을 관리한다. Free List는 현재 비어 있는 메모리 구간들의 연결 리스트이다.

초기 힙(heap)은 전부 비어 있는 하나의 블록으로 구성된다.

 

 

 

Splitting

만약 여기서 10바이트 보다 작은 할당을 요청하면, allocator는 splitting을 한다.

 

예를 들어서 1 byte의 요청이 왔다고 가정하자.

malloc()은 address 20을 반환하고, Free list는 다음과 같이 업데이트된다.

• Free region은 21부터 시작한다.
• 남아있는 크기는 9byte이다.

 

 

과정을 시각화하면 다음과 같다. 

 

이와 같은 동작이 Splitting(분할) 이다. 반대로 인접한 free 블록을 합치는 것이 Coalescing(병합)이다.

 

 

Coalescing

coalescing(병합)은 인접한 free 블록들을 하나로 합치는 과정이다. free()가 호출될 때 단순히 블록을 리스트에 추가하기만 하면, 리스트에는 여러 개의 작은 조각이 생긴다.

 

만약 요청 크기가 어느 하나의 free chunk보다 크다면, 전체 여유 공간이 충분하더라도 연속된 블록이 없어 할당이 실패할 수 있다. 이 문제를 해결하기 위해 coalescing을 수행한다.

 

즉, 새로운 블록이 추가될 때 앞이나 뒤의 블록이 free 상태이면 하나로 합친다. 이를 통해 fragmentation을 해결하고 더 큰 연속적인 free space을 가진다.

 

 

---

 

 

free()가 크기를 알 수 있는 이유

free()는 인자로 크기를 받지 않는다. 그럼에도 정확히 해제할 수 있는 이유는, malloc()이 블록 앞에 메타데이터(header)를 붙이기 때문이다.

 

typedef struct {
    int size;
    int magic;
} header_t;

 

malloc()은 요청 크기보다 더 큰 공간을 잡고, 앞부분에 header를 기록한다. free()는 포인터를 header 크기만큼 되돌려 해당 블록의 크기를 계산할 수 있다. 

 

따라서 N byte 요청이 오게되면, allocator는 N + header size의 free chunk를 찾게된다.

 

 

---

 

 

Free List 내부에 구현하기 (Embedding a Free List)

malloc()의 내부는 단순한 배열이 아니라, 메모리 그 자체가 연결 리스트로 동작한다.

 

Free List를 힙 내부에 직접 구현된다.

Free List는 남은 빈 공간을 추적하기 위한 자료구조이다. 이전까지는 이를 개념적으로 별도의 리스트처럼 다뤘지만, 실제 구현에서는 malloc()으로 리스트를 만들 수 없기 때문에 그 리스트 자체를 힙 내부에 직접 포함(embedding) 해야 한다.

 

즉, 관리자가 사용하는 메타데이터조차 사용자가 사용할 힙 공간 안에서 관리되어야 한다.

 

 

Free List 초기화 

초기에는 운영체제가 제공하는 빈 메모리 영역(예: 4KB)을 힙으로 사용한다.
이 영역을 가리키는 포인터가 Free List의 head가 된다.

typedef struct __node_t {
    int size;
    struct __node_t *next;
} node_t;

• size: 해당 블록의 크기
• next: 다음 free 블록을 가리키는 포인터

 

초기 상태에서는 head 노드가 전체 4KB(4096B) 중, 구조체 크기만 제외한 영역을 나타낸다.

node_t *head = mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0);
head->size = 4096 - sizeof(node_t);
head->next = NULL;

 

 

 

즉, Free List는 다음과 같이 시작한다.

 

메모리 할당

할당 과정은 다음 단계로 진행된다.

1. Free List에서 요청 크기보다 큰 블록을 찾는다.
2. 찾은 블록을 split(분할) 하여 필요한 크기만큼만 할당한다.
3. 남은 부분은 Free List에 그대로 유지한다.

예를 들어, 요청 크기가 100바이트일 경우 실제로는 헤더 8바이트가 포함되어 108바이트를 할당한다.

 

 

 

메모리 해제 과정

free()가 호출되면 다음과 같은 절차가 실행된다.

1. 사용자 포인터 앞의 header 위치로 이동한다.
2. header에서 블록 size를 읽어낸다.
3. 해당 블록을 Free List의 head 위치에 삽입한다.

void free(void *sptr) {
    header_t *hptr = sptr - sizeof(header_t);

    node_t *tmp = head;
    head = (node_t *) hptr;
    head->next = tmp;
}

즉, 새로 해제된 블록이 Free List의 가장 앞에 추가된다. 따라서 Free List에는 여러 개의 빈 블록 노드가 존재하게 된다.

 

 

첫 번째 블록을 해제하는 경우를 알아보자

 

• 예를 들어 첫 번째 블록의 사용자 데이터 시작 주소는 16KB(16384) + 8바이트 헤더 크기인 16392가 된다.
• 헤재하게 되면 100byte가 free로 남게되고 다음 next 주소 값은 16392 + 100인 16492가 된다.

 

마지막 블록을 해제하는 경우를 알아보자

 

• 마지막 블록을 해제하면 모든 블록이 free 상태가 된다.
• 이때 각 free 노드는 Free List의 head에 삽입되므로 연결된 순서는 할당/해제 순서에 따라 달라질 수 있다.

그러나, 이 상태에서도 Free List는 여러 개의 작은 조각으로 나뉘어 있다.

 

 

여기서의 문제와 Coalescing

위의 상태에서는 전체 힙이 사실상 비어 있지만, Free List에는 여러 개의 작은 블록이 등록되어 있다.

이렇게 되면 총 공간은 충분하지만, 큰 연속 블록이 없어서 큰 요청이 실패할 수 있다. (Fragmentation)

이를 해결하기 위해 병합(coalescing) 을 수행한다.

Coalescing 동작 예시

즉, 인접한 free 블록을 하나로 합쳐 외부 단편화를 줄이는 과정이다. 결과적으로 Free List는 다시 단 하나의 노드만 가지게 된다.

 

 

 

---

 

 

 

Free Space Management Strategies 

메모리 관리자의 목표는 두 가지이다.

1. 빠른 할당 속도
2. 단편화 최소화

그러나 이 두 가지는 서로 충돌하는 경우가 많다. 할당 요청의 패턴은 예측할 수 없기 때문에 항상 최선인 전략은 존재하지 않는다.

 

다음과 같은 대표적 전략들을 알아보자.

 

 

Best Fit 

정의

• free list에서 요청을 만족할 수 있는 가장 작은 블록을 찾는다.

장점

• 남는 조각이 최소가 되어 내부 단편화를 줄이는 경향이 있다.

단점

• free list 전체를 탐색해야 하므로 느리다.
• 오히려 아주 작은 조각들이 많이 남아 외부 단편화가 발생하기도 한다.

예시
free list: 10, 25, 15, 30, 20
요청: 18
→ 선택: 20

 

 

Worst Fit 

정의

• free list에서 가장 큰 블록을 선택하여 분할한다.

장점

• 남는 블록도 큰 편이므로, 이후 요청을 처리하기 좋을 가능성이 있다.

단점

• 실제로는 단편화를 줄이지 못하는 경우가 많으며, 전체 탐색 비용도 크다.
• 실전에서 자주 사용되지 않는다.

예시
free list: 10, 25, 15, 30, 20
요청: 18
→ 선택: 30

First Fit 

정의

• free list를 앞에서부터 탐색하여 처음으로 요청을 만족하는 블록을 선택한다.

장점

• 빠르고 전체 탐색이 필요 없다.
• 단순한 구현으로 높은 실용성을 가진다.

단점

• free list 앞부분에 작은 조각이 쌓여 단편화가 발생할 수 있다.

예시
free list: 10, 25, 15, 30, 20
요청: 18
→ 선택: 25

Next Fit 

정의

• First Fit과 유사하지만, free list의 마지막 검색 지점부터 탐색을 진행한다.

장점

• free list 앞부분에 작은 조각이 몰리는 현상을 완화한다.
• 탐색 비용이 낮다.

단점

• 특정 패턴에서는 오히려 단편화를 야기할 수 있다.

예시
free list: 10, 25, 15, 30, 20
현재 탐색 시작 지점: 15
요청: 18
→ 선택: 30

---

 

 

커널 전략: Buddy Allocator 

위의 전략들은 사용자 수준 malloc()에서도 사용되지만, 운영체제 커널은 더 빠르고 예측 가능한 방식이 필요하다.
이를 위해 Buddy Allocator라는 구조를 사용한다.

Buddy Allocator의 필요성 

커널은 다음과 같은 특징을 가진다.

• 2ⁿ 크기의 페이지(4KB 등)를 자주 할당한다.
• 매우 빠른 할당/해제가 필요하다.
• 단편화가 증가하면 시스템 전체가 불안정해진다.

일반 free list기반 전략은 이러한 요구를 충족시키기 어렵기 때문에 버디 시스템(buddy system)이 등장했다.

Buddy Allocator는 2ⁿ 크기의 블록들만 사용한다.

예: 1KB, 2KB, 4KB, 8KB, 16KB …

이를 위해 크기별로 N+1개의 free list를 만든다.

• freelist[0] → 1KB
• freelist[1] → 2KB
• freelist[2] → 4KB

할당 과정

1. 요청을 만족하는 가장 작은 2ⁿ 블록을 찾는다.
2. 없으면 더 큰 블록을 반복적으로 2로 나누어(split) 사용한다.
3. 나머지 절반(버디)는 free list에 저장한다.

 

예시

64KB 메모리 공간에서 7KB 요청
→ 64KB → 32KB → 16KB → 8KB 블록 선택
내부 단편화는 있지만 관리가 단순해진다.

 

 

Buddy Allocator 해제 & 병합 

해제 과정은 다음과 같다.

1. 해제된 블록의 buddy 주소를 계산한다.
2. buddy가 free 상태면 병합(coalesce)한다.
3. 병합된 블록을 상위 크기 free list에 저장한다.
4. 가능하면 반복적으로 계속 병합한다. (8KB → 16KB → 32KB..)

 

 

• 큰 블록을 split할 때 사용되지 않은 절반은 buddy 블록으로 free list에 들어간다.
• 반대로 free할 때는 해당 buddy가 free 상태라면 두 블록이 병합되어 더 큰 블록이 된다.
• 16KB는 또 buddy를 찾고 그 과정이 재귀적으로 반복된다.
  
  

 

위 그림과 같이 buddy주소를 찾을 수 있다.

 

Buddy Allocation 예시

freelist[k] 는 2ᵏ 크기의 블록을 저장한다.
예시에서는 특정 블록들이 할당되거나 해제되며 각 free list의 값이 변화한다.

• 블록을 할당하면 더 큰 블록을 split 하고
• 블록을 free하면 buddy와 병합하여 더 큰 free 블록이 된다.

이 시스템은

• 빠르고(정해진 크기),
• 병합이 자동적이고,
• 단편화가 비교적 낮다.

 

---

 

 

Slab Allocator

Buddy Allocator가 페이지 단위(4KB 단위) 메모리를 관리한다면, Slab Allocator는 커널 객체(task_struct, inode 등) 를 관리한다.

 

Slab Allocator의 필요성

커널은 같은 구조체를 반복적으로 할당하고 해제한다.

• task_struct (~1.7KB)

이런 객체들은 크기가 고정되어 있고 많이 생성되므로, 매번 buddy system으로 페이지 단위로 할당하는 것은 비효율적이다.

 

그러므로 커널은

"같은 크기의 객체를 위한 전용 캐시를 만들자" 라는 개념으로 Slab Allocator를 사용한다.

 

Slab 구조

Slab Allocator는 다음과 같은 구조를 가진다.

1) Cache

• 특정 객체 타입을 위한 전용 저장소
• 예: inode_cache, task_struct_cache

2) Slab

• 여러 페이지가 묶인 덩어리
• Slab 하나에는 동일한 객체가 여러 개 들어간다

3) Bitmap

• 각 슬롯이 free인지 used인지 표시하는 비트 배열
• 빠른 탐색이 가능하다 (스캔할 필요 없음)

 

Slab 동작 방식

할당 과정

1. 해당 객체의 cache를 찾는다.
2. partial slab에 free 슬롯이 있으면 그 슬롯을 사용한다.
3. 없다면 empty slab에서 할당한다.
4. empty slab도 없다면 buddy allocator에서 새 slab을 가져온다.

해제 과정

1. bitmap에서 해당 비트를 0으로 바꾼다.
2. slab이 완전히 비면 empty slab이 된다.

장점

• 매우 빠른 성능
• 외부 단편화가 거의 없음
• 동일 객체 재사용으로 캐시 효율 증가
• 커널에서 널리 쓰는 고성능 전략

 

 

 

 

 

출처: 경북대학교 한명균 교수님, "운영체제" 강의 자료