9.9.13 암묵적 Free Lists

암묵적 Free List는 우리에게 몇 가지 기본적인 할당자 개념을 도입할 수 있는 간단한 방법을 제공한다. 그러나 블록 할당 시간은 힙 블록의 총 수에 선형적이기 때문에 암묵적 Free List는 범용 할당자로 적합하지 않다.(힙 블록의 수가 적다고 미리 알려진 특수 목적의 할당자에는 괜찮을 수 있음).
-> 암묵적 Free List의 한계.

    더 나은 접근법은 Free 블록들을 명시적인 데이터 구조의 어떤 형태로든 구성하는 것이다. 정의에 의해 Free 블록의 본문은 프로그램에 의해 필요하지 않기 때문에, 데이터 구조를 구현하는 포인터들은 Free 블록의 본문 내에 저장될 수 있다. 예를 들어, 힙은 그림 9.48과 같이 Free 블록에 pred(사전)와 succ(후계) 포인터를 포함함으로써 이중 링크된 Free List로 구성할 수 있다.
-> 명시적 Free List의 기본 원리

    암묵적 Free List 대신 이중 링크된 List을 사용하면, First-fit 할당 시간이 전체 블록 수의 선형에서 Free 블록 수의 선형으로 단축된다. 그러나 블록을 Free 시키는 시간은 Free List에서 블록을 정렬하기 위해 선택한 정책에 따라 선형이거나 상수일 수 있다.

    한 가지 방법은 List 시작 부분에 새로 Free된 블록을 삽입하여 LIFO(Last-In First-Out) 순서로 List를 유지하는 것이다. LIFO 순서 지정 및 First-fit placement 정책을 통해 할당자는 가장 최근에 사용된 블록을 먼저 검사한다. 이 경우 일정한 시간에 블록을 해제할 수 있다. 경계 태그를 사용하는 경우 일정한 시간에 병합을 수행할 수도 있다.

    또 다른 접근법은 List 의 각 블록의 주소가 후속 블록의 주소보다 작은 주소 순서로 List를 유지하는 것이다. 이 경우 블록을 해제하려면 적절한 이전 블록을 찾기 위해 선형 시간 검색이 필요하다. 단점은 address-ordered first-fit 이 LIFO-ordered first-fit보다 메모리 활용도가 더 뛰어나기 때문에 best-fit 의 최적화에 근접하다는 것이다.

    일반적으로 명시적 Lists의 단점은 Free 블록이 Header와 Footer뿐만 아니라 필요한 포인터를 모두 포함할 수 있을 만큼 충분히 커야 한다는 것이다. 따라서 최소 블록 크기가 커지고 내부 조각화의 가능성이 커진다.

9.9.14 Segregated Free Lists

지금까지 살펴본 바와 같이, Free 블록의 링크된 단일 List를 사용하는 할당자는 블록을 할당하기 위해 Free 블록의 수에 있어 시간 선형이 필요하다. 할당 시간을 줄이기 위한 일반적인 접근 방식(일반적으로 Segregated Storage라고 함)은 여러 개의 사용 가능한 Lists들을 유지하는 것이다. 각 List는 크기가 거의 동일한 블록을 보관한다. 일반적인 아이디어는 가능한 모든 블록 크기의 집합을 size 클래스라고 하는 동등성 클래스로 분할하는 것이다. size 클래스를 정의하는 방법은 여러 가지가 있다. 예를 들어 블록 크기를 2의 거듭제곱으로 분할할 수 있다.

{1}, {2}, {3, 4}, {5–8}, . . . , {1,025–2,048}, {2,049–4,096}, {4,097–∞}
또는 작은 블록을 자체 크기 클래스에 할당하고 큰 블록을 분할할 수도 있다.
2의 powers:
{1}, {2}, {3}, . . . , {1,023}, {1,024}, {1,025–2,048}, {2,049–4,096}, {4,097–∞}

    할당자는 크기 클래스당 하나씩의 Free Lists 배열을 크기 순서대로 유지 관리한다. 할당자에게 n 크기의 블록이 필요한 경우 적절한 Free List를 검색한다. 적합한 블록을 찾을 수 없으면 다음 리스트를 검색하는 방식으로 진행된다.

    동적 스토리지 할당 문헌에는 size 클래스를 정의하는 방법, 병합을 수행할 때, 운영 체제에 추가 힙 메모리를 요청할 때, 분할 허용 여부 등이 서로 다른 수십 가지 유형의 세분화된 스토리지가 설명되어 있다. 어떤 것이 가능한지에 대한 이해를 돕기 위해 간단한 segregated storage와 segregated fits의 2가지 기본 접근 방식에 대해 설명한다.

