Memory 단편화 Fragmentation 과 병합 Coalescing

Memory Fragmentation

메모리 단편화(Fragmentation)는 동적 메모리 할당 시스템에서 발생하는 문제로, 메모리가 사용 가능한 작은 조각들로 나뉘어져 큰 메모리 블록을 할당하지 못하는 상황을 의미합니다. 단편화는 크게 두 가지로 나뉩니다:

1. 외부 단편화(External Fragmentation): 사용 가능한 메모리 공간이 여러 작은 조각으로 나뉘어져 있어, 비록 전체적으로는 충분한 공간이 있지만 요청된 크기의 연속적인 공간을 제공할 수 없는 경우.
2. 내부 단편화(Internal Fragmentation): 할당된 메모리 블록이 실제 필요한 크기보다 더 커서, 블록 내의 일부 공간이 낭비되는 경우.

Memory Coalescing

메모리 병합(Coalescing)은 주로 외부 단편화를 해결하기 위한 전략으로, 메모리 해제 시 인접한 빈 메모리 블록들을 병합하여 하나의 큰 블록으로 만드는 방법입니다. 이를 통해 연속된 메모리 공간을 확보하여 단편화를 줄일 수 있습니다.

1. 즉시 병합(Immediate Coalescing)
   • 메모리 블록이 해제될 때 즉시 주변의 빈 블록들과 병합을 시도하는 방법입니다.
   • 해제된 블록의 바로 앞이나 뒤에 연속된 빈 블록이 있으면 이들을 합쳐 더 큰 하나의 빈 블록으로 만듭니다.
   • 장점:
     • 단편화를 실시간으로 줄일 수 있습니다.
     • 할당 시 빈 블록을 찾기 더 쉬워져 성능이 향상될 수 있습니다.
   • 단점:
     • 매번 해제될 때마다 주변 블록을 검사하고 병합해야 하므로, 해제 연산이 느려질 수 있습니다.
2. 지연된 병합(Deferred Coalescing)
   • 메모리 해제 시에는 병합을 하지 않고, 특정 시점에 한꺼번에 빈 블록들을 병합하는 방법입니다.
   • 일정한 주기마다 또는 메모리가 부족할 때 병합 작업을 수행합니다.
   • 장점:
     • 해제 연산이 빠르게 처리될 수 있습니다.
     • 병합 작업을 한번에 처리함으로써 효율적인 메모리 관리가 가능합니다.
   • 단점:
     • 병합이 지연됨으로써, 프로그램이 큰 블록을 할당하려 할 때 적절한 크기의 연속적인 공간을 찾지 못할 가능성이 있습니다.
3. 경계 태그 병합(Boundary Tag Coalescing)
   • *각 메모리 블록의 시작과 끝에 태그(metadata)를 추가하여, 인접한 블록의 상태(사용 중인지 해제되었는지)를 기록하는 방법입니다.*
   • 메모리 블록이 해제될 때 이 태그를 사용하여 인접한 블록이 해제된 상태라면 병합을 즉시 수행합니다.
   • 장점:
     • 인접한 블록의 상태를 빠르게 확인할 수 있어, 병합이 비교적 효율적으로 이루어집니다.
   • 단점:
     • 태그를 저장하는 데 추가적인 메모리 공간이 필요합니다.

병합 전략과 메모리 할당 알고리즘의 관계

메모리 병합 전략은 메모리 할당 알고리즘과 밀접한 관계가 있습니다. 아래는 병합 전략과 자주 사용되는 할당 알고리즘입니다.

1. First-Fit 할당과 병합
   • First-Fit 할당은 빈 메모리 공간 중 처음으로 요청된 크기에 맞는 블록을 할당하는 방식입니다.
   • 이 경우, 해제 후 병합을 통해 빈 블록을 유지하면 새로운 메모리 할당 시 사용할 수 있습니다.
2. Best-Fit 할당과 병합
   • Best-Fit 할당은 요청된 크기에 가장 적합한 크기의 빈 블록을 할당합니다.
   • 작은 블록들이 남게 되어 외부 단편화가 발생하기 쉽기 때문에 병합 전략이 필요하며, 병합을 통해 외부 단편화를 줄일 수 있습니다.
