[운영체제] CSAPP 9.9장 Malloc-lab

동적 메모리 할당? 🤔

동적 메모리 할당기는 프로세스의 가상 메모리 영역 중 힙(Heap) 이라고 불리는 곳을 관리한다.

위 그림처럼 힙은 보통 초기화되지 않은 데이터(.bss) 영역 바로 뒤에서 시작해서 위쪽(높은 주소)으로 자라나는 구조다.

커널은 각 프로세스마다 brk라는 커널 관리 변수(포인터)를 유지하는데, 이 포인터가 바로 힙의 꼭대기(top)를 가리킨다.

할당기는 이 힙을 다양한 크기의 블록(block) 들의 집합으로 관리한다. 각 블록은 연속된 가상 메모리 덩어리이며, 할당되었거나(allocated) 혹은 가용(free) 상태 중 하나이다.

할당된 블록 (Allocated block): 애플리케이션이 명시적으로 요청해서 사용 중인 블록.
가용 블록 (Free block): 할당될 수 있는 상태의 블록.

할당기는 크게 두 가지 스타일로 나뉜다.

명시적 할당기 (Explicit Allocators)
- 애플리케이션이 명시적으로 할당된 블록을 반납(free)해야 한다.
- C언어의 malloc과 free 함수가 대표적인 예시다.
- 우리가 이번에 다룰 내용이 바로 이것!
묵시적 할당기 (Implicit Allocators)
- 할당기가 알아서 더 이상 사용되지 않는 블록을 감지하고 해제한다.
- 이걸 가비지 컬렉션(Garbage Collection) 이라고 부르고, 할당기를 가비지 컬렉터(Garbage Collector) 라고 한다.
- Java, Lisp, ML 같은 고급 언어들이 이 방식을 사용한다.

9.9.1 `malloc` 과 `free` 함수

C 표준 라이브러리는 malloc 패키지라는 명시적 할당기를 제공한다.

malloc

#**include** <stdlib.h>

void *malloc(size_t size);

역할: 힙에서 size 바이트 이상의 메모리 블록을 요청하고, 그 블록의 시작 주소를 가리키는 포인터를 리턴한다.
정렬 (Alignment): malloc이 리턴하는 블록의 주소는 어떤 종류의 데이터든 저장할 수 있도록 정렬되어 있다. 32비트 모드에서는 주소가 항상 8의 배수이고, 64비트 모드에서는 항상 16의 배수인 주소를 리턴한다.
에러 처리: 만약 요청한 메모리가 가용한 가상 메모리보다 크면 NULL을 리턴한다.
초기화: malloc은 할당한 메모리를 초기화하지 않는다. 쓰레기 값이 들어있을 수 있다는 뜻. (초기화를 원하면 calloc을 사용하면 된다.)

free

#**include** <stdlib.h>

void free(void *ptr);

역할: ptr이 가리키는 할당된 블록을 해제하여 가용 상태로 만든다.
주의사항: ptr은 반드시 malloc, calloc, realloc으로 할당된 블록의 시작 주소를 가리켜야 한다. 아니면 미정의 동작이 발생하며, free 함수는 아무런 에러 표시도 해주지 않기 때문에 디버깅이 매우 어려워진다. 😱

sbrk

malloc 같은 할당기는 sbrk 함수를 사용해서 힙을 직접 늘리거나 줄일 수 있다.

#**include** <unistd.h>

void *sbrk(intptr_t incr);

커널의 brk 포인터를 incr 만큼 증가시켜 힙을 늘린다. 성공하면 이전 brk 포인터 값을, 실패하면 -1을 리턴한다.

동작 예시

책의 그림(Figure 9.34)은 malloc과 free가 16워드 크기의 작은 힙을 어떻게 관리하는지 보여준다.

책에서는 4바이트 워드, 8바이트 정렬을 가정한 32비트 환경을 예시로 하고 있으므로. 이를 64비트 환경에 맞게 생각해보자. (헤더/푸터는 8바이트, 정렬은 16바이트 규칙 적용)

