Dynamic Memory Allocation

상위 문서: 컴퓨터 시스템

개요

Figure 1. The heap

프로그래머들은 가상 메모리(virtual memory)를 습득하고 사용해야 할때, malloc() 함수와 같은 동적 메모리 할당기(dynamic memory allocator)를 사용한다. 동적 메모리 할당기는 프로세스의 가상 메모리 내에 있는 (heap)이라고 불리는 영역을 관리한다. 이때 각 프로세스마다 커널은 힙의 맨위를 가리키는 brk라고 하는 변수를 유지한다. Figure 1은 가상 메모리를 시각적으로 보여준다.

동적 메모리 할당기는 힙을 크기가 다양한 블록 들의 집합으로 유지한다. 이때 각 블록은 연속적인 가상 메모리 조각이며, 할당되었거나(allocated) 비어있다(free). 할당된 블록은 애플리케이션에 의해 명시적으로 사용하기 위해 예약된 블록이다. 또한 비어 있는 블록(free block)은 할당이 가능한 상태이며, 애플리케이션에 의해 명시적으로 할당될 때까지는 계속 비어 있는 상태로 남는다. 할당된 블록은 애플리케이션이 명시적으로 free 하거나, 메모리 할당기 자체가 암묵적으로 해제할 때까지는 계속 할당된 상태이다.

동적 메모리 할당기는 두 가지의 기본적인 스타일로 나뉜다. 이때 두 스타일 모두 애플리케이션이 명시적으로 블록을 할당해야 한다는 점은 공통되며, 할당된 블록을 누가 해제하는지에 따라 차이가 있다:

• 명시적 할당기(explicit allocators): 애플리케이션이 할당한 블록을 명시적으로 해제해야 한다.
  • 예를 들어, C 표준 라이브러리의 malloc 패키지가 이에 해당한다. C 프로그램은 malloc() 함수를 호출해 블록을 할당하고, free() 함수를 호출해 블록을 해제한다. C++의 new와 delete 호출도 이와 유사하다.
• 암시적 할당기(implicit allocators): 애플리케이션이 더 이상 할당된 블록을 사용하지 않게 되었음을 할당기가 감지해서 자동으로 해제한다.
  • 암시적 할당기는 가비지 컬렉터(garbage collectors)라고도 불리며, 사용되지 않는 할당된 블록을 자동으로 해제하는 과정을 가비지 컬렉션(garbage collection)이라고 한다.
  • 예를 들어, Lisp, ML, Java 같은 고급 언어들은 가비지 컬렉션에 의존해서 할당된 블록을 해제한다.

하지만, 해당 문서에서는 명시적 할당기의 설계와 구현에 대해 논의한다. 또한 앞으로 word 사이즈는 int를 기준으로 하고, 바이트가 아닌, 워드 단위로 주소를 사용한다고 가정한다.

The malloc and free Functions

C 표준 라이브러리는 malloc 패키지로 알려진 명시적 할당기를 제공한다. 프로그램은 malloc 함수를 호출하여 힙에서 블록을 할당한다:

#include <stdlib.h>
void *malloc(size_t size); //반환값: 성공하면 할당된 블록을 가리키는 포인터, 실패하면 NULL 반환

malloc() 함수는 size 바이트 크기의 메모리 블록을 반환하며, 해당 블록에 포함될 수 있는 데이터 객체가 적절하게 정렬(alignment)되도록 한다. 실제로 이 정렬 방식은 코드가 32비트 모드(gcc -m32)로 컴파일되었는지 64비트 모드로 컴파일 되었는지에 따라 달라진다. 32비트 모드에서는, malloc이 반환하는 블록의 주소는 항상 8의 배수이고, 64비트 모드에서는, 그 주소가 항상 16의 배수이다(바이트 기준).

만약 초기화된 동적 메모리가 필요한 경우, 프로그램은 calloc() 함수를 사용할 수 있으며, calloc() 함수는 내부적으로 malloc을 호출하고 할당된 메모리를 0으로 초기화한다. 이미 할당된 블록의 크기를 변경하고 싶은 경우에는, realloc() 함수를 사용하면 된다. malloc을 통해 동적으로 할당된 공간을 해제하고자 할때는, free() 함수를 이용하면 된다:

#include <stdlib.h>
void free(void *ptr); //반환값 없음

Figure 2. Allocating and freeing blocks with malloc and free

이때 ptr 인자는 malloc, calloc, 또는 realloc을 통해 할당된 블록의 시작 주소를 가리켜야 한다. 그렇지 않은 경우, free의 동작은 정의되지 않는다(undefined behavior). Figure 2는 malloc과 free가 어떻게 작은 힙을 관리할 수 있는지를 보여준다. 이때 각 상자는 4바이트 워드를 나타내며, 따라서 해당 시스템은 32비트 시스템이다. 초기에는 힙이 더블 워드(8바이트) 정렬되어 있는 빈 메모리 공간이다:

1. Figure 2(a)에서는 프로그램이 4워드 블록을 요청한다. malloc은 비어 있는 블록의 앞쪽에서 4워드를 잘라 새 블록으로 만들고, 그 첫 번째 워드의 주소를 반환한다.
2. Figure 2(b)에서는 프로그램이 5워드 블록을 요청한다. 정렬을 유지하기 위해 malloc은 앞쪽에서 6워드 블록을 할당해준다.
3. Figure 2(c)에서는 프로그램이 6워드 블록을 요청하고, malloc은 비어 있는 블록에서 6워드를 잘라서 할당한다.
4. Figure 2(d)에서는 프로그램이 (b)에서 할당된 6워드 블록을 해제한다. free 호출이 끝난 후에도, 포인터 p2는 여전히 해제된 블록을 가리킨다.
   • 포인터 p2를 사용하지 않는 것은 애플리케이션에게 달려있다.
5. Figure 2(e)에서는 프로그램이 2워드 블록을 요청한다. malloc은 이전 단계에서 해제된 블록 중 일부를 재사용하여 새 블록을 할당하고, 해당 주소를 반환한다.

Allocator Requirements and Goals

Allocator Requirements

명시적 할당기(explicit allocator)는 몇 가지 매우 엄격한 제약 조건 내에서 동작해야 한다:

1. 임의의 요청 시퀀스를 처리해야 한다.
   • 애플리케이션은 임의의 할당 및 해제 요청 시퀀스를 만들 수 있으며, 단 각 해제 요청은 이전의 할당 요청으로부터 얻은 현재 할당된 블록에 해당해야 한다는 제약을 가진다. 따라서, 할당기는 할당과 해제 요청의 순서에 대해 어떤 가정도 할 수 없다.
2. 할당기는 할당 요청에 즉시 응답해야 한다.
   • 즉, 성능 향상을 위해 요청을 재정렬하거나 버퍼링하는 것은 허용되지 않는다.
3. 할당기가 확장 가능(scalable)하려면, 할당기에서 사용하는 모든 비스칼라(nonscalar) 자료구조는 힙 내에 저장되어야 한다.
4. 할당기는 블록을 어떤 타입의 데이터 객체든 담을 수 있도록 정렬해서 제공해야 한다.
5. 할당기는 비어 있는(free) 블록만 조작하거나 변경할 수 있으며, 한 번 할당된 블록은 수정하거나 이동할 수 없다.

Allocator Goals

이러한 제약 조건 안에서, 할당기 설계자는 성능 목표들, 즉 처리량(throughput)과 메모리 활용률(utilization)을 달성해야 한다. 하지만 이 둘은 종종 상충하는 목표이다.

어떤 길이 n을 가지는 할당 및 해제 요청 시퀀스 R₀, R₁, ..., R_k, ..., R_n-1이 주어졌을 때, 할당기의 처리량을 최대화해야 한다. 이때 처리량은 단위 시간당 처리한 요청 수로 정의된다. 예를 들어, 어떤 할당기가 1초 동안 malloc 500회, free 500회를 처리했다면, 그 처리량은 초당 1,000개의 연산이다. 일반적으로, 처리량을 높이기 위해서는 할당 및 해제 요청을 처리하는 평균 시간을 최소화해야 한다.

힙을 얼마나 효율적으로 사용하는지 측정하는 방법은 여러 가지가 있지만, 가장 유용한 척도는 최고 활용률(peak utilization)이다. 앞과 같이 할당 및 해제 요청 시퀀스 R₀, R₁, ..., R_k, ..., R_n-1이 주어졌다고 하자. 이때 애플리케이션이 p 바이트 크기의 블록을 요청했다면, 그 결과 할당된 블록에서 p 바이트는 payload에 해당한다. 요청 R_k까지 완료된 후, 현재 할당된 모든 블록의 payload 총합을 P_k라고 하고, 힙의 현재 크기를 H_k라고 하자. 이 경우 그러면, 첫 k+1개 요청에 대한 최고 활용률 U_k는 다음과 같이 정의된다:

Uk = (maxi<=k{Pi})/Hk 

Fragmentation

힙 활용률이 낮은 주요한 원인은 단편화(fragmentation)이라고 알려진 현상 때문이다. 단편화는 실제로 사용되지 않는 메모리가 존재함에도 불구하고 할당 요청을 만족시킬 수 없는 상황에서 발생한다. 이때 단편화에는 두 가지 형태가 있다:

• 내부 단편화(internal fragmentation)
• 외부 단편화(external fragmentation)

Internal Fragmentation

내부 단편화는 할당된 블록의 크기가 그 payload보다 큰 경우 발생한다. 이러한 현상은 여러 이유로 인해 발생할 수 있다. 예를 들어:

