메모리 할당 정책

메모리 할당 정책

응용프로그램이 메모리의 블록을 요청할 때,
메모리 할당기는 요청한 블록을 저장하기에 충분히 큰
가용 블록을 리스트에서 검색한다

이러한 검색을 수행하는 방식 중 주로 사용되는 방식이
‘first fit’, ‘next fit’, ‘best fit’ 방식이다

first fit

가용 리스트를 처음부터 검색하며,
크기가 맞는 첫 번째 가용 블록을 선택한다

특징이라면,
가장 앞에서부터 리스트를 검색하기에
끝에 가까울수록 ‘큰 용량’을 가진 가용 블록이 남는
경향이 있다는 점이다

다만, 이로 인하여
큰 가용 블록을 찾을 때,
검색 시간 또한 늘어난다는 점이다

예시코드 (C)

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;
}

next fit

위와 비슷하지만,
검색을 시작하는 부분은 ‘이전에 검색이 종료된 부분부터’이다

next fit는 first fit의 대안으로
‘이전 검색’ 시, ‘가용 블록’을 찾았다면,
다음 검색에서는, ‘리스트’의 나머지를 검색하는 것이
원하는 블록을 찾을 가능성이 높다는 점에서 착안되었다고 한다

매우 빠른 속도를 보이지만,
first fit 보다 낮은 메모리 이용도를 보인다

아래 예시 코드에서 보듯
prev_bp라는 이전에 검색된 변수를 이용하여
해당 위치 시점에서 재검사를 해준다

다만, 이 뿐 아니라 ‘할당’을 하거나,
‘할당 해제’하는 부분에서 해당 변수에 대하여
추가적인 설정을 해줄 필요도 있다

예시코드 (C)

static void* find_fit(size_t asize)
{
    /* next fit*/
    void * bp = NEXT_BLKP(prev_bp);

    for(; 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;
        }
    }

    // 위에서 찾지 못할 시, 처음부터 다시 검사해준다
    for(bp = NEXT_BLKP(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;
}

best fit

모든 가용 블록을 검사하며,
이 중, 크기가 맞는 가장 작은 블록을 선택한다

위의 두 검색법보다 좋은 ‘메모리 이용도’를 보인다
다만, 일반적으로는 ‘리스트’를 모두 검색해야 한다는 점이
단점이다

메모리 이용도는 확실히 좋았으나,
처리량이 발목을 잡았다

추가적인 최적화를 해준다면 모르겠지만
확실히 ‘모든 블록’을 검사한다는 점이
가장 큰 특징인듯하다

예시코드 (C)

static void* find_fit(size_t asize)
{
    /* next fit*/
    void * bp;
    void* bestbp;
    
    size_t bFindPlace = 0;
    size_t bestSize = -1;   // UINT_MAX

    for(bp = heap_listp; GET_SIZE(HDRP(bp)) > 0 ; bp = NEXT_BLKP(bp))
    {
        /* 헤더 확인하니 가용 상태, 해당 블록 사이즈가 asize보다 큼 */
        if(!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))
        {
            if(bestSize > GET_SIZE(HDRP(bp)))
            {
                bFindPlace = 1;
                bestSize = GET_SIZE(HDRP(bp));
                bestbp = bp;
            }

            if(bestSize == asize)
            {
                return bestbp;
            }
        }
    }

    if(bFindPlace != 0)
        return bestbp;

    /* 할당 안됨 */
    return NULL;
}