컴퓨터 시스템 : CSAPP 9장 정리 - 9.9.14 분리 가용 리스트

9.9.14 분리 가용 리스트 (Segregated Free Lists)

명시적 가용 시트 문제점 :

단일 연결 리스트로 모든 가용 블록을 관리하면, 원하는 크기의 블록을 찾기 위해 모든 블록을 선형 탐색해야 해서 시간이 오래 걸린다.

해결책:

"분리 저장소 (Segregated Storage)"라는 기법을 사용하여, 크기별로 여러 개의 가용 리스트를 유지한다. 즉, 비슷한 크기의 블록들끼리 따로 모아서 관리하는 것이다.

---

기본 아이디어

• 가능한 블록 크기 전체를 여러 '크기 클래스(size class)'로 나누어 분류한다.
• 예를 들면:
  • {1}, {2}, {3, 4}, {5–8}, ..., {1025–2048}, {2049–4096}, {4097–∞}
• 작은 블록은 세밀하게 구분하고, 큰 블록은 대략적인 크기별로 묶을 수도 있다.
• 각 크기 클래스별로 하나의 가용 리스트를 유지한다.

---

동작 방식

1. 할당할 때:
   • 필요한 크기의 블록을 저장한 리스트부터 검색한다.
   • 찾지 못하면 그보다 큰 크기 클래스의 리스트를 검색한다.
2. 반환할 때:
   • 블록을 해제하면, 주변 블록들과 병합(coalescing)할 수 있고,
   • 병합 결과 블록을 적절한 크기 클래스의 리스트에 다시 추가한다.

---

두 가지 주요 방법

1. Simple Segregated Storage (간단한 분리 저장소)
   • 각 크기 클래스는 고정 크기의 블록들만 가진다.
   • 블록을 나누거나 병합(coalescing)하지 않는다.
   • 장점: 매우 빠른 할당/반환 (상수 시간).
   • 단점: 내부 및 외부 단편화(fragmentation) 발생 가능.
2. Segregated Fits (분리 적합)
   • 각 크기 클래스 안에 다양한 크기의 블록이 존재할 수 있다.
   • 요청에 맞는 블록을 first-fit 방식으로 리스트 내에서 찾아서 할당한다.
   • 필요시 블록을 분할(splitting)할 수도 있다.
   • 장점: 할당 속도 빠름 + 메모리 활용률 좋음.
   • 실제로 GNU malloc처럼 많은 프로덕션 할당기들이 이 방식을 사용한다.

---

분리 가용 리스트 구현 

기존 구현했던 명시적 가용 리스트에서 구현했던 코드를 기반으로 다수의 가용 리스트를 관리하기 위한 방법을 중점으로 설명하겠다.

가용 리스트 관리 방법의 차이

항목	명시적 가용 리스트	분리 가용 리스트
가용 리스트 개수	1개 (free_listp)	여러 개 (16개, GET_ROOT(class))
삽입/삭제 위치	항상 하나의 리스트	크기에 따라 다른 리스트에 삽입

/* 분리 가용 리스트 */
#define SEGREGATED_SIZE 16

/* 분리 가용 리스트의 루트*/
#define GET_ROOT(class) (*(void **)((char *)(heap_listp) + (WSIZE * class)))

---

1. mm_init 변경

항목	명시적	분리
힙 크기	8워드	(SEGREGATED_SIZE + 4) 워드
구조	padding + prologue + free list + epilogue	padding + prologue + 루트 포인터 배열 + epilogue

• 명시적 가용 리스트:
  • free_listp만 초기화
  • 8워드(패딩 + 프롤로그 + 에필로그 + 초기 free block)만 사용
• 분리 가용 리스트:
  • (SEGREGATED_SIZE + 4) * WSIZE 크기로 메모리 요청
  • 크기 클래스별 루트 포인터들을 초기화 (for 루프 사용)
  • heap_listp는 루트 배열 이후 위치로 설정

