[Malloc Lab-3] Malloc을 구현해봐요 (2) : find_fit과 place 함수 구현하기

은채·2025년 4월 30일

Malloc Lab

목록 보기

18/21

1. find_fit 함수 구현

static void *find_fit(size_t asize)

find_fit 함수는 묵시적 가용 리스트를 이용해 first-fit 방식으로 free 블록을 탐색하는 함수이다.
find_fit 함수는 *mm_malloc 함수 안에서 다음과 같이 호출된다.

if ((bp = find_fit(asize)) != NULL) {
    place(bp, asize);
    return bp;
}

이를 통해 find_fit 함수의 반환 조건을 알 수 있다.

성공하면 할당할 위치의 포인터를 반환한다.
실패하면 NULL을 반환한다.

1) 설계 흐름

find_fit 함수를 구현하기 위해 다음과 같이 설계했다.

처음 위치에서 가용 리스트 순회를 시작한다.
크기가 맞는 free 블록이라면, 현재 위치의 포인터를 반환한다.
찾지 못했다면, 다음 블록으로 이동한다.
리스트를 끝까지 순회했음에도 할당 가능한 위치를 찾지 못했다면, NULL을 반환한다.

다음은 각 순서에서 디테일하게 고민한 내용이다.

(1) 처음 위치에서 리스트 순회를 시작한다.

가용 리스트는 어떻게 만들지?
묵시적 가용 리스트를 사용하라 했으니, 가용 리스트를 따로 만들 필요는 없겠다.
그냥 header값을 확인하면서 전체 힙을 돌자.
리스트 순회는 어떤 방식을 사용할까?
재귀? while문? for문?
while문을 사용하는 게 가장 편하겠다.
순회하면서 현재 위치를 표시할 포인터가 필요하다.
bp로 명칭한 포인터를 사용하자.
처음 위치는 어떻게 알지?
초기 힙의 위치인 heap_listp을 사용하자.

(2) 크기가 맞는 free 블록이라면, 현재 위치의 포인터를 반환한다.

크기가 맞는지는 어떻게 알지?
현재 블록의 크기를 확인하고, asize와 비교해보면 되겠다.
현재 블록의 크기는 header에서 블록 크기 값을 반환하자.
이 값이 asize보다 같거나 크면 크기가 맞는 블록이다.
free 블록인지의 여부는 어떻게 확인할까?
header에서 할당 여부를 확인하면 되겠다.
1이면 할당 블록, 0이면 free 블록이다.
현재 위치의 포인터는 어떻게 반환할까?
단순히 bp값을 return하면 된다.

(3) 찾지 못했다면, 다음 블록으로 이동한다.

이동은 어떻게 하지?
다음 블록의 헤더로 bp를 이동시키면 되겠다.
매크로 NEXT_BLKP을 사용하면 편하겠다.

(4) 리스트를 끝까지 순회했음에도 할당 가능한 위치를 찾지 못했다면, NULL을 반환한다.

리스트를 끝까지 순회한 것은 어떻게 알지?
에필로그 블록을 찾으면, 마지막 블록임을 확인할 수 있다.
에필로그 블록은 크기가 0인 할당된 블록이니, 확인이 쉬울 것이다.

2) 구현

구현한 코드는 다음과 같다.

static void *find_fit(size_t asize) {
    char *bp = heap_listp;

    while (GET_SIZE(HDRP(bp)) != 0) {
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
            return bp;
        }
        bp = NEXT_BLKP(bp);
    }

    return NULL;
}

bp는 초기 힙 위치인 heap_listp로 설정했다.

에필로그 블록을 만날 때까지 while문을 순회한다.
에필로그 블록을 만나 while문을 탈출하면, NULL을 반환한다.

만약 현재 블록이 free 상태이고, 요청한 크기 이상이면 조건을 만족한다.
조건을 만족하면 그 블록의 포인터 bp를 반환한다.

못 찾았다면 다음 블록으로 이동한다.

2. place 함수 구현

static void *place(void *bp, size_t asize)

place 함수는 bp 위치에 블록을 배치한다.
만약 남은 부분이 16바이트보다 같거나 큰 경우, 분할한다.

1) 설계 흐름

place 함수 구현을 위해 아래와 같이 설계했다.

현재 블록의 크기를 확인한다.
분할이 가능한지 확인한다.
- 만약 블록이 16바이트보다 같거나 크면 분할한다.
- 그렇지 않다면 분할하지 않는다.

다음은 각 순서에서 디테일하게 고민한 내용이다.

(1) 현재 블록의 크기를 확인한다.

현재 블록의 크기는 어떻게 확인하지?
매크로를 쓰면 편하겠다.

(2) 분할이 가능한지 확인한다.

분할이 가능한지는 어떻게 알지?
나머지 블록의 크기가 16바이트보다 같거나 큰지 확인하자.
크면 분할, 아니면 분할하지 말자.
분할하려면 어떻게 해야하지?
header/footer를 두개씩 써야겠다.
한 쌍은 할당한 블록에, 한 쌍은 새로 분할된 free 블록에 쓰자.
bp는 free block으로 보내야 하니깐, 업데이트하자.
분할하지 않는 경우에는?
header/footer를 각각 할당되었다고 업데이트해주자.

2) 구현

구현한 코드는 다음과 같다.

static void place(void *bp, size_t asize)
{
    size_t csize = GET_SIZE(HDRP(bp));

    if ((csize - asize) >= (2 * DSIZE)) {
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(csize - asize, 0));
        PUT(FTRP(bp), PACK(csize - asize, 0));
    }

    else {
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}