CS:APP 9장 9절 (명시적 할당)

Jinhoon Yoon·2026년 10월 1일

📑 9.9 동적 메모리 할당

9.9.1 malloc과 free 함수

9.9.2 왜 동적 메모리 할당인가?

9.9.3 할당기 요구사항과 목표

9.9.4 단편화

9.9.5 구현 이슈

9.9.6 묵시적 가용 리스트

9.9.7 할당한 블록의 배치

9.9.8 가용 블록의 분할

9.9.9 추가적인 힙 메모리 획득하기

9.9.10 가용 블록 연결하기

9.9.11 경계 태그로 연결하기

9.9.12 종합 설계: 간단한 할당기의 구현

9.9.13 명시적 가용 리스트

9.9.14 분리 가용 리스트

한 줄 요약: 이 절이 해결하려는 핵심 문제

메모리 구조/비트: 블록 레이아웃

팀 논의 질문: 이 구현에서 왜 이렇게 처리했을까?

9.9 동적 메모리 할당

물리메모리 vs. 가상메모리
{mmap 함수, munmap 함수} 로도 가상메모리 영역을 생성/삭제 가능

808
각각의 프로세스에 대해서, 커널은 힙의 꼭대기를 가리키는 변수 brk(break)를 사용한다
-> 스택에서 push/pop 을 위해서 스택의 꼭대기가 어디인지 추적하는 포인터가 있듯이, 변수 brk 는 힙의 꼭대기가 어디인지 추적하는 포인터인가?
808
할당기는 힙을 다양한 크기의 블록들의 집합으로 관리한다. 각 블록은 할당되었거나 가용한 가상메모리의 연속적인 묶음이다.
808

명시적 할당기: ex) malloc 패키지 (할당: malloc 함수, 반환: free 함수)
묵시적 할당기: ex) 가비지 컬렉터 (언제 프로그램에 의해 사용되지 않고 블록을 반환하는지를 할당기가 특정할 수 있어야 함)
808
메모리 할당은 다양한 문맥에서 일어나는 일반적인 아이디어다. (이번 절에서는 힙 메모리를 관리하는 할당기만을 논한다)

그림9.33 힙heap.

9.9.1 malloc과 free 함수

809
프로그램은 malloc 함수를 호출해서 힙으로부터 블록들을 할당받는다.

#include <stdlib.h>
void *malloc(size_t size);
Returns: pointer to allocated block if OK, NULL on error

stdlib.h 를 불러온 뒤 malloc(원하는_바이트수) 를 호출하면, 성공 시 메모리의 시작 주소를 주고, 메모리가 부족해 실패하면 NULL 을 준다.
그래서 malloc() 을 호출한 뒤 if (p == NULL) 로 잘 할당되었는지 확인하는 에러 체크 코드를 항상 작성해야 한다.
809
malloc 함수는 블록 내에 포함될 수 있는 어떤 종류의 데이터 객체에 대해서 적절히 정렬된 최소 size 바이트를 갖는 메모리 블록의 포인터를 리턴한다 (malloc은 어떤 엄격한 데이터를 집어넣든 CPU가 최고 속도로 에러 없이 읽을 수 있도록, 8이나 16의 배수로 규격화된 주소에 요청한 크기 이상의 넉넉한 공간을 보장해서 넘겨준다)

최소 size 바이트를 갖는
- 요청한 것보다 절대 작게 주지 않는다. 만약 작게 주면 buffer overflow 가 발생하기 때문이다.
- 더 크게는 줄 수 있다.
  - 힙 관리용 헤더/푸터 를 붙여야 하기 때문
  - 하드웨어 정렬 단위(8 or 16 바이트)의 배수로 블록 크기를 올림해야 하기 때문.
적절히 적렬된
- CPU 는 메모리를 1바이트씩 찔끔찔끔 읽지 않는다. 데이터 버스 규격에 맞춰 8 or 16 바이트 단위의 경계선에 걸쳐서 한 번에 긁어옴
  - 32비트 모드: 주소가 항상 8의 배수(끝 3비트가 000)인 블록을 리턴
  - 64비트 모드: 주소가 항상 16의 배수(끝 4비트가 0000)인 블록을 리턴
