[CS:APP/말록랩] 명시적·암묵적 가용 리스트 할당기(malloc·free·sbrk) 동작 원리와 가용 블록 병합(coalesce)·분할(place) 메커니즘

자신감·4일 전

COALESCE CSAPP malloc sbrk 크래프톤정글 핀토스커널

6주차

목록 보기

4/7

소주제

동적 메모리 할당의 물리적 필요성: 런타임 크기 결정, 스택 프레임 수명 극복, 힙 경계 확장(sbrk)
가용 블록 탐색 3대 정책: First-fit, Next-fit, Best-fit의 처리 속도 및 외부 단편화 비교
가용 블록 병합(Coalescing) 4가지 물리 케이스와 시작 포인터 bp의 재조정 규칙
블록 배치 및 분할(Splitting, place): 최소 블록 크기(16바이트) 기준 내부 단편화 방지
핀토스(Pintos) 커널 적용: threads/malloc.c의 페이지 기반 아레나(Arena) 구조와 블록 디스크립터(Descriptor) 동작 메커니즘

1. 동적 메모리 할당의 물리적 필요성: 런타임 크기 결정, 스택 프레임 수명 극복, 힙 경계 확장(sbrk)

1.1 동적 할당이 필요한 하드웨어 이유

스택 용량 한계 (Stack Overflow): 프로세스의 스택 세그먼트는 보통 수 MB(Linux 기본 8MB)로 제한되어 있어 대용량 버퍼를 선언하면 스택 경계를 침범해 즉시 충돌합니다.
함수 스택 프레임 수명(Lifetime) 한계: 함수 내부에서 선언된 지역 변수는 함수가 반환(ret)하는 즉시 스택 포인터가 원복되어 파괴되므로, 외부로 주소를 넘기면 댕글링 포인터가 발생합니다.
런타임 크기 가변성: 사용자 입력이나 네트워크 패킷 크기는 컴파일 시점에 알 수 없으므로, 거대한 힙(Heap) 세그먼트에서 필요한 바이트를 동적으로 요청해야 합니다.

1.2 저수준 힙 확장 시스템 콜 sbrk

void *sbrk(intptr_t incr);

힙 영역의 최상단 경계 주소를 brk(Program Break)라고 부릅니다.
sbrk(incr)는 커널에 요청하여 brk 주소를 incr 바이트만큼 증가시키고, 확장되기 직전의 시작 주소를 반환합니다. 할당 실패 시 (void *)-1을 반환합니다.

2. 가용 블록 탐색 3대 정책: First-fit, Next-fit, Best-fit의 처리 속도 및 외부 단편화 비교

프로그래머가 malloc(asize)를 호출했을 때, 가용 블록 목록에서 요청 크기를 수용할 수 있는 빈 블록을 선택하는 정책 3가지입니다.

First-fit (최초 적합):
- 힙의 맨 처음(heap_listp)부터 순차적으로 탐색하여 크기 >= asize인 첫 번째 빈 블록을 즉시 반환합니다.
- 장점: 힙 뒷부분에 거대한 가용 블록이 보존됩니다.
- 단점: 힙 앞쪽에 자잘한 자투리 블록들이 누적되어 탐색 시간이 갈수록 길어집니다.
Next-fit (다음 적합):
- 매번 처음부터 찾지 않고, 직전 탐색이 종료된 포인터 위치부터 이어서 탐색합니다.
- 장점: First-fit보다 탐색 속도가 빠릅니다.
- 단점: 힙 뒷부분의 거대한 빈 메모리 덩어리들을 빠르게 쪼개어 단편화를 가속시킵니다.
Best-fit (최적 적합):
- 힙 전체의 모든 가용 블록을 검사하여, 크기 >= asize를 만족하면서 남는 자투리 크기가 가장 작은 블록을 선택합니다.
- 장점: 자투리 크기를 최소화하여 메모리 활용도(외부 단편화 방지)가 가장 뛰어납니다.
- 단점: 매 할당마다 힙 전체를 끝까지 순회해야 하므로 $O(N)$ 시간 지연이 발생합니다.

3. 가용 블록 병합(Coalescing) 4가지 물리 케이스와 시작 포인터 bp의 재조정 규칙

메모리를 해제(free)할 때 인접한 빈 블록들을 하나로 합치지 않으면 거대한 연속 메모리를 할당할 수 없는 외부 단편화가 발생합니다.

static void *coalesce(void *bp)

Case 1 (직전 블록: 할당 / 다음 블록: 할당):
- 인접 블록이 모두 사용 중이므로 병합 불가. bp를 그대로 반환.
Case 2 (직전 블록: 할당 / 다음 블록: 가용):
- 현재 블록 크기에 다음 블록 크기를 합산.
- 현재 블록의 헤더와 다음 블록의 푸터 크기를 합산값으로 갱신. bp 유지.
Case 3 (직전 블록: 가용 / 다음 블록: 할당):
- 직전 블록 크기에 현재 블록 크기를 합산.
- 직전 블록의 헤더와 현재 블록의 푸터 크기를 합산값으로 갱신.
- 중요: 시작 포인터를 직전 블록의 시작 번지수로 이동 (bp = PREV_BLKP(bp)).
Case 4 (직전 블록: 가용 / 다음 블록: 가용):
- 직전 크기 + 현재 크기 + 다음 크기 3개를 합산.
- 직전 블록의 헤더와 다음 블록의 푸터 크기를 3개 합산값으로 갱신.
- 시작 포인터를 직전 블록 시작 번지수로 이동 (bp = PREV_BLKP(bp)).

4. 블록 배치 및 분할(Splitting, place): 최소 블록 크기(16바이트) 기준 내부 단편화 방지

가용 블록을 찾았을 때, 요청 크기보다 블록이 훨씬 크다면 잉여 공간을 잘라내어 새 가용 블록으로 만들어야 합니다.

static void place(void *bp, size_t asize) {
    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));
        // 뒷부분은 쪼개서 새로운 가용 블록으로 등록
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(csize - asize, 0));
        PUT(FTRP(bp), PACK(csize - asize, 0));
    } else {
        // 16바이트 미만 자투리는 쪼갤 수 없으므로 통째로 할당 (내부 단편화 허용)
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

5. 핀토스(Pintos) 커널 적용: threads/malloc.c의 페이지 기반 아레나(Arena) 구조와 블록 디스크립터(Descriptor) 동작 메커니즘

핀토스는 CS:APP의 암묵적 가용 리스트보다 한 단계 더 진화한 아레나(Arena) & 슬랩(Slab) 기반 디스크립터 할당기를 커널 내부에 탑재하고 있습니다.

5.1 블록 디스크립터 (Block Descriptor)

핀토스 커널은 16, 32, 64, 128, 256, 512, 1024바이트 크기별로 디스크립터 구조체(struct desc)를 배열로 유지합니다.
각 디스크립터는 같은 크기의 메모리 블록들만 모아둔 페이지 목록(free_list)을 관리합니다.

5.2 아레나 구조 (Arena)

핀토스는 4KB 페이지를 할당받으면 페이지 맨 앞부분에 아레나 헤더(struct arena)를 심습니다.
아레나 헤더에는 해당 페이지가 몇 바이트 크기 블록들로 쪼개져 있는지, 남은 가용 블록 수는 몇 개인지 기록됩니다.
free(ptr) 호출 시, 핀토스는 복잡한 탐색 없이 ptr의 하위 12비트를 잘라내어(pg_round_down(ptr)) 단 1번의 비트 연산으로 4KB 페이지 시작점의 아레나 헤더를 즉시 찾아내고 블록을 반환합니다.