(a) 16바이트(4*sizeof(int))를 요청: 할당기는 헤더/푸터(16바이트) + 페이로드(16바이트) = 32바이트를 할당한다. 32는 16의 배수이므로 패딩은 필요 없다.
(b) 20바이트(5*sizeof(int))를 요청: 할당기는 헤더/푸터(16바이트) + 페이로드(20바이트) = 36바이트가 필요하다고 계산한다. 64비트 시스템의 16바이트 정렬 조건을 맞추기 위해, 할당기는 이 크기를 16의 배수인 48바이트로 올림하여 할당한다. 여기서 추가된 12바이트가 패딩(padding) 이다.
(c) 24바이트(6*sizeof(int))를 요청: 헤더/푸터(16바이트) + 페이로드(24바이트) = 40바이트가 필요. 16의 배수인 48바이트로 올림하여 할당한다. 여기서 8바이트가 패딩이다.
(d) (b)에서 할당했던 블록(p2)을 free: 48바이트 블록이 다시 가용 상태가 된다. 하지만 포인터 p2는 여전히 해제된 블록을 가리키므로, 재할당받기 전까지 사용하면 안 된다!
(e) 8바이트(2*sizeof(int))를 요청: 헤더/푸터(16바이트) + 페이로드(8바이트) = 24바이트가 필요. 16의 배수인 32바이트로 올림하여 할당한다. malloc은 (d)에서 해제된 48바이트 가용 블록의 일부(32바이트)를 떼어내 할당한다.

free는 "이 메모리 이제 안 써요"라는 통보일 뿐, 포인터 자체를 건드리진 않는다.

따라서 해제된 포인터는 위험하니 절대 다시 사용하면 안 된다. (d 내용)

이런 실수를 방지하기 위해 free를 한 직후 해당 포인터에 NULL을 할당하는 습관을 들이는 것이 좋다.
free(p2);
p2 = NULL; // p2가 더 이상 유효하지 않음을 명시

왜 동적 할당을 쓸까?

가장 중요한 이유는 프로그램 실행 전까지는 데이터 구조의 크기를 알 수 없는 경우가 많기 때문이다.

예를 들어, n개의 정수를 입력받아 배열에 저장하는 프로그램을 짠다고 해보자.

나쁜 예: 고정된 크기의 정적 배열

#**define** MAXN 15213 // 무슨 근거로?

int array[MAXN];
...
scanf("%d", &n);
if (n > MAXN)
    app_error("Input file too big");

MAXN 값은 임의적이고, 실제 가용 메모리와는 아무 상관이 없다. 만약 사용자가 MAXN보다 큰 파일을 처리하고 싶으면 코드를 다시 컴파일해야만 한다. 이건 유지보수 측면에서 최악이다.

좋은 예: 동적 할당

int *array, i, n;
...
scanf("%d", &n);
array = (int *)Malloc(n * sizeof(int)); // n을 알고 난 후에 할당!
...
free(array); // 다 썼으면 반납

이 방식은 n 값이 정해진 후에 정확히 필요한 만큼만 메모리를 할당한다. 배열의 최대 크기는 오직 가용한 가상 메모리 양에 의해서만 제한된다. 훨씬 유연하고 효율적이다. 👍

할당기의 요구사항과 목표

명시적 할당기는 꽤나 까다로운 제약 조건 하에서 동작해야 한다.

요구사항

임의의 요청 순서 처리: malloc과 free 요청이 어떤 순서로 들어올지 예측할 수 없다.
요청에 즉시 응답: 성능 향상을 위해 요청을 재정렬하거나 버퍼링할 수 없다.
힙만 사용: 할당기가 사용하는 자료구조(예: 리스트)는 반드시 힙 내부에 저장되어야 한다.
블록 정렬: 할당하는 블록은 어떤 데이터 타입이든 저장할 수 있도록 정렬되어야 한다.
할당된 블록은 수정 금지: 일단 할당된 블록은 할당기가 임의로 옮기거나 수정할 수 없다.

이러한 제약 하에 할당기는 상충되는 두 가지 성능 목표를 달성해야 한다.

목표

처리율(Throughput) 극대화: 단위 시간당 완료하는 요청(malloc, free)의 개수를 최대화하는 것. 즉, 각 요청을 최대한 빨리 처리해야 한다.
메모리 이용률(Utilization) 극대화: 힙 메모리를 최대한 아껴 쓰고 효율적으로 사용하는 것. ⇒ 최고 이용률(peak utilization) 이라는 척도를 사용한다.
- k : 시간의 흐름, 즉 k번째 요청(malloc 또는 free)이 완료된 시점을 의미
- U_k : 프로그램 시작부터 k번째 요청까지의 기간 동안 메모리를 얼마나 효율적으로 사용했는지를 나타내는 값
- H_k: k번째 요청이 끝난 후, 할당기가 운영체제로부터 받아온 힙 메모리의 총량 ⇒ 보통 줄어들지 않고 계속 증가
  
  P_i : i번째 요청이 끝난 후, 현재 할당된 블록들의 순수 데이터 공간(페이로드)의 총합
  
  max (i≤k) P_i : 프로그램이 시작된 후 k번째 요청 시점까지, 페이로드 합계(Pi)가 가장 높았던 순간의 값 ⇒ 즉, 프로그램이 실행되는 동안 메모리를 '가장 바쁘게' 사용했던 시점의 순수 데이터 총량

