동적 할당과 malloc 내부

목표 학습 시간: 105분 + 복습 15분 · 전공 수준 정독용

이 챕터를 마치면: (1) 할당자가 OS의 페이지 단위와 프로그램의 잘은 요청 사이를 어떻게 잇는지 설명하고, (2) 묵시적·명시적·분리 free list를 구분하고, (3) 배치 정책과 splitting/coalescing(경계 태그)을 설명하고, (4) 내부/외부 단편화를 정량적으로 계산하고, (5) 현대 할당자가 멀티스레드에서 빠른 이유를 설명할 수 있다.

0. 학습 지도 (105분)

1. 할당자의 일

1.1 두 세계를 잇는 다리

힙(heap)은 OS가 프로세스에게 준 큰 메모리 영역이다. 할당자(allocator) 는 이 영역을 관리하며 두 요청을 처리한다.

• void *malloc(size_t n): 연속된 n바이트 이상을 찾아 시작 주소 반환.
• void free(void *p): 그 블록을 다시 "빈 공간"으로 표시.

문제의 본질은 세분성의 간극이다. OS는 메모리를 페이지(4KB) 단위로만 준다. 그런데 프로그램은 24바이트, 7바이트, 1메가바이트처럼 제멋대로 요청한다. 할당자는 "OS에서 큰 덩어리(페이지들)를 받아와, 프로그램의 잘은 요청들로 잘라 나눠주고, 반납된 걸 다시 합쳐 관리하는" 중간상이다.

1.2 힙은 어디서 오나 — sbrk와 mmap

할당자가 OS에게 메모리를 더 달라고 하는 두 통로:

• brk/sbrk: 힙의 끝(program break)을 위로 밀어 연속 영역을 늘린다. 작은 증분에 전통적으로 쓰임.
• mmap: 익명 매핑으로 큰 덩어리를 따로 받는다(세션 6). 큰 할당이나 독립적으로 반납하고 싶은 영역에 쓴다. glibc malloc은 임계 크기 이상의 요청은 mmap으로 직접 처리하고 free 시 munmap으로 OS에 바로 돌려준다.

즉 malloc(24)는 보통 OS를 부르지 않는다 — 이미 받아둔 힙 안에서 잘라 준다. OS 호출은 힙이 모자랄 때만 일어난다.

2. free list — 빈 공간을 어떻게 추적하나

할당자의 핵심 자료구조는 "지금 비어 있는 블록들의 목록"이다. 이걸 표현하는 세 방식을 깊이 보자.

2.1 블록 헤더와 묵시적 free list (implicit)

가장 단순한 설계: 모든 블록(사용 중이든 빈 것이든) 앞에 헤더를 둔다. 헤더에 크기와 사용 여부(allocated bit) 를 담는다. 블록 크기를 정렬 배수로 맞추면 하위 비트가 항상 0이라, 그 비트를 alloc 플래그로 재활용할 수 있다(공간 절약 기법).

힙 (한 줄로):
 [hdr|사용 32][hdr|빈 16][hdr|사용 48][hdr|빈 64] ...
   └ 각 헤더의 크기 필드로 "다음 블록"의 위치를 계산할 수 있다

크기를 알면 "현재 블록 주소 + 크기 = 다음 블록 주소"로 힙 전체를 훑을 수 있다. 이를 묵시적 free list라 한다(별도 포인터 없이 크기로 순회). 단점: 빈 블록을 찾으려면 사용 중 블록까지 전부 지나가야 해 할당이 O(전체 블록 수)로 느리다.

2.2 명시적 free list (explicit)

개선: 빈 블록 안에 다음/이전 빈 블록을 가리키는 포인터(next/prev)를 넣어 빈 블록들만 연결 리스트로 잇는다. 빈 블록의 페이로드 공간은 어차피 안 쓰니 거기에 포인터를 둔다(공짜).

빈 블록 내부:  [ hdr | next | prev | (남은 빈 공간) | footer ]

이제 할당 시 빈 블록만 순회하면 되니 훨씬 빠르다. free 시 이 리스트에 다시 넣는다(LIFO 또는 주소 순).

