동적 메모리 할당 | Malloc Lab | (4) 할당기 배치 전략 개선 (next fit)

동적 메모리 할당 | Malloc Lab | (1) Malloc은 어떻게 구현되는가?에서, 동적 할당기의 배치 전략에는 대표적으로 세 가지가 있음을 살펴보았다. 

 

1. first fit: 처음부터 탐색하며, 먼저 발견된 충분한 용량의 가용 블록에 할당
2. next fit: 이전 탐색 지점부터 탐색하며, 먼저 발견된 충분한 용량의 가용 블록에 할당 (-> 빠른 검색)
3. best fit: 모든 블록을 탐색하여, 요청 메모리에 가장 가까운 가용 블록에 할당 (-> 꼼꼼한 검색)

그리고 동적 메모리 할당 | Malloc Lab | (3) 기초적인 할당기 작동 원리, 구현에서, implicit free list의 블록 포맷을 가지고, first fit의 배치전략을 사용하는 기초적인 할당기를 이해해보았다. 

 

malloc-lab 테스트 기준으로, 기초적인 할당기의 성능은 45(util) + 7(thru) = 총점 53점 (반올림)으로 처리 속도 측면에서 많이 부족했는데, 이에 따라 배치 전략을 살짝 개선해보기로 했다. 처리 속도가 문제인만큼, best fit 보다는 next fit으로 수정하는 것이 더 유효할 것이라고 판단했다. 

 

---

구현 코드

next fit은 first fit 기반의 코드에서 배치 로직을 수행하는 find_fit() 함수와 연결 로직을 수행하는 coalesce() 함수를 집중적으로 바꿔줌으로써 구현이 가능했다. 그리고 추가적으로 정의할 매크로는 없고, 직전 탐색이 끝난 지점을 저장하는 prev_bp 변수만 추가적으로 정의해준다. 

 

주의할 점은, free() 함수와 extend heap() 함수 안에서 발동되는 coalesce 과정에서 prev_bp가 중간에 붕 떠버리는 경우가 발생할 수 있다는 점이다. 이 부분만 유의해서 예외처리를 해주면 된다. 

 

전체 코드는 다음 레포지토리에 올려놨다. (혹시 다음 기수 정글러분들이 발견할 수도 있으니 ..ㅎ)

https://github.com/Vacayy/Malloc-lab/tree/implicit/next-fit

GitHub - Vacayy/Malloc-lab: C 프로그래밍으로 동적 메모리 할당(malloc)을 구현하는 과제입니다.

 

 

mm_init()

static void *heap_listp;
static void *prev_bp; // <- 추가된 부분

int mm_init(void)
{
    /* Create the initial empty heap */
	// ... 
	// heap_listp += (2*WSIZE);    

    prev_bp = heap_listp; // <- 추가된 부분

    /* Extend the empty heap with a free block of CHUNKSIZE bytes */
    // ...
}

 

먼저 prev_bp를 사용하기 위해 위에서 선언해주고, 처음 init 시 heap의 시작 지점을 우선 prev_bp로 지정해준다. 

 

 

find_fit()

/* next fit */
static void *find_fit(size_t asize)
{
    void *bp;
    
    /* prev_bp 부터 에필로그 헤더까지 탐색 */
    for (bp = prev_bp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)){
        /* 할당되지 않았고, asize보다 크다면 */
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))){ 
            prev_bp = bp;
            return bp;
        }
    }

    /* 처음부터 prev_bp까지 탐색 */
    for (bp = heap_listp; bp < prev_bp; bp = NEXT_BLKP(bp)) {
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
            prev_bp = bp;
            return bp;
        }
    }

    return NULL; /* No fit */
}

 

1. 저장되어 있는 이전 탐색 지점(prev_bp)부터 시작해서, 에필로그 헤더까지 first fit과 같은 방식으로 탐색한다. 
2. 끝까지 찾지 못했다면, 힙의 시작 지점부터 prev_bp까지 다시 탐색한다. 

first fit의 로직을 변형하면 구현할 수 있다. 

만약 위 과정으로 적합한 공간을 찾지 못했다면, malloc 내부에서 find_fit() 이후에 extend_heap()으로 처리될 것이다.

 

 

coalesce()

static void *coalesce(void *bp)
{
    // GET_ALLOC: 해당 주소의 마지막 비트 반환 -> 헤더 or 푸터라면, 할당됐으면 1, 아니면 0 반환됨
    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)); // 현재 블록의 사이즈 확인

    // if문에서 0은 false, 그 외 숫자는 true로 인식
    if (prev_alloc && next_alloc){              /* Case 1. 이전 & 다음 not free */
        return bp;
    } 
    else if (prev_alloc && !next_alloc){        /* Case 2. 다음 블록 free */
        void *old_bp = NEXT_BLKP(bp);
        
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));

        // prev_bp 지점과 겹쳤을 경우 처리         
        if (old_bp == prev_bp){ 
            prev_bp = bp;
        }        
    }
    else if (!prev_alloc && next_alloc){        /* Case 3. 이전 블록 free */
        void *old_bp = bp;

        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
        bp = PREV_BLKP(bp);
        
        // prev_bp 지점과 겹쳤을 경우 처리 
        if (old_bp == prev_bp){ 
            prev_bp = bp;
        }        
        
    }
    else {                                      /* Case 4. 이전 & 다음 free */
        void *old_bp1 = bp;
        void *old_bp2 = NEXT_BLKP(bp);

        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));        
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
        
        // prev_bp 지점과 겹쳤을 경우 처리 
        if (old_bp1 == prev_bp | old_bp2 == prev_bp){ 
            prev_bp = bp;
        }        
    }
    return bp;
}

 

coalesce에 대한 처리를 처음에 놓치기 쉽다. 나도 segmentation fault를 몇번을 당했는지 모른다..

 

인접 블록을 연결하지 않는 case 1의 경우에는 상관이 없지만, 그 외의 경우에는 prev_bp가 피통합되는 블록을 가리키고 있을 경우를 처리해줘야 한다. 그렇지 않으면, 만약 prev_bp가 가리키던 블록이 합쳐질 경우 prev_bp가 원래 있어야 할 자리(payload 시작점)가 아니라 허공에 위치하게 되기 때문이다. 

 

1. 연결 과정에서 bp는 변경될 수 있으므로, 연결 전에 미리 bp를 old_bp에 저장해놓는다. 
2. 연결 이후, 만약 old_bp 지점을 prev_bp가 가리키고 있었다면, prev_bp를 올바른 위치(새로운 bp)로 이동시켜준다.

 

---

결과

이 정도만 수행하면 first fit -> next fit으로의 수정은 끝이난다.

 

그리고 그 결과는 ->

 

 

util 점수는 1점 떨어졌지만, 처리량 점수가 무려 33점이 올랐다. 결과적으로 53 -> 84점으로 큰 성능 향상이 이루어졌다.