동적 메모리 할당기 구현

Dynamic Memory Allocation을 하는 이유

우리는 왜 동적 메모리 할당을 해야할까? 이유는 반대편의 정적 메모리 할당은 메모리 관리가 어렵기 때문이다. 왜냐하면, 정적 메모리 할당은 선언된 배열 요소의 수가 사용된 요소의 수보다 많을 수도 있고, 선언된 배열 요소의 수가 사용된 요소의 수보다 적을 수도 있고, 배열 선언할 때 배열 길이에 변수를 설정하면 에러가 발생할 수 있기 때문이다. 즉, 정적 메모리 할당은 프로그램 컴파일시에 메모리 statck에 얼마만큼의 크기로 할당을 해야하는지 결정되기 때문에 컴파일 이후 크기가 변경될 수 없다. 이러한 문제점을 해결하고자 메모리 관리의 어려움을 해결해주는 Runtime시 메모리 heap에 데이터를 동적으로 할당해주는 Dynamic memory allocation이 나왔다. 이로써 메모리의 최대 크기는 사용 가능한 가상 메모리의 양에 의해서만 제한된다.

 

정리하면 동적 메모리 할당을 하는 이유는 프로그램을 실행시키기 전에 자료구조의 크기를 알 수 없는 경우가 많아 이를 해결하고자 나온 방식이다.

 

Dynamic Memory Allocator는 왜 중요한가

우선 동적 메모리 할당기가 무엇인지 알아보면, 이는 프로세스 가상 메모리 영역을 관리하고, 이 가상 메모리 영역을 힙(heap)이라고 한다. 우리는 이 동적 메모리 할당기를 사용해 프로그램이 돌아가는 시간(런타임)에 추가 가상 메모리를 얻는다. 즉, 동적 메모리 할당기는 heap이라는 가상 메모리 영역을 관리하며, 메모리 할당, 해제, 알맞은 가용블록 찾기, 가용블록이 없으면 heap 확장 후 새 주소 할당 등의 역할을 한다.

 

Dynamic Memory Allocatior는 어디에서 메모리를 가져와서 할당해주고, 반납할까

힙 영역은 사용자에 의해 메모리가 할당되고, 해제되는 영역으로 필요에 의해 동적으로 메모리를 할당할 때 사용한다. 그래서 가상 메모리 영역을 관리하고, 메모리 주소값에 의해서만 참조되고 사용되는 영역이다. 여기까지가 힙에 대한 설명인고, 어플리케이션이 사용하는 메모리 영역이 여러 segment로 범주화되어 관리되는 것을 데이터 세그먼트에 정의라고 할 수 있다. 그리고 이들 개념을 합쳐 Heap Segment는 다양한 사이즈의 할당된 블록(allocated block)과 가용 블록(free block)들로 이루어져 있다고 말할 수 있다.

 

즉, 어플리케이션이 동적 메모리 할당기에 메모리 할당을 요청하면,

1. 먼저 적당한 free block을 찾아서 이 free block에 대한 pointer를 어플리케이션에 반환해주고, 해당 free block을 allocated 되었다고 기입해둔다.
2. 만약 어플리케이션이 요청하는 사이즈의 free block을 찾을 수 없다면, sbrk라는 system call을 통해서 시스템으로부터 더 많은 메모리를 할당받는다. 이를 통해서 적절한 사이즈의 free block을 확보하고, 이에 대한 포인터를 어플리케이션에게 반환해준다. 즉, sbrk를 호출하면 brk 포인터를 위로 올리거나 낮춤으로써 heap memory를 증가시키거나 감소시킬 수 있다.

 

Allocator와 free list 확실히 이해하기 (explicit vs implicit)

