[CSAPP 9장 완전 정복] 9.9(Part 7) 블록 배치(Placement) 정책의 종류와 장단점

블록 배치(Placement) 정책의 종류와 장단점

이번 포스트에서는 메모리를 할당할 때 어떤 블록을 선택할지 결정하는 배치 정책(Placement Policy)에 대해 알아보겠습니다. 배치 정책에는 다양한 규칙들이 있는데요. 어떤 배치 방법을 선택하는지에 따라 메모리 활용률과 프로그램 성능이 크게 달라질 수 있습니다.

 

 

배치 정책(Placement Policy)이란?

배치 정책(Placement Policy)은 malloc 요청이 들어왔을 때, 어떤 free block에 메모리를 배치할지를 결정하는 규칙을 말합니다. 좋은 정책을 선택하게 되면 단편화를 줄이고 성능을 향상시킬 수 있습니다.

 

 

주요 Placement 정책들

• First-Fit (최초 적합)
  • Free List의 처음부터 탐색하여, 요청 크기 이상인 첫 번째 블록에 배치하는 규칙
  • 장점: 탐색이 빠르며, 구현이 간단
  • 단점: 앞쪽에 작은 조각(splinter)이 쌓여 외부 단편화 증가 가능성 있음
• Next-Fit (다음 적합)
  • 이전 탐색이 끝난 지점 이후부터 탐색을 시작하는 규칙
  • 장점: 앞쪽에 쌓인 작은 블록 무시 가능, 일부 상황에서 탐색 속도 개선
  • 단점: 메모리 전체가 점점 분산되어 외부 단편화 심화 가능
• Best-Fit (최적 적합)
  • 전체 Free List를 탐색해, 요청 크기와 가장 가까운 블록에 배치하는 규칙
  • 장점: 내부 단편화 최소화 가능
  • 단점: 탐색 비용이 높음 (특히 암시적 리스트에서는 전체 힙 순회 필요)

 

정책 비교 요약

정책	탐색 속도	메모리 활용률	단편화 경향
First-Fit	빠름	중간	앞쪽에 splinter 증가
Next-Fit	더 빠를 수 있음	조금 낮을 수 있음	전체적으로 분산
Best-Fit	느림	높음	작은 조각들 증가 가능성

 

 

실제 설계 선택 전략

• 속도가 중요할 때: First-Fit + 명시적 Free List(LIFO) 조합
• 메모리 활용이 더 중요할 때: Best-Fit + Segregated List 조합
• Next-Fit은 특수 상황에서만 고려됨

 

마치면서

이번 편에서는 메모리 할당 시 블록을 어떻게 선택하는지가 시스템 성능과 메모리 효율에 어떤 영향을 미치는지를 살펴보았는데요. 결국, 속도와 활용률 사이의 트레이드 오프(Trade-Off) 사이에서 균형을 잡는 것이 핵심이라고 할 수 있습니다.

 

다음 편에서는 블록을 배치할 때 어떻게 분할(Splitting)할지에 대해 자세히 살펴보겠습니다. 감사합니다.