가용 리스트

가용 리스트

가용 리스트는 메모리 할당 및 해제를 관리하기 위한 자료구조이며,
동적으로 할당될 수 있는 메모리 블록을 추적하는 데 사용된다.
즉, 전에 할당되었지만 반환되어 가용 가능한 메모리 블록에 대한 정보를 저장한다.
가용 리스트는 일반적으로 운영 체제의 메모리 관리자 또는 프로그래밍 언어의 런타임 시스템에서 사용된다.

명시적 가용 리스트

명시적 가용 리스트에서의 반환된 모든 메모리 블럭은 포인터 또는 참조 등의 추가적인 정보를 가지고 있으며, 이는 다음 가용 가능한 메모리 블록을 명시적으로 나타낸다.
명시적 가용 리스트는 연결 리스트 또는 다른 자료구조를 유지하며, 해당 자료구조의 각 노드에게 반환된 메모리 블록을 나타내게 함으로 다음의 가용 가능 메모리 블록을 가르키게 한다.
메모리 블록이 반환되는 시점에 할당기는 적절한 포인터 또는 참조를 갱신하여 해당 블록을 명시적 가용 리스트에 추가한다.
메모리를 할당하기 위해 할당기는 명시적 가용 리스트를 탐색하여 충분한 크기의 메모리 블록을 찾고, 해당 메모리 블록을 가용 리스트에서 제거한 후 메모리를 요청한 프로세스에 할당한다.

묵시적 가용 리스트

묵시적 가용 리스트에서는 할당기가 할당 및 반환된 메모리 블록을 명시적인 포인터 또는 참조 없이 관리한다.
반환된 메모리 블록은 직접적인 포인터나 참조 대신 힙 내에서의 각각의 크기와 위치로 구분된다.
메모리 블록이 반환되는 시점에 할당기는 이를 가용 가능한 것으로 표시하며 인접한 반환된 블록들과 합쳐 더 큰 가용 가능한 블록을 만든다. 메모리를 할당하기 위해 할당기는 해당 태스크에 사용되기 적절한 메모리 블록을 찾기 위해 크기와 위치를 고려하여 힙을 탐색 및 찾은 후 메모리를 할당한다.

차이

명시적 가용 리스트와 묵시적 가용 리스트의 주요 차이는 가용 가능한 메모리 블록들의 정보를 관리하는 방식에 있다.
명시적 가용 리스트는 직접적인 포인터 또는 참조를 사용하여 반환된 메모리 블록을 연결하여 관리하며, 추가적인 포인터 또는 참조를 저장해야 하기 때문에 일반적으로 더 많은 메모리를 필요로 한다.
이에 반해, 묵시적 가용 리스트는 힙 내에서의 메모리 블록의 위치와 크기에 의존하여 메모리의 가용 가능성을 판단하며,
메모리 할당 시 적절한 메모리 블록을 찾기 위해 더 많은 시간(계산)이 필요하다 (힙이 파편화되어 있으면 더욱 그렇다).