• Explicit Allocator : 할당된 블록을 명시적으로 free해줘야하는 할당기
• Implicit Allocator : 자바의 가비지 컬렉터처럼 할당된 블록이 더이상 사용되지 않으면 이를 감지해서 해제해주는 할당기
• Explicit Free List : 가용(free)블록들이 묵시적 또는 암묵적으로 서로 연결되어 잇는 가용 리스트. 여기서 묵시적이라는 뜻은 겉으로 드러나게 다른 free 블록들과 연결되어 있는 것은 아니지만, 간접적으로 블록의 헤더에 사이즈가 명시되어있기 때문에 연결되어있다고 볼 수 있다.
• Implicit Free List : 가용(free)블록의 payload는 어차피 프로그램에 의해서 필요하지 않으므로, 이 자리에 이전 블록과 다음 블록을 가리키는 포인터를 포함해서 '명시적 또는 직접적'으로 다른 가용 블록과 연결되어 있는 가용리스트이다.

 

Dynamic Memory Allocator를 만드는 이유

어플리케이션이 메모리를 요청하면 malloc을 통해 메모리를 할당받고, free를 통해 메모리를 반환한다. 이렇게 malloc이 어떻게 돌아가는지 그 과정을 파악하고, CMU 과제 중 하나인 malloc lab을 직접 구현해본다. 그리고 추가적으로 C 포인터 개념과 gdb 디버거 사용법 등을 익힌다.

 

가상 메모리의 동작 방식 측면. 결국에 동적 메모리 할당기는 힙을 관리하는 역할을 하고, 힙은 가상 메모리의 영역이기 때문에 동적 메모리 할당기의 동작 방식을 이해함으로써 가상 메모리의 동작 방식을 수월하게 이해할 수 있다.

 

Dynamic Memory Allocator를 구현하면서 실제로 중요하게 고려해야 할 점

동적 메모리 할당기의 성능을 측정하는 대표적인 지표는 memory utilization과 throughput이다. 즉, heap segment를 얼마나 낭비하는 공간 없이 어플리케이션이 필요한 데이터를 꽉 채워썼는가와 얼마나 빨리 어플리케이션의 allocate/free 요청을 처리해줄 수 있는가이다.

 

그리고 이에 영향을 끼치는 중요한 구현 요소는 다음과 같다.

 

free block organization

heap segment는 array of bytes이고, 이 array가 다양한 size의 free block과 allocated block으로 뒤섞여있다. 이런 상황에서 어떤 방식으로 free block들을 축적 관리할 것인가에 관한 것이 free block organization이다. 이렇게 free block들을 일종의 리스트 형태로 추적 관리하는 방식은 크게 다음과 같이 3가지가 있다. implicit free list, explicit free list, segregated free list. 어떤 종류의 free block organization을 채택하느냐에 따라 free block format, placing 방식, spliting 방식, coalescing 방식이 모두 달라질 수 있다.

 

placing

어플리케이션으로부터 메모리를 할당해달라는 요청을 받았을 때, 할당기는 위에서 결정된 free block organizations에 따라 사용하고 있는 free list에서 적절한 free block을 찾아야 한다. 이때, 이 free block을 찾는 방식에 관한 것이 placing이고, 여기에는 first-fit, next-fit, best-fit이 있다.

 

splitting

fit한 free block을 찾고나서, 해당 블록을 allocated로 표시하고, 어플리케이션에게 해당 블록에 대한 포인터를 바로 반환할 수 있다. 하지만 만약 해당 free block이 어플리케이션이 요청한 사이즈보다 훨씬 클 경우에는 이 block을 통째로 어플리케이션에게 주면 낭비가 된다.(내부 단편화). 따라서 이 낭비를 줄이기 위해, free block을 적절히 2개의 블록으로 쪼개서 필요한 만큼만 allocated 처리하고, 나머지 block은 free 상태로 처리해놓을 수 있다.

 

coalescing

splitting 이후에 생성된 free block의 앞, 뒤로 만약에 또 다른 free block이 존재한다면 블록들을 합쳐놓는게 좋을 수 있다. 즉, coalescing의 정확한 목적은 외부 단편화를 막기 위함이다. 즉, free list에서 fit한 크기의 free block을 찾지 못해서 널을 반환하거나 sbrk system call을 이용해서 불필요하게 늘려야 할 때를 대비해서 연속적으로 존재하는 free block을 미리 합쳐놓는 작업이다.

 

 

구현

