[C언어] Malloc 파헤치기: 묵시적 할당기 2탄

가용 블록의 분할 (Splitting Free Blocks)

할당기가 요청에 맞는 가용 블록 하나를 찾았다고 끝은 아니다.

이제는 그 블록 전체를 다 쓸지, 아니면 일부만 잘라서 쓸지를 결정해야 한다.

1. 가용 블록 전체를 사용하는 방식

• 이건 가장 단순하고 빠르다.
• 블록을 통째로 써버리는 거라 별다른 추가 작업이 필요 없다.
• 문제는, 내부 단편화(internal fragmentation) 가 발생할 수 있다는 점이다.

예를 들어 20바이트만 필요했는데 64바이트짜리 블록을 그대로 써버리면

나머지 44바이트는 낭비다. → 이게 내부 단편화.

→ 물론 요청 크기와 블록 크기가 비슷하면 이 정도 단편화는 감수할 수도 있다.

2. 블록을 쪼개서 일부만 사용하는 방식

• 만약 가용 블록이 충분히 크다면,
• 요청한 크기만큼만 할당하고, 남은 부분은 새 가용 블록으로 다시 등록할 수 있다.
• 이걸 **분할(Splitting)**이라고 한다.

하지만 너무 자잘하게 쪼개면?

블록들이 지나치게 작아져서 나중에 쓸모없는 "조각"들만 남을 수도 있다.

그래서 최소 블록 크기 조건을 고려해 쪼개야 한다.

요청 블록이 없다면? — 힙 확장으로 대응하기

요청한 크기를 만족하는 가용 블록이 없다면, 할당기는 다음을 시도한다:

1. *이웃한 가용 블록을 병합(coalesce)**해서
2. 더 큰 블록을 만들어 본다.
3. 그래도 안 되면, 커널에게 sbrk를 통해 힙 확장을 요청한다.
4. → 새 메모리를 받아오고, 이를 가용 블록으로 변환한다.
5. 이 새 블록을 가용 리스트에 삽입하고,
6. 거기서 다시 요청한 크기만큼 할당한다.

가용 블록 연결(Coalescing): 단편화 해결의 열쇠

할당된 블록을 free 했을 때,

그 양 옆에 가용 블록이 있을 수 있다.

이때 그냥 놔두면 단편화 문제가 발생할 수 있다.

특히 각각은 작은데, 합치면 요청을 처리할 수 있는 상황이 문제다.

예:

옆에 3워드, 반대쪽에 2워드짜리 가용 블록이 있는데

사용자가 5워드를 요청하면?

→ 따로는 안 되고, 합치면 가능한데 연결되지 않으면 요청 실패.

---

그렇다면 연결은 언제 할까?

1. 즉시 연결 (Immediate Coalescing)
   • 블록이 반환될 때마다 바로 병합 수행
   • 단순하고 구현도 쉽다
   • 하지만 자잘한 병합이 연쇄적으로 일어나 오히려 쪼개질 위험도 있음
2. 지연 연결 (Deferred Coalescing)
   • 나중에, 일정 조건(시간 or 요청 수 등)이 되면 한꺼번에 병합
   • 오버헤드는 줄이지만, 단편화는 더 유지될 수 있음
3. 실패 시 연결 (On-demand Coalescing)
   • 요청 처리 실패 시, 그때 주변 블록을 합쳐본다
   • 최대한 느긋하게 병합을 수행함

---

🔍 즉시 연결은 빠르고 간단하지만,

너무 자주 쓰면 오히려 불필요한 병합/분할 연쇄로 성능을 떨어뜨릴 수 있다.

그래서 현실적인 구현에서는 즉시 연결 + 조건 기반 최적화 조합이 자주 쓰인다.

경계 태그(Coalescing with Boundary Tags)

할당기를 구현할 때, 반환된 블록과 **양 옆 가용 블록을 병합하는 것(coalescing)**은

단편화를 줄이기 위한 핵심 메커니즘이다.

예를 들어 반환하는 블록이 cur 이라고 할때 다음 가용블록을 연결하는 것은 쉽다고 생각한다.

현재블록의 헤더는 다음블록의 헤더를 가리키고 있기 때문에 다음 블록이 가용한지 결정할 수 있게 된다

하지만 이전블록들은? 헤더를 사용하는 묵시적 가용리스트는 현재블록에 도달할때까지 전체 리스트를 검색해서 이전블록들을 기억하는 방식을 사용한다. 그러면 찾는데 시간이 너무 오래 걸리기 때문에 상수시간 안에 해결 할 수 없는 단점이 있다

이를 해결하기 위해 각블록의 끝부분에 푸터라는 경계를 추가 하는것으로 찾기 쉽게 했고 이 푸터에는 헤더와 같은 데이터를 가진다

Footer가 중요한 이유

#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE((char *)(bp) - DSIZE))

• HDRP(bp)는 현재 블록의 헤더 주소
• FTRP(bp)는 현재 블록의 푸터 주소
• PREV_BLKP(bp)는 푸터를 기준으로 이전 블록의 시작 주소를 계산

이런 방식으로 이전 블록의 헤더를 푸터로부터 역으로 찾아낼 수 있게 되는 것이다.

덕분에 상수 시간 안에 병합이 가능해진다.

Coalescing 가능한 네 가지 상황

free(bp)로 블록을 반환한다고 했을 때,

현재 블록을 기준으로 가능한 병합 케이스는 아래와 같다:

1. 이전과 다음 블록 모두 할당됨 → 병합 불가, bp 그대로 리턴

2. 이전은 할당 / 다음은 가용 → bp와 다음 블록을 병합

3. 이전은 가용 / 다음은 할당 → 이전 블록과 bp를 병합 → 새로운 bp는 이전 블록의 시작 주소

4. 이전과 다음 모두 가용 → 세 블록 모두 병합 → 새로운 bp는 이전 블록의 시작 주소

이 네 가지를 조건문으로 구현하면 아래와 같이 정리된다:

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

그럼 bp는 뭐야?

bp는 payload 시작 지점을 가리키는 포인터야.

즉, 실제 데이터가 들어가는 부분.

하지만 헤더/푸터는 이 payload의 앞뒤에 붙어 있기 때문에,

bp를 기준으로 offset을 계산해서 헤더/푸터 주소를 구하는 거야.

경계 태그의 단점: 오버헤드 발생

푸터까지 쓰면 블록당 헤더 + 푸터 = 8바이트를 메타데이터로 사용하게 된다.

작은 블록이 많아질 경우, 상당한 메모리 오버헤드가 생길 수 있다.

그래서 이를 해결하기 위해 블록 크기를 8바이트 단위로 정렬하고,

최소 블록 크기를 16바이트 이상으로 설정하는 경우가 많다.