- CPU 가 메모리에 2번 접근해서 앞뒤를 잘라 합쳐야 한다면, 성능이 반토막난다.
- 따라서 항상 하드웨어가 가장 빠르게 읽을 수 있도록 주소가 정렬되어 있다.
어떤 종류의 데이터 객체에 대해서
- C언어는 다양한 자료형이 있고, 요구하는 정렬 규격이 다르다.
  - char: 1바이트 정렬 (어디에 있든 상관없음)
  - int: 4바이트 정렬 (주소가 4의 배수여야 함)
  - double, long, 포인터: 8바이트 정렬 (주소가 8의 배수여야 함)
  - long double / SIMD 벡터(__m128): 16바이트 정렬 필요
- 가장 큰 정렬 기준(16바이트)이 들어오더라도 문제없도록 무조건 최상위 수준으로 정렬된 주소를 내어준다
  - 16 의 최소 공배수는 1, 2, 4, 8, 16이다.
  - 따라서 어떤 주소가 16의 배수라면, 그 주소는 반드시 1, 2, 4, 8의 배수이다.
  - 따라서 16바이트에 맞추면, 그 어떤 데이터 타입이 들어와도 정렬 규격을 반드시 만족한다.

8의 배수
- bin: 맨끝 3비트가 000
- hex: 맨끝은 0 또는 8 (0000 = 0, 1000 = 8)

16의 배수
- bin: 맨끝 4비트가 0000
- hex: 맨끝은 0

메모리 블록 크기를 나타내는 헤더(Header)를 저장할 때 이 규칙을 활용한다.
모든 블록의 크기와 주소가 8 또는 16의 배수로 정렬되면, 블록 크기를 2진수로 나타냈을 때,
하위 3개 비트(끝 3자리)는 항상 000으로 비어 있게 된다.

낭비되는 끝 3비트를 그냥 두지 않고
- 맨 마지막 비트 1개를 할당 플래그(Allocated bit) 로 활용한다
  - 1 (이 블록이 현재 할당되었음)
  - 0 (이 블록이 빈 상태임)

동적 메모리 3형제

malloc: 크기만 잡아서 주소 넘김 (쓰레기값 남아있음)
calloc: 메모리 잡고 전부 0으로 덮어씀
- 내부적으로 malloc 을 먼저 부른 다음, 그 자리에 memset(ptr, 0, size) 으로 0으로 초기화해서 반환함
realloc: 기존의 데이터는 보존하면서, 메모리 크기를 늘리거나 줄임
- 만약 바로 뒤에 연속된 빈 공간이 없다면, 데이터를 새 자리로 복사(memcpy)해 옮겨 심은 뒤, 이전 자리는 free 한다

heap 영역은 아래에서 위로 자란다.

brk (break pointer) 은 맨 꼭대기 경계선(울타리)을 가리키는 포인터다.
- brk 아래쪽은 이미 OS한테 허락받아 쓸 수 있다.
- brk 위쪽은 아직 OS 소유다 (접근하면, Segmentation Falut 난다)

sbrk 시스템 콜 함수 (Space Break)

sbkr(incr): 울타리를 몇 바이트 더 위로 밀어 올릴 것인가?
- incr 가 양수인 경우: sbrk(4096) 을 호출하면, 커널이 brk(울타리)를 위로 4KB 밀어 올려준다. 그 결과 힙 영역이 4KB 커진다.
- incr 가 0인 경우: sbrk(0) 을 호출하면, 지금 brk 가 어디인지 조회하는 용도로 쓴다.
- incr 가 음수인 경우: sbrk(-100) 을 호출하면, brk(울타리)을 아래로 내려서 OS한테 반납한다 (합법)
  - 하지만 규칙대로, 이전의 brk 주소를 return 한다. 그래서 return 값 처리가 복잡해진다.
sbrk() 는 왜 새로운 brk 주소가 아니라, 이전의 brk 주소를 return 할까?
- 영역을 확장하기 전의 위치가, 방금 확장한 영역이 시작점 이기 때문.
  - 원래 울타리 위치: 0x1000
  - sbrk(100) 호출 -> 새 울타리 위치: 0x1064
  - 리턴값: 0x1000 (새로 얻은 100바이트 땅의 시작 주소)
