컴퓨터 시스템 : CSAPP 9장 정리 - 9.9 동적 메모리 할당 9.9.1~9.9.5

9.9 동적 메모리 할당 (Dynamic Memory Allocation)

C 프로그래머는 mmap 및 munmap 같은 저수준 함수보다는, 실행 시간에 추가적인 가상 메모리가 필요할 때 동적 메모리 할당자(dynamic memory allocator)를 사용하는 것을 더 선호한다.

동적 메모리 할당자는 프로세스의 가상 메모리 내 힙(heap)이라고 불리는 영역을 관리한다. 이 힙은 초기화되지 않은 데이터 영역 바로 다음에서 시작해서, 더 높은 주소 방향으로 확장되는 demand-zero memory이다. 커널은 각 프로세스마다 brk라는 포인터를 유지하여 힙의 꼭대기를 추적한다.

할당자는 힙을 다양한 크기의 블록으로 구성된 컬렉션으로 유지하며, 각각은 할당됨(allocated) 또는 비어있음(free) 상태다. 비어 있는 블록은 애플리케이션이 명시적으로 요청할 때까지 할당되지 않은 상태로 유지된다. 마찬가지로, 할당된 블록은 명시적 free() 호출이나 자동 메모리 관리 기법(예: garbage collection)에 의해 해제되기 전까지는 유지된다​.

할당자는 크게 두 종류로 나뉜다:

• 명시적 할당자(explicit allocator): 프로그래머가 직접 malloc, free 등을 호출해 메모리를 할당/해제함 (C의 표준 라이브러리가 이에 해당).
• 암시적 할당자(implicit allocator): 사용되지 않는 메모리를 자동으로 감지하고 해제함. 주로 garbage collector가 이 역할을 수행하며, Java, ML, Lisp 등의 언어가 대표적이다.

이 장에서는 명시적 할당자, 특히 힙 메모리를 다루는 방식에 중점을 두고 설명한다.

---

9.9.1 malloc과 free 함수

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

#include <stdlib.h>
void *malloc(size_t size);  // 성공 시 블록의 포인터, 실패 시 NULL 반환

• malloc(size)는 최소 size 바이트 크기의 메모리 블록을 할당하며, 다양한 데이터 객체에 적절한 정렬 조건을 만족한다.
• 32비트 모드: 주소는 8의 배수
• 64비트 모드: 주소는 16의 배수

할당 실패 시 malloc은 NULL을 반환하고 errno를 설정한다. 초기화되지 않은 메모리를 반환하므로, 메모리를 0으로 초기화하려면 calloc, 크기를 바꾸려면 realloc을 사용할 수 있다.

free 함수

#include <stdlib.h>
void free(void *ptr);

• ptr은 반드시 malloc, calloc, realloc을 통해 얻은 메모리 블록의 시작 주소여야 한다.
• 잘못된 주소를 넘겨줄 경우 정의되지 않은 동작(undefined behavior)을 유발할 수 있으며, 에러 메시지도 없기 때문에 디버깅이 매우 어렵다​.

---

9.9.2 왜 동적 메모리 할당을 사용하는가? (Why Dynamic Memory Allocation?)​

프로그램이 동적 메모리 할당(dynamic memory allocation)을 사용하는 가장 중요한 이유는, 프로그램이 실행되기 전까지는 특정 데이터 구조의 크기를 알 수 없는 경우가 많기 때문이다.

예제: 사용자로부터 정수 리스트를 입력받는 프로그램

다음과 같은 프로그램을 생각해 보겠다. 사용자로부터 n개의 정수를 입력받아 배열에 저장하는 프로그램이다.

#include "csapp.h"

#define MAXN 15213

int array[MAXN];

int main() {
    int i, n;
    scanf("%d", &n);
    if (n > MAXN)
        app_error("Input file too big");
    for (i = 0; i < n; i++)
        scanf("%d", &array[i]);
    exit(0);
}

이 프로그램은 배열 크기를 MAXN이라는 상수로 정적으로 정의한다. 하지만 이는 매우 비효율적이고, 유지 보수가 어려운 방법이다.

• MAXN은 시스템의 가상 메모리와 아무 관련도 없이 임의로 정해진 값이다.
• 만약 입력이 MAXN보다 크면 프로그램을 재컴파일해야만 한다.
• 대규모 소프트웨어에서는 이러한 방식이 심각한 유지 보수 문제로 이어질 수 있다.

개선된 방식: 동적 할당

보다 나은 방법은, n이 정해진 후에 배열을 런타임에 동적으로 할당하는 것이다.

#include "csapp.h"

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);
}

이 방식의 장점은 다음과 같다:

• 배열의 최대 크기가 가상 메모리의 실제 사용 가능량에 의해서만 제한된다.
• 메모리 사용이 훨씬 유연하고 효율적이다.

---

9.9.3 할당자의 요구사항과 목표 (Allocator Requirements and Goals)

명시적 할당자(explicit allocator)는 다음과 같은 엄격한 제약 조건들 하에서 작동해야 한다​:

제약 조건

1. 임의의 요청 순서 처리 (Handling arbitrary request sequences)
   • 할당자에게는 어떤 순서로 malloc과 free 요청이 들어올지 알 수 없다.
   • 어떤 free 요청이 반드시 그 이전의 malloc 요청으로부터 얻어진 블록에 대응해야 한다는 조건만 있다.
   • 요청이 중첩되거나 순차적으로 짝을 이루는 것이라고 가정할 수 없다.
