[CSAPP 9장 완전 정복] 9.9(Part 9) 블록 병합(Coalescing) 로직과 실제 구현

블록 병합(Coalescing) 로직과 실제 구현

이번 포스트에서는 메모리 단편화를 줄이기 위한 핵심 기술인 블록 병합(Coalescing)을 구체적으로 살펴보겠습니다. 특히, 병합 로직을 실제 코드 수준에서 어떻게 구현하는지도 함께 다뤄봅니다.

 

 

블록 병합이 필요한 이유

free()로 블록을 해제할 때, 주변에 있는 free block들과 즉시 병합하면 외부 단편화를 크게 줄일 수 있는데요. 이를 통해 큰 메모리 요청이 오더라도 무리 없이 처리할 가능성 또한 높아지게 됩니다.

 

 

병합 시 고려해야 할 4가지 경우

이전의 Boundary Tag를 소개했을 때 앞서 한 번 블록 병합 전략에 대해 소개한 적이 있었는데요. 복습하는 겸 다시 한 번 알아보겠습니다.

• Case 1: 이전/다음 블록이 모두 할당된 경우
  • 병합 없음
• Case 2: 이전 블록이 할당됐고, 다음 블록이 free인 경우
  • 현재 블록과 다음 블록을 병합
• Case 3: 이전 블록이 free이고, 다음 블록이 할당된 경우
  • 이전 블록과 현재 블록을 병합
• Case 4: 이전/다음 블록이 모두 free인 경우
  • 세 블록 모두 병합

병합 시 각 케이스마다 총 free block 크기를 합산하고, Header 및 Footer를 갱신하게 됩니다.

 

 

Boundary Tag를 활용한 빠른 병합

병합은 O(1) 시간에 처리해야 효율적인데요. 이를 위해 다음 정보를 사용합니다.

• 현재 블록 바로 뒤의 Header로 다음 블록 상태 확인
• 현재 블록 바로 앞의 Footer로 이전 블록 상태 확인

Boundary Tag 기법 덕분에, 전체 리스트를 탐색할 필요 없이 바로 병합 여부를 판단할 수 있게 됩니다.

 

 

병합 로직 코드 예시

아래 C 코드는 병합 로직을 구현한 예시인데요. Case 별로 처리가 달리지는 것을 볼 수 있습니다.

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

각 경우마다 size를 갱신하고, Header/Footer를 업데이트한 뒤, 병합 결과 블록의 시작 주소를 반환하게 됩니다.

 

 

즉시 병합 vs 지연 병합

• 즉시 병합: free() 호출 시 바로 주변 블록과 병합 (가장 보편적)
• 지연 병합: 필요할 때 (예: malloc 실패 시 전체 병합) 수행

학습 및 기본 구현에서는 보통 즉시 병합을 사용하게 됩니다.

 

 

마치면서

이번 편에서는 블록 병합(Coalescing) 기법과 그 실제 구현 방법을 살펴봤습니다. Boundary Tag 덕분에 병합을 매우 빠르게 처리할 수 있고, 이는 메모리 단편화 관리에 핵심적인 역할을 합니다.

 

다음 편에서는 할당기 설계 시 고려해야 할 제약과 성능 목표를 정리하면서, 설계 관점에서 동적 메모리 관리 문제를 바라보는 시각을 넓혀보겠습니다. 감사합니다.