Malloc Lab: first-fit 을 next-fit 로 바꾸며 만났던 문제들

이형준·2023년 5월 15일

TIL

목록 보기

24/37

더 높은 점수를 향해 🪜

Malloc Lab을 Implicit List로 구현한 후 받은 첫 점수는 53점! 더 높은 점수를 위해서는 만든 동적 메모리 할당기의 성능을 다양한 방법으로 끌어올려야 했다. Malloc Lab에서의 동적 메모리 할당기의 성능은 두 가지로 평가된다. Space Utilization과 Throughput. 영어 의미대로 `공간을 얼마나 잘 활용하는가'와 '할당 속도가 얼마나 빠른가'로 평가한다. 내가 선택한 더 높은 점수를 위한 첫 단추는 first-fit을 next-fit으로 바꿔 Throughput을 개선하는 것!

뭐야? 별거 아닌데? 😄

first-fit: 매 할당마다 처음부터 메모리를 쭉~ 보다가, 알맞은 자리가 있다면 할당!
next-fit: first-fit과 동일하지만, 시작 위치를 처음부터가 아닌 이전 할당 위치부터!

first-fit을 next-fit으로 바꾸려고 마음먹은 후, 처음 든 생각은 '별거 아닐거 같은데?' 였다. 기존의 first-fit 을 활용한 find_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;
}

사전에 정의된 변수들과 상수들을 떼놓고 보면, 정말 로직이 간단하다고 느껴졌고, for문의 초기값을 정해주는 부분인 bp = heap_listp를 bp = recently_allocated와 같이 최근 할당한 블록의 위치를 기억하는 전역 포인터로 바꿔준다면 간단하게 탐색 위치를 바꿀 수 있을거라 생각했다. 신나게 코드를 바꾸고,

static void *find_fit(size_t asize){
    void *bp;
    if (recently_allocated == NULL) {
        recently_allocated = heap_listp;
    }
    
    for (bp = recently_allocated; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)){
         if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
            recently_allocated = bp;
            return bp;
            }
    }
    
    return NULL;
}

테스트!

overlaps...? ran out of memory...? 이 무슨.... 😨

찾아낸 문제점들 ⚠️

간단한 로직 수정이었기에 저 코드에서의 문제는 없다고 생각이 들었다. 그렇다면 혹시 C언어 숙련도 문제로 포인터 recently_alloacated를 잘못 처리했나? 싶어 문제점을 찾아봤는데 눈 씻고 찾아봐도 문제가 없어 보였다.. 대체 뭘까? 🤔

다양한 상황을 고려하기 위해 다양한 경우의 수를 생각해 보던 중, 할당 이전에 free과정을 하고, 그로 인해 할당 가능한 블록들을 합쳐주는 coalesce과정을 거친 후라면 내가 원하는 곳을 가리키지 않을수도 있겠다는 것을 알게 되었다. 그도 그럴게 단순무식하게 한 블록을 할당하면, 다음 블록이 할당되기까지 그 위치만을 계~속 기억하고 있으니까.. 그림을 그려 정리해보았다.

문제 해결! ✅

coalesce 과정이 문제가 된다면, 해당 부분을 거친 후에도 recently_allocated 포인터를 갱신해주면 될 것!

static void *coalesce(void *bp)
{   
    // 타겟 블록의 직전 블록, 직후 블록의 할당 여부를 저장
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    // 타겟 블록의 사이즈를 저장
    size_t size = GET_SIZE(HDRP(bp));

    // Case 1
   
    ... 
    
    // Case 4

    recently_allocated = bp;
    return bp; // 블록의 포인터를 리턴
}

coalesce 함수의 결과(병합 과정을 거친 블록의 주소)를 리턴하기 전, recently_allocated 포인터를 결과값으로 갱신해주었다. 이렇게 되면 최근 free해준 블록이 있다면, 그곳에서 탐색을 시작하게 되기에, 완벽한 next-fit은 아니지만 위의 버그는 확실하게 해결해줄 수 있을것!

테스트!

드라마틱하게 오른 Throughput 점수! 속도면에서 많은 개선을 이뤄냈다.

문득 생각난 개선점 ❗

현재 코드에서는 이전에 블록을 할당했던 위치 or 할당을 해제해준 블록의 위치부터 힙의 끝까지 탐색해보고, 넣을 수 없다면 힙의 사이즈를 늘려서 할당한다.

하지만 recently_allocated이전에 수많은 할당 가능한 빈 공간이 있을 수 있는데, 이를 확인하지 않고 그냥 힙을 늘려서 할당해주는 것은 아쉽다고 느껴졌고, 그렇다면 recently_allocated부터 쭉~ 탐색하고, 할당할 곳을 못 찾았다면 처음부터 한번 더 탐색해 보면 어떨까? 하는 생각이 들었다. 이렇게 하면 물론 앞에 빈 공간 없이 꽉꽉 알차게 할당되어있을 경우에는 동작 시간 저하를 유발하겠지만, 조금이라도 빈 공간이 있다면 훨씬 효율적으로 동작할 수 있겠다는 생각이 들었다.

static void *find_fit(size_t asize){
    void *bp;
    if (recently_allocated == NULL) {
        recently_allocated = heap_listp;
    }

    for (bp = recently_allocated; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)){
         if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
            recently_allocated = bp;
            return bp;
            }
    }
	// 저장된 위치부터 보고 나서 할당할 곳을 못찾았다면, 처음부터 재탐색 한번 더!
    for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)){
         if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
            recently_allocated = bp;
            return bp;
            }
    }

    return NULL;
}