[크래프톤 정글] 동적 메모리 할당기 총정리

하루이2222 2024. 10. 16. 20:43

동적 메모리 할당기 총정리

동적 메모리 할당기는 프로그램 실행 중에 필요에 따라 메모리를 동적으로 할당하고 해제하는 시스템이다. 이 메모리 관리 방법은 고정된 크기의 메모리 할당이 아닌, 동적인 메모리 사용을 허용하며, 프로그램의 유연성을 높인다. 동적 메모리 할당기를 구현하는 방법은 여러 가지가 있으며, 각각의 방식은 메모리 사용 효율성, 성능, 단편화 문제 등에 대한 다른 접근 방식을 제공한다.

1. 동적 메모리 할당기의 개념

동적 메모리 할당기는 다음과 같은 핵심 기능을 수행한다:

할당(allocation): 필요한 크기만큼 메모리 블록을 할당하고, 이 블록의 주소를 반환한다.
해제(deallocation): 사용이 끝난 메모리 블록을 해제하고, 해당 블록을 가용 메모리로 다시 돌려놓는다.
프래그멘테이션 관리: 메모리 블록의 분할과 병합을 통해 외부 및 내부 단편화를 최소화하는 방식으로 메모리를 효율적으로 관리한다.

2. 메모리 블록의 구성

메모리 블록은 크게 두 가지 종류로 나뉜다:

사용 중인 블록(allocated block): 프로그램이 현재 사용 중인 메모리 블록.
가용 블록(free block): 아직 할당되지 않았거나, 할당되었다가 해제된 메모리 블록.

각 메모리 블록에는 일반적으로 다음과 같은 메타데이터가 포함된다:

블록 크기(size): 블록의 크기를 나타낸다.
할당 여부(allocated/free): 해당 블록이 사용 중인지, 가용 상태인지를 나타낸다.
(명시적 가용 리스트에서) 포인터(next/prev): 가용 블록 사이를 연결하는 포인터로, 다음 또는 이전 가용 블록을 가리킨다.

3. 동적 메모리 할당기 구현 방법

동적 메모리 할당기는 메모리 블록을 관리하는 방식에 따라 여러 가지 기법으로 나뉜다. 대표적인 방법으로는 묵시적 가용 리스트(implicit free list), 명시적 가용 리스트(explicit free list), 그리고 버디 할당기(buddy allocator) 등이 있다.

3.1. 묵시적 가용 리스트 (Implicit Free List)

구조: 메모리 블록들이 연속적으로 배열되어 있고, 메모리 블록에 크기와 할당 여부만을 저장한다.
탐색: 할당기가 처음부터 끝까지 순차적으로 블록을 탐색하면서 가용 블록을 찾는다.
장점: 구현이 간단하고, 추가적인 포인터 저장 공간이 필요 없다.
단점: 힙을 순차적으로 탐색해야 하기 때문에, 큰 힙에서는 성능이 저하될 수 있으며 외부 단편화 문제가 발생할 수 있다.

예시:

typedef struct {
    size_t size;
    int is_free;
} block_header;

void* heap_start;

void* malloc_implicit(size_t size) {
    block_header* current = (block_header*)heap_start;
    while (current != NULL) {
        if (current->is_free && current->size >= size) {
            current->is_free = 0;
            return (void*)(current + 1);
        }
        current = (block_header*)((char*)current + current->size + sizeof(block_header));
    }
    return NULL;
}

3.2. 명시적 가용 리스트 (Explicit Free List)

구조: 가용 블록만을 따로 연결 리스트로 관리하여, 할당 시 가용 블록만 탐색할 수 있도록 한다.
탐색: 가용 블록들의 리스트를 관리하므로, 할당할 때 불필요한 블록을 탐색하지 않고 가용 블록만 탐색한다.
장점: 탐색 성능이 향상되며, 가용 블록들을 효율적으로 관리할 수 있다. 병합(coalescing)과 분할(splitting)을 통한 단편화 해결이 용이하다.
단점: 추가적인 포인터(다음, 이전 블록)를 저장해야 하므로 메모리 오버헤드가 발생한다.