- malloc 입장에서는 sbrk() 가 돌려준 주소를 그대로 새 청크의 시작 주소로 쓰면 되기에 효율적이다.
메모리가 꽉차서 실패하면 (ENOMEM = Erro NO Memory) (void *)-1 을 return 한다

void free(void *ptr);
						Returns: nothing

ptr 인자는 malloc, calloc, realloc 에서 획득한 할당된 블록의 시작을 가리켜야 한다

free 는 size 를 인자로 받지 않는다. 인자 ptr 바로 앞에 헤더(메타데이터가 담김)를 숨겨두었다
free 는 아무것도 return 하지 않는다. 그래서 뭔가 잘못되었다는 것을 알릴 수 없고, 런타임 에러 발생 여지가 있다.

free(ptr)의 내부 동작

크기를 모르기 때문에, 건네 받은 주소의 바로 앞(헤더)을 까봐야 크기를 알 수 있다.

// ptr 바로 앞 주소로 4 or 8 바이트 이동해서 숨겨진 헤더를 읽음
header = ptr - 8;
size = get_size(header);	// "아, 이 블록이 N 바이트 짜리구나!"
set_free(header);			// "이제 이 블록은 빈 블록(Free)으로 변경!"

규칙을 어기는 경우

블록 중간 주소를 넘기면? free(ptr + 4)
- free는 무조건 인자 앞으로 8바이트 이동해서 메모리를 읽으려고 한다
- 근데 이 경우, 진짜 헤더가 아니라, payload 의 한가운데다.
- 엉뚱한 데이터를 블록 크기로 해석하면서, 힙 관리 구조가 깨지고, free(): invalide pointer 에러와 함께 SIGSEGV 가 터진다.
스택 변수나 엉뚱한 주소를 넘기면? int a; free(&a);
- 힙 영역이 아닌 영역을 건드리면, 프로그램이 즉사한다.
이미 해제된 주소를 또 넘기면? Double Free
- 힙 내부 연결 고리(List) 가 꼬이거나, 순환 참조 루프에 빠져, 보안 취약점의 통로가 된다.

811
그림 9.34 (상태 a~e)
812
더 큰 MAXN 값을 사용해서 다시 컴파일하는 것이다... 고정된 배열 크기아 있다는 것은, 수백만 라인의 코드와 수많은 사용자가 있는 큰 규모의 소프트웨어 제품에서는, 관리가 어렵다. 더 나은 방법은 n값을 알 수 있을 때, 배열을 런타임에 동적으로 할당하는 것이다. 이 방법으로, 배열의 최대 크기는 가용한 가상메모리의 양에 의해서만 제한된다.

int main()
{
    int *array, i, n;

    scanf("%d", &n);
    array = (int *)Malloc(n * sizeof(int));
    for (i = 0; i < n; i++)
        scanf("%d", &array[i]);
    free(array);
    exit(0);
}

int *array, i, n; (컴파일 타임의 질서)

스택 프레임에 변수 3개가 자리잡는다.
- n: 정수 4바이트
- i: 정수 4바이트
- array: 8바이트 주소표(포인터)
컴파일러는 array 라는 이름이 스택의 베이스 포인터로부터 몇 바이트 아래에 있는지 미리 알고 있다.
하지만 그 주소표가 가리킬 데이터 본체는 아직 세상에 존재하지 않는다.