2.3 분리 free list (segregated)

실전 할당자의 핵심: 크기 클래스별로 free list를 따로 둔다. 예: {16}, {17–32}, {33–64}, {65–128}, … 각 구간마다 별도 리스트. malloc(20)이면 {17–32} 리스트만 보면 되니 탐색이 짧고, 같은 크기끼리 모여 관리가 단순하다. glibc의 bins, tcmalloc/jemalloc의 size class가 모두 이 아이디어다(6절).

3. 배치 정책 — 어느 빈 블록을 줄까

malloc(size)에 들어맞는 빈 블록이 여럿이면, 어느 걸 줄지 고르는 전략이 성능·단편화를 가른다.

• first-fit: 리스트를 처음부터 훑어 처음 맞는 블록. 빠르지만, 앞쪽에 작은 자투리가 쌓이는 경향.
• next-fit: 지난번 멈춘 곳부터 탐색. first-fit의 변형으로 앞쪽 재탐색을 줄임.
• best-fit: 가장 딱 맞는(가장 작은) 블록. 큰 블록을 아껴 외부 단편화에 유리하지만, 매번 전체를 봐야 하고 아주 작은 자투리가 많이 생길 수 있음.

트레이드오프 요약: first-fit은 빠름·중간 단편화, best-fit은 느림·낮은 외부 단편화(대신 미세 자투리). 실전 분리 리스트에선 "맞는 크기 클래스에서 first-fit"처럼 둘을 절충한다.

4. splitting과 coalescing — 단편화와 싸우는 두 무기

4.1 splitting(분할)

요청보다 큰 빈 블록을 줄 때, 필요한 만큼만 떼고 나머지는 다시 빈 블록으로 둔다. 안 그러면 큰 블록을 통째로 작은 요청에 줘 내부 낭비가 커진다.

빈 64B 블록에서 malloc(24) →  [사용 24 + hdr][빈 (나머지)]   (분할)

4.2 coalescing(병합)과 경계 태그(boundary tag)

free 시 인접한 빈 블록과 합쳐 큰 블록으로 되돌린다. 병합이 없으면 빈 공간이 점점 잘게 쪼개져 외부 단편화가 악화된다.

free(B):  [사용 A][빈 B][빈 C]  →  병합  →  [사용 A][   빈 B+C   ]

문제: "다음 블록"은 현재 헤더의 크기로 쉽게 찾지만, "이전 블록" 은? 헤더만으론 앞으로 갈 수 없다. Knuth의 경계 태그(boundary tag) 가 이를 푼다 — 블록 끝에 footer(크기 복제) 를 둔다. 그러면 현재 블록 바로 앞 바이트들이 이전 블록의 footer이므로, 거기서 이전 블록 크기를 읽어 시작 주소를 계산할 수 있다 → 양쪽 인접 블록과 O(1)로 병합 가능.

블록 구조 (경계 태그):
 [ header(크기|alloc) | ... 페이로드 ... | footer(크기|alloc) ]
                                          └ 다음 블록이 "이전"을 찾을 때 읽는다

대가: 모든 블록이 footer만큼 오버헤드를 더 진다(내부 단편화 증가). 그래서 일부 설계는 "이전 블록이 사용 중일 땐 footer 생략" 같은 최적화를 쓴다.

5. 단편화 — 정량적으로

단편화: 전체로는 공간이 충분한데 "원하는 연속 블록"이 없는 상태. 두 종류를 구분하고 숫자로 보자.

5.1 내부 단편화 (internal)

요청보다 크게 떼어줘 블록 안에 못 쓰는 부분이 남는 것. 원인: 헤더/footer 오버헤드, 정렬 반올림, 최소 블록 크기, 크기 클래스 반올림.

예제. 헤더 8B, 16B 정렬, 최소 블록 32B인 할당자에서 malloc(20)을 하면:

필요 = 헤더 8 + 페이로드 20 = 28
16B 정렬로 올림 → 32B 블록 할당
내부 단편화 = (블록 32) − (헤더 8) − (요청 20) = 4 바이트 낭비 + 헤더 8 오버헤드

