2026. 10. 2. 14:43ㆍ크래프톤 정글/포스팅
지금 위치: 네 가지 결정 중 마지막 ④ 병합입니다.
이번 파트의 질문:
블록을 free하고 난 후, free된 블록의 이웃이 free라면 어떻게 할까?
그리고 앞 뒤 이웃의 상태와 위치를 어떻게 빨리 알아낼까?
1. 문제: 이웃한 빈 블록이 "가짜 단편화"를 만든다
블록을 free하면 그 이웃도 free일 수 있습니다. 합치지 않고 두면 이런 일이 생깁니다.
[ free 3워드 ][ free 3워드 ] ← 합치면 6워드
이 상태에서 payload 4워드를 요청하면(블록 크기 6워드 필요?) 각각은 3워드라 둘 다 작아서 실패합니다.
합계는 충분한데 쪼개져 있어서 못 쓰는 상태, 이것이 가짜 단편화(false fragmentation)입니다.
해결은 간단합니다. 인접한 빈 블록은 하나로 합칩니다(coalescing). 책은 이를 필수라고 봅니다.
2. 언제 합칠까?
| 방식 | 내용 | 특징 |
| Immediate (즉시) | free할 때마다 바로 합침 | 단순하고 상수 시간. 다만 "합쳤다가 바로 다시 쪼개는" 낭비(thrashing)가 생길 수 있음 |
| Deferred (지연) | 나중에 한꺼번에 합침 (예: 할당 실패 시) |
빠른 allocator가 선호 |
예를 들어 같은 크기의 할당/해제를 반복하면, 즉시 병합은 합쳤다가 다시 쪼개기를 반복합니다.
책의 allocator와 과제는 immediate coalescing입니다.
3. 다음 블록 합치기는 쉽다
현재 블록의 헤더로 다음 블록의 위치를 알 수 있습니다. (현재 블록 헤더 위치 + 현재 블록 사이즈)
다음 블록 헤더를 보고 free인 경우
현재 블록 헤더에 새 크기(현재 크기 + 다음 블록 크기)를 기록하면 끝이고, 상수 시간입니다.
합치기 전: [ H(n) | ... ][ H(m2) | ... ]
합치기 후: [ H(n+m2) | ............... ]
↑ 옛 m2의 헤더가 있던 자리는 그냥 참조하지 않는 값으로 남아있음4. 이전 블록 합치기는 어렵다 → boundary tag (푸터) 사용
상황: 블록 n을 free했고, 앞 뒤 이웃이 free인지 알아야 한다
[ m1: ? ][ n: 방금 free ][ m2: ? ]
합치려면 m1과 m2가 free인지 알아야 합니다.
m2와 합치는 것은 쉽습니다. n의 헤더에 n의 크기가 있으므로 m2 헤더로 이동할 수 있고
m2의 헤더를 읽으면 해당 블록이 free인지 바로 압니다.
이전 블록(m1)은 갈 수가 없다
m1의 위치 = n의 위치 - (m1의 크기)
그런데 n의 헤더에는 n 자신의 크기만 있어서 m1의 크기를 모릅니다. 얼마나 뒤로 가야 할지 계산할 수 없습니다.
힙 처음부터 훑으며 n 직전 블록을 기억하는 방법은 있지만, free마다 힙 전체를 훑어야 해서 너무 느립니다.
해결: m1이 자기 끝에 정보를 남겨둔다 (푸터)
그래서 모든 블록 맨 끝에 헤더의 복사본(푸터)을 둡니다.
[ m1: H | ...... | F ][ n: H | ...... | F ][ m2: H | ... | F ]
↑ ↑
m1의 푸터 n의 헤더
블록들은 빈틈없이 이어 붙어 있으므로
n의 헤더 바로 앞 4바이트에서 m1의 푸터에 접근하여 m1의 크기와 free/allocated 여부를 확인할 수 있게됩니다.
n의 bp(payload 시작)를 기준으로 따라가보면..
- n의 헤더 = bp - 4
- 헤더의 앞 4바이트인 m1의 푸터 = bp - 8
- bp - 8을 읽는다 → m1의 크기와 상태를 알게 된다
- m1이 free면 합칠 대상이다
- m1의 bp = n의 bp - m1의 크기
숫자 예시: m1 크기 16, n의 bp = 140이면
- 푸터 위치 = 140 - 8 = 132 → "크기 16, free" 읽음
- m1의 bp = 140 - 16 = 124
읽기 한 번과 뺄셈 한 번으로 끝나므로 상수 시간입니다
5. free시 4가지 Case
| Case | 이전 블록 | 다음 블록 | 동작 |
| 1 | allocated | allocated | 합칠 것 없음. 현재 블록만 free로 표시 |
| 2 | allocated | free | 현재 + 다음 합침. 크기 n+m2. 현재 헤더, 다음 블록의 푸터를 갱신 |
| 3 | free | allocated | 이전 + 현재 합침. 크기 m1+n. 이전 블록의 헤더, 현재 푸터를 갱신 |
| 4 | free | free | 셋 모두 합침. 크기 n+m1+m2. 이전 블록 헤더, 다음 블록 푸터를 갱신 |
핵심 규칙: 합쳐진 블록의 "맨 앞 헤더"와 "맨 뒤 푸터"에 새 크기를 기록합니다.
Case 4: [ m1: free ][ n: 방금 free ][ m2: free ]
↓ 합침
[ 헤더: m1+n+m2|f ...... 푸터: m1+n+m2|f ]6. 푸터의 비용과 최적화
문제: 푸터는 모든 블록에 4바이트를 더 쓴다
푸터 덕분에 이전 블록을 상수 시간에 찾지만, 모든 블록이 끝에 4바이트를 더 차지합니다.
┌────────┬─────────┬─────────┬────────┐
│ Header │ Payload │ Padding │ Footer │
│ 4B │ │ │ 4B │
└────────┴─────────┴─────────┴────────┘
└────────────── 블록 크기 ──────────────┘작은 블록이 많으면 비율이 커집니다. 예를 들어 블록 크기 16에서 헤더+푸터가 8바이트이니 절반입니다.
푸터가 정말 항상 필요한가?
푸터는 블록 n을 free할 때 이전 블록 m1이 free인지 알아내려고 읽는 값이었습니다.
[ m1: ? ][ n: 방금 free ][ m2: ? ]- 알고 싶은 것: 이전 블록 m1이 free인가 allocated인가
- m1이 allocated이면 합칠 일이 없으니 m1의 크기도 필요 없습니다. (m1이 "allocated다"라는 사실만 필요)
- m1이 free일 때만 합쳐야 하므로 크기가 필요합니다.
즉 m1이 allocated인 동안은 한 비트 정보를 얻으려고 푸터 4바이트를 통째로 쓰고 있었던 겁니다.
m1의 상태 비트를 n의 헤더에 미리 적어둔다
31 3 2 1 0
┌──────────────────────────────┬──┬──┬──┐
│ 블록 크기를 나타내는 숫자 │ 0│ p│ a│
└──────────────────────────────┴──┴──┴──┘
│ └ a: 현재 블록 (1 = allocated, 0 = free)
└─── p: 이전 블록 (1 = allocated, 0 = free)헤더에서 크기 값은 언제나 8의 배수라 하위 3비트가 비어 있기 때문에 최하위 비트에 현재 블록의 상태를 적습니다.
그런데 비트가 더 남아있으니, 그 옆의 남는 비트에 "이전 블록이 allocated?인지를 적습니다.
그러면 n은 자기 헤더만 보고 이전 블록의 상태를 압니다. 이전 블록이 allocated이면 푸터를 읽으러 갈 필요가 없습니다.
따라서 현재 블록이 allocated인 경우 푸터를 가질 필요가 없다.
하지만 현재 블록이 free인 경우에는, 다음 블록이 free될 때 이 블록과 병합해야 하므로 푸터에서 이 블록의 크기를 읽어 시작 위치로 가야 한다. 그래서 free 블록에는 푸터가 필요하다.
최소 블록 계산 하기
- allocated 블록의 payload는 최소 1바이트, free 블록에는 payload 없음
- 블록 크기는 정렬 단위의 배수로 올림 (Single word = 4, Double word = 8)
| 정렬 단위 | allocated 구성 | 최소 블록 크기 계산 | free 구성 | 최소 블록 크기 계산 | 최종 최소 블록 크기 |
| 4B | 헤더+푸터 | 4+1+4=9 → 12 | 헤더+푸터 (payload 없음) |
4+4=8 | 12 |
| 4B | 헤더만 | 4+1=5 → 8 | 4+4=8 | 8 | |
| 8B | 헤더+푸터 | 4+1+4=9 → 16 | 4+4=8 | 16 | |
| 8B | 헤더만 | 4+1=5 → 8 | 4+4=8 | 8 |
7. epilogue와 prologue가 필요한 이유
문제: 힙의 양 끝 블록은 이웃이 없다
coalesce는 블록을 free할 때 항상 이웃 둘을 확인합니다.
prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); // 이전 블록의 푸터를 읽는다 → bp - 8
next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); // 다음 블록의 헤더를 읽는다 → (bp - 4) + 현재 크기)
그런데 가장자리 블록은 이웃이 없습니다.
낮은 주소 높은 주소
◀───────────────────────────▶
? [ 첫 블록 ][ ... ][ 마지막 블록 ] ?
↑ ↑
이전 블록이 없다 다음 블록이 없다- 첫 블록을 free하면: 이전 푸터 자리(bp - 8)가 힙 바깥입니다. 그걸 읽으면 엉뚱한 값을 읽습니다.
- 마지막 블록을 free하면: 다음 헤더 자리도 힙 바깥입니다.
이 문제를 그대로 두면 코드에 이런 if가 필요해집니다.
if (첫 블록이면) → 이전 확인 건너뛰기
if (마지막 블록이면) → 다음 확인 건너뛰기
free할 때마다 이 검사를 하게 되어 코드가 지저분해지고, 실수하기 쉽고, 느려집니다. 그리고 case도 늘어납니다.
해결: 가짜 이웃을 미리 깔아둔다 - prologue와 epilogue
양 끝에 항상 allocated인 표식 블록을 둡니다. 그러면 가장자리 블록에게도 이웃이 "있는 것"이 되고, 그 이웃이 allocated이니 "합칠 대상이 아님"으로 자연스럽게 기존 코드 로직 그대로 처리됩니다. 예외 처리가 사라지고 4가지 case만으로 모든 경우가 처리됩니다.
[ 패딩 ][ prologue: H | F ][ 첫 진짜 블록 ] ... [ 마지막 진짜 블록 ][ epilogue: H ]
└ 크기 8,allocated ┘ └ 크기 0,allocated ┘- prologue (맨 앞 블록, 맨 처음 블록의 이전 쪽 이웃)
- 구성: 헤더 + 푸터(8바이트) payload는 0바이트인 특수한 블록입니다.
→ 헤더나 푸터 둘 중 하나만 있으면 안될까? 헤더+푸터를 다 두는 이유: prologue를 "크기 8짜리 진짜 블록"으로 만들기 위해. 블록의 모양은 헤더 + 푸터가 한 세트라서, 다른 코드들이 prologue를 평범한 블록처럼 다룰 수 있게 됩니다. - 적혀있는 값: 크기 8, 상태 allocated
- 블록들이 이전 블록을 확인을 할 때 읽는 bp - 8이 prologue의 푸터입니다. "allocated"가 읽히므로 합치지 않습니다.
- 구성: 헤더 + 푸터(8바이트) payload는 0바이트인 특수한 블록입니다.
- epilogue (맨 뒤 블록, 마지막 블록의 다음 쪽 이웃)
- 구성: 헤더만(4바이트)
→ 헤더만 필요한 이유: 다음 블록 확인은 헤더만 읽기 때문입니다. - 적혀있는 값: 크기 0, 상태 allocated.
- 마지막 진짜 블록이 다음 확인을 할 때 읽는 것이 epilogue의 헤더입니다. "allocated"가 읽히므로 합치지 않습니다.
- 크기 0이라는 값이 훑기(find_fit)의 종료 표식 역할도 합니다.
- 힙이 늘어나면 extend_heap에서 새 free 블록이 옛 epilogue 자리를 덮어쓰고, 새 영역 끝에 새 epilogue를 다시 씁니다. 그래서 힙이 몇 번 늘어나도 "끝은 항상 allocated 헤더"라는 불변식이 유지됩니다.
- 구성: 헤더만(4바이트)
예시: 첫 블록을 free할 때
[ 패딩 ][ prologue(a) ][ 첫 블록 n ][ m2 ]
n을 free하면:
- 이전 확인: bp - 8(= prologue의 푸터)을 읽는다 → allocated
- 다음 확인: m2의 헤더를 읽는다
- 결과: Case 1 (a/a) 또는 Case 2(a/f)가 됨. 가장자리라서 따로 처리할 것이 없다.
인접한 빈 블록을 합치지 않으면 합계는 충분한데 못 쓰는 가짜 단편화(외부 단편화)가 생기므로, free할 때 즉시 합친다.
→ 다음 블록은 헤더의 크기로 쉽게 찾지만, 이전 블록은 알 방법이 없어서 블록 끝에 헤더의 복사본인 푸터(boundary tag)를 둔다.
현재 블록 바로 앞 4바이트가 이전 블록의 푸터라서 이전 블록의 상태와 위치를 상수 시간에 알 수 있다.
→ 합쳐진 블록의 맨 앞 헤더와 맨 뒤 푸터에 새 크기를 쓴다.
→ 양끝에 항상 allocated인 prologue/epilogue를 두어 가장자리 예외 처리를 없앤다.