Malloc Lab: Explicit Free List를 구현하며 만났던 문제들

개념은 쉽고, 구현은 어려워 🎵

나만의 동적 메모리 할당기의 성능을 더더욱 높이기 위해, Explicit Free List를 이용한 구현에 대해 공부했다. Implicit Free List를 사용한 할당기는 간단하게 구현할 수 있지만 블록의 할당에 소모되는 시간이 힙의 모든 블록 수에 비례한다는 단점이 있었다. 반면에 Explicit Free List를 이용한다면, 블록의 할당에 소모되는 시간을 힙의 가용 블록 수로 줄일 수 있다.

Explicit Free List의 개념은 생각보다 간단했다. 가용 가능한 블록의 내부에 다음 가용 블록의 주소를 가리키는 포인터 Next와 이전 가용 블록의 주소를 가리키는 포인터 Prev 를 포함하는 것! 이렇게 해주면 블록을 할당하려 할 때, 가용 블록들의 Next 포인터를 읽어나가며 가용 블록들만 탐색할 수 있게 된다.

Ok! 생각보다 별로 어려울 게 없어보였다. 가용 블록을 만들어 줄 때, 포인터들만 잘 포함해 주면 될 것 같은 느낌? 바로 작업에 착수했다.

포인터만 담으면 되겠네 ❓

• Place 함수를 이렇게 변환하면 되겠다! 싶어 정리해본 그림

처음 생각했던 대로 가용 블록에 Next 와 Prev 포인터를 물리적으로 포함시키려 했었다. 최소 블록 사이즈는 2*DSIZE 였고, 기존의 Header 와 Footer를 제외하고도 DSIZE 만큼이 남게 된다. 그럼 포인터를 담을 공간이 딱 확보가 되어있네?

신나게 Prev 와 Next 의 주소를 계산하는 매크로 함수를 선언하고, 함수들의 로직을 변경해나갔다. 행복했던 시간도 잠시, Free 함수를 수정하던 중 의문점이 생겼다. 할당됬던 블록은 Next와 Prev 포인터를 가지고 있지 않는데... 그럼 매번 Free해줄 때 마다 블록 앞 뒤로 가용 블록을 찾아야 해? 말이 안되는 소리였다. 저렇게 설계한다면 Explicit Free List의 장점들을 다 내다가 버리는 꼴이였다.

결국 다른 방안을 모색하기 위해 CSAPP를 더 읽어보고, 다른 사람들의 코드를 보고 공부했다. 대부분의 사람들이 택한 방법은 가용 블록들을 관리하는 free_listp 를 따로 두는 것. 실제로 배열은 아니고, Linked List와 같은 형태로 가용 블록들을 관리하는 것!

힙을 초기화 할 때, free_listp를 위한 공간을 따로 할당해주고, 함수들을 수정하고, 또 새로 만들었다.

    PUT(heap_listp, 0); // 미사용 패딩 워드
    PUT(heap_listp + (1*WSIZE), PACK(2*DSIZE, 1)); // Prologue Block Header
    PUT(heap_listp + (2*WSIZE), NULL); // predecessor for free_listp
    PUT(heap_listp + (3*WSIZE), NULL); // successor for free_listp
    PUT(heap_listp + (4*WSIZE), PACK(2*DSIZE, 1)); // Prologue Block Footer
    PUT(heap_listp + (5*WSIZE), PACK(0, 1)); // Epilogue Block Head
    
    free_listp = heap_listp + (2*WSIZE);

• 추가된 함수의 예: free_listp 를 관리하는 주요 함수 add_freelist, remove_freelist

// Free List의 맨 앞에 삽입
void add_freelist(void *bp){
    FREE_NEXT(bp) = free_listp;
    FREE_PREV(bp) = NULL;
    FREE_PREV(free_listp) = bp;
    free_listp = bp;
}

// Free List에서 삭제
void remove_freelist(void *bp){
        // Free List의 첫번째 블록인 경우
    if (bp == free_listp) {
        FREE_PREV(FREE_NEXT(bp)) = NULL;
        free_listp = FREE_NEXT(bp);
    }
    else {
        FREE_NEXT(FREE_PREV(bp)) = FREE_NEXT(bp);
        FREE_PREV(FREE_NEXT(bp)) = FREE_PREV(bp);
    }
}

• 수정된 함수의 예: 할당할 위치를 찾는 find_fit 함수. free_listp를 탐색하게 바뀌었다.

static void *find_fit(size_t asize){
    void *bp;

    for (bp = free_listp; GET_ALLOC(HDRP(bp))!= 1; bp = FREE_NEXT(bp)){
        if (asize <= GET_SIZE(HDRP(bp))) {
            return bp;
        }
    }

    return NULL;
}

테스트!

비록 작은 수치이지만 점수가 올랐다! 하지만 Malloc Lab: first-fit 을 next-fit 로 바꾸며 만났던 문제들에서 내가 최종적으로 개선했던 코드보단 오히려 점수가 떨어졌다. 하지만 여기에 Segregated Storage와 같은 기법을 이용한다면 좀 더 높은 점수를 기대할 수 있겠지? 😎