CSAPP 9장 파트 1: 왜 allocator가 필요한가?

2026. 10. 1. 21:51ㆍ크래프톤 정글/포스팅

1. 문제의 출발: 프로그램이 필요한 메모리 크기를 미리 알 수 없다

프로그램이 필요로 하는 메모리 크기는 실행해봐야 아는 경우가 많습니다. 예를 들어 "정수 n개를 입력받아 저장하라"는 프로그램에서 n은 실행 중에 입력으로 들어옵니다.

 

가장 단순한 해결책은 정적 배열입니다.

#define MAXN 15213
int array[MAXN];     // 크기를 코드에 박아둠

하지만 이 방식에는 한계가 있습니다.

  • MAXN은 코드를 만들 때 넣어둔 임의의 숫자일 뿐이고, 실제 사용할 수 있는 메모리 크기, 사용자가 필요한 메모리 크기와 무관합니다.
  • 사용자가 MAXN보다 큰 메모리를 요청하는 경우 그냥 실패합니다.
  • 더 키우려면 코드를 고치고 다시 컴파일해야 합니다. (유지보수 지옥) 

그래서 필요한 것은 동적 메모리 할당입니다. 

array = (int *)Malloc(n * sizeof(int));   // n을 읽은 뒤에 크기 결정
for (i = 0; i < n; i++)
    scanf("%d", &array[i]);
free(array);
  • 실행 중에, 필요한 크기를 정해서 메모리를 빌리고, 다 쓰면 돌려주는 것 → 동적 메모리 할당
  • n을 알게 된 후에 필요한 만큼 할당하므로, 크기 제한은 사용 가능한 가상 메모리뿐입니다.
  • 동적 할당은 유용하지만, 제대로 쓰려면 allocator가 어떻게 동작하는지 알아야 합니다. 

2. 동적으로 할당할 메모리를 어떻게 빌려와야하나?

메모리를 실제로 가진 쪽은 커널입니다. 그렇다면 애플리케이션이 매번 커널에게 직접 요청하면 될까요? 책은 mmap이라는 직접 요청 방법이 있다고 소개하지만, 이렇게 쓰는 것은 불편하고 이식성도 떨어진다고 말합니다. 작은 크기의 요청이 수없이 오가는데, 그때마다 커널과 주고받는 것은 부담이 크기 때문입니다.

 

그래서 allocator라는 중간 관리자를 둡니다. 실행 중에 메모리가 필요해지면 allocator가 커널에게 힙 영역을 조금씩 늘려 달라고 요청하고(sbrk), 늘려 받은 영역 안에서는 커널에 가지 않고 잘게 나눠 빌려주고 회수합니다. 작은 요청마다 커널에 갈 필요가 없어지는 것입니다.

애플리케이션  ──(malloc/free)──▶  allocator  ──(sbrk)──▶  커널
 "40바이트 줘"                  힙을 잘게 나눠              "힙 영역 자체를
 "그거 반납"                    빌려주고 회수                 넓혀줘"
  • allocator: 커널에게서 큰 영역(힙)을 받아두고, 그 안을 잘게 나눠 빌려주고 회수하는 관리자
  • sbrk: 힙이 모자랄 때만 allocator가 커널에게 하는 요청
  • malloc/free: 애플리케이션이 allocator에게 메모리를 요청·반납하는 창구

한가지 중요한 점은, 힙은 미리 크게 받아두는 영역이 아니라 필요할 때 늘려 가는 영역입니다. allocator는 가진 힙 안에서 먼저 빈 블록을 찾고, 없을 때만 넉넉한 단위로 sbrk해서, 커널에 가는 횟수를 줄입니다. allocator의 일 대부분은 "이미 받아둔 힙 안에서의 관리"이고, sbrk는 영역이 모자랄 때의 마지막 수단입니다.

3. 힙은 어떻게 생겼나

프로세스는 자기만의 가상 주소 공간(virtual address space)을 가집니다. 힙(heap)은 그 안의 한 영역입니다.

높은 주소
   ┌──────────────────────┐
   │        ...           │
   ├──────────────────────┤ ← brk (힙의 끝, "top of the heap")
   │         Heap         │
   │          ↑           │   위쪽(높은 주소)으로 자란다
   ├──────────────────────┤
   │ Uninitialized (.bss) │
   │ Initialized (.data)  │
   │ Code (.text)         │
   └──────────────────────┘
낮은 주소
  • 힙은 .bss 바로 위에서 시작해서 높은 주소 쪽으로 자랍니다.
  • 커널은 프로세스마다 brk라는 변수를 관리하고, 이것이 힙의 끝을 가리킵니다.
  • allocator는 이 힙을 크기가 제각각인 블록(block)들의 모음으로 관리합니다. 블록은 연속된 메모리 조각이고 둘 중 하나입니다.
    • allocated: 애플리케이션이 쓰도록 예약됨
    • free: 할당받을 수 있는 상태

4. malloc, sbrk, free 

#include <stdlib.h>
void *malloc(size_t size);   // 성공: 블록 포인터, 실패: NULL
void  free(void *ptr);       // 반환값 없음

#include <unistd.h>
void *sbrk(intptr_t incr);   // 성공: 이전 brk, 실패: -1

malloc

  • 최소 size 바이트 이상의 블록을 주고, 어떤 데이터 타입이든 담을 수 있게 정렬(aligned) 되어 있습니다.
    • 32비트: 주소가 항상 8의 배수
    • 64비트: 주소가 항상 16의 배수
  • 실패하면(예: 가상 메모리보다 큰 요청) NULL을 반환하고 errno를 설정합니다.
  • 메모리를 초기화하지 않습니다. 0으로 채워진 메모리가 필요하면 calloc, 크기를 바꾸려면 realloc을 씁니다. 

