Lecture 19: Dynamic Memory Allocation: Basic Concepts

Basic Concepts

---

Dynamic Memory Allocation

할당자(Allocator)는 동적 메모리 할당과 해제를 담당하는 객체로, 힙을 다양한 크기의 블록으로 나누어 관리한다. 각 블록은 할당된 상태(Allocated) 또는 할당되지 않은 상태(Free)로 존재한다.

• 명시적 할당자 (Explicit allocator): 애플리케이션이 메모리를 할당하고 해제한다. (예: malloc(), free())
• 암시적 할당자 (Implicit allocator): 애플리케이션이 메모리를 할당하지만, 시스템이 해제한다. (예: 가비지 컬렉션)

malloc() Package

void *malloc(size_t size);

최소 size 바이트의 정렬(Alignment)¹된 메모리 블록을 할당한다. 성공 시 해당 블록을 가리키는 포인터를 반환하고, size == 0이거나 오류 발생 시 null 포인터를 반환한다.

void free(void *ptr);

ptr이 가리키는 메모리 블록을 해제한다. 아무 것도 반환하지 않는다.

그 외에 다른 함수들이 몇 가지 있다.

• calloc(): 메모리를 할당하고 0으로 초기화한다.
• realloc(): 이미 할당된 블록의 크기를 변경한다.
• sbrk(): 힙의 크기를 조절하기 위해 할당자가 내부적으로 사용하는 시스템 콜이다.

자세한 내용은 man 3 malloc, man 2 brk 참고

malloc() Example

#include <stdio.h>
#include <stdlib.h>

int main(int n) {
    int *p;
    /* Allocate a block of n ints */
    p = (int *)malloc(n * sizeof(int));
    if (p == NULL) {
        perror("malloc()");
        return 1;
    }
    /* Initialize allocated block */
    for (int i = 0; i < n; i++)
        p[i] = i;
    /* Return allocated block to the heap */
    free(p);
    return 0;
}

Constraints

할당자에는 다음과 같은 제약 조건이 존재한다.

• 할당된 블록의 크기나 개수를 제어할 수 없다.
• malloc() 요청에 즉시 응답해야 한다.
  • 요청을 일괄적으로 처리하는 것이 더 효율적일 수 있지만, 허용되지 않는다.
• 할당되지 않은 메모리에서 블록을 할당해야 한다.
  • 할당된 블록은 애플리케이션에 속하므로, 할당자가 건드릴 수 없다.
• 블록은 저장된 가장 큰 객체의 크기에 맞춰 정렬되어야 한다.
  • 일반적으로 64비트 시스템에서는 16바이트 정렬, 32비트 시스템에서는 8바이트 정렬을 사용한다.

Performance Goal

할당자의 성능은 처리량(Throughput) 및 최대 메모리 사용률(Peak memory utilization)과 양의 상관관계를 가진다.

처리량은 단위 시간당 처리되는 요청 수를 의미한다.

• 10초 동안 5,000번의 malloc()과 5,000번의 free() 호출이 처리되었다면, 처리량은 1,000 operation/s이다.

할당된 블록에서 데이터를 저장하기 위해 애플리케이션이 요청한 메모리를 페이로드(Payload)라 하며, 할당자의 구현 방식에 따라 추가로 사용되는 메모리를 오버헤드(Overhead)라 한다. 상황을 단순화하기 위해 할당자가 힙의 크기를 줄이지 않고 늘리기만 한다고 가정하면, $k$번째 요청 후의 최대 메모리 사용률 $U_k$는 다음과 같다.

• $P$ : 총 페이로드 (현재 할당된 모든 블록의 페이로드 합)
• $H$ : 현재 힙 크기

\[U_k = \frac{max_{i \leq k} \ P_i}{H_k}\]

최선의 경우, 할당된 각 블록이 오직 페이로드만으로 구성되어 메모리 사용률은 1이 된다. 하지만 실제로는 블록에 할당자의 자료 구조와 패딩이 포함되므로, 100%의 메모리 사용률을 달성하기 어렵다. 16바이트 정렬을 사용하는 시스템에서 2바이트의 페이로드를 요청하면, 많은 바이트가 낭비되어 메모리 사용률이 감소한다.

Fragmentation

단편화(Fragmentation)가 발생하면, 메모리 사용률이 감소한다.

내부 단편화 (Internal fragmentation)

• 페이로드의 크기가 블록보다 작은 경우이다. (오버헤드 존재)
• 과거의 메모리 요청 내역(페이로드 크기)을 통해 쉽게 파악할 수 있다.

외부 단편화 (External fragmentation)

• 전체적으로는 충분한 공간이 있으나, 분산되어 있어 할당이 불가능한 경우이다.
• 메모리 할당과 해제를 반복하면서 빈 공간이 여러 곳으로 흩어지며 발생한다.
• 할당자는 힙을 확장하여 충분히 큰 free 블록을 확보해야 한다.
• 미래의 메모리 요청에 의존적이므로 파악하기 어렵다.

Knowing Block Size

할당자는 할당 및 해제할 블록의 크기를 알아내기 위해, 각 블록의 앞에 블록 크기를 나타내는 헤더(Header)를 유지한다.

Word offset from ptr	-1		0	1		2		3
Block	5		Payload	—	—	—	—	—	→

Keeping Track of Free Blocks