명시적 가용 리스트 예시

free_listp = mem_sbrk(8 * WSIZE);

분리 가용 리스트 예시

heap_listp = mem_sbrk((SEGREGATED_SIZE + 4) * WSIZE);

// 루트 포인터들 NULL로 초기화
for (int i = 0; i < SEGREGATED_SIZE; i++) 
    PUT(heap_listp + ((2 + i) * WSIZE), NULL);

heap_listp += (2 * WSIZE); // 루트 포인터 이후로 heap_listp 이동

---

2. add_free_block 변경

• 명시적 가용 리스트:
  • 항상 free_listp 앞에 블록을 삽입
• 분리 가용 리스트:
  • 블록 크기에 맞는 클래스를 get_class(size)로 계산
  • 해당 클래스의 루트에 삽입
  • 루트 포인터 업데이트

명시적 가용 리스트 예시

GET_SUCC(bp) = free_listp;
if (free_listp != NULL)
    GET_PRED(free_listp) = bp;
free_listp = bp;

분리 가용 리스트 예시

int class = get_class(GET_SIZE(HDRP(bp)));
GET_SUCC(bp) = GET_ROOT(class);
if (GET_ROOT(class) != NULL)
    GET_PRED(GET_ROOT(class)) = bp;
GET_ROOT(class) = bp;

변경 요약:
단일 free_listp 대신, 크기별 클래스(GET_ROOT(class))에 삽입한다.

---

3. splice_free_block 변경

• 명시적 가용 리스트:
  • free_listp 기준으로 제거
  • 단일 리스트에서 앞/뒤 블록 연결
• 분리 가용 리스트:
  • 블록의 크기에 맞는 클래스를 get_class(size)로 계산
  • 해당 클래스의 루트 포인터 수정
  • 앞/뒤 블록 연결은 동일하지만 루트 갱신 주의 필요

명시적 가용 리스트 예시

if (bp == free_listp) {
    free_listp = GET_SUCC(free_listp);
    return;
}
GET_SUCC(GET_PRED(bp)) = GET_SUCC(bp);
if (GET_SUCC(bp) != NULL)
    GET_PRED(GET_SUCC(bp)) = GET_PRED(bp);

분리 가용 리스트

int class = get_class(GET_SIZE(HDRP(bp)));
if (bp == GET_ROOT(class)) {
    GET_ROOT(class) = GET_SUCC(GET_ROOT(class));
    return;
}
GET_SUCC(GET_PRED(bp)) = GET_SUCC(bp);
if (GET_SUCC(bp) != NULL)
    GET_PRED(GET_SUCC(bp)) = GET_PRED(bp);

변경 요약:
루트 포인터(free_listp) 대신 GET_ROOT(class)를 기준으로 업데이트한다.

---

4. find_fit 변경

• 명시적 가용 리스트:
  • free_listp부터 선형 탐색
• 분리 가용 리스트:
  • 요청 크기에 맞는 클래스를 get_class(size)로 찾음
  • 해당 클래스에서 탐색
  • 없으면 다음 큰 클래스 순서로 넘어가면서 탐색

명시적 가용 리스트

void *bp = free_listp;
while (bp != NULL) {
    if (asize <= GET_SIZE(HDRP(bp)))
        return bp;
    bp = GET_SUCC(bp);
}
return NULL;

분리 가용 리스트

int class = get_class(asize);
void *bp;

while (class < SEGREGATED_SIZE) {
    bp = GET_ROOT(class);
    while (bp != NULL) {
        if (asize <= GET_SIZE(HDRP(bp)))
            return bp;
        bp = GET_SUCC(bp);
    }
    class++;
}
return NULL;

변경 요약:
하나의 리스트를 탐색하는 대신, 클래스별로 작은 것부터 차례차례 탐색한다.

---

5. get_class 추가 (새 함수)