우선 즉시 경계 태그 연결을 사용하여 묵시적 가용 리스트에 기초한 간단한 할당기를 구현해보도록 한다.

 

기본 할당기는 memlib.c 패키지에서 제공되는 메모리 시스템의 모델을 사용한다. 이 모델의 목적은 우리가 설계한 할당기가 기존의 시스템 수준의 malloc 패키지와 상관없이 돌 수 있도록 하기 위한 것이다.

mem_init 함수에서 mem_brk 다음에 오는 바이트들은 미할당 가상메모리를 나타낸다. 할당기는 mem_sbrk 함수를 호출해서 추가적인 힙 메모리를 요청하며, 이것은 힙을 축소하라는 요청을 거부하는 것만 제외하고는 시스템의 sbrk 함수와 동일한 의미일뿐만 아니라 동일한 인터페이스를 가진다.

 

할당기 자체는 사용자가 자신의 응용 프로그램에서 컴파일하고 링크할 수 있는 소스 파일에 포함된다. 그리고 할당기는 다음 세 개의 함수를 응용 프로그램에 알려준다.

mm_init, *mm_malloc, mm_free

 

mm_init 함수는 할당기를 초기화하고, 성공이면 0을 반환한고, 아니면 -1을 반환한다.

mm_malloc과 mm_free 함수는 이들에 대응되는 시스템 함수들과 동일한 인터페이스와 의미를 갖는다.

할당기의 최소 블록 크기는 16바이트이며, 묵시적 가용 리스트에서는 다음과 같이 변하지 않는 형태를 갖는다.

묵시적 가용 리스트의 불변하는 형식

위 그림에서 첫 번째 워드는 더블 워드 경계로 정렬된 미사용 패딩 워드이다.

패딩 다음에는 특별한 prologue 블록이 오며, 이것은 header와 footer로만 구성된 8바이트 할당 블록이다. prologue 블록은 초기화 과정에서 생성되며 절대로 반환하지 않는다.

prologue 블록 다음에는 malloc 또는 free를 호출해서 생성된 0 또는 1개 이상의 일반 블록들이 온다.

그리고 heap은 항상 특별한 epilogue 블록으로 끝나며, 이것은 header만으로 구성된 크기가 0으로 할당된 블록이다

이러한 prologue와 epilogue 블록들은 연결과정 동안에 가장자리 조건을 없애주기 위한 속임수로 볼 수 있다.

 

할당기는 1개의 static 전역변수인 *heap_listp를 사용하고, 이는 항상 prologue 블록을 가리킨다.

 

Implicit free list 방식

implicit free list의 장점은 단순성이다. 하지만 큰 단점을 가지는데, 가용 리스트를 탐색해야 하는 연산들의 비용이 heap에 있는 전체 할당된 블로과 가용 블록수에 비례한다는 단점이다. 따라서 실제로 사용되지는 않는다.

그러나 할당에 꼭 필요한 개념을 가지고, explicit free list와 segregated list를 이용하는 발전된 방식들의 뿌리가 이 방법이므로 처음 할당기를 구현한다면 implicit 방식을 먼저 구현해봐야 한다.

 

묵시적 가용 리스트는 다음 구조들이 연결되어 있는 형태를 띈다.

header

• 크기는 1워드(4byte)
• header와 추가적인 padding, footer를 모두 포함한 블록 크기
• 블록이 할당되었는지 아닌지를 확인 가능

payload

• 정렬 요구사항을 만족하며, 외부 단편화를 극복하게 한다.

padding

footer

• header와 동일한 데이터를 가진다.
• 경계조건을 없애주기 위해 존재한다.

 

Implicit free list를 사용하는 malloc을 구현하기 위해 고려되어야 하는 부분