💡 핵심 과제: 처리율과 이용률 사이의 균형을 찾는 것! 처리율을 높이기 위해 간단한 방법을 쓰면 이용률이 엉망이 되기 쉽고, 이용률을 높이려고 복잡한 방법을 쓰면 처리율이 떨어질 수 있다.

단편화 (Fragmentation)

분명 사용하지 않는 메모리인데도, 정작 할당 요청을 처리할 수 없는 상태를 의미

⇒ 할당기의 성능을 저해하는 주범

1. 내부 단편화

할당된 블록이 요청한 페이로드(실제 데이터)보다 클 때, 블록 내부에 발생하는 낭비 공간

내부 단편화가 발생하는 가장 대표적인 이유는 바로 정렬 요구조건 때문이다.

전제 조건

시스템: 64비트
워드 크기: 1워드(Word) = 8바이트, 더블 워드(Double Word) = 16바이트
규칙: malloc은 CPU 성능 최적화를 위해 모든 메모리 블록의 시작 주소와 총 크기를 16바이트 단위(더블 워드)로 맞춘다.

발생 과정 예시

요청: 프로그래머가 malloc(18)을 호출하여 18바이트의 메모리를 요청
할당기의 계산: 할당기는 18바이트를 담을 수 있으면서, 전체 크기가 16의 배수인 가장 작은 블록을 찾음
- 16바이트 블록: 18바이트를 담기에 너무 작으므로 ❌
- 32바이트 블록: 18바이트를 담기에 충분 ✅
결과: 프로그래머는 32바이트짜리 블록을 받아 그중 18바이트를 사용

정량화

내부 단편화의 정량화는 간단하다.

🔢 할당된 블록 크기 (32바이트) - 요청한 페이로드 크기 (18바이트) = 14바이트

단순히 할당된 블록의 크기와 이들의 데이터 사이의 차이의 합이기 때문에

내부 단편화의 양은 이전에 요청한 패턴과 할당기 구현에만 의존한다.

2. 외부 단편화

힙에 가용 메모리의 총합은 충분하지만, 요청을 만족시킬 만큼 큰 연속된 단일 가용 블록이 없을 때 블록 외부에 발생하는 낭비 공간

전제 조건

원인: malloc과 free가 반복적으로 일어나면서, 컸던 가용 블록이 잘게 조각나기 때문에 발생
규칙: 모든 블록의 총 크기는 16의 배수 (헤더+푸터 오버헤드는 16바이트)

발생 과정 예시

초기 상태
- 96바이트 크기의 연속된 가용 공간이 있음
```
[ 96바이트 가용 공간 ]
```
요청 1: malloc(16) 호출
- 필요 크기: 페이로드(16B) + 오버헤드(16B) = 32바이트
- 32는 16의 배수이므로, A블록으로 32바이트를 할당
```
[ A (32B) ][ 64바이트 가용 공간 ]
```
요청 2: malloc(32) 호출
- 필요 크기: 페이로드(32B) + 오버헤드(16B) = 48바이트
- 48은 16의 배수이므로, B블록으로 48바이트를 할당
```
[ A (32B) ][ B (48B) ][ 16바이트 가용 공간 ]
```
반납: free(A) 호출
- A 블록(32바이트)을 반납하여 가용 공간으로 만듬
```
[ 32바이트 가용 공간 ][ B (48B) ][ 16바이트 가용 공간 ]
```
문제 발생: malloc(24) 호출
- 필요 크기: 페이로드(24B) + 오버헤드(16B) = 40바이트.
- 40은 16의 배수가 아니므로, 다음 배수인 48바이트로 크기를 올림
- ⇒ 즉, 할당기는 48바이트의 연속된 가용 공간을 찾아야 함

현재 가용 공간 총합: 32바이트 + 16바이트 = 48바이트

힙 전체에는 요청을 처리하기에 딱 맞는 48바이트의 가용 공간이 있지만.. 가장 큰 연속된 가용 공간은 32바이트뿐

결론: 48바이트를 할당해달라는 요청은 실패! ❌

정량화

외부 단편화는 정량화하기가 매우 어렵다. 왜냐하면 앞으로 어떤 크기의 요청이 들어올지에 따라 그 심각성이 달라지기 때문이다.

예를 들어 힙에 16바이트짜리 가용 블록만 100개 있다고 가정했을 때

앞으로 들어올 요청이 모두 16바이트 이하라면 외부 단편화는 '0'이다.