예시:

typedef struct block {
    size_t size;
    struct block* next;
    struct block* prev;
} block_header;

block_header* free_list = NULL;

void* malloc_explicit(size_t size) {
    block_header* current = free_list;
    while (current != NULL) {
        if (current->size >= size) {
            if (current->prev) current->prev->next = current->next;
            if (current->next) current->next->prev = current->prev;
            return (void*)(current + 1);
        }
        current = current->next;
    }
    return NULL;
}

3.3. 버디 할당기 (Buddy Allocator)

구조: 메모리 블록을 2의 거듭제곱 크기로 나누어 관리하는 방식. 메모리를 할당할 때 필요한 크기에 맞는 가장 작은 2^n 크기의 블록을 찾아 할당한다. 필요하면 블록을 나누고, 해제 시 병합할 수 있다.
장점: 분할과 병합이 빠르고, 큰 블록을 나중에 다시 할당할 수 있으므로 외부 단편화 문제를 해결할 수 있다.
단점: 메모리 크기가 2의 거듭제곱이 아니면 내부 단편화가 발생할 수 있다.

4. 할당 알고리즘

동적 메모리 할당기에서 가용 블록을 찾는 방법에는 여러 가지가 있다. 각 방법은 성능과 메모리 활용 효율성에 차이가 있다.

First Fit (첫 맞춤): 프리 리스트에서 첫 번째로 맞는 크기의 가용 블록을 찾아 할당한다. 간단하고 빠르지만 외부 단편화가 발생할 수 있다.
Best Fit (최적 맞춤): 크기가 가장 적합한 가용 블록을 찾는다. 외부 단편화를 줄일 수 있지만, 리스트를 전체 탐색해야 하므로 성능이 저하될 수 있다.
Worst Fit (최악 맞춤): 가장 큰 가용 블록을 할당한다. 남는 블록이 커서 나중에 큰 블록을 할당할 수 있지만, 외부 단편화가 발생할 가능성이 있다.
Next Fit (다음 맞춤): First Fit과 유사하지만, 탐색을 처음부터 시작하지 않고 마지막으로 할당된 블록 이후부터 시작한다.

5. 동적 메모리 할당에서의 단편화 문제

외부 단편화: 가용 블록들이 분산되어 있어서, 할당 요청이 들어왔을 때 충분한 총 메모리가 있음에도 불구하고, 연속된 블록이 부족하여 할당할 수 없는 상태.
내부 단편화: 할당된 블록 내에서 사용되지 않는 공간이 발생하는 문제. 예를 들어, 300바이트를 요청했을 때 512바이트가 할당되면, 212바이트가 낭비된다.

이를 해결하기 위해서는 블록 병합(coalescing), 분할(splitting), 그리고 적절한 메모리 관리 알고리즘이 필요하다.

6. C 언어와 동적 메모리 할당기

C 언어의 표준 라이브러리(malloc, free)는 주로 묵시적 가용 리스트 또는 분리형 리스트(segregated list)와 같은 단순한 동적 메모리 관리 기법을 사용한다. C는 매우 저수준 언어로, 명시적 가용 리스트와 같은 복잡한 구조를 기본적으로 제공하지 않는다. 대신, 성능과 메모리 사용의 효율성을 최대한 높이기 위해 단순한 구조를 채택하며, 메모리 관리의 많은 부분을 프로그래머에게 맡긴다.

복잡한 메모리 관리가 필요한 경우, dlmalloc이나 jemalloc과 같은 고성능 메모리 할당기를 사용할 수 있으며, 이들은 명시적 가용 리스트 또는 다른 복잡한 구조를 사용하여 메모리 할당과 해제의 효율성을 높인다.

결론

동적 메모리 할당기는 프로그램의 유연한 메모리 사용을 가능하게 하지만, 그 구현 방식에 따라 성능, 메모리 오버헤드, 단편화 문제 등 다양한 요소가 영향을 미친다. 묵시적 가용 리스트는 단순하지만 성능 문제가 발생할 수 있고,

