9.9 동적 메모리 할당

동적 메모리 할당기는 힙(heap)이라고 하는 프로세스의 가상메모리 영역을 관리한다.

일반화의 오류를 범하지 않는 한도에서 힙이 미초기화된 데이터 영역 직후에 시작해서 위쪽으로(높은 주소 방향으로) 커지는 무요구 메모리 영역이라고 가정한다.

각각의 프로세스에 대해서, 커널은 힙의 꼭대기를 가리키는 변수 brk를 사용한다.

할당기는 힙을 다양한 크기의 블록들의 집합으로 관리한다. 각 블록은 할당되었거나 가용한 가상메모리의 연속적인 묶음이다. 할당된 블록은 응용하기 위해 명시적으로 보존되었다. 가용한 블록은 할당을 위해 사용할 수 있다.

할당기는 두 개의 기본 유형이 존재하며, 두 유형 모두 응용이 명시적으로 블록을 할당하도록 요구한다.

명시적인 할당기(explicit allocator)는 응용이 명시적으로 할당된 블록을 반환해 줄 것을 요구한다. C 표준 라이브러리는 malloc 패키지라고 하는 명시적 할당기를 제공한다. C 프로그램은 malloc 함수를 호출해서 블록을 할당하며, free 함수를 호출해서 블록을 반환한다.

묵시적인 할당기(implicit allocator)는 언제 할당된 블록이 더 이상 프로그램에 의해 사용되지 않고 블록을 반환하는지를 할당기가 검출할 수 있을 것을 요구한다. 묵시적 할당기는 자동으로 사용하지 않은 할당된 블록을 반환시켜 주는 가비지 컬렉터(garbage collection) 작업을 수행한다.

9.9.1 malloc과 free 함수

C 표준 라이브러리는 malloc 패키지로 알려진 명시적인 할당기를 제공한다. 프로그램은 malloc 함수를 호출해서 힙으로부터 블록들을 할당받는다.

#include <stdlib.h>

void *malloc(size_t size);

malloc 함수는 블록 내에 포함될 수 있는 어떤 종류의 데이터 객체에 대해서 적절히 정렬된 최소 size 바이트를 갖는 메모리 블록의 포인터를 리턴한다.

malloc은 리턴하는 메모리를 초기화하지 않는다.

초기화한 동적 메모리를 원하는 응용들은 calloc을 사용할 수 있는데, 이것은 할당된 메모리를 0으로 초기화하는 calloc 함수 주위의 얇은 래퍼 함수다.

이전에 할당된 블록의 크기를 변경하려는 응용은 realloc 함수를 사용할 수 있다.

malloc과 같은 동적 메모리 할당기는 mmap과 munmap 함수를 사용해서 명시적으로 힙 메모리를 할당하거나 반환되며, 또는 sbrk 함수를 사용할 수 있다.

#include <unistd.h>

void *sbrk(intptr_t incr);

sbrk 함수는 커널의 brk 포인터에 incr을 더해서 힙을 늘리거나 줄인다. 성공한다면 이전의 brk 값을 리턴하고, 아니면 -1을 리턴하고 errno를 ENOMEM으로 설정한다.

프로그램들은 할당된 힙 블록을 free 함수를 호출해서 반환한다.

include <stdlib.h>

void free(void *ptr);

ptr 인자는 malloc, calloc, realloc에서 획득한 할당된 블록의 시작을 가리켜야 한다.

free 함수는 아무것도 리턴하지 않기 때문에 응용이에게 뭔가 잘못되었다는 것을 알릴 수 없다.

예제 9.34 - malloc과 free를 사용해서 블록을 할당하고 반환시키기

p1 = malloc(4 * sizeof(int))

(a) 프로그램은 4워드 블록을 요청한다. malloc은 가용 브록의 앞부분에서 4워드 블록을 잘라내고, 이 블록의 첫번째 워드를 가리키는 포인터를 리턴한다.

