[CS:APP] 컴퓨터 시스템 9.9 동적 메모리 할당

9.9.6 Implicit Free Lists

실제 할당기는 블록 경계를 구별하고 할당된 블록과 빈 블록을 구별하는 데이터 구조가 필요합니다. 대부분의 할당기는 이 정보를 블록 자체에 내장합니다. 이 경우 블록은 한 워드 헤더, 페이로드 및 추가 패딩으로 구성됩니다. 

 

Figure 9.35에서는 할당 블록과 비할당 블록을 식별하는 헤더를 보여줍니다. 헤더에는 블록의 크기와 할당 비트가 포함됩니다. 할당 비트는 블록이 할당되었는지 여부를 나타냅니다.

Figure 9.36에서는 메모리 블록이 연속된 할당 및 비할당 블록 시퀀스로 구성된 것을 보여줍니다. 비할당 블록은 헤더의 크기 필드에 의해 암묵적으로 연결됩니다.

 

이러한 암시적 비할당 블록 목록의 장점은 간단함입니다. 단점은 할당 블록을 배치하는 데 필요한 검색 비용이 힙에 할당된 및 비할당된 블록의 총 수에 비례한다는 것입니다. 블록 형식은 할당자의 최소 블록 크기를 결정합니다. 할당된 블록이나 비할당 블록은 이 최소값보다 작을 수 없습니다. 더블 워드 정렬 요구 사항을 가정하는 경우, 각 블록의 크기는 2 워드 (8 바이트)의 배수 여야 합니다. 따라서 Figure 9.35의 블록 형식은 최소 블록 크기를 2 워드로 유도합니다.

(1) 메모리 블록의 헤더

동적 할당(dynamic allocation)에서는 메모리 블록의 헤더에 정보를 저장하기 위해 사용됩니다. 

헤더는 블록 크기(헤더 및 패딩을 포함한)와 블록이 할당되었는지 빈 블록인지(할당 여부)를 인코딩합니다. 더블 워드 정렬 제약 조건을 적용하면 블록 크기는 항상 8의 배수이고 블록 크기의 3개 하위 비트는 항상 0입니다. 따라서 블록 크기의 상위 29개 비트만 저장하면 나머지 3비트는 다른 정보를 인코딩하는 데 사용됩니다. 이 경우에는 이 중에서 가장 낮은 비트(할당된 비트)를 사용하여 블록이 할당되었는지 여부를 나타냅니다.

예를 들어 블록 크기가 24바이트(0x18)인 할당된 블록이 있다면 해당 헤더는 0x00000018 | 0x1 = 0x00000019가 됩니다. 마찬가지로 블록 크기가 40바이트(0x28)인 빈 블록은 0x00000028 | 0x0 = 0x00000028의 헤더를 가집니다.

 

"|" 기호는 비트 OR 연산자입니다. 각 비트 별로 OR 연산을 수행하게 되는데, 각 자릿수에서 두 수 중 하나 이상이 1이면 결과값이 1이 됩니다.

0x00000018은 이진수로 00000000 00000000 00000000 00011000으로 표현됩니다. 0x1은 이진수로 00000000 00000000 00000000 00000001로 표현됩니다. 따라서 0x00000018 | 0x1 두 개의 32 비트 값을 OR 연을 수행하면 00000000000000000000000000011001이 됩니다. 이 값을 16진수로 나타내면 0x00000019가 되는 것입니다.(10진수로 25)

 

"0x00000028 | 0x0"은 두 개의 32 비트 값을 OR 연산한 결과를 나타냅니다. 이 경우, 0x00000028 | 0x0은 0000 0000 0000 0000 0000 0000 0010 1000(십진수로 40) = 0x00000028과 같습니다. 이는 빈 블록의 경우 헤더 값이 블록 크기와 정확히 일치함을 의미합니다.

 

 

(2) Implicit Free Lists(묵시적 가용 리스트)

 

(나의 질문) :1. unused 블럭의 목적이 힙의 시작영역을 표시해주면서, 힙 내의 가용 영역이 있어서 추가로 할당가능하다는 표시가 맞을까요? 2. 각 블럭의 크기가 더블 워드 기준으로 정렬된 점선들 표시와 맞아떨어져야 한다고 생각했는데 unused 블록으로 인해, 더블 워드 기준으로 정렬된 점선들 표시와 블럭들마다의 마지막 지점이 엇갈리고 있습니다. 그렇다면, 9.36에서의 점선의 의미를 어떻게 바라봐야 할까요? (조교님 답변) : unused의 용도는 말씀해주신 이유가 아니라, payload부분이 double-word alignment를 맞추도록 하기 위해서입니다. implicit free list 방식에서 첫 4byte는 block header로 사용되고, 유저가 사용할 수 있는 메모리인 payload는 block header를 제외한 나머지 부분입니다. payload부분이 유저가 자유롭게 쓸 수 있는 공간이므로 payload시작지점이 double word alignment가 되길 원하고, 그래서 맨 처음 4byte는 사용하지 않는 겁니다.이 사실은 점선 (double word address 위치) 을 보셔도 잘 알 수 있습니다. 항상 block header의 다음 부분은 점선이 통과합니다.

첫 번째 블록의 헤더는 "8/0"입니다. 이 헤더에서 "8"은 이 블록 전체의 크기를 나타내며, "0"은 이 블록이 현재 사용 가능한 free block임을 나타냅니다.

두 번째 블록은 할당된 블록으로, "16/1" 헤더를 가지고 있습니다. 이 헤더에서 "16"은 이 블록 전체의 크기를 나타내며, "1"은 이 블록이 현재 할당된 상태임을 나타냅니다.

세 번째 블록은 다시 free block으로, "32/0" 헤더를 가지고 있습니다. "32"는 이 블록 전체의 크기를 나타내며, "0"은 이 블록이 현재 사용 가능한 free block임을 나타냅니다.

네 번째 블록은 다시 할당된 블록으로, "16/1" 헤더를 가지고 있습니다.

마지막 칸은 특별히 표시된 종료 블록입니다.

 

implicit free list은 가용 블럭이 헤더 내 필드에 의해 암묵적(묵시적)으로 연결됩니다. 할당자는 힙(heap)의 모든 블록을 탐색함으로써 비어있는 블록의 전체 집합을 간접적으로 탐색할 수 있습니다. 연결 방식으로 특별히 표시된 종료 블록이 필요합니다.

Implicit Free Lists의 장점은 단순성이다. 중요한 단점은 할당된 블록 배치와 같은 빈 블록 목록을 검색하는 모든 작업의 비용이 힙(heap)의 할당된 블록과 빈 블록의 총 수에 비례하여 선형적으로 증가한다는 것입니다.