요청 20에 실제로 32를 소비했다 — 작은 요청일수록 헤더·정렬 오버헤드 비율이 커진다. 그래서 잘은 객체를 수백만 개 만들면 내부 단편화가 메모리를 크게 좀먹는다.

5.2 외부 단편화 (external)

빈 공간이 작은 조각으로 흩어져, 합치면 충분한데 연속이 아니라 큰 요청을 못 받는 것.

예제. 16B 빈 블록 3개가 사용 중 블록들 사이사이에 흩어져 있다(총 48B 여유). 그런데 malloc(32)(연속 32B)는 실패한다 — 48B가 비어 있어도 한 덩어리로 32B가 없기 때문. coalescing이 이 문제를 줄이지만, 인접하지 않은 조각은 합칠 수 없다.

핵심 대비: 내부 = "준 블록 안의 낭비"(반올림·오버헤드), 외부 = "블록들 사이의 흩어진 낭비"(연속 부족). splitting은 내부를, coalescing은 외부를 줄인다.

6. 현대 할당자 — 왜 더 빠르고 멀티스레드에 강한가

ptmalloc(glibc), tcmalloc(Google), jemalloc(FreeBSD/Facebook)의 공통 아이디어.

6.1 크기 클래스(size classes)

임의 크기 대신 16, 32, 48, 64, … 정해진 등급으로 반올림해 같은 크기끼리 모아 관리한다. 탐색이 짧고(해당 클래스 리스트만), 같은 크기라 splitting/coalescing 고민이 줄고, 재사용이 빠르다. 대가는 약간의 내부 단편화(반올림).

6.2 멀티스레드 문제와 per-thread 캐시

가장 중요한 포인트. 여러 스레드가 하나의 전역 힙을 공유하면, malloc/free마다 락을 걸어야 해 코어가 늘수록 락 경쟁이 병목이 된다. 해법:

• per-thread 캐시(tcache/thread cache): 스레드마다 작은 캐시에 자주 쓰는 크기 클래스의 빈 블록을 쟁여둔다. 대부분의 malloc/free를 락 없이 스레드 로컬에서 처리 → 경쟁 소멸. (glibc는 2.26부터 tcache 도입.)
• 아레나(arena): 스레드들을 여러 독립 힙(아레나)에 분산해, 락을 잡더라도 경쟁하는 스레드 수를 줄인다.
• 스레드 캐시가 비거나 넘치면 중앙(아레나)에서 채우거나 반납한다.

한 줄: 현대 할당자의 속도는 알고리즘보다 "락을 얼마나 피하는가(스레드 로컬화)"에서 나온다. 멀티코어 시대의 핵심 설계.

6.3 보너스: 작은 객체 vs 큰 객체

작은 객체는 크기 클래스 + 스레드 캐시로, 큰 객체는 mmap 직할로 처리하는 식의 이원화도 흔하다(큰 객체는 free 시 OS에 바로 반납해 RSS를 낮춤).

7. 힙 메타데이터와 보안 (세션 9 예고)

할당자의 헤더·free list 포인터는 힙 안에, 사용자 데이터 바로 옆에 산다. 그래서:

• 힙 버퍼 오버플로가 인접 블록의 헤더/포인터를 덮으면 할당자 내부 구조가 깨진다.
• double free는 같은 블록을 free list에 두 번 넣어 리스트를 모순 상태로 만든다.

이런 손상은 크래시뿐 아니라 임의 메모리 쓰기로 악용될 수 있다. 그래서 현대 할당자는 헤더에 무결성 검사(예: free list 포인터 보호)를 넣고, 세션 9의 ASan/Valgrind가 이런 손상을 잡는다.

8. 흔한 오해 바로잡기