scanf("%d, &n); (카오스의 시작)

런타임에 유저가 키보드로 숫자를 입력한다.
유저가 5를 넣을지, 100만을 넣을지, 프로그램을 실행하기 전까지는 CPU와 컴파일러는 전혀 알 수 없다.
이 순간 정적 배열(int arr[n]) 대신, 동적 메모리 할당이 필요해진다.

array = (int *)Malloc(n * sizeof(int)); (주차권 발급)
(대문자 Malloc 은 malloc 이 실패해 NULL을 뱉었을 때, 에러를 출력하고 프로그램을 안전하게 종료시키는 얇은 래퍼 함수다.)

바이트 계산: sizeof(int) 는 4바이트이므로, 만약 n = 10 이라면 총 40바이트의 연속된 공간이 필요하다.
할당자 내부 동작
- 힙 영역의 빈 청크들을 뒤져서 40바이트를 담을 수 있는 자리를 찾는다.
- 이때 40바이트 딱 맞게 주는 게 아니다. 앞쪽에 메타데이터(헤더 4 or 8바이트)를 붙이고, 하드웨어 4 or 16바이트 정렬 규칙에 맞춘 블록을 마련한다.
- 주소표 반환: 할당자는 헤더를 건너뛴, 실제 데이터가 들어갈 페이로드의 첫번째 바이트 주소(0x5555...)를 &rax(8바이트 레지스터)에 담아 돌려준다.
- 대입: 스택에 있던 8바이트 변수 array에 그 주소값이 복사된다. 이제 array는 힙의 그 거대한 공간을 통제하는 유일한 핸들이 된다.

for (i = 0; i < n; i++) scanf("%d", &array[i]); (포인터 연산)

array[i] 는 C문법 설탕이고, 본질은 *(array + i) 이다.
array 의 타입이 int * (4바이트 단위)이므로, CPU는 주소 연산을 다음과 같이 한다:
- 실제 주소 = array + (4 X i)
힙의 베이스 주소에서 4바이트씩 전진하며 유저가 입력한 정수를 차곡차곡 채워 넣는다.

free(array); (주차권 반납과 헤더)

free 함수에는 오직 array 주소만 던진다. 배열 크기 n 이나 40바이트 라는 정보를 전혀 전달하지 않는다.
free는 전달받은 array - 8 (array 주소에서 앞으로 8바이트 이동) 해서 숨겨진 헤더를 까본다.
헤더에서 "아, 이 블록은 x바이트 크기구나!" 라는 사실을 알아내고, 해당 블록의 할당 비트를 0으로 바꿔 Free List 에 편입시킨다.
만약 앞뒤에 다른 빈 블록이 있다면 병합(Coalescing) 작업까지 수행한다.
스택의 변수 array는 여전히 그 힙 주소값이 그대로 남아 있다 (Dangling Pointer)

exit(0); (자원 정리)

운영체제에게 정상 종료(0) 신호를 보내며 프로세스의 모든 가상 주소 공간(스택, 힙, 코드)이 일괄 해제된다.

RAM 메모리는 1차원 배열이다. 스택과 힙도 1차원이다.

(논리적으로) 가상 메모리 공간은 0x0000000000000000 번지부터 바이트 단위로 인덱스가 매겨진 거대한 1차원 char memory[] 배열과 같다.
Stack, Heap, BSS, Data, Code(Text) 영역은 그저 하나의 1차원 주소선 위에 구역(Segment)만 나눠둔 것이다.
- Heap 은 낮은 주소에서 높은 주소 방향으로 자라고,
- Stack 은 높은 주소에서 낮은 주소 방향으로 자라고,
- 둘다 동인한 1차원 수직선 위를 오르내릴 뿐이다.

malloc() 은 항상 "연속된" 공간을 할당하는가?

소프트웨어 (가상 메모리) 관점
- malloc(4) 을 호출했을 때, 20바이트는 0x1000 에 주고 나머지 20바이트는 0x5000 에 떨어뜨려서 주는 일은 절대 없다.
- 이유: C언어의 핵심인 포인터 연산(*(ptr + i)) 때문이다.
  - array[3] 을 읽으려면 CPU는 단순히 시작 주소에 오프셋을 더하는 단일 덧셈 연산(array + 3 * 4)을 수행한다.
  - 공간의 중간이 끊겨 있다면, 덧셈 한 번으로 다음 원소를 찾아갈 수 없으므로, C언어의 배열 문법과 포인터 연산 전체가 성립하지 않는다.
하드웨어 (물리 메모리) 관점
- 실제 물리 RAM: 페이지 테이블(MMU)이 중간에서 매핑해주기 때문에, 물리적으로 4KB 단위 페이지들이 흩어져 있어도 상관없다. 하지만 CPU 와 프로그램은 이를 인지하지 못하며, 연속된 주소 공간으로만 인식하고 사용한다.

813
프로그래머들은 할당기를 정확하고 효율적으로 사용하기 위해서 어떻게 이들이 동작하는지 이해할 필요가 있다.
9.11절에서 할당기의 잘못된 사용으로 발생할 수 있는 위험한 에러들에 대해 설명할 것이다.

9.9.3 할당기 요구사항과 목표

요구사항

임의의 요청 순서 처리하기
요청 즉시 응답하기
힙만 사용하기
블록 정렬하기 (정렬 요건)
할당된 블록을 수정하지 않기

813
일반적으로, 할당과 반환 요청들을 만족시키기 위한 평균 시간을 최소화해서 처리량을 최대화한다.
813
한 시스템에서 모든 프로세스에 의해 할당된 가상메모리의 양은 디스크 내의 스왑 공간의 양에 의해 제한된다.
814
$U_k = \frac{\max_{i \le k} P_i}{H_k}$

비율 0~1
- 분모: OS 한테 뜯어낸 전체 땅
- 분자: 진짜로 쓴 알맹이 데이터
비율 1 (100%) 로 꽉 채우는 것은 불가능하다.
- 헤더도 붙여아하고, 8 or 16 바이트 정렬도 맞춰야 하고, 단편화(중간에 쪼개진 빈 공간)도 생기기 때문에, 분모는 분자보다 항상 크다.
Malloc Lab 점수 산출 기준:
- 과제 채점기(mdriver)를 돌리면 두 가지 점수가 나옵니다:
  - Throughput (처리량): 초당 malloc/free를 얼마나 빠르게 처리하는가?
  - Memory Utilization (메모리 이용도): 바로 $U_{n-1}$ 값. 땅을 낭비하지 않고 얼마나 알뜰하게 썼는가?
트레이드오프(긴장 관계):
- 처리량을 늘리려고 대충 빈곳에 던져주면 이용도가 개판이 되고,
- 이용도를 극대화하려고 빈틈없이 맞추려다 보면 탐색 속도가 느려진다.

9.9.4 단편화

2종류의 단편화가 있다.
외부 단편화는 측정하기 어렵고 예측 불가능하기 때문에
할당기들은 대개 많은 수의 더 작은 가용 블록들보다는, 더 적은 수의 더 큰 가용 블록들을 유지하려는 방법들을 채택하고 있다.

내부 단편화는 현재의 힙 공간으로 감당 가능하지만,
외부 단편화는 현재의 힙 공간으로 감당 불가능하다. 그래서 OS 에게 추가 힙 공간을 요청(sbrk)해야 한다.

내부 단편화
- 정량화가 단순하다. 할당된 블록의 크기와 이들의 데이터 사이의 차이의 합이다.
  - 시간상 어디서든 내부 단편화의 양은 이전에 요청한 패턴과 할당기 구현에만 의존한다.
외부 단편화
- 할당된 요청을 만족시킬 수 있는 메모리 공간이 전체적으로 공간을 모았을 때는 충분한 크기가 존재하지만, 이 요청을 처리할 수 있는 단일한 가용블록은 없는 경우에 발생한다.
  - 이전 요청의 패턴과 할당기 구현에만 의존하는 것이 아니라, 미래의 요청 패턴에도 의존한다.

9.9.5 구현 이슈

815
이 초보적인 할당기는 디자인 공간에서 극단점에 해당한다.
815
처리량과 이용도 사이에 좋은 균형을 갖는 실용적인 할당기는 다음 이슈들을 고려해야 한다:

가용 블록 구성: 어떻게 가용 블록을 지속적으로 추적하는가?
배치: 새롭게 할당된 블록을 배치하기 위한 가용 블록을 어떻게 선택하는가?
분할: 새롭게 할당된 블록을 가용 블록에 배치한 후 가용 블록의 나머지 부분들로 무엇을 할 것인가?
연결: 방금 반환된 블록으로 무엇을 할 것인가?

배치, 분할, 연결은 서로 다른 가용 블록 구조와 관련된다.
묵시적 가용 리스트로 알려진, 간단한 가용 블록 구조의 맥락에서 소개할 것이다.

반납된 빈 땅을 재활용 하면서도, 속도 저하를 최소화하기 위해 4가지 설계 변수를 결정해야 한다.
4가지 각각을 어떻게 조합하느냐에 따라 과제의 Throughput(처리 속도)과 Utilization(메모리 이용도) 점수 판도가 완전히 갈리게 된다.

4가지 핵심 설계

1) 가용 블록 구성 (Free Block Organization): 힙 안에 블록들(할당/가용)이 마구 섞여 있을 때, 가용 블록을 어떻게 지속적으로 추적하는가?
- 암묵적 가용 리스트 (Implicit List)
  - 빈 블록만을 위한 별도의 장부 없이, 헤더의 크기 정보를 이용해서, 힙의 모든 블록(할당/가용)을 차례대로 탐색
