Segregated Free List 기반 동적 할당기 구현하기
💡 주의사항
이 글에서는 배열을 이용한 Segregated Free List 방식의 동적 할당기 구현을 다루고 있습니다.하지만 malloc_lab 과제에서는 배열 사용이 금지되어 있으므로, 이 내용은 참고용으로만 활용해 주세요. 배열 제한이 있는 환경에서는, Explicit Free List 기반 할당기를 최적화하는 편이 더 적합하다고 알려져 있습니다.
지난 글에서는 Explicit Free List 기반으로 동적 메모리 할당기를 구현해봤는데요. 이번에는 한 걸음 더 나아가, Segregated Free List 방식을 적용해 성능을 최적화해봅니다.
Segregated Free List란?
- 여러 개의 free list를 생성해
- 블록 크기별로 따로따로 관리하고
- 할당 요청 시, 적당한 크기 리스트만 빠르게 탐색하는 방식입니다.
이를 통해 특히 큰 규모의 테스트나 프로그램에서 할당 속도를 대폭 향상시킬 수 있습니다.
Segregated Free List 기본 개념 요약
| 항목 | Explicit Free List | Segregated Free List |
| 리스트 개수 | 1개 | 여러 개 (20개 정도) |
| 블록 검색 | 전체 free block 순회 | 적당한 크기의 리스트만 순회 |
| 삽입 | 한 리스트에 삽입 | 크기에 맞는 리스트에 삽입 |
| 코드 구조 | 비교적 단순 | 리스트 관리 복잡 |
| 성능 | 준수 | 매우 빠름 (특히 대형 테스트에서) |
Segregated Free List 구현
새롭게 추가된 핵심 구조
segregated_free_lists 배열 추가
#define LISTLIMIT 20
void *segregated_free_lists[LISTLIMIT];LISTLIMIT 크기만큼 free list 배열을 만들고, 블록 크기 그룹별로 따로 관리합니다.
신규 함수: 크기에 맞는 리스트 인덱스 계산(get_list_index)
static int get_list_index(size_t size) {
int idx = 0; // 시작 인덱스는 0 (가장 작은 크기의 리스트부터 시작)
size_t temp = size; // 입력받은 블록 크기를 temp에 복사해 사용
// 블록 크기(temp)가 1보다 크고, 리스트 인덱스가 LISTLIMIT - 1보다 작을 때까지 반복
while (idx < LISTLIMIT - 1 && temp > 1) {
temp >>= 1; // 블록 크기를 오른쪽으로 1비트 시프트 (2로 나누는 것과 동일)
idx++; // 인덱스 1 증가
}
// 최종적으로 결정된 인덱스를 반환
return idx;
}블록 크기를 반씩 줄여가며 알맞은 free list 인덱스를 결정합니다. 이때 큰 블록일수록 큰 인덱스로 매핑됩니다.
기존 함수 변경 사항
Free Block 삽입(insert_free_block): 크기에 맞는 리스트에 추가
static void insert_free_block(void *bp) {
size_t size = GET_SIZE(HDRP(bp)); // 현재 블록(bp)의 크기를 가져옴
int idx = get_list_index(size); // 블록 크기에 맞는 리스트 인덱스를 구함
void *headPtr = segregated_free_lists[idx]; // 해당 인덱스 리스트의 현재 첫 번째 블록을 가져옴
// 새 블록(bp)의 후임 포인터(SUC)는 기존 리스트의 맨 앞 블록을 가리킴
SUC(bp) = headPtr;
// 새 블록(bp)의 선임 포인터(PRED)는 NULL (리스트의 첫 번째가 되기 때문)
PRED(bp) = NULL;
// 만약 기존에 리스트에 블록(headPtr)이 있었다면
if (headPtr) {
// 기존 리스트 첫 블록의 PRED를 새 블록(bp)으로 변경
PRED(headPtr) = bp;
}
// 해당 리스트의 맨 앞(headPtr 자리에)을 새 블록(bp)으로 변경
segregated_free_lists[idx] = bp;
}이제 free list가 여러 개가 되었기 때문에, free block을 크기에 맞는 리스트의 head에 삽입합니다. 몇 번째 free list인지만 구하면, 마찬가지로 O(1) 시간 복잡도로 빠르게 삽입할 수 있습니다.
Free Block 제거(remove_free_block): 크기에 맞는 리스트에서 제거
static void remove_free_block(void *bp) {
void *pred = PRED(bp); // bp의 바로 앞 블록 (선임 블록)
void *succ = SUC(bp); // bp의 바로 다음 블록 (후임 블록)
// 선임 블록이 존재하는 경우
if (pred) {
// 선임 블록의 SUC를 현재 블록의 SUC로 변경 (bp를 건너뜀)
SUC(pred) = succ;
}
// 선임 블록이 없는 경우 (즉, bp가 리스트의 맨 앞에 있는 경우)
else {
size_t size = GET_SIZE(HDRP(bp)); // 현재 블록(bp)의 크기를 가져옴
int idx = get_list_index(size); // 블록 크기에 맞는 리스트 인덱스를 구함
segregated_free_lists[idx] = succ; // 리스트의 시작 포인터를 bp의 다음 블록(succ)으로 변경
}
// 후임 블록이 존재하는 경우
if (succ) {
// 후임 블록의 PRED를 현재 블록의 PRED로 변경 (bp를 건너뜀)
PRED(succ) = pred;
}
}마찬가지로 head 블록을 제거하는 경우, 크기에 맞는 리스트로부터 해당 블록을 삭제하고 후임 블록으로 head를 변경해 줍니다.
힙 초기화(mm_init): segregated_free_lists 초기화 추가
int mm_init(void)
{
// 각 free list 주소를 NULL로 초기화
for (int i = 0; i < LISTLIMIT; i++) {
segregated_free_lists[i] = NULL;
}
...
}초기에 segregated_free_lists 배열의 모든 요소를 NULL로 초기화합니다. 이를 수행하지 않으면, 각 리스트 포인터가 초기 쓰레기값(garbage value)을 갖게 되어, mdriver 실행 중 잘못된 포인터를 참조하거나 따라가면서 segmentation fault가 발생할 수 있습니다. 따라서 이 초기화는 프로그램의 안정성을 보장하는 데 있어 매우 중요한 단계입니다.
맞는 블록 찾기(find_fit): 리스트별 탐색으로 수정
static void *find_fit(size_t asize)
{
int idx = get_list_index(asize); // 요청한 크기에 맞는 시작 인덱스 구하기
// 크기가 asize 이상인 블록을 찾을 때까지 리스트를 탐색
for (int i = idx; i < LISTLIMIT; i++) {
void *bp = segregated_free_lists[i]; // 현재 인덱스(i)의 리스트에서 첫 번째 블록 가져오기
// 현재 리스트에 있는 블록들을 순회
while (bp != NULL) {
// 만약 현재 블록(bp)의 크기가 요청한 크기(asize) 이상이면
if (GET_SIZE(HDRP(bp)) >= asize) {
return bp; // 이 블록을 사용하기 위해 반환
}
bp = SUC(bp); // 그렇지 않으면 다음 블록으로 이동
}
}
// 모든 리스트를 다 뒤졌지만, 적합한 블록을 못 찾은 경우
return NULL;
}기존에는 하나의 free list 전체를 순회했지만, 이제는 적절한 리스트로부터 찾아 올라가면서 탐색합니다.
주위 블록과 병합(coalesce): 병합 후 리스트 이동 필요 (코드 수정 X)
static void *coalesce(void *bp) {
...
insert_free_block(bp);
return bp;
}사실 이 함수 자체는 변경 사항이 없지만, 동작 흐름이 병합 후 새 크기에 맞는 리스트로 이동하는 것으로 변경되었기 때문에 간략하게 명시했습니다. 이러한 처리 자체는 하위 함수인 insert_free_block이 담당하게 됩니다.
블록 배치(place): 삽입/제거 과정을 명확히 하도록 변경
static void place(void *bp, size_t asize) {
size_t csize = GET_SIZE(HDRP(bp));
remove_free_block(bp);
if (csize - asize >= 2 * DSIZE) {
...
insert_free_block(bp);
} else {
...
}
}이 함수는 여러 free list를 관리하는 과정에서 발생할 수 있는 버그를 방지하기 위해, 블록 할당 전에 먼저 free list에서 할당할 블록을 제거하도록 변경되었습니다. 이후 블록을 나누어 남은 블록이 있을 경우, 이를 새로운 크기에 맞게 다시 삽입하는 방식으로 동작합니다.
전체 코드
/******************************************************************************
* Segregated Free List 기반 malloc 패키지
*
* 1) 크기 구간(size class)별로 free list를 여러 개(여기선 20개) 둠
* 2) free block은 자신에게 맞는 리스트에 삽입·삭제 (O(1) 시간)
* 3) 할당 시에는 적절한 크기 리스트부터 탐색 → 큰 테스트에서 효율 ↑
*
* ────────────────────────────────────────────────────────────────────────────
* 코드 흐름 요약
* • mm_init : 힙 초기화 + free list 배열 NULL 세팅
* • mm_malloc : get_list_index → find_fit → place
* • mm_free : 블록 해제 → coalesce → insert_free_block
* • mm_realloc : in-place 축소/확장 시도 → 안 되면 새로 할당
* • 내부 헬퍼 함수 : extend_heap, coalesce, get_list_index, insert_/remove_
*****************************************************************************/
#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_t team = {
"ateam",
"Harry Bovik",
"bovik@cs.cmu.edu",
"",
""
};
/*──────────────────── 상수 · 매크로 정의 ───────────────────*/
/* 16바이트 정렬(64비트 환경 기준) */
#define ALIGNMENT 16
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0xF) // 0xF = 15
/* 워드(8B)·더블워드(16B)·기본 확장 단위 */
#define WSIZE 8
#define DSIZE 16
#define CHUNKSIZE (1 << 12) // 4KB: 초기 힙 확장량
/* 헤더·푸터 구성: 하위 3bit는 할당 비트, 나머지는 크기 */
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define PACK(size, alloc) ((size) | (alloc)) // 헤더/푸터 값 만들기
#define GET(p) (*(unsigned long *)(p)) // 8B 읽어오기
#define PUT(p, val) (*(unsigned long *)(p) = (val))
#define GET_SIZE(p) (GET(p) & ~0x7) // 하위 3bit 제거 → size
#define GET_ALLOC(p) (GET(p) & 0x1) // 할당 여부 (1: alloc, 0: free)
/* 블록 내 주요 포인터 계산 */
#define HDRP(bp) ((char *)(bp) - WSIZE) // 헤더 주소
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // 푸터 주소
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp)-WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp)-DSIZE)))
/* Explicit list용 포인터(PRED/SUC) 위치
* [헤더][pred][succ]···[푸터] ← free block 구조
* pred : 바로 앞 free block, succ : 바로 뒤 free block
*/
#define SUC(bp) (*(void **)((char *)(bp) + WSIZE)) // succ = bp+8
#define PRED(bp) (*(void **)(bp)) // pred = bp
/* Segregated list 개수 (size class 20개 ≒ 최대 2^19 배수까지 관리) */
#define LISTLIMIT 20
/*──────────────────── 전역 변수 ───────────────────*/
static void *heap_listp; // 힙 시작점(프롤로그 이후)
static void *segregated_free_lists[LISTLIMIT]; // size class 헤드 포인터 배열
/*──────────────────── 내부 함수 프로토타입 ───────────────────*/
static int get_list_index(size_t size);
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);
/*──────────────────── 힙 확장 (mem_sbrk) ───────────────────*/
static void *extend_heap(size_t words)
{
/* words(8B 단위)를 2배수로 맞춰 16B 정렬 유지 */
size_t size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
char *bp = mem_sbrk(size); // 힙 영역 요청
if ((long)bp == -1) return NULL;
/* 새 free block 헤더/푸터 & 새로운 에필로그 헤더 세팅 */
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // 에필로그
/* 병합 후 free list에 넣기 */
return coalesce(bp);
}
/*──────────────────── 인접 free 블록 병합 ───────────────────*/
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));
/* Case 1: 양옆 모두 할당 → 그냥 삽입만 */
if (prev_alloc && next_alloc) {
insert_free_block(bp);
return bp;
}
/* Case 2: 뒤가 free → 뒤 블록을 떼서 size 합치기 */
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));
}
/* Case 3: 앞이 free → 앞 블록과 병합 (포인터 bp 갱신) */
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);
}
/* Case 4: 앞·뒤 모두 free → 세 블록을 하나로 */
else {
size += GET_SIZE(HDRP(PREV_BLKP(bp))) +
GET_SIZE(HDRP(NEXT_BLKP(bp)));
remove_free_block(PREV_BLKP(bp));
remove_free_block(NEXT_BLKP(bp));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
}
insert_free_block(bp);
return bp;
}
/*──────────────────── 첫 번째 맞춤(find-first) 탐색 ───────────────────*/
static void *find_fit(size_t asize)
{
int idx = get_list_index(asize); // 시작할 size class 계산
/* 현재 인덱스부터 큰 쪽으로 차례로 스캔 */
for (int i = idx; i < LISTLIMIT; i++) {
void *bp = segregated_free_lists[i]; // 해당 리스트의 head
while (bp != NULL) {
if (GET_SIZE(HDRP(bp)) >= asize) // 충분히 크면 반환
return bp;
bp = SUC(bp); // 리스트 순회
}
}
return NULL; // 못 찾으면 NULL
}
/*──────────────────── 블록 배치(place) ───────────────────*/
static void place(void *bp, size_t asize)
{
size_t csize = GET_SIZE(HDRP(bp)); // 현재 free block 크기
remove_free_block(bp); // 리스트에서 빼기
/* split 조건: 남는 공간이 최소 블록 크기(16B*2) 이상 */
if (csize - asize >= 2 * DSIZE) {
/* 앞쪽을 할당, 뒤쪽을 새 free block으로 분할 */
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));
insert_free_block(bp); // 새 free block 삽입
} else {
/* 통째로 사용 */
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}
/*──────────────────── 패키지 초기화(mm_init) ───────────────────*/
int mm_init(void)
{
/* 1) segregated list 헤드 포인터 0으로 초기화 */
for (int i = 0; i < LISTLIMIT; i++)
segregated_free_lists[i] = NULL;
/* 2) 프롤로그(가드) 블록 만들기 (heap_listp ← 페이로드 주소) */
if ((heap_listp = mem_sbrk(4 * 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(0, 1)); // 에필로그 헤더
heap_listp += (2*WSIZE);
/* 3) 최초 CHUNKSIZE만큼 힙 확장 → free list 등록 */
if (extend_heap(CHUNKSIZE / WSIZE) == NULL) return -1;
return 0;
}
/*──────────────────── 블록 할당(mm_malloc) ───────────────────*/
void *mm_malloc(size_t size)
{
if (size == 0) return NULL; // 0B 요청 무시
/* 사용자가 요청한 사이즈 → 실제 필요한 크기(asize) 계산
* 헤더+푸터 16B 포함, 16B 정렬 유지
*/
size_t asize = (size <= DSIZE) ?
2 * DSIZE :
DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);
/* 1) free list에서 맞는 블록 찾기 */
char *bp = find_fit(asize);
if (bp != NULL) {
place(bp, asize);
return bp;
}
/* 2) 없다면 힙 확장 후 배치 */
size_t extendsize = MAX(asize, CHUNKSIZE);
bp = extend_heap(extendsize / WSIZE);
if (bp == NULL) return NULL;
place(bp, asize);
return bp;
}
/*──────────────────── 블록 해제(mm_free) ───────────────────*/
void mm_free(void *ptr)
{
size_t size = GET_SIZE(HDRP(ptr));
/* 헤더/푸터만 free로 표시 후 coalesce */
PUT(HDRP(ptr), PACK(size, 0));
PUT(FTRP(ptr), PACK(size, 0));
coalesce(ptr);
}
/*──────────────────── 블록 재할당(mm_realloc) ───────────────────*/
void *mm_realloc(void *ptr, size_t size)
{
if (ptr == NULL) return mm_malloc(size); // realloc(NULL) = malloc
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 = (size <= DSIZE) ?
2 * DSIZE :
DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);
/* Case 1: 축소 → 내부 분할 */
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;
}
/* Case 2: 뒤 블록이 free라면 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;
}
}
/* Case 3: 새 영역 할당 → 데이터 복사 → 기존 free */
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;
}
/*──────────────────── free list 삽입 (O(1)) ───────────────────*/
static void insert_free_block(void *bp)
{
size_t size = GET_SIZE(HDRP(bp));
int idx = get_list_index(size);
void *head = segregated_free_lists[idx]; // 현재 리스트 헤드
/* 새 블록을 head 앞으로 삽입 (LIFO 방식) */
SUC(bp) = head;
PRED(bp) = NULL;
if (head) PRED(head) = bp;
segregated_free_lists[idx] = bp;
}
/*──────────────────── free list 삭제 (O(1)) ───────────────────*/
static void remove_free_block(void *bp)
{
size_t size = GET_SIZE(HDRP(bp));
int idx = get_list_index(size);
void *pred = PRED(bp);
void *succ = SUC(bp);
if (pred) SUC(pred) = succ; // 중간 or 끝 노드
else segregated_free_lists[idx] = succ; // head 노드였음
if (succ) PRED(succ) = pred;
}
/*──────────────────── size → 리스트 인덱스 매핑 ───────────────────
* 크기를 2로 나누며(log2) 몇 번째 구간인지 계산
* 0: <= 2^0 (=1워드) … 사실상 16~31B
* 1: <= 2^1 (=2워드) … 32~63B
* 2: <= 2^2 (=4워드) … 64~127B
* ...
* 19: <= 2^19 … 1MB 이상
*/
static int get_list_index(size_t size)
{
int idx = 0;
size_t temp = size;
while (idx < LISTLIMIT - 1 && temp > 1) {
temp >>= 1; // size /= 2
idx++;
}
return idx;
}
Segregated Free List 흐름 요약
| 단계 | 설명 |
| malloc(size) | 크기에 맞는 리스트 탐색 → 블록 찾기/할당 |
| free(ptr) | 블록 해제 → 병합 → 크기에 맞는 리스트 삽입 |
| realloc(ptr, size) | in-place 확장 시 neighbor free block 연결 시도 |
마치면서
이번에 구현한 Segregated Free List 기반 할당기에서는 할당 속도를 획기적으로 향상시켰을 뿐만 아니라 free block 탐색 비용을 최소화하고, 블록 관리 효율성도 높여 보았습니다. 다만, 리스트 수가 너무 적으면 효과가 줄고, 너무 많으면 관리 복잡성이 증가하기 때문에 적절한 리스트 수를 선정해야 하는데요. 보통 20개 정도를 기준으로 삼으면 가장 무난합니다.
'크래프톤 정글 > Code 정글(C언어)' 카테고리의 다른 글
| [WebProxy] echo 서버 구현 실습 및 코드 해석하기 (0) | 2025.05.02 |
|---|---|
| [WebProxy] VSCode에서 빨간 줄이 뜨는 현상 해결하기 (0) | 2025.05.02 |
| [Malloc] Explicit Free List 기반 동적 할당기 구현하기 + 최적화하기 (0) | 2025.04.27 |
| [Malloc] Implicit Free List 기반 동적 할당기 구현하기 (0) | 2025.04.26 |
| [RBTree] set 기반 RBTree를 multiset 기반으로 전환하기 (0) | 2025.04.24 |