명시적가용 리스트는 성능이 좋지만 구현이 복잡하다. 이와 같은 다양한 할당 기법은 프로그램의 요구 사항에 맞게 선택할 수 있다. C 언어는 기본적으로 묵시적 가용 리스트 방식의 동적 메모리 할당을 사용하지만, 필요에 따라 복잡한 할당기 구조를 사용하는 외부 라이브러리를 활용할 수 있다.

묵시적 가용 리스트와 명시적 가용 리스트 블럭 의 헤더&푸터

묵시적 가용 리스트(Implicit Free List)와 명시적 가용 리스트(Explicit Free List)는 동적 메모리 할당에서 사용되는 메모리 블록 관리 방식이다. 두 방식 모두 메모리 블록을 할당하고 해제할 때 필요한 메타데이터(헤더 및 푸터)를 사용하지만, 블록을 관리하는 방식과 사용하는 정보가 다르다.

헤더와 푸터는 각 메모리 블록의 크기와 할당 상태 등을 저장하는 메타데이터를 나타내며, 이를 통해 메모리 관리의 효율성을 높일 수 있다. 헤더와 푸터의 위치와 기능은 블록의 관리 방식에 따라 다를 수 있다.

1. 묵시적 가용 리스트(Implicit Free List)의 헤더와 푸터

헤더(Header)

묵시적 가용 리스트에서 헤더는 각 메모리 블록의 시작 부분에 위치하며, 블록의 크기와 할당 상태를 저장한다. 헤더는 보통 크기와 할당 상태를 함께 저장한 하나의 필드를 사용한다.

헤더 구조:
- 크기: 블록의 크기를 나타내며, 메모리 할당기에서 블록 크기를 계산할 때 사용된다.
- 할당 여부: 해당 블록이 사용 중인지 가용 상태인지를 나타낸다. 일반적으로 크기의 하위 비트 1비트를 사용하여 할당 상태를 저장한다.

푸터(Footer)

묵시적 가용 리스트에서는 보통 푸터가 사용되지 않지만, 블록 병합(coalescing)을 지원하는 경우, 푸터를 사용하여 블록의 뒤에서부터도 메타데이터에 접근할 수 있게 한다. 푸터는 헤더와 동일한 정보를 담고 있으며, 블록의 끝 부분에 위치하여 뒤에서부터 블록 크기와 할당 상태를 확인할 수 있다.

푸터 구조:
- 헤더와 동일한 정보를 포함한다 (크기와 할당 상태).

묵시적 가용 리스트 블록 구조:

| 헤더 (크기 + 할당 여부) | 데이터 영역 | (푸터) |

푸터는 항상 사용되지는 않으며, 특히 블록 병합이 필요하지 않다면 생략될 수 있다.

예시 코드 (묵시적 리스트):

typedef struct {
    size_t size_and_alloc;  // 블록 크기와 할당 상태를 함께 저장
} block_header;

void* malloc_implicit(size_t size) {
    block_header* current = (block_header*)heap_start;
    while (current != NULL) {
        size_t block_size = current->size_and_alloc & ~1;  // 크기만 추출
        int is_alloc = current->size_and_alloc & 1;  // 할당 상태 추출
        if (!is_alloc && block_size >= size) {
            current->size_and_alloc |= 1;  // 블록을 할당된 상태로 표시
            return (void*)(current + 1);  // 헤더 뒤의 데이터 부분 반환
        }
        current = (block_header*)((char*)current + block_size);
    }
    return NULL;
}

2. 명시적 가용 리스트(Explicit Free List)의 헤더와 푸터

명시적 가용 리스트는 가용 블록을 별도의 연결 리스트로 관리하며, 추가적인 포인터(이전 블록과 다음 블록)를 저장한다. 명시적 리스트에서는 헤더와 푸터 외에도 각 블록에 포인터 필드가 추가된다.

헤더(Header)

명시적 가용 리스트의 헤더는 블록 크기와 할당 상태를 저장하며, 블록을 연결 리스트로 관리하기 위한 포인터도 포함된다.