• 힙 영역의 시작과 끝 부분 및 각 가용블록의 경계표시, 블록의 사이즈, 할당여부 표기법
  • 힙 영역은 prologue block과 epilogue block으로 경계가 구분된다. 그리고 각각의 블록은 블록 사이즈 정보와 가용 여부가 표기되어 있는 header와 footer로 구분된다.
  • header : 블록 사이즈, 할당 여부를 저장
  • payload : 할당된 블록에만 값이 저장됨
  • padding : double word 정렬을 위해 optional하게 존재
  • footer : 경계 태그로 사용되며, header의 값이 복사되어 있다. 즉, 블록을 반환할 때, 이전 블록을 상수 시간 내에 탐색할 수 있도록 한다. 만약 footer가 없으면, 모든 블록의 사이즈 정보가 다르기 때문에 이전 header를 찾기위해 heap의 시작점부터 순차적으로 탐색해야하는 불편함이 있다.
• 할당가능 블록 탐색 및 배치
  • Implicit free list의 경우, 가용리스트를 따로 관리하지 않고, 때마다 요청 블록 사이즈와 맞는 블록을 탐색해서 찾는다. 여기에 3가지 방법이 있다.
  • First Fit : 힙 시작점부터 탐색한다. 즉, 요청에 맞는 첫 번째 블록 발견할때까지 탐색한다.
  • Next Fit : 마지막 가용블록을 발견한 지점부터 탐색을 시작한다.
  • Best Fit : 전체를 탐색하는 아이디어여서 이 부분에 단점이 있지만, 가장 알맞은 사이즈의 블록을 찾을 수 있기 때문에 메모리 이용도는 다른 방법보다 우수하다.
• 할당 시 가용리스트 분할
  • 발견한 가용 블록의 크기가 큰 경우에는 2가지 옵션이 있다.
  • 그대로 채택한다. (내부 단편화 문제 발생 가능)
  • 필요한 부분만 잘라서 쓰고, 나머지 부분을 가용블록으로 변경한다.
• 할당 불가능시 추가 힙 영역 획득
  • 기존 힙 영역에 할당 가능한 가용블록이 없는 경우, 힙 영역을 상단으로 확장시켜서 추가로 메모리를 할당받는다.
  • 이때, mem_sbrk 함수를 사용하는데, heap 영역의 최상단에 위치한 포인터를 incr만큼 이동시키는 함수이다.
• 인접한 가용리스트들끼리의 연결
  • 총 4가지 케이스가 있다.
  • case 1 : 직전, 직후 블록이 할당되어 있을 때
  • case 2 : 직전 블록 할당, 직후 블록 가용일 때
  • case 3 : 직전 블록 가용, 직후 블록 할당일 때
  • case 4 : 직전, 직후 블록 모두 가용일 때

 

memlib.c 메모리 시스템 모델 이해

 

가용 리스트 조작을 위한 기본 상수 및 매크로 정의

매크로란 동적 할당기를 만들 때, 자주 쓰는 기능들을 미리 만들어 놓고, 가져다가 쓰는 것이다. 따라서 섬세한 이해가 필요하다.

아래에는 코드 전체에서 사용하게 될 상수와 매크로를 보여준다.

#define WSIZE       4           // 워드 사이즈
#define DSIZE       8           // 더블 워드 사이즈
#define CHUNKSIZE   (1 << 12)   // 초기 가용 블록과 힙 확장을 위한 기본 크기

#define MAX(x, y)   ((x) > (y) ? (x) : (y))

// 사이즈와 할당 비트를 합쳐서 header, footer에 저장할 수 있는 값 반환
#define PACK(size, alloc)   ((size) | (alloc))

// 특정 주소 p에 워드 읽고, 쓰기
#define GET(p)  (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))

// 특정 주소 p에 해당하는 블록의 사이즈와 가용 여부 반환
#define GET_SIZE(p)     (GET(p) & ~0x7)
#define GET_ALLOC(p)    (GET(p) & 0x1)

// 특정 주소 p에 해당하는 블록의 header, footer의 포인터 주소 반환
#define HDRP(bp)    ((char *)(bp) - WSIZE)
#define FTRP(bp)    ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

// 다음, 이전 블록의 헤더 이후의 시작 위치의 포인터 주소 반환
#define NEXT_BLKP(bp)   (((char *)(bp) + GET_SIZE((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp)   (((char *)(bp) - GET_SIZE((char *)(bp) - DSIZE)))

 

 

