1. 8바이트/16바이트 주소 정렬의 하드웨어 버스 전송 이유와 하위 3비트(000)의 가용 여부 플래그 활용법
1.1 하드웨어 정렬(Alignment)의 물리적 이유
CPU가 메모리 버스를 통해 RAM과 데이터를 주고받을 때, 데이터 버스는 64비트(8바이트) 폭으로 묶여 전송됩니다.
- 만약 8바이트 정수가 8의 배수 번지수(예: 0x1000)에 위치하면, 메모리 컨트롤러는 단 1번의 버스 사이클로 데이터를 완벽히 읽어옵니다.
- 만약 주소가 8의 배수가 아니어서 두 개의 버스 블록에 걸쳐 있으면(Misaligned), CPU는 메모리 버스를 2번 작동시키고 비트를 이어 붙여야 하므로 성능이 반토막 납니다.
1.2 하위 3비트 비트 패킹(Bit Packing) 트릭
- 8바이트 정렬 규칙에 따라, 모든 할당 블록의 크기는 반드시 8의 배수(8, 16, 24, 32...)가 됩니다.
- 2진수로 8의 배수는 최하위 3개 비트가 항상
000입니다 (, , ). - 이 하위 3비트는 블록 크기를 나타내는 데 전혀 쓰이지 않고 항상 0이므로, 할당기는 최하위 1개 비트를 할당 상태 플래그(1=사용 중, 0=가용 빈 블록)로 재활용합니다.
2. 4바이트 블록 헤더 설계: 블록 크기와 할당 상태 비트(1=할당, 0=가용)를 비트합(|)으로 패킹하는 원리
동적 메모리 할당기(Implicit Free List)의 핵심 메타데이터 매크로는 비트 연산으로 구현됩니다.
// 블록 크기(size)와 할당 여부(alloc)를 1개의 4바이트 워드로 결합
#define PACK(size, alloc) ((size) | (alloc))
// 하위 3비트를 0으로 마스킹하여 순수 블록 크기(8의 배수) 추출 (~0x7 = ...11111000)
#define GET_SIZE(p) (GET(p) & ~0x7)
// 최하위 1비트만 마스킹하여 할당 여부(0 또는 1) 추출
#define GET_ALLOC(p) (GET(p) & 0x1)- 예시: 24바이트 크기의 블록이 할당(1)된 경우
PACK(24, 1)= (10진수 25)- 헤더에는 정수 25가 기록되지만,
GET_SIZE를 거치면 하위 3비트가 잘려 순수 크기 24가 추출되고,GET_ALLOC을 거치면 1이 추출됩니다.
3. 프롤로그 블록, 에필로그 블록, 정렬 패딩의 물리적 배치와 힙 경계 검사 제거 목적
힙 초기화 함수 mm_init은 힙의 시작과 끝에 특수한 더미 블록들을 심어 경계 조건 예외 처리를 제거합니다.
[초기 힙 물리 배치 구조]
0x1000: [ 패딩 4B (0) ] <-- 8바이트 정렬을 맞추기 위한 여백
0x1004: [ 프롤로그 헤더 4B (8/1) ] <-- 크기 8, 할당됨(1)
0x1008: [ 프롤로그 푸터 4B (8/1) ] <-- 크기 8, 할당됨(1) <-- heap_listp 시작점
0x100C: [ 에필로그 헤더 4B (0/1) ] <-- 크기 0, 할당됨(1) <-- 힙의 끝 표시 벽- 에필로그 블록 (크기 0, 할당됨 1): 다음 블록을 순회하다가 크기가 0인 헤더를 만나는 즉시 힙의 끝임을 감지하고 순회를 안전하게 종료시킵니다.
- 프롤로그 블록 (크기 8, 할당됨 1): 맨 앞 블록이 이전 블록과 병합을 시도할 때, 물리 메모리 시작 번지수 이전으로 주소가 넘어가지 않도록 '항상 할당된 벽' 역할을 합니다.
4. 경계 태그(푸터, Footer)가 이전 블록 역방향 탐색 및 O(1) 상수 시간 병합을 가능하게 하는 기계적 구조
- 다음 블록 주소 계산: 현재 페이로드 포인터
bp에서 내 헤더에 적힌 내 크기만큼 앞으로 더하면(bp + GET_SIZE(HDRP(bp))) 즉시 나옵니다. - 이전 블록 주소 계산의 한계: 내 바로 앞 블록의 크기를 모르면, 그 블록의 시작 번지수를 알 수 없어 힙 맨 처음부터 시간으로 순회해야 합니다.
- 경계 태그(푸터)의 해결책: 각 블록의 마지막 4바이트에 헤더와 완전히 똑같은 크기/할당 정보를 복사해 둡니다.
- 내 헤더의 바로 4바이트 뒤(
bp - DSIZE)를 읽으면 직전 블록의 푸터를 단 1회의 역참조로 즉시 읽을 수 있으며, 그 크기만큼 주소를 뒤로 빼면 이전 블록의 시작 위치를 상수 시간에 찾아내어 양방향 병합을 완료합니다.
5. 핀토스(Pintos) 커널 적용: 4KB 단위 물리 페이지 할당자(palloc)와 블록 기반 동적 할당자(malloc)의 2단계 계층 구조
핀토스 커널(threads/palloc.c, threads/malloc.c)은 하드웨어 MMU 페이징과 소프트웨어 동적 할당을 2단계 계층으로 분리하여 관리합니다.
5.1 1단계: 페이지 할당자 (palloc)
- 물리 RAM을 4KB() 단위의 페이지 프레임으로 쪼개어 관리합니다.
- 비트맵(Bitmap) 자료구조를 사용하여, 각 비트 1개가 4KB 물리 메모리 1개의 사용 여부를 나타냅니다.
- 커널 전용 메모리 풀(Kernel Pool)과 유저 프로세스 전용 메모리 풀(User Pool)로 분리되어 독립적으로 할당됩니다.
5.2 2단계: 블록 할당자 (malloc)
- 개발자가
malloc(64)처럼 작은 바이트를 요구할 때 매번 4KB 페이지를 줄 수 없으므로,palloc으로 4KB 페이지를 먼저 받아온 뒤 그 내부를 잘게 쪼개어 할당합니다. - CS:APP의 동적 할당 원리가 핀토스 커널의 기본 메모리 공급 엔진으로 작동합니다.
잘할 수밖에 없는 자신감