동적 메모리 할당 시스템에서 메모리를 관리하는 방법에는 여러 가지가 있으며, 그 중 implicit free list와 explicit free list가 대표적인 두 가지 방식입니다.
Implicit Free List (암시적 자유 목록)
Implicit free list 방식에서는 할당되지 않은 메모리 블록들이 연속적으로 메모리에 나열되어 있으며, 각 블록은 자신의 크기와 할당 여부를 나타내는 헤더로 시작합니다. 메모리를 할당하거나 해제할 때, 메모리 전체를 순차적으로 탐색하면서 자유 블록(free block)을 찾거나, 사용 중인 블록(allocated block)을 해제합니다.
이 방식의 가장 큰 특징은 자유 블록 목록이 별도로 존재하지 않는다는 것입니다. 즉, 메모리 할당자는 헤더를 통해 메모리를 순차적으로 탐색하며 사용 가능한 블록을 찾아야 합니다. 이 방식은 구현이 간단하지만, 메모리 할당과 해제 과정에서 효율성이 떨어질 수 있습니다(예: 메모리를 탐색하는 데 시간이 오래 걸림).
Explicit Free List (명시적 자유 목록)
Explicit free list 방식에서는 모든 자유 블록들이 하나의 연결 리스트(linked list) 또는 여러 연결 리스트로 관리됩니다. 각 자유 블록은 다음과 이전 자유 블록을 가리키는 포인터를 포함하고 있어, 자유 블록 목록을 통해 빠르게 사용 가능한 메모리 블록을 찾을 수 있습니다.
명시적 자유 목록 방식은 메모리를 할당하고 해제할 때 효율적입니다. 메모리 할당자는 리스트를 따라가며 적절한 크기의 블록을 빠르게 찾을 수 있고, 메모리 블록을 해제할 때도 해당 블록을 자유 목록에 추가하기만 하면 됩니다. 하지만 이 방식은 암시적 목록에 비해 복잡한 구현이 요구됩니다.
성능 비교
Implicit free list는 메모리 할당 및 해제 시 전체 메모리를 탐색해야 하므로 할당 시간이 오래 걸릴 수 있습니다. 이는 특히 메모리가 많이 할당되어 있을 때 더욱 심해집니다.Explicit free list는 자유 블록을 빠르게 찾을 수 있어 할당과 해제가 빠릅니다. 하지만 리스트를 유지 관리해야 하는 추가적인 오버헤드가 있습니다.
Explicit free list는 메모리 관리에서 더 나은 성능을 제공하지만, 구현의 복잡성이 증가하는 트레이드오프가 있습니다. 실제 시스템에서는 이러한 방식들을 개선하여 더욱 효율적인 메모리 할당자를 구현합니다. 예를 들어, segregated free list는 다양한 크기의 블록들을 서로 다른 자유 목록에 분리하여 관리하는 방식으로, 효율성과 속도의 균형을 맞추려는 시도 중 하나입니다.