p2 = malloc(5 * sizeof(int))

(b) 프로그램은 5워드 블록을 요청한다. malloc은 가용 블록의 앞부분에서 6워드 블록을 할당한다. 이 예제에서 malloc은 가용 블록이 더블 워드 경계에 정렬되도록 하기 위해 블록에 추가적인 워드를 패딩하였다.

p3 = malloc(6 * sizeof(int))

(c) 프로그램은 6워드 블록을 요청하고, malloc은 가용 블록에서 6워드 블록을 잘라낸다.

free(p2)

(d) 프로그램은 (b)에서 할당된 6워드 블록을 반환해 준다. free로의 호출이 리턴한 후에 포인터 p2는 malloc된 블록을 가리킨다. p2가 새로운 malloc 콜에 의해 다시 초기화될 때까지 p2를 사용하지 않는다는 것은 응용이의 책임이다.

p4 = malloc(2 * sizeof(int))

(e) 프로그램은 2워드 블록을 요청한다. 이 경우에 malloc은 이전 단계에서 반환된 블록의 부분을 할당하고, 이 새로운 블록의 포인터를 리턴한다.

9.9.2 왜 동적 메모리 할당인가?

프로그램들이 동적 메모리 할당을 사용하는 가장 중요한 이유는 종종 이들이 프로그램을 실제 실행시키기 전에는 자료 구조의 크기를 알 수 없는 경우들이 있기 때문이다.

가장 간단한 방법은 배열을 정해진 최대 배열 크기를 갖는 정적 배열로 정의하는 것이다.

그러나 배열을 정해진 크기를 사용해서 할당하는 것은 종종 나쁜 방법이 된다.

만약 이 프로그램의 사용자가 실제 머신에서 가용한 가상메모리의 크기와는 무관한 임의 값을 정하여 더 큰 파일을 읽으려고 한다면 가능한 유일한 대책은 프로그램을 더 큰 값을 사용해서 다시 컴파일하는 것이다.

더 나은 방법은 n값을 알 수 있을 때 배열을 런타임에 동적으로 할당하는 것이다. 이 방법으로 배열의 최대 크기는 가용한 가상메모리의 양에 의해서만 제한된다.

9.9.3 할당기 요구사항과 목표

명시적 할당기들은 다소 엄격한 제한사항 내에서 동작해야 한다.

1. 임의의 요청 순서 처리하기
   : 응용프로그램은 각각의 가용 블록이 이전의 할당 요청에 의해 현재 할당된 블록에 대응되어야 한다는 제한사항을 만족하면서 임의의 순서로 할당과 반환요청을 할 수 있다.

2. 요청에 즉시 응답하기
   : 할당기는 블록들을 이들이 어떤 종류의 데이터 객체라도 저장할 수 있도록 하는 방식으로 정렬해야 한다.

3. 힙만 사용하기
   : 확장성을 갖기 위해서 할당기가 사용하는 비확장성 자료 구조들은 힙 자체에 저장되어야 한다.

4. 블록 정렬하기(정렬 요건)
   : 할당기는 블록들을 이들이 어떤 종류의 데이터 객체라도 저장할 수 있도록 하는 방식으로 정렬해야 한다.

5. 할당된 블록을 수정하지 않기
   : 할당기는 가용 블록을 조작하거나 변경할 수만 있다. 특히, 일단 블록이 할당되면 이들을 수정하거나 이동하지 않는다.

목표 1: 처리량 극대화하기
: n번의 할당과 반환 요청의 배열이 주어졌을 때, 할당기의 처리량을 최대화하려고 하며, 이것은 단위 시간당 완료되는 요청의 수로 정의된다. 일반적으로, 할당과 반환 요청들을 만족시키기 위한 평균 시간을 최소화해서 처리량을 최대화한다.

