저번에 시스템 콜에 대해서 언급하면서 malloc이 내부적으로 ptmalloc이라는 메모리 할당기를 통해서 관리되고 있다는 것을 잠깐 언급한 적이 있는데요.

할당기를 제대로 만들어주지 않으면 여러 단편화 문제를 겪을 수 있다는 것도 알았습니다.

implicit free list 와 explicit free list는 메모리 할당기가 어떻게 실용적으로 메모리를 할당해주는지에 관한 내용입니다.

할당기를 만들 때, 여러가지 구현 이슈가 있어요.

1. 가용 블록 구성 : 사용할 수 있는 블록(free된)을 어떻게 추적할까?
2. 배치 : 새롭게 할당된 블록을 배치하기 위해서, 가용 블록을 어떻게 선택할까?
3. 분할 : 가용 블록을 배치하고, 나머지 부분들로 무엇을 할까?
4. 연결 : 방금 반환된 블록으로 무엇을 할까?

이런 점들을

• implicit free list 묵시적 가용 리스트와
• explicit free list 암시적 가용 리스트로 살펴볼게요.

1. Implicit free list

Implicit Free List는 메모리 블록들 자체를 하나의 리스트처럼 보고, 헤더(header)를 통해 각 블록의 크기와 할당 여부를 저장함으로써 가용 블록을 추적하는 방식입니다.

구조 설명

• 모든 블록은 [헤더 | payload | (optional footer)] 구조로 구성됩니다.
• 헤더에는 보통 블록의 크기와 할당 여부 비트가 들어갑니다.
• free인지 아닌지는 비트 하나로 구분됩니다.
• 리스트 형태이지만, 포인터가 따로 존재하지 않기 때문에 묵시적(implicit)이라 부릅니다.
• 가용 블록을 찾을 때는 처음부터 끝까지 선형 탐색을 하며, 첫 번째 적절한 블록을 고르거나(First Fit), 가장 잘 맞는 블록을 고르는(Best Fit) 전략 등을 씁니다.

다음이 free 이든 used 이든 무조건 가리킴

✂️ 분할(Splitting)

• 큰 블록이 발견되면, 필요한 크기만큼 할당하고 남은 공간을 새로운 블록으로 분할해서 다시 가용 리스트에 포함시킵니다.

🔗 연결(Coalescing)

• 블록이 반환되면 주변 블록을 검사하여 연결(merge) 시도.
• 바로 앞/뒤 블록이 free라면 하나의 큰 free 블록으로 병합합니다.

✅ 장점

• 구조가 간단해서 구현이 쉬움
• 별도의 포인터가 없기 때문에 공간 오버헤드가 적음

❌ 단점

• 선형 탐색이 필요해서 성능이 나쁠 수 있음 (특히 많은 블록이 있을 경우)
• 연결(coalescing)도 인접 블록을 모두 확인해야 해서 비용이 큼
• 단편화가 심해질 수 있음

2. Explicit Free List (명시적 가용 리스트)

Implicit 방식의 단점을 보완하기 위해, 가용 블록들만 따로 리스트로 관리하는 방식이 Explicit Free List입니다.

🔧 구조 설명

• 가용 블록들만 양방향 혹은 단방향 연결리스트로 관리합니다.
• 각 free 블록의 payload 공간에 다음/이전 free 블록을 가리키는 포인터를 저장합니다.

따라서, 모든 블록을 순회할 필요 없이, free 리스트만 탐색하면 됨

free 의 다음이 used 가 아니라 free 인 것을 확인할 수 있다.

🔍 탐색 방식

• 연결 리스트이기 때문에 First Fit, Best Fit, Next Fit 등 다양한 방식으로 효율적 탐색이 가능

✂️ 분할(Splitting)

• 가용 블록에서 필요한 만큼 할당하고, 나머지는 다시 free list에 넣습니다.
• 삽입 위치는 보통 리스트의 맨 앞(head 삽입)이나 특정 정책에 따라 다름

🔗 연결(Coalescing)

• 블록을 반환하면 인접한 free 블록을 병합한 뒤, free list에 다시 삽입
• 삽입 방식: LIFO(후입선출) 방식이 일반적 (성능과 단순성 때문)

✅ 장점

• 탐색 속도가 빠름 (free 블록만 탐색)
• 더 나은 메모리 재활용 성능 (단편화 줄일 수 있음)
• 연결/분할 등 메모리 관리 정책을 더 정교하게 구현 가능

❌ 단점

• 포인터를 추가로 저장해야 하므로 공간 오버헤드 발생
• 구조가 복잡해져서 구현 난이도 증가

마무리

키워드 공부인 implicit free list 와 explicit free list 를 마쳤는데요.
이제부터 malloc 을 직접 구현해볼게요. 가보작오~