정적 변수 선언

static char *heap_listp;

• global variable & functions
  항상 prologue block을 가리키는 정적 전역 변수를 설정한다.

static char *last_bp;

• 마지막 block pointer를 가리키는 정적 전역 변수를 설정한다.

 

함수 선언

// 기본 함수 선언
int mm_init(void);
void *mm_malloc(size_t size);
void mm_free(void *ptr);
void *mm_realloc(void *ptr, size_t size);

// 추가 함수 선언
static void *extend_heap(size_t words);
static void *coalesce(void *bp);
static void *find_fit(size_t asize);
static void place(void *bp, size_t newsize);

 

int mm_init(void) : 초기 가용 리스트 만들기

우선 mem_sbrk 함수로 16비트 만큼의 초기 힙 영역을 할당받는다. 여기서 mem_sbrk 함수는 힙 영역을 incr(0이 아닌 양수) 바이트만큼 확장하고, 새로 할당된 힙 영역의 첫번째 바이트를 가리킨다.

따라서 4워드 크기 만큼 힙 영역 공간을 확보했고, 각각의 주소에 1워드(4byte) 간격으로 패딩, 프롤로그 헤더, 프롤로그 풋터, 에필로그 헤더를 할당하였다. 이후 heap_listp를 2워드(8byte) 만큼 뒤로 보낸다.

여기 extend_heap 쪽 로직이긴 한데, 우선 size에 words * WSIZE 만큼을 담아주기 때문에  ptr = mem_sbrk(size)를 수행하면, 4워드만큼 증가된 위치의 주소 16비트를 가리키는 포인터가 포인터 변수 *ptr에 담긴다.

그리고 기존 에필로그 헤더의 위치를 크기/가용 여부 값이 포함된 블록 헤더로 새롭게 초기화하고, 블록의 끝에 풋터를 초기화한 후, 풋터의 끝에 새롭게 에필로그 헤더를 할당해준다. 이 과정이 결과적으로는 프롤로그 블록과 에필로그 헤더 사이에 공간을 밀어넣는 결과를 가져온다.

 

int mm_init(void)
{
    // 초기 힙 영역의 크기 할당
    if((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1) {
        return -1;
    }

    PUT(heap_listp, 0);                             // padding
    PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1));  // prologue header
    PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1));  // prologue footer
    PUT(heap_listp + (3 * WSIZE), PACK(0, 1));      // epilogue header
    heap_listp += (2 * WSIZE);

    // 4096 비트만큼 힙 영역 확장
    if (extend_heap(CHUNKSIZE / WSIZE) == NULL) {
        return -1;
    }

    return 0;
}

 

void *mm_malloc(size_t size)

void *mm_malloc(size_t size)
{
    size_t adjust_size;
    size_t extend_size;
    char *ptr;

    // 의미없는 요청은 처리 안함
    if (size == 0) {
        return NULL;
    }

    // 더블 워드 정렬 제한 조건을 만족하기 위해, 할당할 공간의 크기 계산
    if (size <= DSIZE) {
        adjust_size = 2 * DSIZE;    // header(4byte) + footer(4byte) + 나머지(8byte)
    } else {
        adjust_size = DSIZE * ((size + DSIZE + (DSIZE - 1)) / DSIZE);
    }

    // 가용 블록을 가용 리스트에서 검색하고, 할당기는 요청한 블록을 배치
    if ((ptr = find_fit(adjust_size)) != NULL) {
        place(ptr, adjust_size);
        return ptr;
    }

    // 리스트에 들어갈 수 있는 free 리스트가 없으면, 메모리를 확장하고 블록을 배치
    extend_size = MAX(adjust_size, CHUNKSIZE);
    if ((ptr = extend_heap(extend_size / WSIZE)) == NULL) {
        return NULL;
    }
    place(ptr, adjust_size);

    return ptr;
}

 

void *mm_realloc(void *ptr, size_t size)