목표 2: 메모리 이용도를 최대화하기
: 한 시스템에서 모든 프로세스에 의해 할당된 가상메모리의 양은 디스크 내의 스왑 공간의 양에 의해 제한된다. 한 시스템에서 모든 프로세스에 의해 할당된 가상메모리의 양은 디스크 내의 스왑 공간의 양에 의해 제한된다.

할당기가 힙을 얼마나 효율적으로 사용하는지를 규정하는 방법 중 가장 유용한 단위는 최고 이용도(peak utilization)이다. 할당기의 목적은 최고 이용도 U을 전체 배열에 대해서 최대화하는 것이다.

9.9.4 단편화

나쁜 힙 이용도의 주요 이유는 단편화라는 현상이며, 단편화는 가용 메모리가 할당 요청을 만족시키기에는 가용하지 않았을 때 일어난다.

내부 단편화는 할당된 블록이 데이터 자체보다 더 클 때 일어난다. 내부 단편화는 단순히 할당된 블록의 크기와 이들의 데이터 사이의 차이의 합으로 정량화할 수 있다.

외부 단편화는 할당 요청을 만족시키기 위한 모든 가용한 메모리가 충분하지 않지만, 요청을 처리하기에 충분히 큰 한 개의 가용 블록이 없을 때 일어난다. 외부 단편화는 이전 요청의 패턴과 할당기 구현에만 의존하는 것이 아니라 미래의 요청 패턴에도 의존하기 때문에 내부 단편화보다 더 측정하기 어렵다.

9.9.5 구현 이슈

가장 간단히 상상할 수 있는 할당기는 힙을 하나의 커다란 바이트의 배열과 이 배열의 첫번째 바이트를 가리키는 포인터 p로 구성할 수 있다.

size 바이트를 할당하기 위해서 malloc은 현재 p값을 스택에 저장하고, p를 size 크기만큼 증가시키고, p의 이전 값을 호출자에게 리턴한다. free는 단순히 호출자에게 리턴한다.

이러한 할당기는 각 malloc과 free가 적은 수의 인스트럭션들을 실행하기 때문에 처리량은 매우 좋다. 그러나 할당기는 블록들을 하나도 재사용하지 않기 때문에 메모리 이용도는 매우 나쁠 것이다.

처리량과 이용도 사이에 좋은 균형을 갖는 실용적인 할당기는 다음 이슈들을 고려해야 한다.

가용 블록 구성: 어떻게 가용 블록을 지속적으로 추적하는가?
배치: 새롭게 할당된 블록을 배치하기 위한 가용 블록을 어떻게 선택하는가?
분할: 새롭게 할당한 블록을 가용 블록에 배치한 후 가용 블록의 나머지 부분들로 무엇을 할 것인가?
연결: 방금 반환된 블록으로 무엇을 할 것인가?

9.9.6 묵시적 가용 리스트

모든 실용적인 할당기는 블록 경계를 구분하고, 할당된 블록과 가용 블록을 구분하는 데이터 구조를 필요로 한다. 할당기는 이 정보를 블록 내에 내장한다.

한 블록은 1워드 헤더, 데이터, 추가적인 패딩으로 구성된다.

헤더는 블록 크기(헤더와 추가적인 패딩 포함)와 블록이 할당되었는지 가용 상태인지를 인코딩한다.

헤더 다음에는 응용이가 malloc을 불렀을 때 요구한 데이터가 따라온다.

데이터 다음에는 사용하지 않는 패딩이 따라올 수 있는데, 이들의 크기는 가변적이다. 패딩은 외부 단편화를 극복하기 위한 할당기 전략의 일부분일 수 있다. 또는 정렬 요구사항을 만족하기 위해 필요할 수 있다.

가용 블록이 헤더 내 필드에 의해서 묵시적으로 연결되기 때문에 묵시적 리스트라고 부른다.

묵시적 가용 리스트의 장점은 단순성이다. 중요한 단점은 할당된 블록을 배치하는 것과 같은 가용 리스트를 탐색해야 하는 연산들의 비용이 힙에 있는 전체 할당된 블록과 가용 블록의 수에 비례한다는 것이다.