- 명시적 가용 리스트 (Explicit List)
  - 빈 블록 내부의 페이로드 공간 (어차피 비어있으므로 유저 데이터가 없음)에 next, prev 포인터를 심어서, 빈 블록들끼리만 이중 연결 리스트(Doubly Linked List)로 엮어둔다.
  - 할당된 블록은 건너뛰고, 빈 블록들만 순회하므로, 탐색 속도가 크게 오른다.
- 분리 가용 리스트 (Segregated Free List)
  - 크기별로 리스트를 여러 개 만든다 (ex. 16~32바이트 용, 33~64바이트 용, 65~128바이트 용)
  - 현대 상용 할당기(ptmalloc, jemalloc)가 채택하는 방식으로, 탐색 시간이 거의 $O(1)$ 에 가까워진다.
2) 배치 (Placement): 가용 블록이 여러 개 있을 때, 어떻게 선택하는가?
- First-Fit
  - 리스트의 처음부터 탐색하다가, 요청 크기를 수용할 수 있는 가장 첫 번째 빈 블록을 바로 선택
  - 탐색 속도가 비교적 빠르지만, 리스트 앞쪽에 자투리 조각들이 쌓이는 경향이 있다.
- Next-Fit
  - 직전 탐색이 끝난 위치부터 다음 탐색을 시작
  - First-Fit 보다 속도가 빠를 수 있으나, 메모리 이용도가 떨어지는 경우가 많을 수 있다.