Simple Segregated Storage

단순 segregated storage를 사용하면 각 size 클래스의 사용 가능한 list에는 size 클래스의 가장 큰 요소 size인 동일한 size의 블록이 포함된다. 예를 들어 일부 size 클래스가 {17-32}로 정의되어 있으면 해당 클래스의 Free list는 size가 32인 블록으로 모두 구성된다.

    주어진 size의 블록을 할당하기 위해 적절한 Free List를 확인한다. List가 비어 있지 않으면 첫 번째 블록을 모두 할당한다. 할당 요청을 충족하기 위해 여유 블록은 분할되지 않는다. List가 비어 있으면 할당자는 운영 체제에 고정 size의 추가 메모리 CHUNK를 요청하고(일반적으로 페이지 크기의 배수), CHUNK를 동일한 크기의 블록으로 나눈 다음 블록을 함께 연결하여 새로운 Free List를 만든다. 블록을 해제하려면 할당자가 해당 Free List의 맨 앞에 블록을 삽입하기만 하면 된다.

    이 간단한 계획에는 많은 장점이 있다. 블록 할당 및 해제 작업은 모두 빠른 상수 시간 작업이다. 또한 각 CHUNK에 동일한 크기의 블록이 조합되고 분할되지 않으며 병합되지 않는다는 것은 블록당 메모리 오버헤드가 매우 적다는 것을 의미한다. 각 청크는 동일한 크기의 블록만 가지고 있기 때문에 할당된 블록의 크기는 주소에서 추론할 수 있다. 병합이 없기 때문에 할당된 블록은 헤더에 할당/해제 플래그를 필요로 하지 않는다. 따라서 할당된 블록에는 Header가 필요하지 않으며 병합이 없으므로 Footer도 필요하지 않는다. 할당 및 Free 연산은 Free List의 시작 부분에 블록을 삽입하고 삭제하기 때문에 List는 이중으로 링크되지 않고 단일 링크만 하면 된다. 결론적으로 블록에서 필요한 유일한 필드는 각 Free 블록에 있는 하나의 단어 succ pointer이며, 따라서 최소 블록 크기는 단 하나의 단어이다.

    중요한 단점은 simple segregated storage 는 내부 및 외부 단편화에 취약하다는 것이다. 내부 단편화가 가능한 것은 Free 블록이 절대 분할되지 않기 때문이다. 설상가상으로, 특정 기준 패턴은 Free 블록이 결코 병합되지 않기 때문에 극단적인 외부 단편화를 야기할 수 있다.

Segregated Fits

이 접근 방식을 통해 할당자는 Free Lists의 배열을 유지한다. 각 Free Lists는 size 클래스와 연결되며 명시적 또는 암묵적 Lists로 구성된다. 각 리스트에는 크기가 size 클래스의 구성원인 서로 다른 크기의 블록이 포함되어 있다. Segregated Fits에는 많은 변종이 있다. 여기서는 단순한 버전을 설명한다.

    블록을 할당하기 위해 요청의 size 클래스를 결정하고 적합한 블록에 대한 적절한 Free List를 먼저 검색한다. 하나를 찾으면 (선택적으로) 분할하여 적절한 Free List에 fragment를 삽입한다. 적합한 블록을 찾을 수 없으면 다음으로 큰 크기의 클래스를 free list로 검색합니다. 우리는 맞는 블록을 찾을 때까지 반복한다. Free Lists에 적합한 블록이 없으면 운영 체제에 추가 힙 메모리를 요청하고 이 새 힙 메모리에서 블록을 할당한 후 나머지를 적절한 size 클래스에 배치한다. 블록을 해제하기 위해 결과를 병합하여 적절한 Free List에 넣는다.

    Segregated Fits 접근법은 빠르고 메모리 효율적이기 때문에 C 표준 라이브러리에서 제공되는 GNU malloc 패키지와 같은 생산 품질 할당자들에게 인기가 있는 선택이다. 검색이 전체 힙이 아닌 힙의 특정 부분으로 제한되기 때문에 검색 시간이 단축된다. 분리된 Free List에 대한 단순한 first-fit 검색이 전체 힙에 대한 가장 적합한 검색에 가깝다는 흥미로운 사실 때문에 메모리 활용도가 향상될 수 있다.