컴퓨터 시스템 : CSAPP 9장 정리 - 9.9.12 종합 설계 : 간단한 할당기의 구현 Part.2

2025.04.27 - [크래프톤 정글 (컴퓨터 시스템: CSAPP)/9장 가상 메모리] - 컴퓨터 시스템 : CSAPP 9장 정리 - 9.9.12 종합 설계 : 간단한 할당기의 구현 Part.1

컴퓨터 시스템 : CSAPP 9장 정리 - 9.9.12 종합 설계 : 간단한 할당기의 구현 Part.1

이전 포스팅에 이어서 묵시적 가용 리스트를 사용하는 할당기를 구현해 보겠다.

---

CSAPP 9.9.12 '간단한 할당기의 구현(Putting It Together: Implementing a Simple Allocator)'

블록 반환과 연결 (Freeing and Coalescing)

동적 메모리 관리에서는 malloc으로 할당한 블록을 다 쓴 뒤, free로 반환해야 한다. 반환된 블록은 다른 할당 요청에 재사용할 수 있어야 한다. 그러나 반환된 블록 주변에도 가용 블록이 있을 수 있기 때문에, 가능하다면 인접한 가용 블록들과 병합(coalescing) 해서 더 큰 가용 블록을 만든다. 이렇게 하면 외부 단편화(external fragmentation) 를 줄일 수 있다.

---

mm_free 함수

mm_free(void *bp) 함수는 주어진 블록 포인터 bp가 가리키는 블록을 반환한다.

구체적인 동작은 다음과 같다:

1. bp가 가리키는 블록의 헤더를 찾아 블록 크기를 얻는다.
2. 해당 블록의 헤더와 풋터를 "가용 상태(allocated = 0)"로 변경한다.
3. coalesce(bp)를 호출하여 인접한 가용 블록들과 병합한다.

PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));

void mm_free(void *bp)
{
    size_t size = GET_SIZE(HDRP(bp));

    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    coalesce(bp);
}

---

coalesce 함수

coalesce(void *bp) 함수는 현재 블록 bp의 이전 블록과 다음 블록이 가용 상태인지 확인한 뒤, 필요하면 병합한다.

coalesce 함수는 다음 네 가지 경우를 처리한다:

1. 이전 블록과 다음 블록 둘 다 할당됨
   → 병합하지 않고 그대로 둔다.
2. 이전 블록은 할당됨, 다음 블록은 가용 상태
   → 현재 블록과 다음 블록을 병합한다.
3. 이전 블록은 가용 상태, 다음 블록은 할당됨
   → 이전 블록과 현재 블록을 병합한다.
4. 이전 블록과 다음 블록 둘 다 가용 상태
   → 이전 블록, 현재 블록, 다음 블록 세 개를 모두 병합한다.

병합할 때는 블록의 크기를 업데이트하고, 새로운 블록의 헤더와 풋터를 수정한다.

static void *coalesce(void *bp)
{
    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 (prev_alloc && next_alloc) {            /* Case 1 */
        return bp;
    }

    else if (prev_alloc && !next_alloc) {       /* Case 2 */
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    }

    else if (!prev_alloc && next_alloc) {       /* Case 3 */
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(bp), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }

    else {                                      /* Case 4 */
        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);
    }
    return bp;
}

병합 흐름 요약

• 병합 전후에 항상 HDRP와 FTRP를 일관되게 수정한다.
• 에필로그 블록은 항상 할당 상태이기 때문에, coalesce는 힙 경계를 넘어가는 경우를 별도로 신경 쓸 필요가 없다.
• 프롤로그 블록도 항상 할당 상태이므로, 힙의 시작 부분에서도 병합 처리를 간단히 할 수 있다​.

---

블록 할당

 

• mm_malloc는 요청된 size를 내부 관리용 오버헤드(헤더와 풋터)와 정렬을 반영하여 asize로 조정한다.
• 가용 리스트를 순회하면서 find_fit으로 첫 번째로 맞는 블록을 찾는다.
• 맞는 블록이 있으면 place를 호출해 배치한다. 필요시 블록을 분할(split)한다.
• 맞는 블록이 없다면 힙을 확장(extend_heap)한 뒤 새 가용 블록에 place한다.

 

void *mm_malloc(size_t size)
{
    size_t asize; /* Adjusted block size */
    size_t extendsize; /* Amount to extend heap if no fit */
    char *bp;

    /* Ignore spurious requests */
    if (size == 0)
        return NULL;

    /* Adjust block size to include overhead and alignment reqs. */
    if (size <= DSIZE)
        asize = 2*DSIZE;
    else
        asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);

    /* Search the free list for a fit */
    if ((bp = find_fit(asize)) != NULL) {
        place(bp, asize);
        return bp;
    }

    /* No fit found. Get more memory and place the block */
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
        return NULL;
    place(bp, asize);
    return bp;
}