시스템의 정렬 요구조건과 할당기의 블록 포맷 선택이 할당기에 최소 블록 크기를 결정한다.

9.9.7 할당한 블록의 배치

어플리케이션이 k바이트의 블록을 요청할 때, 할당기는 요청한 블록을 저장하기에 충분히 큰 가용 블록을 리스트에서 검색한다.

First Fit

First fit은 가용 리스트를 처음부터 검색해서 크기가 맞는 첫번째 가용 블록을 선택한다.

First fit의 장점은 리스트의 마지막에 가장 큰 가용 블록들을 남겨두는 경향이 있다.

단점은 리스트의 앞부분에 작은 가용 블록들을 남겨두는 경향이 있어서 큰 블록을 찾는 경우에 검색 시간이 늘어난다.

Next Fit

Next fit은 검색을 리스트의 처음에서 시작하는 대신, 이전 검색이 종료된 지점에서 검색을 시작한다.

이전 검색에서 가용 블록을 발견했다면 다음 검색에서는 리스트의 나머지 부분에서 원하는 블록을 찾을 가능성이 높다는 아이디어에서 착안한 방법이다.

Next fit은 first fit에 비해서 매우 빠른 속도를 갖는다.

그러나 next fit이 first fit보다 최악의 메모리 이용도를 갖는다.

Best Fit

Best fit은 모든 가용 블록을 검사하며 크기가 맞는 가장 작은 블록을 선택한다.

Best fit은 first fit이나 next fit보다 더 좋은 메모리 이용도를 갖는다.

묵시적 가용 리스트 같은 단순한 가용 리스트 구성을 사용해서는 best fit을 사용하면 힙을 완전히 다 검색해야 한다.

9.9.8 가용 블록의 분할

할당기가 크기가 맞는 가용 블록을 찾은 후에 가용 블록의 어느 정도를 할당할지에 결정을 내려야 한다.

한 가지 옵션은 이 가용 블록 전체를 사용하는 것이며, 이 방법은 간단하고 빠르지만 내부 단편화가 생긴다.

크기가 잘 안 맞는다면 할당기는 가용 블록을 두 부분으로 나누고, 첫번째 부분은 할당한 블록이 되고, 나머지는 새로운 가용 블록이 된다.

9.9.9 추가적인 힙 메모리 획득하기

만일 할당기가 요청한 블록을 찾을 수 없다면 한 가지 옵션은 메모리에서 물리적으로 인접한 가용 블록들을 연결해서 더 큰 가용 블록을 만들어 보는 것이다.

그럼에도 불구하고 충분히 큰 블록이 만들어지지 않거나 가용 블록이 이미 최대로 연결되었다면, 이 할당기는 커널에게 sbrk 함수를 호출해서 추가적인 힙 메모리를 요청한다. 할당기는 추가 메모리를 한 개의 더 큰 가용 블록으로 변환하고, 이 블록을 가용 리스트에 삽입한 후에 요청한 블록을 이 새로운 가용 블록에 배치한다.

9.9.10 가용 블록 연결하기

할당기가 할당한 블록을 반환할 때, 새롭게 반환하는 블록에 인접한 다른 가용 블록들이 있을 수 있으며, 이러한 인접 가용 블록들은 오류 단편화라는 현상을 유발할 수 있다.

오류 단편화를 극복하기 위해 실용적인 할당기라면 연결(coalescing)이라는 과정으로 인접 가용 블록들을 통합해야 한다.

9.9.11 경계 태그로 연결하기

할당기는 반환하려고 하는 현재 블록(current block)을 다음 가용 블록과 연결하는 것은 쉽고 효율적이다.

현재 블록의 헤더는 다음 블록의 헤더를 가리키고 있으며, 이것은 다음 블록이 가용한지 결정하기 위해 체크될 수 있다.