• 요청된 블록 크기에 따라 클래스를 결정
• 16바이트부터 시작하여 2배씩 증가하는 크기 배열을 사용

static int get_class(size_t size) {
    if (size < 16)
        return 0;

    size_t class_sizes[SEGREGATED_SIZE];
    class_sizes[0] = 16;
    for (int i = 0; i < SEGREGATED_SIZE; i++) {
        if (i != 0)
            class_sizes[i] = class_sizes[i-1] << 1;
        if (size <= class_sizes[i])
            return i;
    }
    return SEGREGATED_SIZE-1;
}

---

전체 코드

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

#include "mm.h"
#include "memlib.h"

team_t team = {
    "team 1",
    "Jaewoong Ko",
    "jaewoong.ko0504@gmail.com",
    "",
    ""};

#define ALIGNMENT 8

#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)

/* 기본 상수 & 매크로 */
#define WSIZE 8             // word size
#define DSIZE 16             // double word size
#define CHUNKSIZE (1 << 12) // 힙 확장을 위한 기본 크기 (= 초기 빈 블록의 크기)

/* 가용 리스트를 접근/순회하는 데 사용할 매크로 */
#define MAX(x, y) (x > y ? x : y)
#define PACK(size, alloc) (size | alloc)                              // size와 할당 비트를 결합, header와 footer에 저장할 값
#define GET(p) (*(unsigned long *)(p))                                 // p가 참조하는 워드 반환 (포인터라서 직접 역참조 불가능 -> 타입 캐스팅)
#define PUT(p, val) (*(unsigned long *)(p) = (unsigned long)(val))      // p에 val 저장
#define GET_SIZE(p) (GET(p) & ~0x7)                                   // 사이즈 (~0x7: ...11111000, '&' 연산으로 뒤에 세자리 없어짐)
#define GET_ALLOC(p) (GET(p) & 0x1)                                   // 할당 상태
#define HDRP(bp) ((char *)(bp)-WSIZE)                                 // Header 포인터
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)          // Footer 포인터 (🚨Header의 정보를 참조해서 가져오기 때문에, Header의 정보를 변경했다면 변경된 위치의 Footer가 반환됨에 유의)
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp)-WSIZE))) // 다음 블록의 포인터
#define PREV_BLKP(bp) ((char *)(bp)-GET_SIZE(((char *)(bp)-DSIZE)))   // 이전 블록의 포인터

#define GET_SUCC(bp) (*(void **)((char *)(bp) + WSIZE)) // 다음 가용 블록의 주소
#define GET_PRED(bp) (*(void **)(bp))                   // 이전 가용 블록의 주소

/* 분리 가용 리스트 */
#define SEGREGATED_SIZE 16

/* 분리 가용 리스트의 루트*/
#define GET_ROOT(class) (*(void **)((char *)(heap_listp) + (WSIZE * class)))

static char *heap_listp; // 가용 리스트의 맨 앞 블록의 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);
static int get_class(size_t size);
static void splice_free_block(void *bp); // 가용 리스트에서 제거
static void add_free_block(void *bp);    // 가용 리스트에 추가