하지만 바로 다음 요청이 32바이트라면? 이는 심각한 외부 단편화 상태인 것이다.

이처럼 외부 단편화는 메모리의 총량 문제가 아니라, 가용 공간이 어떻게 배치되어 있는지의 문제이고, 이 문제를 해결하기 위해 free 시 인접한 가용 블록들을 합쳐주는 연결(Coalescing) 작업이 매우 중요하다.

할당기 구현 이슈

자, 그럼 이제 실제 할당기를 만들려면 무엇을 고민해야 할까?

가용 블록 구성 (Free block organization): 가용 블록들을 어떻게 추적하고 관리할 것인가?
배치 (Placement): 새로운 블록을 할당할 때, 여러 가용 블록 중 어떤 것을 선택할 것인가?
분할 (Splitting): 선택한 가용 블록이 요청보다 클 때, 남는 부분을 어떻게 처리할 것인가?
연결 (Coalescing): 해제된 블록을 주변의 다른 가용 블록과 어떻게 합칠 것인가?

이 이슈들을 묵시적 가용 리스트(Implicit Free List) 라는 간단한 구조를 통해 알아보자.

묵시적 가용 리스트 (Implicit Free Lists)

가장 간단한 방법은 힙의 모든 블록을 헤더(header)에 있는 블록 크기 정보를 이용해 암묵적으로 연결하는 것이다.

블록 구조 (64비트 기준)

implicit

Header: 8바이트(64비트) 크기. 블록 전체 크기와 할당 여부(allocated/free)를 담고 있다.
- 블록 크기는 항상 16의 배수이므로, 주소의 하위 3비트는 항상 0이다.
- 이 남는 비트 중 하나를 할당 여부를 나타내는 플래그(allocated bit)로 사용한다 (1: 할당됨, 0: 가용).
Payload: 애플리케이션이 실제 사용하는 데이터 영역.
Padding: 위 '동작 예시'에서 본 것처럼, 총 블록 크기가 16의 배수가 되도록 패딩이 추가될 수 있다.

힙 구조

implicit-free-list

위 그림처럼 힙은 연속된 블록들로 이루어져 있다. 특정 블록의 헤더에서 크기 정보를 읽으면 다음 블록의 시작 주소를 바로 알 수 있다. 이렇게 모든 블록을 순회할 수 있으므로, 가용 블록들 또한 '암시적으로' 연결되어 있다고 말하는 것이다.

장점: 구조가 매우 단순하다.
단점: 가용 블록을 찾으려면 힙 전체를 처음부터 끝까지 스캔해야 한다. 즉, 블록 배치(placement) 비용이 힙 전체 블록 수에 비례(linear time)한다. 😩

배치 정책 (Placement Policy)

k 바이트를 할당해달라는 요청이 들어왔을 때, 어떤 가용 블록을 선택할 것인가?

First Fit (최초 적합): 가용 리스트를 처음부터 검색해서, 크기가 맞는 첫 번째 블록을 선택.
- 장점: 리스트 뒤쪽에 큰 가용 블록을 남겨두는 경향이 있다.
- 단점: 리스트 앞쪽에 작은 조각(splinter)들이 많이 생겨 검색 시간을 늘릴 수 있다.
Next Fit (다음 적합): 이전 검색이 끝난 지점부터 검색을 시작.
- First Fit보다 빠를 수 있지만, 메모리 이용률은 더 나쁘다는 연구 결과가 있다.
Best Fit (최적 적합): 모든 가용 블록을 다 검색해서, 요청을 만족하는 가장 작은 블록을 선택.
- 메모리 이용률은 가장 좋지만, 힙 전체를 검색해야 하므로 시간이 오래 걸린다.

가용 블록 분할

요청을 만족하는 가용 블록을 찾았는데, 그 블록이 요청보다 크다면?

보통은 그 블록을 두 부분으로 분할(split) 한다.
앞부분은 요청한 크기만큼 할당하고, 뒷부분은 새로운 가용 블록으로 남겨둔다.

연결 (Coalescing)

블록을 free할 때, 반환된 블록의 양 옆에 다른 가용 블록이 있다면?

이들을 합치지 않으면 위 그림처럼 오류 단편화(false fragmentation)가 발생한다. 분명히 합치면 충분한 공간이 있는데도 작은 조각들로 나뉘어 있어 큰 요청을 처리하지 못하는 것이다.

따라서 인접한 가용 블록들은 하나로 합쳐주는 연결(coalescing) 과정이 필수다.