헤더 구조:
- 크기: 블록의 크기를 저장한다.
- 할당 여부: 해당 블록이 할당되었는지, 가용 상태인지를 나타낸다.
- 다음 블록 포인터: 가용 리스트에서 다음 가용 블록을 가리키는 포인터.
- 이전 블록 포인터: 가용 리스트에서 이전 가용 블록을 가리키는 포인터.

푸터(Footer)

명시적 가용 리스트에서도 병합(coalescing)을 지원하기 위해 푸터가 사용된다. 푸터는 헤더와 동일하게 블록 크기와 할당 상태를 포함하며, 주로 블록을 뒤에서부터 접근할 수 있게 해준다. 이 정보를 사용하면, 인접한 블록을 확인하여 병합할 수 있다.

명시적 가용 리스트 블록 구조:

| 헤더 (크기 + 할당 여부 + 포인터) | 데이터 영역 | 푸터 (크기 + 할당 여부) |

헤더와 푸터 모두 블록의 할당 상태와 크기를 기록하므로, 블록을 해제할 때 인접한 가용 블록과 병합할 수 있다.

예시 코드 (명시적 리스트):

typedef struct block {
    size_t size_and_alloc;  // 크기와 할당 상태
    struct block* next;     // 다음 가용 블록
    struct block* prev;     // 이전 가용 블록
} block_header;

void* malloc_explicit(size_t size) {
    block_header* current = free_list;
    while (current != NULL) {
        size_t block_size = current->size_and_alloc & ~1;  // 크기 추출
        int is_alloc = current->size_and_alloc & 1;  // 할당 여부
        if (!is_alloc && block_size >= size) {
            current->size_and_alloc |= 1;  // 블록을 할당된 상태로 표시
            // 가용 리스트에서 블록 제거
            if (current->prev) current->prev->next = current->next;
            if (current->next) current->next->prev = current->prev;
            return (void*)(current + 1);  // 헤더를 건너뛰고 데이터 반환
        }
        current = current->next;
    }
    return NULL;
}

3. 헤더와 푸터의 역할 정리

헤더의 역할

크기 정보: 블록의 크기를 저장하여, 블록의 끝 위치와 인접 블록을 찾을 때 사용한다.
할당 여부: 블록이 할당된 상태인지 가용 상태인지를 저장한다.
포인터 필드(명시적 리스트): 가용 블록끼리의 연결을 위해 다음 블록과 이전 블록을 가리키는 포인터를 포함한다.

푸터의 역할

크기 정보와 할당 상태: 블록의 끝에서 블록의 크기와 할당 상태를 저장하여, 뒤에서부터 블록 정보를 읽을 수 있게 한다.
블록 병합에 사용: 가용 블록을 해제할 때, 인접한 블록과 병합할 수 있는지 확인하기 위해 푸터 정보를 사용한다.

4. 차이점 정리

항목	묵시적 가용 리스트	명시적 가용 리스트
헤더	블록 크기 및 할당 여부만 저장	블록 크기, 할당 여부, 다음/이전 포인터 저장
푸터	일반적으로 사용하지 않지만 병합 시 사용 가능	병합을 위해 사용, 블록 크기와 할당 여부 저장
탐색 방식	모든 블록을 순차적으로 탐색	가용 블록만 탐색 (가용 블록 간 포인터로 연결)
블록 연결	블록 간 연결 없음	가용 블록 간 포인터로 연결
메모리 오버헤드	적음	추가 포인터 필드로 인해 메모리 오버헤드 발생
블록 병합	푸터가 있는 경우에만 인접 블록을 병합할 수 있음	푸터를 사용하여 인접한 가용 블록을 쉽게 병합할 수 있음

결론