realloc은 이미 할당된 메모리 블록의 크기를 늘리거나 줄일 경우에 호출할 수 있는 함수이다. 이 함수의 의의는 기존 데이터를 유지한 채로 메모리 블록의 크기를 변경한다는데 있다. 다만 주의할 점은 크기를 재할당하려는 현재 블록의 다음 블록에 다른 메모리 블록이 이미 블록의 크기를 변경할 경우에는 다음 블록의 위치들을 전부 밀어줘야 한다는 점이다. 따라서 현재 위치에서 블록의 크기를 늘리는 것이 아닌 현재 위치의 블록의 내용들을 복사한 뒤에 메모리 영역의 크기를 늘린다. 이후에 새로운 메모리 주소를 할당해주고, 기존의 메모리 주소는 할당 해제 시키는 과정을 통해서 메모리 블록 크기의 재할당이 이루어진다.

 

첫번째 알고리즘

void *mm_realloc(void *ptr, size_t size)
{
    if (ptr == NULL) {
        return mm_malloc(size);
    }

    if (size == 0) {
        mm_free(ptr);
        return;
    }

    void *new_ptr = mm_malloc(size);
    if (new_ptr == NULL) {
        return NULL;
    }

    size_t entire_size = GET_SIZE(HDRP(ptr));
    if (size < entire_size) {
        entire_size = size;
    }
    memcpy(new_ptr, ptr, entire_size);  // ptr 위치에서 entire_size 만큼의 크기를 new_ptr에 복사
    mm_free(ptr);   // 기존 메모리는 할당 해제
    return new_ptr;
}

 

 

두번째 알고리즘

void *mm_realloc(void *bp, size_t size)
{
    size_t old_size = GET_SIZE(HDRP(bp));
    size_t new_size = size + (2 * WSIZE);

    // new_size가 old_size보다 작거나 같으면 기존 bp 그대로 사용
    if (new_size <= old_size) {
        return bp;
    }
    // new_size가 old_size보다 크면 사이즈 변경
    else {
        size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
        size_t current_size = old_size + GET_SIZE(HDRP(NEXT_BLKP(bp)));

        // next block이 가용상태이고 old, next block의 사이즈 합이 new_size보다 크면 그냥 그거 바로 합쳐서 쓰기
        if (!next_alloc && current_size >= new_size) {
            PUT(HDRP(bp), PACK(current_size, 1));
            PUT(FTRP(bp), PACK(current_size, 1));
            return bp;
        }
        // 아니면 새로 block 만들어서 거기로 옮기기
        else {
            void *new_bp = mm_malloc(new_size);
            place(new_bp, new_size);
            memcpy(new_bp, bp, new_size);  // 메모리의 특정한 부분으로부터 얼마까지의 부분을 다른 메모리 영역으로 복사해주는 함수(old_bp로부터 new_size만큼의 문자를 new_bp로 복사해라!)
            mm_free(bp);
            return new_bp;
        }
    }
}

 

static void *extend_heap(size_t words)

extend_heap 함수는 2가지 경우의 수가 있다. 첫째는 힙이 초기화될 때이고, 두번째는 mm_malloc이 적당한 맞춤 fit을 찾지 못했을 때이다. 이때, 정렬을 유지하기 위해서 extend_heap은 요청한 크기를 인접 2워드의 배수(8바이트)로 반올림하여, 그 후에 메모리 시스템으로부터 추가적인 힙 공간을 요청한다. 힙은 더블 워드 경계에서 시작하고, extend_heap으로 가는 모든 호출은 그 크기가 더블 워드의 배수인 블록을 반환한다. 따라서 mem_sbrk로의 모든 호출은 에필로그 블록의 헤더에 곧이어서 더블 워드 정렬된 메모리 블록을 반환한다. 이 헤더는 새 가용 블록의 헤더가 되고, 이 블록의 마지막 워드는 새 에필로그 블록 헤더가 된다. 마지막으로 이전 힙이 가용 블록으로 끝났다면, 두 개의 가용 블록을 통합하기 위해서 통합된 블록의 블록 포인터를 반환한다.