2. 요청에 즉시 응답 (Making immediate responses)
   • malloc 요청이 들어오면 즉시 응답해야 하며, 요청을 재정렬하거나 버퍼링 하여 성능을 개선하는 것은 허용되지 않는다.
3. 힙만 사용 (Using only the heap)
   • 할당자가 사용하는 모든 자료구조는 힙 자체에 저장되어야 한다.
   • 이는 할당자의 확장성(scalability) 을 보장하기 위해 필요하다.
4. 블록 정렬 (Alignment requirement)
   • 모든 데이터 객체에 대해 적절한 정렬 조건을 만족하도록 블록을 정렬해야 한다.
5. 할당된 블록은 수정 금지 (Not modifying allocated blocks)
   • 이미 할당된 블록은 이동하거나 수정할 수 없다.
   • 따라서 블록 압축(compaction) 같은 기술은 사용할 수 없다.

위의 제약 조건 하에서 할당자는 다음 두 가지 상충하는 목표를 달성하려고 한다:

1. 처리량 최대화 (Maximizing throughput)
   • 단위 시간당 처리할 수 있는 malloc과 free 요청 수를 최대화해야 한다.
   • 일반적으로는 요청 하나를 처리하는 데 걸리는 평균 시간을 줄이면 된다.
   • 대개 malloc의 최악 수행 시간이 비어 있는 블록 수에 비례(linear) 하고, free는 상수 시간 내에 처리될 수 있다.
2. 메모리 활용도 최대화 (Maximizing memory utilization)
   • 단순한 프로그래머는 가상 메모리가 무한하다고 오해하지만, 실제로는 디스크의 스왑 공간에 의해 제한된다.
   • peak utilization이라는 지표를 사용해 메모리 사용 효율을 측정한다:
   여기서,
   • PiP_iPi​: 현재까지 할당된 블록들의 payload 총합
   • HkH_kHk​: 요청 RkR_kRk​까지의 힙 크기 (단조 증가)
   • UkU_kUk​: 첫 k+1k+1k+1개의 요청에 대한 최대 메모리 활용도

이러한 목표 사이에는 항상 트레이드오프가 존재하며, 할당자는 적절한 균형을 찾아야 한다.

---

9.9.4 단편화 (Fragmentation)​

단편화(fragmentation)는 힙 활용률이 떨어지는 주요 원인이다. 이는 사용되지 않는 메모리가 존재하지만 할당 요청을 만족시킬 수 없는 경우에 발생한다. 단편화에는 두 가지 유형이 있다:

내부 단편화 (Internal Fragmentation)

• 정의: 할당된 블록이 실제 payload보다 더 클 때 발생
• 원인
  • 최소 블록 크기 제약
  • 정렬 조건(alignment)을 만족시키기 위한 크기 조정
• 측정 방법: 모든 할당된 블록에 대해 블록 크기와 payload의 차이를 합산한 값

이 단편화는 오직 이전의 할당 요청 패턴과 할당자 구현에 따라 결정되며. 비교적 정량화가 쉽다.

외부 단편화 (External Fragmentation)

• 정의: 전체적으로는 충분한 비어있는 메모리가 있음에도 불구하고, 단일 연속 블록으로는 부족하여 요청을 만족시킬 수 없는 경우 발생
• 예시: 총 8 워드의 비어있는 메모리가 있지만, 4 워드 + 4 워드로 분리되어 있어 8 워드를 요구하는 요청을 처리할 수 없음.
• 특징
  • 정량화하기 어렵고, 미래 요청 패턴에 따라 달라질 수 있음
  • 예를 들어 모든 비어있는 블록이 4워드일 때, 이후 요청이 4 워드 이하라면 문제없지만, 그보다 크면 외부 단편화가 발생함

해결 전략

• 외부 단편화는 예측이 어렵기 때문에, 할당자들은 일반적으로 소수의 큰 free 블록을 유지하려는 휴리스틱(heuristic)을 사용한다. 이렇게 하면 다양한 크기의 요청을 더 잘 처리할 수 있다.

---

9.9.5 구현 이슈 (Implementation Issues)​

할당자를 설계할 때 고려해야 할 몇 가지 핵심 이슈가 있다. 이 절에서는 메모리 할당기의 기본적 구현 문제와 함께, 그 해결 방안의 방향을 제시한다.

가장 단순한 할당기

• 힙을 바이트 배열로 간주하고, 포인터 p를 첫 바이트에 두는 방식
• malloc(size)는 현재 포인터 p를 저장하고, p를 size만큼 증가시킨 후, 이전 주소를 반환
• free(ptr)는 아무 일도 하지 않고 단순히 반환

➤ 장점: 극단적으로 높은 처리량 (몇 개의 명령어만 실행됨)
➤ 단점: 재사용을 전혀 하지 않기 때문에 메모리 활용도가 극히 낮음

실제 할당기에서 고려해야 할 문제들

1. Free Block Organization (비어 있는 블록 관리)
   • 비어 있는 블록들을 어떻게 추적하고 관리할 것인가?
2. Placement (배치)
   • 새로 할당될 블록을 어떤 비어 있는 블록에 둘 것인가?
3. Splitting (분할)
   • 할당된 블록을 어떤 free 블록에 배치한 후, 남은 부분은 어떻게 처리할 것인가?
4. Coalescing (병합)
   • 해제된 블록을 다른 인접한 free 블록과 어떻게 병합할 것인가?

이러한 문제들을 해결하기 위해 다음 절부터 암시적 free list 같은 구체적인 자료구조를 사용한 할당기 구현이 소개한다.