9.9.11 경계 태그 병합(Boundary-Tag Coalescing)
해제된 블록과 인접한 빈 블록을 헤더·풋터(boundary tags) 정보를 이용해 즉시 합치는 방식입니다.
- 풋터에 크기 정보를 복사해 두면, 해제 시 이전 블록의 크기를 O(1)로 알 수 있습니다.
- free(ptr) 호출 시 왼쪽·오른쪽 이웃 블록의 할당 비트를 검사하고, 모두 자유 상태라면 세 블록을 하나로 합칩니다.
- 즉시 병합(immediate coalescing)을 쓰면 외부 단편화를 효과적으로 줄이지만, 매 free마다 검사 비용이 추가될 수 있습니다.
- Header/Footer 모두에 블록 크기와 할당 비트(a/f)를 저장합니다.
- free 시 Footer로 이전 블록 크기를 즉시 알아낼 수 있어 빠른 병합이 가능합니다.
병합 4가지 케이스
각 블록 이름(m1, n, m2)은 그 블록 크기를, a는 할당(allocated), f는 자유(free)를 나타냅니다.
| 케이스 | 상황 | 동작 |
| 1 | prev = a, 현재 n = a, next = a | 병합 없음: 그냥 n을 f로 표시만(이웃 블록과 모두 할당됨) |
| 2 | prev = a, 현재 n = a, next = f | 오른쪽 병합: n + m2 크기로 합쳐 하나의 자유 블록으로 생성 |
| 3 | prev = f, 현재 n = a, next = a | 왼쪽 병합: m1 + n 크기로 합쳐 하나의 자유 블록으로 생성 |
| 4 | prev = f, 현재 n = a, next = f | 양쪽 병합: m1 + n + m2 크기로 합쳐 하나의 자유 블록으로 생성 |
9.9.12 간단한 할당기의 구현
#include <stdlib.h>
#include <stdio.h>
/*======================================================
전역 변수: 힙의 시작과 끝, 현재 brk 포인터를 추적
- heap_start: 힙의 가장 첫 번째 바이트 주소
- heap_brk: 현재 힙의 끝(마지막 유효 바이트 + 1)
- heap_max: 시스템이 허용한 힙의 최대 주소
======================================================*/
static char *heap_start; // 최초 sbrk로 받은 메모리 시작 주소
static char *heap_brk; // 다음에 사용할 수 있는 힙 상단 위치
static char *heap_max; // sbrk를 통해 확장 가능한 최대 영역
/*======================================================
mem_init: 힙 메모리 초기화 함수
- 처음에 MAX_HEAP 바이트만큼 malloc으로 확보
- prologue/epilogue 블록을 설정하여 경계 조건 단순화
======================================================*/
void mem_init(void) {
/* 1) 시스템으로부터 MAX_HEAP 바이트 확보 */
heap_start = (char *)malloc(MAX_HEAP);
if (!heap_start) {
fprintf(stderr, "mem_init: 초기 힙 메모리 확보 실패\n");
exit(1);
}
heap_brk = heap_start;
heap_max = heap_start + MAX_HEAP;
/* 2) Prologue 블록 설정
- 크기 DSIZE (헤더+풋터) 확보
- 할당 비트 alloc=1 로 표시하여 실제 데이터 블록과 구분
*/
PUT(heap_brk, PACK(DSIZE, 1)); // 헤더: 크기 DSIZE, 할당됨
PUT(heap_brk + WSIZE, PACK(DSIZE, 1)); // 풋터: 크기 DSIZE, 할당됨
heap_brk += DSIZE; // 실제 유효 블록 시작 위치로 이동
/* 3) Epilogue 블록 설정
- 크기 0, alloc=1
- 힙 끝을 표시하며, 반복 탐색 시 종료 조건으로 활용
*/
PUT(heap_brk, PACK(0, 1)); // Epilogue 헤더
}
/*======================================================
extend_heap: 힙을 incr 바이트만큼 확장
- 힙이 heap_max를 넘지 않으면 유효 블록으로 추가
- 새로 생긴 영역을 자유 블록으로 만들고 epilogue 갱신
- coalesce로 인접 자유 블록과 병합
======================================================*/
void *extend_heap(size_t incr) {
char *bp;
/* 1) 확장 가능한지 체크 */
if (heap_brk + incr + WSIZE > heap_max)
return NULL; // 더 이상 확대 불가능
/* 2) 이전 Epilogue 위치를 새 자유 블록 시작으로 사용 */
bp = heap_brk;
/* 3) 새 자유 블록 헤더/풋터 설정
- 헤더: 크기=incr, alloc=0
- 풋터: 블록 끝에서 크기=incr, alloc=0
*/
PUT(HDRP(bp), PACK(incr, 0));
PUT(FTRP(bp), PACK(incr, 0));
/* 4) 새로운 Epilogue 블록 설정
- 위치: bp + incr
- 크기=0, alloc=1
*/
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
/* 5) heap_brk 포인터를 새 Epilogue 뒤로 이동 */
heap_brk = (char *)NEXT_BLKP(bp) + WSIZE;
/* 6) 방금 만든 자유 블록과 인접 자유 블록 병합 */
return coalesce(bp);
}
/*======================================================
coalesce: 블록 bp를 해제하면서 이웃 자유 블록과 병합
- prev_alloc: 이전 블록이 할당되었는지
- next_alloc: 다음 블록이 할당되었는지
- size: 현재 블록 크기
- 네 가지 상황에 따라 병합 수행 후 병합된 블록의 bp 반환
======================================================*/
void *coalesce(void *bp) {
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); // 이전 풋터로 alloc 비트 확인
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); // 다음 헤더로 alloc 비트 확인
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 반환
}
/*======================================================
find_fit: 첫 번째 적합 블록 검색 (First-Fit)
- asize: 요청한 블록 크기(정렬 + 헤더/풋터 포함)
- 힙 시작부터 Epilogue 전까지 순차 탐색
- 크기 ≥ asize && alloc=0인 첫 블록 반환
- 없으면 NULL
======================================================*/
void *find_fit(size_t asize) {
void *bp = heap_start + DSIZE; // Prologue 뒤 첫 블록
while (GET_SIZE(HDRP(bp)) > 0) { // Epilogue(크기=0) 전까지
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))
return bp; // 적합 블록 발견
bp = NEXT_BLKP(bp);
}
return NULL; // 찾지 못함
}
/*======================================================
place: bp 블록을 asize 바이트만큼 할당하고, 잔여 부분 분할
- csize: 기존 빈 블록의 크기
- if 분할 후 남은 부분이 최소 블록 크기(2*DSIZE) 이상이면 분할
- 분할: 앞부분 할당, 뒷부분 자유 블록으로 남김
- else 전체 블록 할당(분할 없이)
======================================================*/
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));
}
}
/*======================================================
mm_malloc: asize 바이트 만큼 동적 할당
- size = 실제 요청 바이트 수
- 1) size=0 면 NULL 반환
- 2) asize = ALIGN(size)+DSIZE를 최소 블록 크기(2*DSIZE)로 올림
- 3) find_fit으로 적합 블록 검색 → 있으면 place
- 4) 없으면 extend_heap(최소 CHUNKSIZE 또는 asize) → 다시 place
======================================================*/
void *mm_malloc(size_t size) {
size_t asize; // 실제 배치할 블록 크기
size_t extendsize; // 힙 확장 단위
char *bp;
if (size == 0)
return NULL;
/* 1) 요청 크기 정렬 + 헤더/풋터 오버헤드 */
asize = MAX(ALIGN(size) + DSIZE, 2 * DSIZE);
/* 2) 기존 힙에서 빈 블록 검색 */
if ((bp = find_fit(asize)) != NULL) {
place(bp, asize);
return bp;
}
/* 3) 빈 블록 없으면 힙 확장 */
extendsize = MAX(asize, CHUNKSIZE);
if ((bp = extend_heap(extendsize)) == NULL)
return NULL; // 메모리 부족
place(bp, asize);
return bp;
}
/*======================================================
mm_free: ptr 블록을 자유(free) 상태로 전환
- 1) 헤더/풋터 alloc 비트를 0으로
- 2) coalesce 호출하여 인접 자유 블록 병합
======================================================*/
void mm_free(void *ptr) {
size_t size = GET_SIZE(HDRP(ptr));
/* 1) 헤더/풋터에 자유 블록 표시 */
PUT(HDRP(ptr), PACK(size, 0));
PUT(FTRP(ptr), PACK(size, 0));
/* 2) 인접 블록과 병합 */
coalesce(ptr);
}동작 흐름 요약
- 초기화(mem_init)
- 프로로그·에필로그 블록 설정
- 할당(mm_malloc)
- 요청 크기를 정렬(ALIGN) 후 헤더·풋터 오버헤드(DSIZE) 포함해 조정
- find_fit로 첫 적합 블록 검색 → place로 분할·할당
- 없으면 extend_heap으로 힙 확장 후 다시 배치
- 해제(mm_free)
- 헤더·풋터의 alloc 비트를 0으로 바꾼 뒤 coalesce 실행
- 양쪽 이웃 블록들과 즉시 병합
9.9.13 명시적 가용 리스트(Explicit Free List)
명시적 자유 리스트 방식에서는 자유 블록(free block)만 별도의 이중 연결 리스트(doubly linked list)로 관리하여, malloc 시 빈 블록 탐색 비용을 크게 줄이는 기법입니다.
- 할당된 블록(a) 은 사용자 페이로드만 있고, 추가 메타데이터(링크 포인터)를 저장하지 않습니다.
- 자유 블록(b) 은 사용자 페이로드 영역에 pred(이전)와 succ(다음) 포인터를 저장해, 이중 연결 리스트 노드로 사용합니다.
- 헤더와 풋터에 남은 것은 암묵적 할당기와 동일하게 크기와 할당 비트를 저장하는 boundary tag 역할을 합니다.\
주요 동작 알고리즘
- 자유 리스트 초기화
- mem_init 또는 extend_heap 시 전체 힙을 하나의 자유 블록으로 만들고, 그 블록의 pred = NULL, succ = NULL 로 설정합니다.
- 할당 (malloc)
- 탐색: 헤드 포인터부터 succ 링크를 따라가며, 요청 크기(asize) 이상인 첫 자유 블록을 찾습니다.
- 분할(선택적): place(bp, asize)에서 분할이 일어나면, 분할된 뒷부분 새로운 자유 블록을 리스트에 새 노드로 남겨둡니다.
- 제거: 선택된 블록 bp를 자유 리스트에서 삭제(remove) 합니다. (pred→succ, succ→pred 링크 갱신)
- 해제 (free)
- 헤더·풋터 alloc=0 으로 표시 후, coalesce(bp)로 인접 블록 병합
- 병합된 블록 bp′ 를 자유 리스트의 헤드에 삽입(insert)하여 새 노드로 추가합니다.
성능 및 장단점
- 탐색 속도: 자유 블록만 순회 → 평균 블록 수 절반 이하로 줄어들고, O(n_free) 탐색
- 삭제/삽입 비용: O(1)
- 메타데이터 오버헤드: 각 자유 블록 페이로드 일부를 주소 포인터(8~16바이트)로 사용
- 외부 단편화 제어: coalesce로 즉시 병합, 분할 전략과 함께 단편화 관리
9.9.14 분리 가용 리스트 (Segregated Free Lists)
크기별로 여러 개의 리스트(“bins”)를 두어, 요청 크기에 가까운 리스트만 탐색하는 기법입니다.
- 예: 8B, 16B, 32B, 64B… 단위로 리스트를 구분하고, malloc(k)는 k 이상인 첫 리스트에서만 조회합니다.
- 리스트가 비어 있으면 상위 크기 리스트를 검색하거나, sbrk로 새 블록을 확보해 해당 리스트에 추가합니다.
- First-Fit이나 분할/병합 정책을 각 리스트별로 독립 적용해 탐색 시간이 크게 단축됩니다.
- GNU malloc(dlmalloc/ptmalloc)은 boundary-tag allocator이면서, segregated bins 방식을 사용합니다.
정리 : 암시적 자유 리스트 VS 명시적 자유 리스트 VS 분리 가용 리스트
| 구분 | 묵시적 가용 리스트 (Implicit Free List) |
명시적 가용 리스트 (Explicit Free List) |
분리 가용 리스트 (Segregated Free List) |
| 메타 데이터 위치 | 각 블록 헤더, 풋터에만 크기, 할당 비트 저장 | 자유 블록 페이로드에 pred/succ 포인터 + 헤더, 푸터 | 자유 블록 페이로드에 포인터 + 헤더, 푸터(크기별 리스트 헤드) |
| 탐색 방식 | 힙 전체 선형 탐색(First-Fit, Next-Fit, Best-Fit) | 자유 리스트만 순회(First-Fit 등) | 요청 크기 클래스 리스트 조회 후 탐색 |
| 탐색 시간 복잡도 | O(n) | O(n₍free₎) 탐색 비용이 자유 블록의 개수에 비례 |
O(1)~O(k) (k=size classes) |
| 삽입/삭제 비용 | free 시 colease 만 | O(1) (pred/succ 포인터 업데이트) | O(1) |
| 분할/병합 | 가능(split), coalesce by boundary tags | 가능(split), coalesce, 리스트에서 삽입/삭제 | 가능(split), coalesce, 리스트에 삽입 |
| 내부 단편화 | 보통(split 시 패딩) | 보통(split 시 패딩) | 보통(split 시 패딩) |
| 외부 단편화 | 높음(지속적 splinter) | 중간 (자유 블록 집중 관리) | 낮음(크기 분류로 큰 블록 유지) |
| 메타 데이터 오버헤드 | 작음(2워드) | 중간 (pred, succ 포함, +2워드) | 높음 (여러 리스트 헤드 + pred/succ) |
| 구현 난이도 | 쉬움 | 보통 | 어려움 |
| 실제 활용 예 | 간단한 임베디드 애플리케이션 | TLSF | ptmalloc2(glibc), Windows Low-Frag heap |
'CSAPP > 9장' 카테고리의 다른 글
| [CSAPP] 9장 가상 메모리(Virtual Memory) - 9.9(9.9.6 ~ 9.9.10) (0) | 2025.04.25 |
|---|---|
| [CSAPP] 9장 가상 메모리(Virtual Memory) - 9.9(9.9.1 ~ 9.9.5) (1) | 2025.04.25 |
| [CSAPP] 9장 가상 메모리(Virtual Memory) - 9.5 ~ 9.8 (5) | 2025.04.22 |
| [CSAPP] 9장 가상 메모리 (Virtual Memory) - 9.3 ~ 9.4 (0) | 2025.04.21 |
| [CSAPP] 9장 가상 메모리(Virtual Memory) - 9.1 ~ 9.2 (0) | 2025.04.21 |