static void *extend_heap(size_t words)
{
    char *ptr;
    size_t size;

    // 더블 워드 정렬 위해 짝수 개수의 워드 할당
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
    if ((long)(ptr = mem_sbrk(size)) == 1) {
        return NULL;
    }

    PUT(HDRP(ptr), PACK(size, 0));  // 기존 epilogue header 초기화(free 블록의 header)
    PUT(FTRP(ptr), PACK(size, 0));  // free 블록의 footer
    PUT(HDRP(NEXT_BLKP(ptr)), PACK(0, 1));  // new epilogue header

    // 만약 이전 블록이 free 였다면, 통합
    return coalesce(ptr);
}

 

mm_free(void *bp)

할당 해제 함수로 매개변수로 들어온 주소 *ptr에 해당하는 위치의 블록 사이즈를 읽고, 해당 블록의 header와 footer의 가용 여부를 0으로 바꿔줌으로써 메모리 할당 해제 기능을 구현할 수 있다.

void mm_free(void *bp)
{
    // 해당 블록의 size를 찾고, header와 footer의 정보를 수집한다.
    size_t size = GET_SIZE(HDRP(bp));
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));

    // 만약 앞뒤 블록이 가용 상태면 연결한다.
    coalesce(bp);
}

 

static void *coalesce(void *bp)

coalesce 함수에서는 4가지 경우를 구현한다. 우리가 선택한 가용 리스트 포맷으로 인해서 프롤로그와 에필로그 블록을 항상 할당으로 표시했기 때문에, 요청한 블록 bp가 힙의 시작 부분 또는 끝 부분에 위치하는 숨겨진 문제가 될 수 있는 경계 조건을 무시할 수 있게 된다. 이 특별 블록 없이는 코드는 더 복잡해지고, 에러가 생길 가능성이 높아지고, 더 느려지는데, 매 반환 요청에 대해서 드물게 발생하는 경계 조건들을 항상 체크해야 하기 때문이다.

static void *coalesce(void *bp)
{
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(ptr))); // 이전 블록의 할당 여부
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(ptr))); // 다음 블록의 할당 여부
    size_t size = GET_SIZE(HDRP(ptr));   // 현재 블록의 사이즈

    if (prev_alloc && next_alloc) {
        // case1 - 직전, 직후 블록이 모두 할당되어 있는 경우.
        last_bp = ptr;
        return ptr;
    } else if (prev_alloc && !next_alloc) {
        // case2 - 직전 블록 할당, 직후 블록이 가용인 경우.
        size += GET_SIZE(HDRP(NEXT_BLKP(ptr)));
        PUT(HDRP(ptr), PACK(size, 0));
        PUT(FTRP(ptr), PACK(size, 0));
    } else if (!prev_alloc && next_alloc) {
        // case3 - 직전 블록 가용, 직후 블록이 할당된 경우.
        size += GET_SIZE(HDRP(PREV_BLKP(ptr)));
        PUT(FTRP(ptr), PACK(size, 0)); 
        PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0));
        ptr = PREV_BLKP(ptr);   // 블록 포인터를 직전 블록으로 옮긴다.
    } else {
        // case4 - 직전, 직후 블록이 모두 가용인 경우.
        size += GET_SIZE(HDRP(PREV_BLKP(ptr))) + GET_SIZE(FTRP(NEXT_BLKP(ptr)));
        PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0));
        PUT(FTRP(NEXT_BLKP(ptr)), PACK(size, 0));
        ptr = PREV_BLKP(ptr);   // 블록 포인터를 직전 블록으로 옮긴다.
    }
    last_bp = ptr;
    return ptr; // 최종 가용 블록 주소를 반환한다.
}

 

static void *find_fit(size_t asize) : first-fit

방법1

/* first-fit */
static void *find_fit(size_t asize)
{
    void *bp;

    for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp))
    {
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))
        {
            return bp;
        }
    }
    return NULL; // No fit
}

 

방법2