---

애플리케이션이 kkk 바이트짜리 블록을 요청하면, 할당기는 가용 리스트(free list) 를 순회하면서 요청을 만족할 수 있는 충분히 큰 블록을 찾는다.
할당기가 어떤 블록을 선택하는지는 배치 정책(placement policy) 에 따라 달라진다​.

대표적인 배치 정책은 다음과 같다:

• First Fit (최초 적합)
  가용 리스트의 시작부터 순차적으로 탐색하여, 요청을 만족하는 처음 만나는 가용 블록을 선택한다.
• Next Fit (다음 적합)
  이전 탐색이 끝난 지점부터 탐색을 계속하여, 요청을 만족하는 가용 블록을 찾는다. 항상 리스트 처음부터 탐색하지 않기 때문에 효율이 더 나을 수 있다.
• Best Fit (최적 적합)
  가용 리스트 전체를 탐색해서, 요청을 만족하는 블록 중 가장 크기가 작은 블록을 선택한다. 외부 단편화를 줄일 수 있지만, 탐색 비용이 크다.

find_fit 함수 구현 (책 예시)

책에서는 First Fit 정책을 사용하는 예시로 find_fit 함수를 이렇게 작성한다:

static void *find_fit(size_t asize)
{
    /* First-fit search */
    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; /* No fit */
}

---

place 함수 구현 (책 예시)

찾은 블록을 배치할 때는 요청 크기보다 블록이 충분히 크면 분할(splitting) 을 수행한다.
분할 가능한 경우, 앞부분에 요청 크기만큼 할당 블록을 만들고, 나머지는 가용 블록으로 남긴다.
분할이 불가능할 정도로 작은 경우에는 전체 블록을 할당해버린다.

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

---

전체 코드

/* Basic constants and macros */
#define WSIZE       4       /* Word and header/footer size (bytes) */
#define DSIZE       8       /* Doubleword size (bytes) */
#define CHUNKSIZE  (1<<12)  /* Extend heap by this amount (bytes) */

#define MAX(x, y) ((x) > (y) ? (x) : (y))

/* Pack a size and allocated bit into a word */
#define PACK(size, alloc)  ((size) | (alloc))

/* Read and write a word at address p */
#define GET(p)       (*(unsigned int *)(p))
#define PUT(p, val)  (*(unsigned int *)(p) = (val))

/* Read the size and allocated fields from address p */
#define GET_SIZE(p)  (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)

/* Given block ptr bp, compute address of its header and footer */
#define HDRP(bp)       ((char *)(bp) - WSIZE)
#define FTRP(bp)       ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

/* Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp)  ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp)  ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

static char *heap_listp; /* Pointer to first block */

/* Function prototypes */
static void *extend_heap(size_t words);
static void *coalesce(void *bp);
static void *find_fit(size_t asize);
static void place(void *bp, size_t asize);

/* Initialize the heap */
int mm_init(void)
{
    if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)
        return -1;
    PUT(heap_listp, 0); /* Alignment padding */
    PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1)); /* Prologue header */
    PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1)); /* Prologue footer */
    PUT(heap_listp + (3*WSIZE), PACK(0, 1)); /* Epilogue header */
    heap_listp += (2*WSIZE);

    if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
        return -1;
    return 0;
}

/* malloc: Allocate a block with at least size bytes of payload */
void *mm_malloc(size_t size)
{
    size_t asize; /* Adjusted block size */
    size_t extendsize; /* Amount to extend heap if no fit */
    char *bp;

    if (size == 0)
        return NULL;

    if (size <= DSIZE)
        asize = 2*DSIZE;
    else
        asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);

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

    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
        return NULL;
    place(bp, asize);
    return bp;
}

/* free: Free a block */
void mm_free(void *bp)
{
    size_t size = GET_SIZE(HDRP(bp));

    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    coalesce(bp);
}

/* coalesce: Boundary tag coalescing. Return ptr to coalesced block */
static void *coalesce(void *bp)
{
    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 (prev_alloc && next_alloc) {            /* Case 1 */
        return bp;
    }

    else if (prev_alloc && !next_alloc) {       /* Case 2 */
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    }

    else if (!prev_alloc && next_alloc) {       /* Case 3 */
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(bp), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }

    else {                                      /* Case 4 */
        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);
    }
    return bp;
}

/* extend_heap: Extend heap with free block and return its block pointer */
static void *extend_heap(size_t words)
{
    char *bp;
    size_t size;

    size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;
    if ((long)(bp = mem_sbrk(size)) == -1)
        return NULL;

    PUT(HDRP(bp), PACK(size, 0)); /* Free block header */
    PUT(FTRP(bp), PACK(size, 0)); /* Free block footer */
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */

    return coalesce(bp);
}

/* find_fit: Find a fit for a block with asize bytes */
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;
}

/* place: Place block of asize bytes at start of free block bp */
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));
    }
}