[C] malloc lab Part.3

고민지·2025년 7월 2일

크래프톤 정글 9기

목록 보기

16/29

크래프톤 정글 52일차

2. best_fit

수도코드

bp = heap_listp
에필로그 만나기 전까지 (while GET_SIZE(HDRP(bp)) > 0)	
할당 안된 블록 중 asize와 가장 크기가 작은 거 찾기
차이가 최소인 블록 저장 (min)
다 돌고나면:
최소 블록이 있다면 return min
없다면 return NULL

//best_fit
static void *find_fit(size_t asize)
{
    char *bp = heap_listp; 
    size_t min_diff = SIZE_MAX; //최소 블록 크기 
    void *best_bp = NULL;

    //에필로그 까지 탐색
    while (GET_SIZE(HDRP(bp)) > 0)
    {
        //크기가 asize이상이고, free 상태인 블록
        if (GET_SIZE(HDRP(bp)) >= asize && !GET_ALLOC(HDRP(bp))){    
            size_t diff = GET_SIZE(HDRP(bp)) - asize; //블록의 차를 diff에 저장
            
            //들어온 diff가 min보다 작다면
            if (diff < min_diff) 
            {
                min_diff = diff; //min갱신
                best_bp = bp; //best_bp 갱신
            }
        }
        bp = NEXT_BLKP(bp); //못 찾았으면 다음 블록 이동
    }
    return best_bp; //최소 블록 반환
}

테스트 결과

왜인지 first_fit과 best_fit의 점수가 같다... 왜일까
->이 문제는 trace가 0이었어서 계속 80점이 나왔다. 실행을 터미널에서 make clean->make->$ ./mdriver -v 로 실행하니 해결되었다.

성능 개선을 위해서 순회를 줄이거나 쓸데없는 비교를 줄이는 방법을 생각해봐야겠다.
-> 딱 맞는 블록이 나타난다면 바로 return

best_fit 개선 후

static void *find_fit(size_t asize)
{
    char *bp = heap_listp; 
    size_t min_diff = SIZE_MAX; //최소 블록 크기 
    void *best_bp = NULL;

    //에필로그 까지 탐색
    while (GET_SIZE(HDRP(bp)) > 0)
    {
        //크기가 asize이상이고, free 상태인 블록
        if (GET_SIZE(HDRP(bp)) >= asize && !GET_ALLOC(HDRP(bp))){    
            size_t diff = GET_SIZE(HDRP(bp)) - asize; //블록의 차를 diff에 저장
            
            //들어온 diff가 min보다 작다면
            if (diff <= min_diff) 
            {
                min_diff = diff; //min갱신
                best_bp = bp; //best_bp 갱신

            if (diff == 0){ //맞는 블럭찾으면 바로 return best_bp
                return best_bp;
            }
            }
        }
        bp = NEXT_BLKP(bp); //못 찾았으면 다음 블록 이동
    }
    return best_bp; //최소 블록 반환
}