- Best-Fit
  - 들어갈 수 있는 모든 빈 블록을 검사한 뒤, 최적의 (크기 차이가 가장 작은) 블록을 고름
  - 단편화를 줄여 메모리 이용도는 최고 수준이지만, 매번 리스트 전체를 뒤져야 하므로 처리량이 급감한다.
3) 분할 (Splitting): 가용 블록의 나머지 부분들로 무엇을 할 것인가?
- 분할 하지 않음
  - 100바이트를 통째로 할당 및 사용
  - 구현은 편하지만, 무려 80바이트의 심각한 내부 단편화
- 분할 (내부 단편화를 획기적으로 줄이는 필수(?) 테크닉)
  - 예를 들어, 20바이트가 필요한데, 찾아낸 빈 블록이 100바이트 크기라면, 어떻게 처리할 것인가?
  - 100바이트를 쪼개서 앞쪽 24바이트 (헤더 포함)는 할당 블록으로 만들고,
  - 남은 76바이트는 새로운 작은 가용 블록으로 헤더/푸터 를 다시 세팅해서 가용 리스트에 남겨둔다.
4) 연결 (Coalescing): 방금 반환된 블록으로 무엇을 할 것인가?
- 연결하지 않음
  - 작은 빈 조각들을 방치: 외부 단편화가 폭발, 전체 빈 공간은 넉넉하지만, 시스템 호출 sbrk() 을 할 경우가 아주 많아질 수 있음
- 즉시 연결 (Immediate Coalescing)
  - free 가 불리자마자 앞 블록의 푸터 와 뒤 블록의 헤더 를 확인하여, 비어있는 이웃이 있다면, 즉시 하나의 거대한 빈 블록으로 병합
- 지연 연결 (Deferred Coalescing)
  - free 때는 그냥 두고, 나중에 malloc 이 빈 공간을 찾다가 실패했을 때, 힙 전체를 한 번에 싹 훑으며 병합

