Explicit Free List 기반 동적 할당기 구현하기 + 최적화하기
Implicit Free List를 넘어, Explicit Free List로의 개선
Implicit Free List 기반 동적 할당기 구현에 성공했다면, 이제 그 다음 단계로 Explicit Free List로의 개선을 시도해볼 수 있습니다.
두 방식의 가장 큰 차이는 '탐색하는 방식'이라고 할 수 있는데요. Implicit Free List에서는 블록의 할당 여부가 명시적으로 드러나 있지 않기 때문에, 힙 전체를 순차적으로 순회하면서 일일이 할당 상태를 확인해야 했습니다. 반면 Explicit Free List는 할당되지 않은 Free Block만 따로 관리합니다. 이중 연결 리스트를 사용해 Free Block들을 연결해 놓고, 필요한 블록을 찾을 때는 이 리스트만 빠르게 탐색하면 되죠. 덕분에 이미 할당된 블록을 건너뛸 수 있어 탐색 성능이 비약적으로 향상됩니다.
물론 이를 위해 Free Block마다 추가로 포인터 공간이 필요합니다. 하지만 기본적인 Implicit Free List 구현에서도 최소 Free Block 크기를 32바이트로 잡아 두었기 때문에, 이 안의 payload 공간을 활용해 prev, next 포인터를 저장할 수 있습니다. 추가적인 공간 소모 없이 Free List 관리 기능만 얹을 수 있다는 점이 큰 장점인 것이죠. 기본적인 메모리 할당과 해제 흐름은 Implicit 방식과 유사하지만, 할당 과정과 해제 과정에서 Free List 삽입과 삭제 작업이 추가로 들어간다는 점이 다릅니다. 이렇게 보면 Explicit Free List는 결국 Implicit Free List의 개선판이라고 할 수 있습니다.
이번 글에서는 Explicit Free List 기반 동적 할당기 구현하기를 목표로, 기존 implicit 구현에서 어떤 부분을 교체·개선해야 하는지, 그리고 explicit 방식에 새롭게 추가되는 요소들은 무엇인지 하나하나 살펴보겠습니다. 그리고 해당 글을 정리하기에 앞서 Explicit 할당기 구현에 도움을 준 강민혁 학우에게 깊은 감사를 표합니다.
Explicit Free List 기반 동적 할당기의 핵심 구현 정리
Implicit Free List 기반 동적 할당기에서 한 단계 더 나아가 Explicit Free List로 업그레이드를 시도한다면, 어떤 변화가 생길까요? 기존 implicit에서 기본 골격은 유지하면서도, 명확하게 개선되는 부분과 추가되는 기능들이 존재하는데요. 지금부터 이 변화를 간단히 정리해 보겠습니다.
추가된 매크로와 전역변수
Explicit Free List에서는 free block을 이중 연결 리스트로 관리하는데요. 기존 payload 공간에 이전 블록과 다음 블록의 주소를 저장하게 됩니다.
#define SUC(bp) (*(void **)((char *)(bp) + WSIZE)) // 다음 Free Block 주소
#define PRED(bp) (*(void **)(bp)) // 이전 Free Block 주소
static void *free_listp; // Free List의 시작 주소
mm_init 함수의 변화
Explicit Free List에서는 dummy free block을 초기화 과정에서 설정하여 복잡한 edge case를 간단히 처리합니다.
if ((heap_listp = mem_sbrk(8*WSIZE)) == (void *)-1) return -1;
PUT(heap_listp, 0);
PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1));
PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1));
// dummy free block 설정
PUT(heap_listp + (3*WSIZE), PACK(2*DSIZE, 0));
PUT(heap_listp + (4*WSIZE), NULL);
PUT(heap_listp + (5*WSIZE), NULL);
PUT(heap_listp + (6*WSIZE), PACK(2*DSIZE, 0));
PUT(heap_listp + (7*WSIZE), PACK(0, 1));
heap_listp += (4*WSIZE);
if (extend_heap(CHUNKSIZE/WSIZE) == NULL) return -1;
변경된 핵심 함수들
| 함수 | 주요 변경 사항 |
| coalesce | 병합 시 free list에서 블록을 제거한 후 병합 후 다시 추가 |
| find_fit | free list에서만 적합한 블록 탐색 |
| place | 할당 전 free list에서 해당 블록 제거, 분할 시 남는 블록 다시 추가 |
추가된 보조 함수들
insert_free_block
static void insert_free_block(void *bp) {
// 새 블록(bp)의 successor를 현재 free list의 첫 번째 블록(free_listp)으로 설정
SUC(bp) = free_listp;
// 새 블록(bp)의 predecessor를 NULL로 설정
// -> 새 블록이 이제 리스트의 맨 앞(head)이므로
PRED(bp) = NULL;
// 만약 기존에 free list에 블록들이 있었던 경우
if (free_listp != NULL)
// 기존 첫 번째 블록의 predecessor를 새 블록(bp)으로 설정
PRED(free_listp) = bp;
// free_listp를 새 블록(bp)으로 갱신
// -> 새 블록을 리스트의 첫 번째 블록으로 갱신
free_listp = bp;
}free list의 맨 앞에 블록을 삽입합니다.
remove_free_block
static void remove_free_block(void *bp) {
// bp 블록의 이전 블록(pred)
void *pred = PRED(bp);
// bp 블록의 다음 블록(succ)
void *succ = SUC(bp);
// bp 앞에 다른 블록(pred)이 있는 경우
if (pred != NULL)
// pred 블록의 successor를 bp의 successor로 연결
SUC(pred) = succ;
else
// bp가 free list의 맨 앞이라면 첫 블록 주소를 bp 블록의 다음 블록으로 변경
free_listp = succ;
// bp 뒤에 다른 블록(succ)이 있는 경우
if (succ != NULL)
// succ 블록의 predecessor를 bp의 predecessor로 연결
PRED(succ) = pred;
}free list에서 특정 블록을 제거합니다.
Explicit Free List의 이점
Explicit Free List로 전환하면 탐색 비용이 O(N)에서 O(Free Blocks)로 줄어들고, 기존 implicit 방식에서 크게 벗어나지 않고도 탐색 성능과 효율성이 눈에 띄게 향상시킬 수 있습니다. 또 최소 블록 크기를 4워드로 잡아놨기에, 최소 크기를 동일하게 유지하면서 도 추가적인 메모리 소모 없이 포인터가 포함된 free block을 간단히 구현할 수 있다는 점도 큰 장점이죠.
최종 구현 코드
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include <stddef.h>
#include "mm.h"
#include "memlib.h"
/*********************************************************
* Team information (과제 제출용)
********************************************************/
team_t team = {
"ateam",
"Harry Bovik",
"bovik@cs.cmu.edu",
"",
""
};
/*********************************************************
* 기본 상수와 매크로 정의
********************************************************/
#define ALIGNMENT 16 // 메모리 정렬 단위: 16바이트
// size를 ALIGNMENT 단위로 반올림 (올림)
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0xF)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
#define WSIZE 8 // Word 크기 (8바이트)
#define DSIZE 16 // Double Word 크기 (16바이트)
#define CHUNKSIZE (1 << 12) // 힙을 확장할 기본 크기 (4KB)
#define MAX(x, y) ((x) > (y) ? (x) : (y))
// header와 footer를 만들 때 (size + alloc 비트)를 합쳐 저장
#define PACK(size, alloc) ((size) | (alloc))
// 포인터 p가 가리키는 메모리 위치에서 값을 읽거나 쓴다
#define GET(p) (*(unsigned long *)(p))
#define PUT(p, val) (*(unsigned long *)(p) = (val))
// header/footer에서 size와 alloc 정보를 추출
#define GET_SIZE(p) (GET(p) & ~0x7) // 하위 3비트(alloc)를 제외한 size만 가져오기
#define GET_ALLOC(p) (GET(p) & 0x1) // 할당 여부만 가져오기
// 블록 포인터 bp로부터 header/footer 위치를 계산
#define HDRP(bp) ((char *)(bp) - WSIZE) // 현재 블록의 header 주소
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // 현재 블록의 footer 주소
// 다음 블록, 이전 블록 포인터 계산
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE((char *)(bp) - DSIZE))
// explicit free list에서의 포인터 접근 (succ: 다음, pred: 이전)
#define SUC(bp) (*(void **)((char *)(bp) + WSIZE))
#define PRED(bp) (*(void **)(bp))
/*********************************************************
* 전역 변수
********************************************************/
static void *heap_listp; // 항상 힙의 시작 부분을 가리키는 포인터
static void *free_listp = NULL; // free block들을 연결하는 리스트의 시작 포인터
/*********************************************************
* 내부 헬퍼 함수들 선언
********************************************************/
static void insert_free_block(void *bp);
static void remove_free_block(void *bp);
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);
/*********************************************************
* 헬퍼 함수 구현
********************************************************/
// 힙 확장: 새로운 메모리를 받아서 free block으로 만듦
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의 헤더
PUT(FTRP(bp), PACK(size, 0)); // 새 free block의 푸터
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // 새로운 에필로그 블록
return coalesce(bp); // 주변과 합칠 수 있으면 합치기
}
// 블록 연결(coalesce): 주위 블록과 병합
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) { // 앞뒤 다 사용 중이면 그냥 free list에 추가
insert_free_block(bp);
return bp;
}
else if (prev_alloc && !next_alloc) { // 뒤가 비어 있으면 합치기
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
remove_free_block(NEXT_BLKP(bp));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
}
else if (!prev_alloc && next_alloc) { // 앞이 비어 있으면 합치기
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
remove_free_block(PREV_BLKP(bp));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp); // 앞으로 포인터 이동
}
else { // 앞뒤 둘 다 비어 있으면 셋 다 합치기
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
remove_free_block(NEXT_BLKP(bp));
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
remove_free_block(PREV_BLKP(bp));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
}
insert_free_block(bp);
return bp;
}
// 첫 번째 맞는 블록 찾기 (first fit)
static void *find_fit(size_t asize) {
void *cur = free_listp;
while (cur != NULL) {
if (GET_SIZE(HDRP(cur)) >= asize) {
return cur;
}
cur = SUC(cur); // 다음 free block으로 이동
}
return NULL; // 못 찾으면 NULL
}
// 블록 배치(place): 필요한 크기만큼 쪼개고 나머지는 새 free block으로
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));
remove_free_block(bp);
bp = NEXT_BLKP(bp); // 나머지 조각 새 블록
PUT(HDRP(bp), PACK(csize - asize, 0));
PUT(FTRP(bp), PACK(csize - asize, 0));
insert_free_block(bp);
}
else { // 그냥 다 사용
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
remove_free_block(bp);
}
}
// free block을 explicit free list에 추가
static void insert_free_block(void *bp) {
// 새 블록(bp)의 successor를 현재 free list의 첫 번째 블록(free_listp)으로 설정
SUC(bp) = free_listp;
// 새 블록(bp)의 predecessor를 NULL로 설정
// -> 새 블록이 이제 리스트의 맨 앞(head)이므로
PRED(bp) = NULL;
// 만약 기존에 free list에 블록들이 있었던 경우
if (free_listp != NULL)
// 기존 첫 번째 블록의 predecessor를 새 블록(bp)으로 설정
PRED(free_listp) = bp;
// free_listp를 새 블록(bp)으로 갱신
// -> 새 블록을 리스트의 첫 번째 블록으로 갱신
free_listp = bp;
}
// free block을 explicit free list에서 제거
static void remove_free_block(void *bp) {
// bp 블록의 이전 블록(pred)
void *pred = PRED(bp);
// bp 블록의 다음 블록(succ)
void *succ = SUC(bp);
// bp 앞에 다른 블록(pred)이 있는 경우
if (pred != NULL)
// pred 블록의 successor를 bp의 successor로 연결
SUC(pred) = succ;
else
// bp가 free list의 맨 앞이라면 첫 블록 주소를 bp 블록의 다음 블록으로 변경
free_listp = succ;
// bp 뒤에 다른 블록(succ)이 있는 경우
if (succ != NULL)
// succ 블록의 predecessor를 bp의 predecessor로 연결
PRED(succ) = pred;
}
/*********************************************************
* 외부 인터페이스 함수들 (main 함수에서 호출)
********************************************************/
// 힙 초기화
int mm_init(void) {
if ((heap_listp = mem_sbrk(8*WSIZE)) == (void *)-1) {
return -1;
}
PUT(heap_listp, 0); // 패딩
PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1)); // 프로로그 헤더
PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1)); // 프로로그 푸터
PUT(heap_listp + (3*WSIZE), PACK(2*DSIZE, 0)); // dummy free block 헤더
PUT(heap_listp + (4*WSIZE), NULL); // dummy block pred
PUT(heap_listp + (5*WSIZE), NULL); // dummy block succ
PUT(heap_listp + (6*WSIZE), PACK(2*DSIZE, 0)); // dummy block 푸터
PUT(heap_listp + (7*WSIZE), PACK(0, 1)); // 에필로그 헤더
heap_listp += (4*WSIZE);
if (extend_heap(CHUNKSIZE/WSIZE) == NULL) {
return -1;
}
return 0;
}
// 메모리 할당
void *mm_malloc(size_t size) {
size_t asize;
size_t extendsize;
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;
}
// 메모리 해제
void mm_free(void *ptr) {
size_t size = GET_SIZE(HDRP(ptr));
PUT(HDRP(ptr), PACK(size, 0));
PUT(FTRP(ptr), PACK(size, 0));
coalesce(ptr);
}
// 메모리 크기 재조정
void *mm_realloc(void *ptr, size_t size) {
if (ptr == NULL)
return mm_malloc(size);
if (size == 0) {
mm_free(ptr);
return NULL;
}
size_t old_block = GET_SIZE(HDRP(ptr));
size_t old_payload = old_block - WSIZE;
size_t new_asize;
if (size <= DSIZE) {
new_asize = 2 * DSIZE;
} else {
new_asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);
}
// 1. in-place 축소
if (new_asize <= old_block) {
if (old_block - new_asize >= 2 * DSIZE) {
PUT(HDRP(ptr), PACK(new_asize, 1));
PUT(FTRP(ptr), PACK(new_asize, 1));
void *nbp = NEXT_BLKP(ptr);
size_t remain = old_block - new_asize;
PUT(HDRP(nbp), PACK(remain, 0));
PUT(FTRP(nbp), PACK(remain, 0));
insert_free_block(nbp);
}
return ptr;
}
// 2. in-place 확장
if (!GET_ALLOC(HDRP(NEXT_BLKP(ptr)))) {
size_t nsize = old_block + GET_SIZE(HDRP(NEXT_BLKP(ptr)));
if (nsize >= new_asize) {
remove_free_block(NEXT_BLKP(ptr));
PUT(HDRP(ptr), PACK(nsize, 1));
PUT(FTRP(ptr), PACK(nsize, 1));
return ptr;
}
}
// 3. 새로 malloc -> 데이터 복사
void *new_ptr = mm_malloc(size);
if (new_ptr == NULL)
return NULL;
size_t copy = (old_payload < size) ? old_payload : size;
memcpy(new_ptr, ptr, copy);
mm_free(ptr);
return new_ptr;
}
Explicit 할당기 최적화하기
explicit 할당기를 구현한 이후, 다양한 최적화를 시도해 보았지만 대부분은 효과가 미미하거나 오히려 점수를 떨어뜨리는 결과를 낳았습니다. 그러나 단 하나의 최적화는 눈에 띄는 성능 향상을 가져왔는데요. 그 내용에 대해 공유해 드리고자 합니다.
Find_fit을 first fit에서 best fit으로 전환하기
초기에는 implicit 할당기에서 넘어오며 기존의 메모리 할당 정책인 first-fit을 그대로 사용했습니다. 이 방식은 탐색 시간이 빠르다는 장점이 있지만, 내부 단편화가 증가해 util 점수가 낮게 나오는 문제가 있었습니다. 이에 따라 best-fit 방식으로 전환을 시도하게 되었고, best-fit은 요청된 크기에 가장 잘 맞는 free block을 선택함으로써 내부 단편화를 최소화할 수 있었습니다.
물론 탐색 시간이 다소 증가하게 되지만, explicit 할당기는 free list의 구조가 단순하고 순회 비용도 크지 않기 때문에 throughput 손실은 제한적인 수준에 그쳤는데요. 그 결과, util 점수가 눈에 띄게 향상되며 전체 성능이 개선되는 효과를 얻을 수 있었습니다.
best fit으로 전환된 find_fit 함수 구현 코드
// best-fit 방식으로 free list에서 할당 가능한 블록을 찾는 함수
static void *find_fit(size_t asize) {
void *cur = free_listp; // free list의 첫 블록부터 탐색 시작
void *best = NULL; // 현재까지 찾은 가장 잘 맞는 블록
size_t min_diff = (size_t)-1; // 최소 크기 차이 (unsigned int 기준 가장 큰 값 -1)
// 모든 free list 순회
while (cur != NULL) {
size_t cur_size = GET_SIZE(HDRP(cur)); // 현재 블록의 전체 크기 가져오기
// 현재 블록이 요청 크기 이상이면 고려 대상
if (cur_size >= asize) {
size_t diff = cur_size - asize; // 크기 차이 계산
// 지금까지 본 블록보다 더 잘 맞으면 갱신
if (diff < min_diff) {
best = cur; // 더 나은 후보로 저장
min_diff = diff;
// 크기가 딱 맞으면 더 이상 탐색할 필요 없음
if (diff == 0) {
break;
}
}
}
// 다음 free block으로 이동
cur = SUC(cur);
}
// 가장 적절했던 블록을 반환 (없으면 NULL)
return best;
}
'크래프톤 정글 > Code 정글(C언어)' 카테고리의 다른 글
| [WebProxy] VSCode에서 빨간 줄이 뜨는 현상 해결하기 (0) | 2025.05.02 |
|---|---|
| [Malloc] (참고용) Segregated Free List 기반 동적 할당기 구현하기 (0) | 2025.04.28 |
| [Malloc] Implicit Free List 기반 동적 할당기 구현하기 (0) | 2025.04.26 |
| [RBTree] set 기반 RBTree를 multiset 기반으로 전환하기 (0) | 2025.04.24 |
| [RBTree] 삭제 구현하기 (erase_fixup, rbtree_erase) (0) | 2025.04.21 |