• Implicit free list: 별도의 리스트 없이, 헤더의 블록 크기 정보를 통해 힙의 모든 블록을 순회하면서 free 블록을 식별한다. 간단하지만, 효율성이 떨어질 수 있다.
• Explicit free list: Free 블록을 연결 리스트로 관리한다. 암시적인 방식보다 효율적일 수 있지만, 추가적인 메모리 공간이 필요하다.
• Segregated free list: Free 블록의 크기에 따라 여러 개의 연결 리스트로 분리하여 관리한다. 이를 통해, 특정한 크기의 블록을 찾는 과정을 최적화할 수 있다.
• Blocks sorted by size: 트리를 이용하여, free 블록을 크기 순으로 정렬한다.

Implicit Free Lists

---

암시적 리스트를 구축하기 위해, 각 블록의 크기 및 할당 상태 정보가 필요하다. 블록이 워드 크기의 2배 단위로 정렬되어 있다면, 블록 크기가 짝수이므로 최하위 비트는 항상 0이다. 이러한 사용되지 않는 비트에 할당 상태를 저장함으로써, 하나의 워드(헤더)에 두 정보를 함께 저장할 수 있다.

Detailed Implicit Free List Example

4바이트 워드와 8바이트 정렬을 사용하는 시스템을 살펴보자.

Word offset	0		2		4		6		8		10		12
Heap	P	2/0		4/1	L	L	P	6/0						0/1

• 헤더는 블록 크기/할당 상태를 나타내며, L은 페이로드, P는 패딩을 의미한다.
• 블록의 페이로드가 8바이트 경계에 정렬되어야 하기에, 중간중간에 패딩이 존재하는 것을 볼 수 있다.
  • 할당된 블록의 경우, 패딩이 추가됨으로써 내부 단편화가 발생한다.
• 마지막에 크기가 0인 할당된 블록이 존재하여, 리스트의 끝임을 나타낸다.

Implicit List: Finding a Free Block

• First fit: 리스트의 처음부터 탐색하며, 크기가 충분한 첫 번째 free 블록을 선택한다. 단순해서 구현이 쉽지만, 메모리 단편화를 초래할 수 있다.
• Next Fit: First fit과 유사하지만, 매번 처음부터 탐색하는 대신 마지막으로 중단한 지점에서 탐색을 시작한다. 하지만 first fit보다 심한 단편화를 초래할 수 있다.
• Best Fit: 요청된 페이로드와 가장 크기가 비슷한 free 블록을 찾는다. 메모리 사용률이 높지만, 모든 free 블록을 탐색해야 하므로 실행 속도가 느리다.

Implicit List: Allocating in Free Block

할당 요청에 알맞은 free 블록을 찾았다면,

• 블록 전체를 할당하거나

• 블록을 분할하여 필요한 만큼만 할당할 수 있다.

  void add_block(ptr p, int len) {
      int old_size = *p & -2;                     // Mask out low bit
      int new_size = ((len + 1) >> 1) << 1;       // Round up to even
      *p = new_size | 1;                          // Set new header
      if (new_size < old_size)
          *(p + new_size) = old_size - new_size;  // Split the block
  }
  

Implicit List: Freeing a Block

할당자는 해제 요청을 받으면, 해당 블록의 할당 상태를 나타내는 플래그를 0으로 설정하여 블록을 해제한다. 그런데 이렇게 블록을 해제하면, 외부 단편화 문제가 발생할 수 있다.

Word offset	0		2		4		6		8		10		12
Heap	P	2/0		4/0				6/0						0/1

메모리가 충분하고 연속적이라 할지라도, 할당자는 free 블록들이 인접해 있다는 사실을 알지 못한다.

Implicit List: Coalescing

따라서 할당 해제 시 인접한 free 블록들을 병합하여, free 블록 뒤에 항상 할당된 블록이 오도록 해야 한다.

void free_block(ptr p) {
    *p &= -2;         // Clear allocated flag
    next = p + *p;    // Find next block
    if ((*next & 1) == 0)
        *p += *next;  // Coalesce with next block
}

하지만 리스트가 단방향이기 때문에, 이전 블록을 확인하기가 어렵다. 불가능한 건 아니지만, free()의 시간복잡도가 힙의 크기에 비례하게 되므로 매우 비효율적이다.

Implicit List: Bidirectional Coalescing

이를 해결하기 위해, 헤더와 동일한 정보를 담고 있는 푸터(Footer)를 추가하여 일종의 양방향 리스트를 구성한다. 이러한 푸터를 경계 태그(Boundary tag)라 한다.

• 경계 태그를 위한 추가 공간이 필요하지만, 상수 시간에 이전 블록을 확인하고 병합할 수 있다.
• 페이로드의 일부가 아니므로 오버헤드에 해당하며, 이는 추가적인 내부 단편화를 유발한다.
• 할당된 블록은 병합할 필요가 없으므로 경계 태그가 필요하지 않다. 대신 헤더의 하위 비트를 활용하여 이전 블록의 할당 상태를 저장한다.
  • 블록이 워드 크기의 4배 단위로 정렬되어 있다면, 헤더의 하위 2비트가 남게 되므로 현재 블록과 이전 블록의 할당 상태를 각각 저장할 수 있다.

References

---

• Carnegie Mellon University. (2015). Lecture 19: Dynamic Memory Allocation: Basic Concepts. [Online].

Footnote

1. “Lecture 08: Machine-Level Programming IV: Data.” 고볼. [Online]. ↩︎