3. Worst-Fit 할당과 병합
   • Worst-Fit 할당은 가장 큰 빈 블록에 메모리를 할당하여 작은 빈 블록이 생기는 것을 방지하는 방식입니다.
   • 해제 후 병합을 통해 큰 블록을 유지할 수 있어 효과적일 수 있습니다.

메모리 병합 예시

병합 전 상황:

| 사용 중 | 해제됨 | 사용 중 | 해제됨 | 사용 중 |

위 상태에서 가운데 사용 중인 블록이 해제 되는 경우 세 개의 해제된 블록을 병합할 수 있습니다.

병합 후 상황:

| 사용 중 | 해제됨 (병합) | 사용 중 |

이처럼 인접한 빈 블록들이 하나로 합쳐지면 큰 메모리 블록을 할당할 수 있는 가능성이 높아집니다.

병합 전략이 중요한 이유

1. 외부 단편화 해결:
   • 메모리 해제 시 병합을 통해 외부 단편화를 해결하지 않으면, 프로그램이 큰 크기의 메모리를 할당할 때 할당 실패가 발생할 수 있습니다.
2. 메모리 활용 효율성 증가:
   • 병합을 통해 메모리 공간이 효율적으로 사용될 수 있으며, 큰 메모리 할당 요청에 대해 더 잘 대응할 수 있습니다.
3. 성능 최적화:
   • 병합 전략을 적절히 사용하면 메모리 할당과 해제 시 성능 저하를 방지하고, 전체 시스템 성능을 향상시킬 수 있습니다.

C언어 예시

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

typedef struct Block {
    size_t size;           // 메모리 블록 크기
    struct Block* next;    // 다음 블록을 가리키는 포인터
    int free;              // 이 블록이 사용 중인지 여부 (1: free, 0: used)
} Block;

Block* freeList = NULL; // 가용 블록 리스트의 시작

// 메모리 할당 요청을 처리하는 함수 (단순화된 구현)
void* allocate(size_t size) {
    Block* current = freeList;
    // 필요한 크기의 메모리 블록을 찾는 과정
    while (current != NULL) {
        if (current->free && current->size >= size) {
            current->free = 0; // 사용 중으로 표시
            return (void*)(current + 1); // 사용자에게 메모리 반환
        }
        current = current->next;
    }
    return NULL; // 적절한 블록을 찾지 못함
}

// 메모리 해제 및 병합하는 함수
void deallocate(void* ptr) {
    if (!ptr) return;

    // 포인터를 블록의 시작 위치로 이동
    Block* block = (Block*)ptr - 1;
    block->free = 1; // 블록을 가용 상태로 변경

    // 병합 가능한 블록들을 확인하여 병합
    Block* current = freeList;
    while (current != NULL) {
        // 현재 블록과 다음 블록이 모두 가용 상태일 때 병합
        if (current->free && current->next && current->next->free) {
            current->size += current->next->size + sizeof(Block); // 크기를 병합
            current->next = current->next->next; // 다음 블록을 건너뛰고 병합
        }
        current = current->next;
    }
}

// 블록들을 초기화하는 함수 (테스트용)
void initializeMemory(size_t totalSize) {
    freeList = (Block*)malloc(totalSize);
    freeList->size = totalSize - sizeof(Block);
    freeList->free = 1;
    freeList->next = NULL;
}

int main() {
    // 1 MB 메모리 공간 초기화
    initializeMemory(1024 * 1024);

    // 메모리 할당 및 해제 예시
    void* ptr1 = allocate(256);
    void* ptr2 = allocate(128);
    deallocate(ptr1);
    deallocate(ptr2);

    // 병합 결과 확인
    return 0;
}

결론

메모리 병합은 외부 단편화를 줄이고, 메모리 사용 효율성을 높이기 위한 중요한 전략입니다. 즉시 병합, 지연된 병합, 경계 태그 병합과 같은 다양한 방식이 있으며, 상황에 따라 적절한 전략을 선택하여 메모리 관리 성능을 향상시킬 수 있습니다.