[CSAPP 9장 완전 정복] 9.9(Part 3) 암시적 가용 리스트(Implicit Free List) vs 명시적 가용 리스트(Explicit Free List)

암시적 가용 리스트(Implicit Free List) vs 명시적 가용 리스트(Explicit Free List)

이번 포스트에서는 동적 메모리 할당의 핵심 관리 기법 중 하나인 Free List에 대해 다뤄볼 예정인데요. 특히, 암시적 가용 리스트(Implicit Free List)와 명시적 가용 리스트(Explicit Free List)의 차이점을 중심으로, 각 방식의 장단점과 활용 전략을 알아보겠습니다.

 

 

암시적 가용 리스트(Implicit Free List)란?

암시적 가용 리스트는 말 그대로, 모든 힙 블록을 순차적으로 탐색하는 방식인데요. 별도의 포인터 없이, 각 블록의 헤더를 읽으며 할당 여부를 판단합니다.

• 모든 블록을 선형 탐색
• 할당/해제 여부는 블록의 Header/Footer 정보만으로 확인
• 탐색: 첫 블록부터 끝까지 순차적으로 진행

구현은 간단하지만, 블록 수가 많아질수록 탐색 시간이 길어지는 단점을 가지고 있습니다.

 

 

명시적 가용 리스트(Explicit Free List)란?

명시적 가용 리스트는 free block만을 따로 연결 리스트로 관리하는 방식입니다. 이때 각 free block 내부에 이전/다음 블록을 가리키는 포인터(pred, succ)를 저장하죠.

• free block끼리만 별도로 연결
• O(1) 시간에 삽입/삭제 가능
• 탐색 속도: free block 수에 비례

Free block 만을 조회하기 때문에 탐색 성능은 훨씬 좋아지지만, free block에 추가적인 메타데이터(pred/succ 포인터)가 필요하기 때문에 메모리 오버헤드가 증가할 수 있습니다. 일종의 트레이드 오프(Trade-Off)인 셈이지요.

 

 

Implicit vs Explicit Free List 비교

구분	Implicit Free List	Explicit Free List
탐색 방식	모든 블록 순회	free block만 탐색
탐색 속도	느림 (O(N))	빠름 (O(free N))
메모리 오버헤드	없음	포인터 2개 추가
구현 난이도	낮음	중간
단편화 관리	어려움	개선 가능

 

 

Explicit Free List의 삽입/삭제 전략

명시적 가용 리스트에서는 free block을 어떻게 관리할지도 중요한데요. 대표적인 삽입 정책은 다음과 같습니다.

• LIFO 방식: 가장 최근에 해제된 블록을 리스트 앞에 삽입
  - 빠른 삽입/탐색 가능, 공간 지역성(locality) 좋음
• 주소 정렬 방식: 주소 순서대로 정렬
  - best-fit에 가깝게 메모리 활용 가능

실습이나 과제에서는 보통 빠르고 간단한 LIFO 방식으로 구현하는 편입니다.

 

 

마치면서

이번 편에서는 암시적 가용 리스트와 명시적 가용 리스트의 구조와 특징을 비교해봤는데요. 가용 리스트 설계 방식은 동적 메모리 할당기의 성능과 메모리 효율을 좌우하는 핵심 요소입니다.

 

다음 편에는 이 Free List를 실제로 사용하면서, Boundary Tag를 어떻게 활용해 블록 병합(Coalescing)을 빠르게 수행할 수 있는지에 대해 이어서 살펴보겠습니다.