CSAPP 9장 | Implicit vs Explicit Free List

앞서, 힙(Heap) 에 대해서 알아보았다.

참고자료 🌸
CSAPP 9장 | 세그먼트와 힙: malloc이 메모리를 관리하는 방법

프로그램이 malloc()을 호출해서 힙에서 메모리를 할당받고,
free() 를 호출해서 메모리를 다시 반납한다.

그렇다면 이번에는,
힙의 관점에서free()가 호출된 이후,
빈 공간(free block)을 어떻게 관리하는지 살펴보자 !

---

Heap은 block으로 이루어져 있다.

프로그램이 malloc()과 free()를 통해 메모리를 요청하고 반납할 때,
heap안에서는 free block들을 따로 관리해야 한다.

Heap은 다양한 메모리 블록(memory block) 으로 구성되어 있다.

• 블록 안에 데이터가 차 있으면 → Allocated Block (할당된 블록)
• 블록 안에 자리가 비어 있으면 → Free Block (가용 블록)

그리고 Heap의 맨 앞과 맨 끝에는,
힙의 경계를 나타내는 특별한 블록이 존재한다.

• Prologue Block : 힙의 시작을 표시하는 작은 dummy 블록
• Epilogue Block : 힙의 끝을 표시하는 크기 0짜리 dummy 블록

한눈에 보기

블록 종류	설명
프로로그 블록 (Prologue Block)	heap 시작에 있는 dummy 블록 (크기 8B, 항상 할당됨)
할당된 블록 (Allocated Block)	malloc()된 메모리 블록
가용 블록 (Free Block)	free()된 메모리 블록
에필로그 블록 (Epilogue Block)	heap 끝을 표시하는 dummy 블록 (size=0, allocated=1)

---

❓Heap 안에서 Free Block은 어떻게 관리할까

그렇다면 malloc()이나 free()가 호출될 때,
Heap 안의 free block들은 어떻게 관리할까?

→ 관리 방식에는 크게 두 가지가 있다!

1. Implicit Free List (암묵적 자유 리스트)

Implicit Free List는
free block끼리 별도의 포인터 연결 없이,
힙(heap)을 순차적으로 훑어가면서 빈 블록을 찾는 방식이다.

블록의 크기는 제각각 다를 수 있다.
그런데도 위 그림처럼 빨간 화살표 방향으로 다음 블록을 정확히 찾아갈 수 있는 이유는,
각 블록의 header에 "블록 크기 정보"가 저장되어 있기 때문이다.

❁ Block 구성요소

👾 블록 안에는

• 사용자 데이터(payload) 뿐만 아니라
• 블록의 크기(size)
• 할당 여부(allocated bit) 도 함께 기록되어 있다.

✏️ [Implicit Free List ] 특징

• free block끼리 따로 포인터로 연결하지 않는다.
• 그냥 heap을 처음부터 끝까지 순서대로 훑어가면서,
  header를 읽어서 free block인지 확인한다.
  

---

앞서 살펴본 Implicit Free List는,
가용 블록과 할당 블록을 구분하지 않고,
heap을 처음부터 끝까지 차례대로 하나하나 모두 확인하는 방식이었다.

⚡️ 하지만 이렇게 하면 heap이 커질수록 탐색 시간이 오래 걸리는 문제가 생긴다.

그렇다면,
가용 블록만 따로 모아두고 빠르게 찾을 수 있다면 더 효율적이지 않을까?

---

2. Explicit Free List (명시적 자유 리스트)

Explicit Free List는 바로 이 아이디어를 구현한 방식이다.
free block끼리 직접 포인터(prev, next)로 연결하는 방식이다.

❁ Block 구성요소

블록에는 기본적으로

• Header : size + allocated 정보
• Footer : size + allocated 정보 가 저장된다.

그런데 explicit free list에서는 추가로,

• prev 포인터 : 이전 free block을 가리키는 포인터
• next 포인터 : 다음 free block을 가리키는 포인터 를 저장한다.

prev, next는 free block 에만 존재한다 !

✏️ [Explicit Free List ] 특징

• free block 안에 prev 포인터와 next 포인터를 심어서
  free block끼리만 연결된 Linked List를 만든다.
• malloc()할 때는 이 free list만 따라가서 빠르게 찾는다.

구조 예시

[ Prologue Block ]
[ Header | Payload (Allocated) ]
[ Header | Prev Pointer | Next Pointer | (빈 공간) | Footer (Free) ]
[ Header | Payload (Allocated) ]
[ Epilogue Block ]

---

마무리 요약

비교 항목	Implicit Free List	Explicit Free List
포인터 연결	❌ 없음	prev/next 포인터로 연결
탐색 방식 🔍	heap 전체 훑기	free list만 빠르게 순회
장점	구조 단순, 메모리 절약	탐색 속도 빠름 🏃
단점	탐색 느림 (heap 크기 커지면 문제)	포인터 공간 추가 필요