[CS기초] Implicit Free List vs Explicit Free List

Implicit Free List vs Explicit Free List

동적 메모리 할당을 관리할 때, 운영체제나 할당기는 사용 가능한(free) 메모리 블록을 효율적으로 관리하기 위해 다양한 전략을 사용하게 되는데요. 이를 위한 대표적인 두 가지 방법이 바로 Implicit Free List와 Explicit Free List입니다. 이번 글에서는 각 방식의 특징과 장단점을 함께 살펴보도록 하겠습니다.

 

 

Implicit Free List

Implicit Free List는 메모리의 모든 블록이 포인터를 갖고 있진 않지만, 크기 정보를 이용해 각 블록을 마치 연결 리스트처럼 순회할 수 있는 구조입니다. 각 블록들은 물리적으로는 연속적으로 배치되어 있지만, 블록마다 크기가 가변적이기 때문에 각 블록의 크기를 이용해 다음 블록으로 건너뛰게 됩니다. 이때 각 블록은 헤더(Header)와 푸터(Footer)에 크기와 할당 여부 정보를 저장하며, 이러한 방식으로 블록들을 암시적으로 연결합니다.

• 특징
  • 블록을 탐색할 때 모든 블록을 확인하면서 빈 블록을 찾는다
  • 추가 포인터가 필요 없으므로 공간 오버헤드가 상대적으로 적다
  • 빈 블록 탐색 시간이 길어질 수 있다
• 장점: 간단한 구조로 관리가 쉽다
• 단점: 빈 블록 탐색 시 모든 블록을 순차적으로 확인해야 하므로 성능이 저하될 수 있다

 

Explicit Free List

Explicit Free List는 비어있는 블록(free block)만 별도의 연결 리스트로 명시적으로 관리하는 방식인데요. 각 빈 블록은 추가적으로 이전 블록(pred)과 다음 블록(succ)을 가리키는 포인터를 가지고 있어, 서로 간에 명시적으로 연결되어 있습니다.

• 특징
  • 할당된 블록을 건너뛰고, 빈 블록만 빠르게 탐색이 가능하다
  • 빈 블록 간의 연결을 위해 추가적인 공간이 필요하다
• 장점: 빈 블록 탐색 및 할당이 더 빠르고 효율적이다
• 단점: 빈 블록마다 포인터(pred, succ)를 저장해야 하므로 공간 오버헤드가 증가한다

 

마치면서

Implicit Free List는 구조가 단순하여 공간 효율은 높으나, 탐색 속도가 느립니다. 반면, Explicit Free List는 탐색 속도는 빠르지만 공간을 더 소비하는 트레이드 오프가 있죠. 따라서 상황에 따라 성능과 공간 효율 중 어떤 요소가 중요한지를 판단하여 적절한 메모리 관리 방식을 선택해야 합니다.