묵시적 가용 리스트와 명시적 가용 리스트는 동적 메모리 할당에서 각각 다른 방식으로 블록을 관리한다. 묵시적 리스트는 단순하고 효율적이지만, 탐색 성능이 떨어지며 블록 병합이 어렵다. 명시적 리스트는 탐색 성능이 좋고 블록 병합이 용이하지만, 포인터 관리로 인해 메모리 오버헤드가 발생한다. 헤더와 푸터는 메모리 블록의 메타데이터를 저장하는 중요한 요소로, 블록 관리의 핵심 역할을 담당한다.

내,외부 단편화의 예시

동적 메모리 할당에서 발생할 수 있는 외부 단편화와 내부 단편화는 메모리 효율성을 저하시키는 주요 문제들이다. 이를 해결하기 위해 다양한 기법들이 사용되며, 그 중에서 대표적인 방법으로 블록 병합(coalescing), 블록 분할(splitting), 그리고 메모리 관리 알고리즘을 통해 문제를 완화할 수 있다.

각각의 단편화와 그 해결책에 대해 예시를 통해 설명하겠다.

1. 외부 단편화(External Fragmentation)

외부 단편화는 가용 블록들이 메모리 공간에 분산되어 있어, 총 메모리 용량은 충분하지만, 연속된 크기의 블록이 없어서 큰 메모리 할당 요청을 처리하지 못하는 상황을 말한다.

예시:

메모리에 가용 블록들이 여러 개 존재하지만, 그 사이에 할당된 블록들 때문에 하나의 큰 연속된 공간이 없다.

[블록 1 할당됨] [가용 블록 100B] [블록 2 할당됨] [가용 블록 200B] [블록 3 할당됨] [가용 블록 150B]

이 상황에서 300바이트 크기의 메모리 할당 요청이 들어오면, 각각의 가용 블록을 모두 합치면 450바이트가 있지만, 연속된 300바이트 크기의 블록이 없기 때문에 할당할 수 없다.

해결책: 블록 병합(Coalescing)

블록 병합은 해제된 인접한 가용 블록들을 하나의 큰 블록으로 합치는 기법이다. 이 기법을 통해 외부 단편화를 완화할 수 있다.

블록 병합 예시:

해제된 두 가용 블록이 인접해 있을 때 이들을 하나로 병합하여 연속된 가용 메모리 공간을 만든다.

[블록 1 할당됨] [가용 블록 100B] [가용 블록 200B] -> [가용 블록 300B]

이제 연속된 300바이트 크기의 가용 블록이 만들어져, 300바이트 할당 요청을 처리할 수 있다.

병합 코드 예시:

void coalesce(block_header* block) {
    block_header* next_block = (block_header*)((char*)block + block->size + sizeof(block_header));

    // 인접한 블록이 가용 상태라면 병합
    if (next_block->is_free) {
        block->size += next_block->size + sizeof(block_header);  // 크기 증가
    }
}

이 코드에서는 현재 블록과 그 다음 블록이 가용 상태일 경우, 두 블록을 병합하여 하나의 큰 블록으로 만드는 방식이다.

2. 내부 단편화(Internal Fragmentation)

내부 단편화는 할당된 블록 내에서 요청한 크기보다 더 큰 블록이 할당되어, 사용하지 않는 여분 공간이 발생하는 문제를 말한다. 이 여분 공간은 프로그램이 사용하지 않지만, 할당된 메모리로 간주되어 낭비된다.

예시:

사용자가 300바이트를 요청했을 때, 할당기에서는 512바이트 블록을 할당한다. 이로 인해 212바이트가 낭비된다.

[블록 512B 할당됨 (300B 사용 + 212B 낭비됨)]

해결책: 블록 분할(Splitting)

블록 분할은 큰 가용 블록이 할당될 때, 남는 부분을 새로운 작은 가용 블록으로 나누어 사용하는 방식이다. 이를 통해 내부 단편화를 줄일 수 있다.

블록 분할 예시:

가용 블록이 512바이트 크기이고, 300바이트의 할당 요청이 들어온 경우:

[가용 블록 512B] -> [블록 300B 할당됨] [가용 블록 212B]

이제 300바이트를 할당하고 남은 212바이트는 새로운 가용 블록으로 나누어 저장한다. 남는 메모리가 낭비되지 않고 재사용될 수 있다.

