[크래프톤 정글] 동적 메모리 할당(CSAP 9.9장)

CSAPP 9.9장은 동적 메모리 할당에 관한 다양한 기법과 문제들을 다루고 있으며, 특히 malloc과 free 같은 C의 기본 메모리 관리 함수와 관련된 동작 원리와 구현 방식을 정리 해보고자 한다.

9.9.1 malloc과 free 함수

malloc 함수는 동적으로 메모리를 할당하고, free 함수는 그 메모리를 해제하는 기본적인 함수이다.

예시:

#include <stdio.h>
#include <stdlib.h>

int main() {
    int *arr = (int *)malloc(5 * sizeof(int)); // 5개의 정수 공간 할당
    if (arr == NULL) {
        printf("메모리 할당 실패\n");
        return 1;
    }

    for (int i = 0; i < 5; i++) {
        arr[i] = i;  // 배열에 값 저장
    }

    for (int i = 0; i < 5; i++) {
        printf("%d ", arr[i]);  // 배열 값 출력
    }
    printf("\n");

    free(arr);  // 할당된 메모리 해제
    return 0;
}

이 예시는 malloc을 사용해 5개의 정수 크기만큼 메모리를 할당하고, free를 통해 해제하는 기본적인 사용 예시이다.

9.9.2 동적 메모리 할당의 필요성

동적 메모리 할당은 프로그램 실행 중에 필요한 만큼 메모리를 유연하게 할당할 수 있는 장점을 제공한다. 정적 메모리 할당은 메모리 크기가 컴파일 시점에 고정되지만, 동적 메모리는 런타임에 크기를 결정할 수 있다.

예시:

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n;
    printf("몇 개의 정수를 입력하시겠습니까?: ");
    scanf("%d", &n);

    int *arr = (int *)malloc(n * sizeof(int)); // 사용자 입력에 따라 메모리 할당
    if (arr == NULL) {
        printf("메모리 할당 실패\n");
        return 1;
    }

    for (int i = 0; i < n; i++) {
        arr[i] = i;  // 배열에 값 저장
    }

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);  // 배열 값 출력
    }
    printf("\n");

    free(arr);  // 메모리 해제
    return 0;
}

이 예시는 사용자가 입력한 값에 따라 동적으로 배열 크기를 설정하고 메모리를 할당하는 예시이다.

9.9.3 할당기 요구 사항과 목표

동적 메모리 할당기에서 중요하게 다루어야 할 요구 사항과 목표는 메모리의 효율적인 사용과 빠른 할당/해제이다. 프로그램은 필요할 때 신속하게 메모리를 할당받아야 하고, 사용 후에는 이를 다시 시스템에 반환해야 한다.

또한, 메모리 단편화를 줄이는 것이 중요하다. 단편화는 메모리가 여러 조각으로 분리되어 실제 사용 가능한 메모리가 남아 있음에도 불구하고 큰 블록을 할당할 수 없는 상황을 초래할 수 있다.

9.9.4 단편화 (Fragmentation)

• 외부 단편화: 할당된 메모리 블록 사이에 사용되지 않는 빈 공간이 발생할 수 있다.
• 내부 단편화: 할당된 메모리 블록 내부에서 실제 사용하지 않는 메모리 공간이 발생할 수 있다.

예시:

#include <stdio.h>
#include <stdlib.h>

int main() {
    // 크기가 서로 다른 블록을 할당하여 외부 단편화 발생
    char *a = (char *)malloc(10);  // 10바이트 할당
    int *b = (int *)malloc(20);    // 20바이트 할당
    char *c = (char *)malloc(15);  // 15바이트 할당

    // 할당된 메모리 해제
    free(a);
    free(b);
    free(c);
    return 0;
}

위 예시에서는 서로 다른 크기의 블록을 할당하고 해제하는 과정에서 외부 단편화가 발생할 수 있다. 큰 블록이 필요한 경우, 빈 공간이 충분히 있어도 연속적인 공간이 없어 할당에 실패할 수 있다.

9.9.5 구현 이슈

메모리 할당기의 구현에서 중요한 고려 사항은 메모리 블록의 효율적인 배치와 사용되지 않는 공간을 줄이는 것이다. 할당기 설계자는 메모리 블록을 어떻게 배치하고, 남는 공간을 어떻게 처리할지에 대한 전략을 선택해야 한다.

9.9.6 암시적 자유 리스트 (Implicit Free List)

암시적 자유 리스트는 명시적으로 블록을 연결하지 않고, 각 블록의 앞부분에 헤더를 두어 메모리 블록의 상태(할당되었는지 여부)와 크기를 저장하는 방식이다. 이렇게 하면 자유 블록과 할당된 블록을 구분할 수 있다.

예시:

// 메모리 블록의 상태를 나타내는 간단한 구조
struct Block {
    size_t size;
    int free;  // 1이면 블록이 사용 중, 0이면 자유 블록
};

9.9.7 블록 배치

블록을 배치할 때 최적 적합(first-fit), 다음 적합(next-fit), 최소 적합(best-fit) 등의 전략이 사용된다.

• 최적 적합: 처음으로 맞는 크기의 블록을 찾으면 바로 할당.
• 최소 적합: 사용할 수 있는 블록 중에서 크기가 가장 작은 블록을 선택.
• 다음 적합: 이전에 사용한 블록 다음 위치부터 검색 시작.

9.9.8 블록 분할

크기가 큰 블록을 사용자가 요청한 크기만큼 분할하여 할당할 수 있다. 이를 통해 단편화를 줄이고, 메모리 공간을 효율적으로 사용할 수 있다.

예시:

struct Block *split_block(struct Block *block, size_t size) {
    // 큰 블록을 요청된 크기만큼 분할
    if (block->size > size + sizeof(struct Block)) {
        struct Block *new_block = (void *)((char *)block + size);
        new_block->size = block->size - size;
        new_block->free = 1;  // 새로 만든 블록은 자유 상태로 설정
        block->size = size;
    }
    return block;
}

9.9.9 힙 메모리 추가 요청

힙에 사용 가능한 메모리가 부족할 때는 운영체제에 추가 메모리를 요청할 수 있다. sbrk 시스템 호출을 사용하여 힙 메모리를 확장할 수 있다.

예시:

void *extend_heap(size_t size) {
    void *new_mem = sbrk(size);  // 힙 확장
    if (new_mem == (void *)-1) {
        return NULL;  // 확장 실패
    }
    return new_mem;
}

9.9.10 블록 병합 (Coalescing)

인접한 자유 블록들을 하나로 병합함으로써 외부 단편화를 줄일 수 있다. 이렇게 하면 더 큰 블록을 필요로 할 때 사용할 수 있는 연속적인 메모리 공간을 확보할 수 있다.

예시:

struct Block *coalesce(struct Block *block) {
    // 인접한 자유 블록을 병합
    if (block->next && block->next->free) {
        block->size += block->next->size;  // 블록 크기 합산
        block->next = block->next->next;
    }
    return block;
}

9.9.11 경계 태그를 사용한 병합

경계 태그는 각 블록의 헤더와 풋터에 블록 크기와 상태 정보를 저장하여, 인접한 블록의 상태를 쉽게 확인하고 병합할 수 있게 한다.

9.9.12 간단한 메모리 할당기 구현

이 절에서는 간단한 메모리 할당기를 구현하는 방법을 다룬다. 주로 암시적 자유 리스트를 사용한 메모리 할당 및 해제 과정에 대해 설명한다.

---