언제 연결할까?
- 즉시 연결 (Immediate coalescing): 블록이 해제될 때마다 즉시 검사하고 인접 블록을 통합
- 지연 연결 (Deferred coalescing): 나중에 필요할 때(ex: 할당 요청이 실패했을 때) 한꺼번에 연결

⇒ 즉시 연결 방법의 경우 간단하고 상수시간 내에 수행될 수 있지만 경우에 따라 블록이 통합되었다가 다시 분할되는 thrashing 상태를 야기할 수 있다. 따라서 속도가 빠른 할당기들은 지연 연결 방법을 사용하는 경우가 많다.

경계 태그를 이용한 연결

💡 문제점: 현재 블록의 다음 블록은 헤더를 통해 쉽게 찾을 수 있지만, 이전 블록을 찾으려면 힙 전체를 처음부터 스캔해야 한다. 너무 비효율적이다.

heap_block_footer

💡 해결책: 경계 태그(Boundary Tags)! 각 블록의 끝에 꼬리말(footer) 을 추가하고, 헤더의 복사본을 저장한다.

이렇게 하면, 현재 블록의 시작 주소에서 한 워드만 앞으로 가면 이전 블록의 꼬리말을 바로 읽을 수 있다. 꼬리말에는 이전 블록의 크기와 할당 정보가 있으므로, 이전 블록의 시작 주소를 상수 시간 $O(1)$에 계산할 수 있다!

연결의 4가지 경우

Case 1: 이전, 다음 블록 모두 할당 상태 -> 연결 안 함
Case 2: 이전은 할당, 다음은 가용 상태 -> 현재 블록과 다음 블록을 연결
Case 3: 이전은 가용, 다음은 할당 상태 -> 이전 블록과 현재 블록을 연결
Case 4: 이전, 다음 블록 모두 가용 상태 -> 세 블록을 모두 연결

더 나은 방법들: 명시적 리스트와 분리 리스트

묵시적 가용 리스트는 간단하지만, 할당 시간이 힙 전체 크기에 비례해서 실제 범용 할당기로는 부적합하다.

명시적 가용 리스트 (Explicit Free Lists)

아이디어: 가용 블록들만 명시적인 자료구조(예: 이중 연결 리스트)로 연결하자!

가용 블록의 페이로드 부분은 어차피 쓰이지 않으므로, 이 공간에 이전/다음 가용 블록을 가리키는 포인터(pred, succ)를 저장한다.

장점: 할당 시간이 전체 블록 수가 아닌, 가용 블록 수에 비례하게 된다. 훨씬 빠르다!
단점: 포인터를 저장할 공간이 필요해서 최소 블록 크기가 커지고, 내부 단편화 가능성도 커진다.

리스트 순서 정책

LIFO (Last-In, First-Out): 새로 해제된 블록을 리스트의 맨 앞에 삽입. free가 상수 시간에 가능.
주소 순서 (Address order): 리스트를 주소 순으로 정렬. free 시 자기 위치를 찾기 위해 선형 검색이 필요. 대신 메모리 이용률은 LIFO보다 좋다.

분리 가용 리스트 (Segregated Free Lists)

아이디어: 블록을 크기별로 그룹화해서 여러 개의 가용 리스트를 관리하자. 이걸 분리 저장소(segregated storage) 라고 한다.

모든 가능한 블록 크기를 크기 클래스(size class) 로 나눈다. (예: 2의 거듭제곱으로 나누기)
각 크기 클래스마다 별도의 가용 리스트를 둔다.
n 바이트 요청이 오면, n에 맞는 크기 클래스의 리스트부터 검색한다. 없으면 다음으로 큰 크기 클래스의 리스트를 검색한다.
장점: 검색 범위를 힙 전체가 아닌 일부로 제한하므로 검색 속도가 매우 빠르다. 메모리 이용률도 좋다 (Best Fit과 비슷한 효과를 낸다).

버디 시스템 (Buddy Systems)

분리 리스트의 특별한 경우로, 각 크기 클래스가 2의 거듭제곱(2k)인 시스템이다.

2k 크기의 블록을 할당해야 하는데 2j(jk) 크기의 블록만 있다면, 2k가 될 때까지 블록을 반으로 계속 쪼갠다. 이때 쪼개지고 남은 각 절반을 버디(buddy) 라고 한다.
블록을 해제할 때는 주변의 가용 버디와 계속 합친다.
핵심 특징: 어떤 블록의 주소와 크기를 알면, 그 버디의 주소를 비트 연산만으로 간단하게 계산할 수 있다.
장점: 검색과 연결이 매우 빠르다.
단점: 블록 크기를 2의 거듭제곱으로만 사용해야 해서 내부 단편화가 심각할 수 있다.