헤더를 사용하는 묵시적 가용 리스트가 주어진다면 이전 블록과 연결할 수 있는 유일한 옵션은 현재 블록에 도달할 때까지 전체 리스트를 검색해서 이전 블록의 위치를 기억하는 것이다.

묵시적 가용 리스트를 사용하면, 이것은 각각의 free 호출이 힙의 크기에 비례하는 시간을 소모할 것이라는 것을 의미한다.

경계 태그라는 기법은 상수 시간에 이전 블록을 연결하게 해준다. 이 아이디어는 각 블록의 끝 부분에 풋터(footer)라는 경계 태그를 추가하는 것으로, 풋터는 헤더를 복사한 것이다.

만일 각 블록이 이와 같은 풋터를 포함하게 되면, 할당기는 시작 위치와 이전 블록의 상태를 자신의 풋터를 조사해서 결정할 수 있게 되며, 이것은 항상 현재 블록의 시작 부분에서 한 워드 떨어진 곳에 위치한다.

할당기가 현재 블록을 반환할 때 가능한 모든 경우의 수

1. 이전과 다음 블록이 모두 할당되어 있다. (이전: 할당/현재: 해제/다음: 할당)
   : 인접 블록 모두가 할당상태이고, 따라서 연결이 가능하다. 현재 블록의 상태는 할당에서 가용으로 변경된다.

2. 이전 블록은 할당상태, 다음 블록은 가용상태다. (이전: 할당/현재: 해제/다음: 가용)
   : 현재 블록은 다음 블록과 통합된다. 현재 블록(의 헤더와)과 다음 블록의 풋터는 현재와 다음 블록의 크기를 합한 것으로 갱신된다.

3. 이전 블록은 가용상태, 다음 블록은 할당상태다. (이전: 가용/현재: 해제/다음: 가용)
   : 이전 블록과 현재 블록은 통합된다. 이전 블록의 헤더와 현재 블록의 풋터는 두 블록의 크기를 합한 것으로 갱신된다.

4. 이전 블록과 다음 블록 모두 가용상태다. (이전: 가용/현재: 해제/다음: 가용)
   : 세 블록 모두는 하나의 가용 블록으로 통합되고, 이전 블록의 헤더와 다음 블록의 풋터는 세 블록의 크기를 합한 것으로 갱신된다.

9.9.13 명시적 가용 리스트

묵시적 가용 리스트는 블록 할당 시간이 전체 힙 블록의 수에 비례하기 때문에 범용 할당기에 적합하지 않다.

가용 블록들을 일종의 명시적 자료구조로 구성하는 방법이 범용 할당기에 더욱 적합하다.

가용 블록의 본체는 프로그램에서 필요하지 않기 때문에 자료구조를 구현하는 포인터들은 가용 블록의 본체 내에 저장될 수 있다.

가용 블록 내에 predecessor와 success 포인터를 포함하는 이중 연결 가용 리스트 힙을 구성할 수 있다.

묵시적 가용 리스트 대신에 이중 연결 리스트를 사용하면 first fit 할당 시간을 전체 블록 수에 비례하는 것에서 가용 블록의 수에 비례하는 것으로 줄일 수 있다신

한 가지 방법은 리스트를 새롭게 반환한 블록들을 리스트의 시작 부분에 삽입해서 후입선출(LIFO: Last In First Out) 순으로 유지하는 것이다. LIFO 순서와 first fit 배치 정책을 사용하면 할당기는 대부분의 최근에 사용된 블록들을 먼저 조사한다.

또다른 방법은 리스트를 주소 순으로 관리하는 것이다. 리스트 내 각 블록의 주소가 다음 블록의 주소보다 작다.

주소 순서를 사용하는 firstfit이 LIFO 순서를 사용하는 경우보다 best fit의 이용도에 근접하는 더 좋은 메모리 이용도를 가진다.