• 동적 메모리 할당기가 요청된 payload보다 큰 최소 블록 크기를 강제하도록 강제하였다.
• 동적 매모리 할당기가 정렬 조건을 만족시키기 위해 블록 크기를 늘릴 수도 있다.

이때 어떤 시점에서의 내부 단편화로 인한 낭비되는 메모리의 양은 이전 요청의 패턴과 할당기 구현 방식에만 의존하므로 정량화(quantify)가 간단하다. 이는 할당된 각 블록의 크기와 그 payload의 차이를 모두 합한 것이다.

External Fragmentation

외부 단편화는 전체 비어 있는 메모리 총량은 충분하지만, 어떤 단일한 free 블록도 요청된 크기를 만족시킬 만큼 크지 않은 경우에 발생한다. 예를 들어, figure 2에서 (e)의 요청이 2워드가 아니라 8워드였다면, 힙에는 총 8워드의 free 메모리가 있지만, 두 개의 작은 free 블록으로 나뉘어 있기 때문에 요청을 만족시킬 수 없다. 이 문제는, 그 8워드가 서로 다른 두 블록에 분산되어 있기 때문에 발생한다. 따라서 외부 단편화는 내부 단편화보다 훨씬 정량화하기 어려운데, 이는 이전 요청 패턴, 할당기 구현, 미래 요청 패턴 모두에 의존하기 때문이다. 예를 들어, k번의 요청 이후 모든 free 블록이 정확히 4워드 크기라고 가정하면, 해당 힙이 외부 단편화를 겪고 있는가에 대한 질문의 답은 미래 요청 패턴에 따라 달라진다. 만약 앞으로의 모든 요청이 4워드 이하라면, 외부 단편화는 없다. 하지만 하나라도 4워드 초과 요청이 발생한다면, 힙은 외부 단편화를 겪고 있다고 할 수 있다.

Implementation Issues

가장 단순하게 상상할 수 있는 할당기는, 힙을 바이트 배열로 구성하고, 포인터 p를 사용해 그 배열의 첫 번째 바이트를 가리키도록 하는 것이다:

1. malloc이 size 바이트를 할당할 때, 현재 p의 값을 스택에 저장하고,
2. p를 size만큼 증가시킨 다음,
3. 이전의 p 값을 호출자에게 반환한다.
4. free는 단순히 아무 작업도 하지 않고 호출자에게 복귀한다.

하지만 이는 단순히 너무 naive하다. 각 malloc과 free가 몇 개의 명령어만 실행하기 때문에, 처리량은 매우 우수할지 몰라도, 블록을 전혀 재사용하지 않기 때문에, 메모리 활용률(memory utilization)은 매우 나쁘다. 현실적인 할당기는 처리량과 메모리 활용률 사이의 더 나은 균형을 추구해야 하며, 다음과 같은 문제들을 고려해야 한다:

• Free block 조직 (Free block organization): 비어 있는 블록들을 어떻게 추적할 것인가?
• 배치 (Placement): 새롭게 할당할 블록을 어떤 free 블록에 배치할 것인가?
• 분할 (Splitting): 어떤 free 블록에 새로 할당된 블록을 배치한 후, 남는 공간은 어떻게 처리할 것인가?
• 병합 (Coalescing): 방금 해제된 블록은 어떻게 처리할 것인가? 인접한 free 블록들과 합칠 것인가?

Implicit Free Lists

Figure 3. Format of a simple heap block

모든 실용적인 할당기는 블록 경계를 구분하고 할당된 블록과 비어 있는 블록을 구분할 수 있도록 하는 자료구조를 필요로 한다. 이때 대부분의 할당기는 이 정보를 블록 내부에 직접 포함시킨다. Figure 3은 이에 대한 한 간단한 접근 방식이다. 이 경우 하나의 블록은 다음과 같은 구성으로 이루어진다:

• 1워드짜리 헤더(header)
• 헤더는 블록의 전체 크기(헤더 포함)와, 해당 블록이 할당되어있는지의 여부를 나타낸다.
• payload(추가적인 padding이 있을 수 있음)

만약 더블 워드 정렬(double-word alignment) 조건을 강제한다면, 블록 크기는 항상 8의 배수가 되고, 따라서 블록 크기의 하위 3비트는 항상 0이다. 이 경우, 우리는 상위 29비트에 블록 크기 정보를 저장하고, 남은 하위 3비트 중 일부를 다른 정보(예: 할당 여부)에 사용할 수 있다. 예를 들어, 24바이트 크기(0x18)의 할당된 블록이 있다면, 헤더는 (0x00000018 | 0x1) = 0x00000019와 같이 구성된다. 헤더 뒤에는 malloc 호출 시 애플리케이션이 요청한 payload가 따라오며, 그 뒤에는 padding이 올 수 있다. 이러한 padding은 외부 단편화를 완화하기 위해서 혹은 정렬 조건을 만족시키기 위해 사용될 수도 있다.