• ❌ "malloc은 매번 OS를 부른다." → 보통은 이미 받아둔 힙에서 잘라 준다. OS 호출(sbrk/mmap)은 힙이 모자랄 때만.
• ❌ "free하면 OS에 바로 돌아간다." → 대개 할당자의 free list로 돌아가 재사용을 기다린다(큰 mmap 블록 등 일부만 즉시 munmap).
• ❌ "단편화는 한 종류다." → 내부(반올림·오버헤드)와 외부(연속 부족)는 원인도 처방도 다르다.
• ❌ "best-fit이 항상 낫다." → 외부 단편화엔 유리해도 느리고 미세 자투리를 많이 만든다. 실전은 분리 리스트로 절충.
• ❌ "멀티스레드 malloc 속도는 알고리즘 문제." → 핵심은 락 경쟁. 스레드 로컬 캐시가 결정적.

9. 한 장 정리

• 할당자는 OS 페이지 단위와 프로그램의 잘은 요청 사이를 잇는 중간상(힙은 sbrk/mmap에서).
• free list: 묵시적(크기로 순회, 느림) → 명시적(빈 블록만 연결) → 분리(크기 클래스별, 실전).
• 배치: first/next/best-fit의 속도·단편화 트레이드오프.
• splitting(내부↓)과 coalescing(외부↓), 후자는 경계 태그(footer) 로 이전 블록과 O(1) 병합.
• 단편화: 내부(블록 안 낭비, 반올림·오버헤드) vs 외부(흩어진 연속 부족).
• 현대 할당자는 크기 클래스 + per-thread 캐시 + 아레나로 빠르고 멀티스레드에 강하다(핵심은 락 회피).

10. 복습 (15분) — 답을 가리고

Q1. malloc(24)가 대개 OS를 안 부르는 이유는?

할당자가 이미 sbrk/mmap으로 받아둔 힙 영역에서 빈 블록을 잘라 주기 때문. OS 호출은 힙이 모자랄 때만 일어난다.

Q2. 묵시적·명시적·분리 free list의 차이를 한 줄씩.

묵시적: 모든 블록을 헤더 크기로 순회(빈 블록 찾기에 사용 중 블록까지 지나가 느림). 명시적: 빈 블록 안 next/prev로 빈 블록만 연결(빠름). 분리: 크기 클래스별로 리스트를 따로 둬 탐색이 짧고 관리가 단순.

Q3. coalescing에서 "이전 블록"을 어떻게 찾나? 그 대가는?

경계 태그 — 블록 끝 footer에 크기를 복제해, 현재 블록 바로 앞이 이전 블록의 footer이므로 거기서 이전 블록 크기를 읽어 시작 주소를 구한다(O(1) 병합). 대가는 모든 블록이 footer 오버헤드를 져 내부 단편화가 는다.

Q4. 헤더 8B, 16B 정렬, 최소 32B 할당자에서 malloc(20)의 내부 단편화를 계산하라.

헤더 8 + 페이로드 20 = 28 → 16B 정렬로 32B 할당. 내부 단편화 = 32 − 8(헤더) − 20(요청) = 4바이트 낭비 + 헤더 8 오버헤드. 요청 20에 32를 소비.

Q5. 16B 빈 블록 3개(총 48B)가 흩어져 있는데 malloc(32)가 실패한다. 무슨 단편화이며 무엇으로 줄이나?

외부 단편화. 총 여유는 충분해도 연속 32B가 없어서다. coalescing(인접 빈 블록 병합)으로 줄이지만, 인접하지 않은 조각은 합칠 수 없다.

Q6. 멀티스레드에서 현대 할당자가 빠른 핵심 메커니즘은?

per-thread 캐시. 스레드마다 빈 블록을 쟁여둬 대부분의 malloc/free를 락 없이 스레드 로컬로 처리해 전역 락 경쟁을 없앤다. 아레나로 경쟁 스레드 수도 분산한다.

Q7. 세션 2·6과의 연결을 한 줄씩.

세션 2: malloc은 max_align_t 정렬을 보장해 어떤 타입도 안전(정렬). 세션 6: 큰 할당과 힙 확장은 mmap/sbrk로 OS의 가상 메모리에서 받아온다.

다음: 세션 8 — 메모리 관리 전략과 GC (이어지는 파일)