int mm_init(void)
{
    // 초기 힙 생성
    if ((heap_listp = mem_sbrk((SEGREGATED_SIZE + 4) * WSIZE)) == (void *)-1) // 8워드 크기의 힙 생성, free_listp에 힙의 시작 주소값 할당(가용 블록만 추적)
        return -1;
    PUT(heap_listp, 0);                    
    PUT(heap_listp + (1 * WSIZE), PACK((SEGREGATED_SIZE + 2) * WSIZE, 1));

    for (int i = 0; i < SEGREGATED_SIZE; i++)
        PUT(heap_listp + ((2 + i) * WSIZE), NULL);
    PUT(heap_listp + ((SEGREGATED_SIZE + 2) * WSIZE), PACK((SEGREGATED_SIZE + 2) * WSIZE, 1)); // 프롤로그 Footer
    PUT(heap_listp + ((SEGREGATED_SIZE + 3) * WSIZE), PACK(0, 1));                             // 에필로그 Header: 프로그램이 할당한 마지막 블록의 뒤에 위치
    
    heap_listp += (2 * WSIZE); // 첫번째 가용 블록의 bp

    // 힙을 CHUNKSIZE bytes로 확장
    if (extend_heap(4) == NULL)
        return -1;
    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)     // 8바이트 이하이면
        asize = 2 * DSIZE; // 최소 블록 크기 16바이트 할당 (헤더 4 + 푸터 4 + 저장공간 8)
    else
        asize = DSIZE * ((size + DSIZE + DSIZE - 1) / DSIZE); // 8배수로 올림 처리

    /* 가용 블록 검색 */
    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 *bp)
{
    size_t size = GET_SIZE(HDRP(bp));
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    coalesce(bp);
}

// 기존에 할당된 메모리 블록의 크기 변경
// `기존 메모리 블록의 포인터`, `새로운 크기`
void *mm_realloc(void *ptr, size_t size)
{
    /* 예외 처리 */
    if (ptr == NULL) // 포인터가 NULL인 경우 할당만 수행
        return mm_malloc(size);

    if (size <= 0) // size가 0인 경우 메모리 반환만 수행
    {
        mm_free(ptr);
        return 0;
    }

    /* 새 블록에 할당 */
    void *newptr = mm_malloc(size); // 새로 할당한 블록의 포인터
    if (newptr == NULL)
        return NULL; // 할당 실패

    /* 데이터 복사 */
    size_t copySize = GET_SIZE(HDRP(ptr)) - DSIZE; // payload만큼 복사
    if (size < copySize)                           // 기존 사이즈가 새 크기보다 더 크면
        copySize = size;                           // size로 크기 변경 (기존 메모리 블록보다 작은 크기에 할당하면, 일부 데이터만 복사)

    memcpy(newptr, ptr, copySize); // 새 블록으로 데이터 복사

    /* 기존 블록 반환 */
    mm_free(ptr);
    
    return newptr;
}

static void *extend_heap(size_t words)
{
    char *bp;

    // 더블 워드 정렬 유지
    // size: 확장할 크기
    size_t size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE; // 2워드의 가장 가까운 배수로 반올림 (홀수면 1 더해서 곱함)

    if ((long)(bp = mem_sbrk(size)) == -1) // 힙 확장
        return NULL;

    PUT(HDRP(bp), PACK(size, 0));         // 새 빈 블록 헤더 초기화
    PUT(FTRP(bp), PACK(size, 0));         // 새 빈 블록 푸터 초기화
    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) // 모두 할당된 경우
    {
        add_free_block(bp); // free_list에 추가
        return bp;          // 블록의 포인터 반환
    }
    else if (prev_alloc && !next_alloc) // 다음 블록만 빈 경우
    {
        splice_free_block(NEXT_BLKP(bp)); // 가용 블록을 free_list에서 제거
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size, 0)); // 현재 블록 헤더 재설정
        PUT(FTRP(bp), PACK(size, 0)); // 다음 블록 푸터 재설정 (위에서 헤더를 재설정했으므로, FTRP(bp)는 합쳐질 다음 블록의 푸터가 됨)
    }
    else if (!prev_alloc && next_alloc) // 이전 블록만 빈 경우
    {
        splice_free_block(PREV_BLKP(bp)); // 가용 블록을 free_list에서 제거
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); // 이전 블록 헤더 재설정
        PUT(FTRP(bp), PACK(size, 0));            // 현재 블록 푸터 재설정
        bp = PREV_BLKP(bp);                      // 이전 블록의 시작점으로 포인터 변경
    }
    else // 이전 블록과 다음 블록 모두 빈 경우
    {
        splice_free_block(PREV_BLKP(bp)); // 이전 가용 블록을 free_list에서 제거
        splice_free_block(NEXT_BLKP(bp)); // 다음 가용 블록을 free_list에서 제거
        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);                      // 이전 블록의 시작점으로 포인터 변경
    }
    add_free_block(bp); // 현재 병합한 가용 블록을 free_list에 추가
    return bp;          // 병합한 가용 블록의 포인터 반환
}