Figure 4. Organizing the heap with an implicit free list

Figure 3를 바탕으로 하는 블록의 형식을 기준으로, 힙을 figure 4와 같이 할당 블록과 비어 있는 블록의 시퀀스로 구성할 수 있다. 이러한 구성을 implicit free list라고 부르는데, free 블록들이 헤더의 size 필드를 통해 암시적으로 연결되어 있기 때문이다. 따라서 할당기는 힙 내의 모든 블록을 순회함으로써, 간접적으로 모든 free 블록들을 탐색할 수 있다. 이때 특별히 표시된 종료 블록(end block)이 필요하다. 이 예에서는, 할당 비트가 설정되고 크기가 0인 헤더가 끝을 나타낸다.

이때 중요한 점은, 시스템의 정렬 요구 사항과 할당기가 선택한 블록 형식이 동적 메모리 할당기에서 허용할 수 있는 최소 블록 크기를 결정한다는 것이다.즉, 어떤 블록도 이 최소 크기보다 작을 수 없다. 예를 들어, 더블 워드 정렬을 만족해야 한다면, 각 블록의 크기는 반드시 2워드(8바이트)의 배수여야 한다. figure 3를 기준으로는 최소 블록 크기는 2워드이며, 하나는 헤더용으로, 다른 하나는 정렬 조건을 유지하기 위한 용도이다. 즉 애플리케이션이 1바이트만 요청하더라도, 할당기는 2워드짜리 블록을 생성한다.

Implicit List: Finding a Free Block

Implicit free list의 장점은 매우 단순하다는 것이다. 하지만 free 리스트를 탐색하는 연산을 수행할 때 힙 내 모든 할당/비어 있는 블록 수에 대해 선형 시간(linear time)이 걸린다는 단점이 있다. 이때, implicit free list에서 free 블록을 탐색하는 배치 정책(placement)에는 3가지 방식이 있다.

첫번째 방식은 처음부터 순차적으로 탐색하여, 처음으로 맞는(fit) 빈 블록을 사용하는 first fit방식이다. 이는 아래와 같은 코드를 사용한다.

p = start;
while ((p < end) &&            // 끝까지 가지 않았고
      ((*p & 1) ||             // *p & 1 : 이 비트가 1이면 할당된 블록
       (*p <= len)))           // *p & -2 : 블록의 실제 크기 (하위 1비트 제거 → alignment 맞추기)
    p = p + (*p & -2);         // 다음 블록으로 이동 (정렬 비트 제거)

이 방식의 장점은 리스트 끝 부분에 큰 free 블록을 보존하는 경향이 있다는 것이다. 하지만 리스트 앞 부분에 작은 free 블록 조각(splinter)가 생기기 쉽다는 단점도 존재한다.

또다른 방식으로는 next fit 방식이 있는데, 이는 first fit과 비슷하지만, 이전 탐색이 끝난 지점부터 다시 시작하는 방식이다. 이는 앞쪽에 이미 안 맞는 블록을 다시 확인하지 않는다는 장점이 존재하지만, 일부 연구에서는 단편화(fragmentation)를 조장한다는 단점이 있다.

마지막으로 best fit이라는 방식도 있는데, 이는 전체 리스트를 끝까지 탐색해, 가장 딱 맞는 블록을 선택하는 방식이다. 이는 작은 free 블록 조각을 감소시켜 메모리 활용도가 증가한다는 장점이 있지만, 탐색 비용이 크다는 단점이 있다. 힙 전체를 탐색하지 않고도 best-fit 정책을 근사적으로 구현하기 위해서는 구분된 free 리스트(segregrated free list) 방식을 사용해야 한다.

Splitting Free Blocks

할당기가 요청에 맞는 free 블록을 찾고 나면, 그 후에는 그 free 블록 중 얼마나 할당할지에 대한 결정을 내려야 한다. 한 가지 선택지는 free 블록 전체를 사용하는 것이다. 이는 단순하고 빠르지만 내부 단편화(internal fragmentation)를 초래할 수 있다는 단점이 있다. 만약 배치 정책이 best fit과 같이 요청한 크기에 거의 딱 맞는 free 블록을 자주 찾아낸다면 어느 정도의 내부 단편화는 감수할 수 있다.

Figure 5. Splitting a free block to satisfy a three-word allocation request

하지만 그렇지 않은 경우, 동적 메모리 할당기는 free 블록을 두 부분으로 분할한다. 첫 번째 부분은 할당된 블록이 되고, 나머지 부분은 새로운 free 블록이 된다. Figure 5는 Figure 3의 8워드짜리 free 블록을 어떻게 분할하는지에 대해 보여준다.