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

모든 실용적인 할당기는 블록 경계를 구분하고 할당된 블록과 비어 있는 블록을 구분할 수 있도록 하는 자료구조를 필요로 한다. 이때 대부분의 할당기는 이 정보를 블록 내부에 직접 포함시킨다.