static void *find_fit(size_t asize)
{
    int class = get_class(asize);
    void *bp = GET_ROOT(class);
    while (class < SEGREGATED_SIZE){
        bp = GET_ROOT(class);
        while (bp != NULL) // 다음 가용 블럭이 있는 동안 반복
        {
            if ((asize <= GET_SIZE(HDRP(bp)))) // 적합한 사이즈의 블록을 찾으면 반환
                return bp;
            bp = GET_SUCC(bp); // 다음 가용 블록으로 이동
        }
        class += 1;
    } 
    return NULL;
}

static void place(void *bp, size_t asize)
{
    splice_free_block(bp); // free_list에서 해당 블록 제거

    size_t csize = GET_SIZE(HDRP(bp)); // 현재 블록의 크기

    if ((csize - asize) >= (2 * DSIZE)) // 차이가 최소 블록 크기 16보다 같거나 크면 분할
    {
        PUT(HDRP(bp), PACK(asize, 1)); // 현재 블록에는 필요한 만큼만 할당
        PUT(FTRP(bp), PACK(asize, 1));

        PUT(HDRP(NEXT_BLKP(bp)), PACK((csize - asize), 0)); // 남은 크기를 다음 블록에 할당(가용 블록)
        PUT(FTRP(NEXT_BLKP(bp)), PACK((csize - asize), 0));
        add_free_block(NEXT_BLKP(bp)); // 남은 블록을 free_list에 추가
    }
    else
    {
        PUT(HDRP(bp), PACK(csize, 1)); // 해당 블록 전부 사용
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

// 가용 리스트에서 bp에 해당하는 블록을 제거하는 함수
static void splice_free_block(void *bp)
{
    int class = get_class(GET_SIZE(HDRP(bp)));
    if (bp == GET_ROOT(class)) // 분리하려는 블록이 free_list 맨 앞에 있는 블록이면
    {
        GET_ROOT(class) = GET_SUCC(GET_ROOT(class)); // 다음 블록을 루트로 변경
        return;
    }
    // 이전 블록의 SUCC을 다음 가용 블록으로 연결
    GET_SUCC(GET_PRED(bp)) = GET_SUCC(bp);
    // 다음 블록의 PRED를 이전 블록으로 변경
    if (GET_SUCC(bp) != NULL) // 다음 가용 블록이 있을 경우만
        GET_PRED(GET_SUCC(bp)) = GET_PRED(bp);
}

// 가용 리스트의 맨 앞에 현재 블록을 추가하는 함수
static void add_free_block(void *bp)
{
    int class = get_class(GET_SIZE(HDRP(bp)));
    GET_SUCC(bp) = GET_ROOT(class);     // bp의 SUCC은 루트가 가리키던 블록
    if (GET_ROOT(class) != NULL)        // free list에 블록이 존재했을 경우만
        GET_PRED(GET_ROOT(class)) = bp; // 루트였던 블록의 PRED를 추가된 블록으로 연결
    GET_ROOT(class) = bp;               // 루트를 현재 블록으로 변경
}

static int get_class(size_t size){
    if (size < 16)
        return 0;
    
    size_t class_sizes[SEGREGATED_SIZE];
    class_sizes[0] = 16;

    for (int i = 0; i < SEGREGATED_SIZE; i++){
        if (i != 0){
            class_sizes[i] = class_sizes[i - 1] << 1;
        }
        if (size <= class_sizes[i]){
            return i;
        }
    }
    return SEGREGATED_SIZE-1;
}