free

  • 인자 ptr은 malloc/calloc/realloc이 돌려준 포인터 그대로여야 합니다. 아니면 동작이 undefined입니다.
  • 반환값이 없어서 잘못 써도 알려주지 않기 때문에, 나중에 이상한 런타임 오류로 나타납니다(9.11에서 다룸). 지금은 "free는 틀려도 조용하다" 정도만 기억하세요.

sbrk 

sbrk(100) 전:  [ ...힙... ]|              brk = 0x1000
sbrk(100) 후:  [ ...힙... ][ 새 100B ]|    brk = 0x1064
                          ↑
               반환값 = 이전 brk = 새 영역의 시작 주소
  • sbrk는 겉보기엔 함수 호출이지만, 운영체제(커널)에게 "내 프로세스의 brk를 올려달라"고 부탁하는 시스템콜입니다. brk는 커널이 프로세스마다 관리하는 값이라서, 프로세스 안의 코드가 직접 바꿀 수 없습니다.
  • brk에 incr을 더해서 힙을 늘리거나 줄입니다.
    • 성공하면 이전 brk 값을 반환합니다. 즉 "새로 늘어난 영역의 시작 주소"를 얻는 셈입니다. 반환값이 이전 brk인 이유는 allocator가 "새로 생긴 영역이 어디서 시작하는지"를 바로 알아야 거기를 free 블록으로 만들 수 있기 때문입니다.
    • 실패하면 -1을 반환하고 errno는 ENOMEM입니다.
  • 커널로부터 새로 받은 영역은 처음 건드릴 때 커널이 0으로 채운 물리 메모리를 연결해주는 방식(demand-zero)이라, sbrk 호출 자체는 가볍습니다. 다만 malloc은 메모리를 초기화해주지 않기 때문에 allocator가 재사용하는 블록은 이전에 데이터가 남아 있을 수 있습니다.

5. 16워드짜리 작은 힙 예제

책의 Figure 9.34는 이 allocator가 실제로 어떻게 움직이는지 보여주는 예제입니다.

이 절에서 1워드 = 4바이트, 블록은 8바이트(2워드) 배수로 맞춥니다.

참고: 왜 8바이트 배수로 주소를 맞추는가?
메모리(DRAM)와 CPU 사이는 8바이트 단위로 묶여 배선되어 있어서, 0~7번지, 8~15번지처럼 8의 배수에서 시작하는 덩어리 단위로만 읽을 수 있다. 그래서 8바이트 데이터가 8의 배수가 아닌 주소(예: 5번지)에 놓이면 두 덩어리에 걸치게 되어, 두 번 읽은 뒤 필요한 부분만 잘라 합쳐야 하므로 느려진다. 이런 손해를 막기 위해 allocator(malloc 등)는 처음부터 8의 배수(요즘은 보통 16의 배수) 주소를 내어주고, 컴파일러는 구조체 멤버가 경계에 걸치지 않도록 중간에 padding을 끼워 넣는다.
단계 요청 일어나는 일 의미
(a) p1 = malloc(4워드) 빈 블록 앞에서 4워드를 잘라 줌 큰 free 블록을 쪼개 씀
(b) p2 = malloc(5워드) 6워드를 줌 (패딩 1워드) 정렬 때문에 요청보다 더 줌 → 낭비의 시작
(c) p3 = malloc(6워드) 6워드를 잘라 줌  
(d) free(p2) p2의 블록이 free가 됨 중간에 빈 구멍이 생김
(e) p4 = malloc(2워드) 그 구멍의 일부를 재사용 재사용되지만 일부만 쓰면 조각이 남음

 

(a)  █ █ █ █ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░ ░
(b)  █ █ █ █ █ █ █ █ █ ▒ ░ ░ ░ ░ ░ ░   패딩때문에 요청보다 한칸 더 줌 
(c)  █ █ █ █ █ █ █ █ █ ▒ █ █ █ █ █ █  
(d)  █ █ █ █ ░ ░ ░ ░ ░ ░ █ █ █ █ █ █   중간에 빈 구멍이 생김
(e)  █ █ █ █ █ █ ░ ░ ░ ░ █ █ █ █ █ █   일부 재사용하지만 남은 조각이 생김

 

이 예제를 보면 세 가지 불편한 점이 눈에 띕니다. 이 문제들이 다음 파트의 주제가 됩니다. 

  1. (b): 요청보다 더 큰 블록을 줬다. 이 낭비는 얼마나 문제일까?
  2. (d)~(e): 중간에 free된 구멍이 생겼다. 그 구멍이 새 요청에 안 맞으면 어떻게 될까?
  3. (e): 구멍보다 작은 요청이 오면 남은 조각은 어떻게 처리하지?

 

정리: 프로그램은 필요한 크기를 실행 중에야 알기 때문에 정적 배열로는 부족하고, 동적 할당이 필요하다.
→ 커널에 매번 직접 요청하는 것은 불편하므로, 커널에게 받은 힙을 잘게 나눠 빌려주고 회수하는 중간 관리자(allocator)를 둔다. 사용자는 malloc/free로 요청·반납하고, 힙 안을 어떻게 쓸지는 allocator가 정하며, 힙 자체가 모자랄 때만 sbrk로 커널에게 영역 확장을 요청한다.
→ 그런데 힙에서 메모리를 빌려주고 돌려받는 과정에서 정렬 패딩과 흩어진 빈 구멍 같은 낭비가 생긴다. 

 

저작자표시 (새창열림)

관련글

티스토리툴바