동적 메모리 할당 - 배치: first-fit, next-fit, best-fit

서론

새롭게 할당된 블록을 배치하기 위한 가용 블록을 선택하는 방법에는 first-fit, next-fit, best-fit 등이 있습니다.

<출처: GeeksforGeeks>

☝🏻 first-fit

: 처음부터 탐색하고 크기가 맞는 첫 가용 블록을 선택한다.

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

• 힙의 시작부터, 크기가 > 0일때동안, 즉 에필로그 헤더가 나오기 전까지 다음 블록으로 이동하면서 원하는 크기 이상의 가용 블록을 찾는다. 가장 먼저 찾은 (원하는 크기 이상의 가용)블록을 선택한다.

👉🏻 next-fit

: 이전 탐색이 종료된 시점부터 탐색한다.
* next-fit은 pointp, 즉 탐색 포인터를 변경해줘야 하기 때문에 find_fit 뿐만 아니라 다른 함수의 코드도 수정해야 한다.

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

• 이전 탐색의 종료지점부터, 크기가 0이 아닐 동안, 즉 에필로그 헤더가 나오기 전까지, 다음 블록으로 이동하면서 원하는 크기 이상의 가용 블록을 선택한다.
  탐색 포인터를 현재 선택된 가용 블록 다음으로 설정한다.
• 이전 탐색의 종료지점부터 찾았는데 사용할 수 있는 블록이 없다면, 다시 앞에서부터 이전 탐색의 종료지점 전까지 이동하면서 선택한다.
  탐색 포인터를 현재 선택된 가용 블록 다음으로 설정한다.

👍🏻 best-fit

: 모든 가용 블록을 검사해서, 크기에 맞는 가용 블록 중 가장 작은 블록을 찾는다.

static void *best_fit(size_t asize)
{
    void *bp;
    void *best = NULL;
    for (bp = free_listp; GET_ALLOC(HDRP(bp)) != 1; bp = GET_NEXT(bp))
    {
        if (asize <= GET_SIZE(HDRP(bp)))
        {
            if (best == NULL)
            {
                best = bp;
            }
            else if (GET_SIZE(HDRP(bp)) <= GET_SIZE(HDRP(best)))
            {
                best = bp;
            }
        }
    }
    if (best != NULL)
    {
        return best;
    }
    return NULL;
}

• 가용리스트 시작부터 마지막 블록까지 다음 블록으로 이동하면서 원하는 크기 이상인 블록 중 가장 작은 블록을 찾아서 선택한다.

참고자료

• <Computer Systems: A Programmers Perspective> Section 9.9 - Randal Bryant
• github dkkim0122/malloc-lab

* 전체 코드는 여기서 확인하실 수 있습니다.