static void *find_fit(size_t a_size) {
     char *bp = heap_listp;
     bp = NEXT_BLKP(bp);
     while (GET_SIZE(HDRP(bp)) < a_size || GET_ALLOC(HDRP(bp)) == 1) {   // bp가 적용될 블록의 크기보다 작고, free일 때
         bp = NEXT_BLKP(bp);
         if (GET_SIZE(HDRP(bp)) == 0) {      // Epilogue를 만났을 때
             return NULL;
         }
     }
     return bp;
}

 

static void *find_fit(size_t asize): next-fit

/* next-fit */
static void *find_fit(size_t asize)
{
    // init할 때, 이미 last_bp를 설정하기 때문에 bp에 그 값을 넣어준다.
    char *bp = last_bp;

    for (bp = NEXT_BLKP(bp); GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
        if (GET_ALLOC(HDRP(bp)) == 0 && (asize <= GET_SIZE(HDRP(bp)))) {
            // free 블록이고, asize보다 큰 블록은 last_bp에 저장한다.
            last_bp = bp;
            return bp;
        }
    }

    // 위에서 반환되지 않았으면, 마지막 last_bp부터 돌렸을 때, 끝까지 갔는데 fit을 찾을 수 없다는 뜻이고, 그럼 맨 처음부터 중간에 free된 블럭을 찾아야 한다.
    bp = heap_listp;
    while (bp < last_bp) {
        // 맨 처음부터 last_bp 전까지만 돌린다.
        bp = NEXT_BLKP(bp);
        if (GET_ALLOC(HDRP(bp)) == 0 && GET_SIZE(HDRP(bp)) >= asize) {
            last_bp = bp;
            return bp;
        }
    }
    
    return NULL; // No fit
}

 

static void place(void *bp, size_t asize)

place 함수는 배치 위치를 탐색한 후에 배치 가능한 블록에 메모리를 place 함수를 이용해서 할당한다.

 

동작 방식을 요약해 말하면 다음과 같다.

내부적으로 할당되는 공간이 넉넉하다면, 할당된 블록이 차지하는 공간을 제외한 나머지 공간을 새로운 가용 블록으로 선언해주게 된다.

 

동작 방식을 좀 더 자세히 말하면 다음과 같다.

블록 내의 할당 부분을 제외한 나머지 공간의 크기가 더블 워드 이상이라면 해당 블록의 공간을 분할한다. 반면에 블록 내의 할당 부분을 제외한 나머지 공간의 크기가 2 * 더블 워드(8byte)보다 작을 경우에는 그냥 해당 블록의 크기를 그대로 사용한다.

static void place(void *bp, size_t asize)
{
    size_t entire_size = GET_SIZE(HDRP(ptr));

    // 블록 공간 분할
    if ((entire_size - adjust_size) >= (2 * DSIZE)) {
        // 블록 할당
        PUT(HDRP(ptr), PACK(adjust_size, 1));
        PUT(FTRP(ptr), PACK(adjust_size, 1));
        ptr = NEXT_BLKP(ptr);
        // 가용 블록
        PUT(HDRP(ptr), PACK(entire_size - adjust_size, 0));
        PUT(FTRP(ptr), PACK(entire_size - adjust_size, 0));
    } else {
        // 분할할 수 없으면 그냥 해당 블록 사용
        PUT(HDRP(ptr), PACK(entire_size, 1));
        PUT(HDRP(ptr), PACK(entire_size, 1));
    }
}

 

 

first-fit으로 테스트 돌렸을 때 결과

./mdriver
Team Name:team 5
Member 1 :kim-jingyu:jingyu@jungle.com
Using default tracefiles in ./traces/
Perf index = 44 (util) + 7 (thru) = 51/100

 

 

안쓰는 매크로 삭제 및 next-fit으로 테스트 돌렸을 때 결과

./mdriver
Team Name:team 5
Member 1 :kim-jingyu:jingyu@jungle.com
Using default tracefiles in ./traces/
Perf index = 43 (util) + 33 (thru) = 77/100

 

realloc 함수 알고리즘 교체 후 테스트 결과

./mdriver
Team Name:team 5
Member 1 :kim-jingyu:jingyu@jungle.com
Using default tracefiles in ./traces/
Perf index = 46 (util) + 40 (thru) = 86/100