명시적 리스트의 단점은 일반적으로 가용 블록들이 충분히 커서 모든 필요한 포인터 뿐만 아니라 헤더, 추가적으로 풋터까지 포함해야 한다는 점이다. 그로 인해 최소 블록 크기가 커지고 잠재적인 내부 단편화 가능성이 증가한다.

9.9.14 분리 가용 리스트

단일 연결 가용 블록 리스트를 사용하는 할당기는 한 개의 블록을 할당하는 데 가용 블록의 수에 비례하는 시간이 필요하다.

분리 저장장치(segregated storage)는 다수의 가용 리스트를 유지하며, 각 리스트는 거의 동일한 크기의 블록들을 저장하여 할당 시간을 줄일 수 있다.

분리 저장장치는 모든 가능한 블록 크기를 크기 클래스(size class)라고 하는 동일 클래스의 집합들로 분리한다.

할당기는 가용 리스트의 배열을 관리하고, 크기 클래스마다 크기가 증가하는 순서로 한 개의 가용 리스트를 가진다. 만일 크기가 맞는 블록을 찾을 수 없다면, 다음 리스트를 검색한다.

간단한 분리 저장장치

각 크기 클래스를 위한 가용 리스트는 간단한 분리 저장장치로 동일한 크기의 블록을 가지며, 각각은 크기 클래스의 가장 큰 원소의 크기를 갖는다.

어떤 주어진 크기의 블록을 할당하기 위해서 적절한 가용 리스트를 검색한다.

만약 리스트가 비어 있지 않다면 첫번째 블록 전체를 할당한다.

가용 블록들은 할당 요청을 만족시키기 위해서 절대로 분할하지 않는다.

만약 리스트가 비어 있다면, 할당기는 운영체제로부터 추가적인 고정 크기의 메모리를 요청한다.

동일한 크기의 블록으로 나누며, 블록들을 함께 연결해서 새로운 가용 리스트를 만든다.

할당기는 블록을 반환할 때 이 블록을 가용 리스트의 맨 앞에 삽입한다.

분리 저장장치의 단점은 내부와 외부 단편화에 취약하다는 점이다.

가용 블록들이 분할되지 않기 때문에 내부 단편화가 발생할 수 있다.

일부 참조 패턴은 가용 블록들이 절대로 연결되지 않기 때문에 극단적인 외부 단편화를 유발할 수 있다.

할당기는 연결하지 않기 때문에 응용프로그램이 절대로 해당 크기 클래스로부터 다시 블록을 요청하지 않기 때문에 각 크기 클래스에 대해 절대로 반환되지 않는 많은 메모리를 만든다.

분리 맞춤 (Segregated Fit)

분리 맞춤 할당기는 가용 리스트의 배열을 관리한다.

각 가용 리스트는 크기 클래스에 연관되며, 일종의 명시적 또는 묵시적 리스트로 구성된다.

각 리스트는 잠재적으로 서로 다른 크기의 블록들을 포함하고 있으며, 이들의 크기는 해당 크기 클래스에 포함된다.

블록을 할당하기 위해서 요청된 크기 클래스를 결정하고, 크기가 맞는 블록을 위해 해당 가용 리스트를 first fit 방식으로 검색한다.

만약 맞는 블록을 찾으면 블록을 분할하고, 나머지를 적당한 가용 리스트에 삽입한다.

만약 맞는 블록을 찾지 못하면 다음 크기의 클래스를 위한 가용 리스트를 검색한다.

블록을 찾을 때까지 이 과정을 반복한다.

만일 가용 리스트 어느 곳에서도 맞는 블록을 찾지 못한다면, 추가적인 힙 메모리를 운영체제에 요청하고, 새 힙 메모리에서 이 블록을 할당하며, 나머지를 적절한 크기의 클래스에 배치한다.

블록을 반환하기 위해서 그 결과를 적절한 가용 리스트에 배치하고 연결한다.

분리 가용 리스트의 단순한 first fit 검색이 전체 힙을 best fit 검색하는 것을 단순화한 것이다.