빈 조각들을 최적으로 채워 넣는 빈 패킹(Bin Packing) 문제는 유한한 경우의 수를 다룸에도 불구하고 다항 시간 안에 완벽한 답을 낼 수 없는 대표적인 난제다. 할당기를 설계한다는 것은 거대한 조합 속에서 '수학적 완벽성'을 찾는 것이 아니라, 경험적 휴리스틱 (First-fit, Segregated list 등) 을 통해 유한한 자원 내에서 실패 확률 (외부 단편화, 지연 시간) 을 실용적인 수준으로 억제하는 작업이다.

9.9.6 묵시적 가용 리스트 (헤더 내 필드에 의해 묵시적으로 연결됌)

모든 실용적인 할당기는 블록 경계를 구분하고, 할당/가용 블록을 구분하는 데이터 구조를 필요로 한다.
대부분의 할당기는 이 정보를 블록 내에 저장한다.

1워드 헤더, 데이터, 추가적인 패딩

헤더가 인코딩하는 정보
- 블록 크기 (헤더, 패딩 포함)
- 블록 할당 여부

패딩을 하는 이유는 여러 가지다.

Minimum Block Size 충족: 해제 시 next / prev 포인터를 담을 수 있는 최저 바이트(16 or 24) 확보
외부 단편화 극복 전략: 할당기 정책상, 블록 분할 후 남는 자투리가 너무 작아 못 쓰게 될 바엔, 기존 블록 패딩으로 흡수
정렬 요구사항 충족: CPU의 4/8/16 바이트 단위 메모리 버스 정렬 규칙 만족
캐시 라인(64바이트) 정렬: 캐시 라인 분할 접근 방지 -> CPU 메모리 읽기 사이클 최소화
멀티스레드 환경의 False Sharing 방지: 코어 간 불필요한 캐시 무효화 핑퐁 방지

할당기는 간접적으로 가용 블록 전체 집합을, 힙 내의 전체 블록을 다니면서 방문할 수 있다.
(가용 블록들끼리 직접 이어주는 연결 고리(포인터)가 없다.

블록 A의 헤더를 읽어서, 크기가 S 바이트임을 확인한다.
주소에 S 를 더해서(ptr + S ) 다음 블록 B의 헤더로 이동한다.
빈 공간을 찾을 때까지, 이 작업을 힙의 끝(에플로그 블록)까지 징검다리 건너듯 반복한다. 가용 블록으로 곧장 점프할 수 없고, 중간에 놓인 할당 블록들을 전부 밟고 지나가야 하므로, "간접적"이라고 표현했다.

장점: 단순성
단점: 연산(할당된 블록 배치, 가용 리스트 탐색) 비용은 힙에 있는 전체 할당/가용 블록의 수에 비례한다.

9.9.7 할당된 블록의 배치

First fit
- 장점: 리스트의 마지막에 가장 큰 가용 블록들을 남겨두는 경향이 있다.
- 단점: 리스트의 앞부분에 작은 가용 블록들을 남겨두는 경향이 있다.
  - 큰 블록을 찾는 경우, 검색 시간이 늘어난다.
Next fit
- 이전 검색에서 가용 블록을 발견했다면, 다음 검색에서는 리스트의 나머지 부분에서 원하는 블록을 찾을 가능성이 높다는 희망
- 장점: 리스트의 앞부분에 많은 작은 크기의 조각들로 구성되는 경우, First fit 에 비해서 아주 빠른 속도
- 단점: First fit 에 비해서 나쁜 메모리 이용도를 가지는 경향
Best fit
- 장점: 대체로 더 좋은 메모리 이용도
- 단점: 묵시적 가용 리스트에서는, 힙을 싹다 검색해야 한다.
  - 대안: 정책을 단순화해서, 힙을 모두 검색하지 않는, segregated free list

9.9.8 가용 블록의 분할

9.9.9 추가적인 힙 메모리 획득하기

9.9.10 가용 블록 연결하기

빠른 할당기들은 종종 지연 연결의 형태를 선택한다는 것을 알아야 한다.

9.9.11 경계 태그로 연결하기

9.9.12 종합 설계: 간단한 할당기의 구현

Jinhoon Yoon

이전 포스트

malloc() 의 문제의식은 뭐였을까? malloc() 은 왜 void* 를 return 하는가?

다음 포스트