분할 코드 예시:

void split_block(block_header* block, size_t size) {
    // 요청된 크기만큼 할당하고, 남는 공간을 새로운 가용 블록으로 나누기
    if (block->size > size + sizeof(block_header)) {
        block_header* new_block = (block_header*)((char*)block + size + sizeof(block_header));
        new_block->size = block->size - size - sizeof(block_header);
        new_block->is_free = 1;

        block->size = size;  // 기존 블록의 크기를 요청된 크기로 설정
    }
}

이 코드에서는 큰 블록이 있을 때, 요청된 크기만큼의 블록을 할당하고, 남은 부분을 새로운 가용 블록으로 만들어 가용 리스트에 추가한다.

3. 적절한 메모리 관리 알고리즘

외부 단편화와 내부 단편화를 최소화하기 위해 다양한 메모리 관리 알고리즘을 사용한다. 이들 알고리즘은 블록을 할당할 때, 가용 블록을 어떻게 선택하는지에 따라 단편화 문제를 완화할 수 있다.

3.1 First Fit (첫 맞춤)

가용 블록 리스트에서 첫 번째로 할당할 수 있는 블록을 선택하는 방식이다. 탐색 속도가 빠르지만, 자주 사용하면 외부 단편화가 발생할 수 있다.

block_header* first_fit(size_t size) {
    block_header* current = free_list;
    while (current != NULL) {
        if (current->is_free && current->size >= size) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

3.2 Best Fit (최적 맞춤)

가용 블록 중 요청된 크기에 가장 가까운, 즉 가장 작은 블록을 선택하는 방식이다. 외부 단편화를 줄일 수 있지만, 탐색 시간이 오래 걸릴 수 있다.

block_header* best_fit(size_t size) {
    block_header* current = free_list;
    block_header* best = NULL;
    while (current != NULL) {
        if (current->is_free && current->size >= size) {
            if (best == NULL || current->size < best->size) {
                best = current;
            }
        }
        current = current->next;
    }
    return best;
}

3.3 Worst Fit (최악 맞춤)

가용 블록 중 가장 큰 블록을 선택하는 방식이다. 큰 블록을 선택해 남는 공간을 줄이려는 의도이지만, 외부 단편화를 유발할 가능성이 있다.

block_header* worst_fit(size_t size) {
    block_header* current = free_list;
    block_header* worst = NULL;
    while (current != NULL) {
        if (current->is_free && current->size >= size) {
            if (worst == NULL || current->size > worst->size) {
                worst = current;
            }
        }
        current = current->next;
    }
    return worst;
}

요약

외부 단편화: 메모리 블록이 분산되어 있어서, 큰 연속된 공간을 찾지 못해 메모리 할당이 어려운 문제. 블록 병합(Coalescing) 기법으로 해결할 수 있다.
내부 단편화: 할당된 블록 내에서 남는 공간이 발생하는 문제. 블록 분할(Splitting) 기법을 통해 남는 공간을 나눠서 사용할 수 있다.
메모리 관리 알고리즘: First Fit, Best Fit, Worst Fit과 같은 메모리 할당 알고리즘을 통해 단편화 문제를 완화할 수 있다.

'cs' 카테고리의 다른 글

[크래프톤 정글] 컴퓨터 시스템 hello.c 실행 전체 플로우 정리 (0)	2024.10.16
[크래프톤 정글] 동적 메모리 할당(CSAP 9.9장) (0)	2024.10.14
[크래프톤 정글] c프로그래밍에서의 고통된 메모리 관련 버그(CSAP 9.11장) (0)	2024.10.14
[크래프톤 정글] 시그널(CSAP 8.5장) (0)	2024.10.12
[크래프톤 정글] 예외상황(CSAP 8.1장) (1)	2024.10.12

현재글[크래프톤 정글] 동적 메모리 할당기 총정리

하루이의 개발 노트

경험 하는 개발자가...되고 싶어요...

Today :
Yesterday :

« 2024/10 »
일	월	화	수	목	금	토
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31