[TIL/크래프톤 정글9기] 48일차 (C/묵시적 가용 리스트 구현 )

묵시적 가용 리스트 구현

1. 블록 구조

각 메모리 블록은 다음과 같은 구조를 가짐:

• 헤더/푸터: 블록의 크기와 할당 상태 정보를 저장
• 페이로드: 실제 사용자가 사용하는 메모리 영역

2. Define

#define WSIZE 4        /* 워드 크기 (바이트) */
#define DSIZE 8        /* 더블 워드 크기 (바이트) */
#define CHUNKSIZE (1<<12) /* 힙 확장 크기 (4KB) */

// 블록 크기와 할당 상태를 하나의 워드로 패킹
#define PACK(size, alloc) ((size) | (alloc))

// 포인터 p가 가리키는 주소에서 4바이트 워드를 읽고 쓰기
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))

// 헤더/푸터에서 정보 추출
#define GET_SIZE(p) (GET(p) & ~0x7)    // 블록 크기
#define GET_ALLOC(p) (GET(p) & 0x1)    // 할당 상태

// 블록 포인터 계산
#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))) // bp에 현재 블록의 크기를 더해 다음 블록의 bp를 계산
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE))) // bp에서 이전 블록의 크기를 빼서 이전 블록의 bp를 계산

• 워드 사이즈가 4인 이유는 코드가 32bit에서 시스템에서의 워드 크기이기 때문
• PACK은 위 그림에 있는 헤더와 푸터의 size와 alloc을 포장하는 역할
• GET_SIZE(p)는 헤더/푸터에 있는 블록 사이즈를 가져옴
• GET_ALLOC(p)는 헤더/푸터에 있는 alloc 상태 비트를 가져옴
• HDRP(bp)는 현재 블럭 위치에서 - 워드사이즈 하여 헤더의 시작 주소를 가져옴
• FTRP(bp)는 bp에 (블록 전체 크기 - 8바이트)를 더해 푸터 시작 주소를 계산
• NEXT_BLKP(bp) 현재 블록의 크기를 더해 다음 블록의 bp를 계산
• PREV_BLKP(bp) 이전 블록의 크기를 빼서 이전 블록의 bp를 계산

함수

1. mm_init() - 초기화

힙을 초기화하고 초기 구조를 설정:

int mm_init(void)
{
    // 16바이트로 초기 힙 구조 생성
    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); // 프롤로그 블록의 페이로드 시작점으로 설정
    
    // 초기 가용 블록으로 힙 확장
    if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
        return -1;
    return 0;
}

• 힙 메모리 영역을 초기화한다.

2. mm_malloc() - 메모리 할당

First-fit 알고리즘을 사용하여 적합한 가용 블록을 찾아 할당:

void *mm_malloc(size_t size)
{
    size_t asize;      /* 조정된 블록 크기 */
    size_t extendsize; /* 확장할 크기 */
    char *bp;
    
    if (size == 0)
        return NULL;
    
    // 블록 크기 조정 (최소 16바이트)
    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;
}

3. mm_free() - 메모리 해제

블록을 해제하고 인접한 가용 블록들과 병합:

void mm_free(void *ptr)
{
    if (ptr == NULL)
        return;
    
    size_t size = GET_SIZE(HDRP(ptr));
    
    // 블록을 가용 상태로 변경
    PUT(HDRP(ptr), PACK(size, 0));
    PUT(FTRP(ptr), PACK(size, 0));
    
    // 인접 블록들과 병합
    coalesce(ptr);
}

• 페이로드 안에 있는 값은 건들지 않고 헤더와 풋터의 alloc을 0으로 설정해 가용 블럭 해줌

4. 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) {           /* 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;
}

배치 알고리즘

1. First-fit 검색

static void *find_fit(size_t asize)
{
    void *bp;
    
    // 힙을 순회하며 첫 번째 적합한 블록 찾기
    for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
            return bp;
        }
    }
    return NULL;
}

2. 블록 분할

남은 공간이 충분하면 블록을 분할하여 내부 단편화 줄이기:

static void place(void *bp, size_t asize) {
    size_t csize = GET_SIZE(HDRP(bp));
    
    // 남은 공간이 최소 블록 크기(16바이트) 이상이면 분할
    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));
    }
}

성능 최적화 포인트

1. 8바이트 정렬: 모든 블록이 8바이트 경계에 정렬되어 효율적인 메모리 접근 보장
2. 블록 병합: 인접한 가용 블록들을 병합하여 외부 단편화 감소
3. 블록 분할: 큰 가용 블록을 분할하여 내부 단편화 감소
4. 최소 블록 크기: 16바이트로 설정하여 헤더/푸터 오버헤드 최소화

학습한 내용

• 메모리 레이아웃: 힙의 구조와 블록 배치 방식
• 단편화: 내부/외부 단편화의 개념과 해결 방법
• 메모리 관리: 동적 할당과 해제의 내부 동작 원리
• 성능 최적화: 메모리 효율성과 속도의 트레이드오프

다음 할 일

• next-fit 구현
• best-fit 구현