동적 메모리 할당

동적 메모리 할당을 사용하는 이유

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

예를 들어, n개의 정수를 입력받아 배열에 담아야 하는 상황에서 가장 간단한 방법은 배열의 크기를 가장 크게 만들어 입력을 받는 방법일 것이다. 하지만 이렇게 하면 입력받은 정수의 갯수를 빼고 남아있는 만큼의 메모리는 낭비되는 것이 됨을 알 수 있다.

이러한 상황에서 우리는 동적으로 필요한 만큼의 메모리만을 할당받아 사용할 수 있다. 그리고 이것을 가능하게 해주는 것이 동적 메모리 할당기이다.

동적 메모리 할당기의 유형

• 명시적 할당기 (Explicit Allocator)

• 어플리케이션에서 직접 메모리를 할당하고 또 반환한다.

• C 표준 라이브러리의 malloc 패키지를 사용한다. (malloc() && free())

• 묵시적 할당기 (Implicit Allocator)

• 어플리케이션에서 메모리를 할당하지만 반환은 할당기가 자동으로 처리한다.

• 이러한 할당기를 가비지 컬렉터(Garbage Collector)라고 부른다. 사용하지 않는 Allocate block들을 자동으로 반환하는 방식을 사용하며, 이러한 방식을 가비지 컬렉션(Garbage Collection)이라고 한다.

할당기 처리량과 메모리 최고 이용도

할당기 처리량

단위 시간 당 완료되는 요청의 수를 의미한다.

메모리 최고 이용도

힙을 얼마나 효율적으로 사용하고 있는 지에 대한 척도가 된다.

처리량 R0, R1, R2, ... , Rn-1의 총 n번의 할당과 반환 요청에 대해

• Hk : k + 1번의 요청 이후의 힙 크기. (항상 증가한다고 가정함.)
• Pk : k + 1번의 요청까지에서의 payload의 합. (Allocated면 증가, free면 감소)
• Uk : 첫 번째 k 요청에 대한 메모리 최고 이용도
• maxPi : k보다 낮은 모든 i에 대해 지금까지의 payload의 합 중 가장 큰 값.

만약 할당기의 Uk가 1이면? 할당기가 가질 수 있는 가장 이상적인 힙 이용도가 되겠다. (다른 오버헤드 없이 순수하게 payload로만 이루어진 힙을 의미)

할당기에서 가장 중요한 것은 할당기의 처리량과 메모리 최고 이용도 사이의 적절한 균형을 찾는 일이다.

메모리 단편화

• 내부 단편화 : 할당된 블록이 데이터 자체보다 클 때 발생한다.

• 외부 단편화 : 메모리에 충분한 용량의 여유가 있지만 정렬 문제로 인해 그 메모리에 할당하지 못하는 경우 발생한다.

할당기 구현 이슈

처리량과 이용도 사이의 좋은 균형을 갖기 위해 할당기는 다음 사항들을 고려해야만 한다.

• 가용 블록의 구성 방법 : 가용 블록들을 어떻게 추적할 것인가?
• 배치 : 동적 할당을 위한 가용 블록을 어떻게 선택할 것인가?
• 분할 : 가용 블록보다 더 작을 블록을 할당해주었을 때, 남는 가용 블록들을 어떻게 처리해줄 것인가? (단편화 문제의 처리 방법)
• 연결 : 방금 반환된 블록을 어떻게 처리해줄 것인가?

가용 블록 구성 방법 (= 가용 블록들을 추적하는 방법)

• 묵시적 가용 리스트 (implicit free list)
• 메모리 할당 과정에서 가용 블럭들을 탐색하는 방식을 채택한다.
• 명시적 가용 리스트 (explicit free list)
• 가용 블록들을 별도의 자료구조 형태로 관리하는 방식을 채택한다.
• 분리 가용 리스트 (Segregated Free List)
• 할당이 해제되어있는 블록들을 사이즈 별로 각각의 연결 리스트를 만들어 관리한다.
• Blocks sorted by size
• 균형 트리(RBtree) 등을 이용해서 가용 리스트들을 크기 순대로 정렬한다.

묵시적 가용 리스트(implicit free list) 기법을 통한 할당기의 구현

묵시적 가용 리스트 방법에서는 블록 간의 경계를 구분하고, 이러한 경계를 통해서 이미 할당된 블록과 가용 블록을 구분한다.

묵시적 가용 리스트 방법을 이용했을 때의 간단한 메모리 블록 구조는 위 그림과 같다.

그림 1 에서 회색으로 칠해진 부분은 실제로 할당된 메모리 블럭이고, 흰색은 비어있는 메모리를 뜻한다. 회색과 흰색 부분의 맨 앞칸에 x/y로 표시되어 있는 부분을 헤더(header)라고 한다.

헤더(header)에는 해당 블럭의 크기/가용 여부를 담는다. 예를 들어 헤더에 8/0이라는 정보가 들어있다면 해당 블록의 크기는 8Byte이고 아직 할당되지 않은 블록 즉, 가용 블록임을 뜻한다. (1 word = 4byte = 32bit)

하지만 이렇게 헤더를 사용하여 경계를 구분하기 위해서는 추가적으로 1 word 만큼의 공간이 더 필요하다. 만약 할당기가 4 word의 메모리를 할당한다면, 헤더를 포함한 5 word의 가용 블록을 할당해야 하고, 헤더 바로 뒤 payload의 첫 주소를 반환할 것이다.

그림 1 에서 두번째 할당된 블록을 살펴보면 16Byte 크기의 블록이 현재 사용되고 있음을 알 수 있다. 하지만 여기서 실제로 사용되고 있는 블록은 가운데 2word일 뿐이다. 맨 앞은 헤더라고 생각할 수 있지만 맨 뒤는 왜 못쓰고 있는 것일까? 여기에 대해서는 일단 정렬(Alignment)에 대해 알고 넘어가야 한다.

최신 컴퓨터 하드웨어의 CPU는 데이터가 자연스럽게 정렬 되어있을 때 메모리에 대한 읽기 및 쓰기를 가장 효율적으로 수행할 수 있다. CPU의 word 크기가 4Byte (32bit)라면 메모리로부터 한번 읽어들일 때마다 4바이트만큼 읽어들일 수 있음을 뜻하고, 이 때 기준 주소 역시 word(4Byte = 32bit)의 배수여야 함을 뜻한다. 결론적으로 CPU가 읽어들일 수 있는 워드의 배수로 메모리가 정렬되어 있다면, 그만큼 읽고 쓰는 연산이 효율적이 될 수 있다는 것을 뜻한다.

현재 메모리 정렬이 double word(8Byte = 64bit) 정렬을 따르고 있으므로 블록의 크기는 항상 8의 배수가 되어야 한다. 이러한 정렬을 지켜주기 위해 가용 블럭은 항상 8의 배수 단위로 나뉘며, 할당된 후 남는 공간이 있다면 패딩(padding)을 추가하여 정렬을 유지한다.

배치 : 묵시적 가용 리스트에서 가용 블록을 탐색하는 방법

할당기가 할당을 요청받았을 때, 할당 기는 가용 블록을 탐색하여 해당 블록에 할당하고, 할당된 블럭 헤더의 바로 뒷 블록의 주소를 반환한다. 이 때 할당기는 어떻게 가용 블록을 찾아낼까?

가용 블록을 찾아내는 방법(배치 정책)에는 다음과 같은 것들이 존재한다.

• First fit
• 사용 가능한 블록을 처음부터 탐색해서 크기가 맞는 첫 번째 블록을 선택하는 방식
• 대체로 리스트의 마지막에 가장 큰 가용 블록이 남는다.
• 대체로 리스트의 앞에 작은 크기의 가용 블록들이 남기 때문에 큰 가용 블록을 검색 시에는 많은 시간이 소요된다.
• Next fit
• 이전 검색에서 가용 블록을 발견했다면? 해당 가용 블록부터 탐색을 진행하는 방식
• 대체로 블록은 앞에서부터 채워나가기 때문에 원하는 블록을 빨리 찾을 가능성이 크다.
• 앞에 가용 블록이 하나 남아있어도 검색 시도를 하지 않기 때문에 메모리 이용도가 낮아지게 된다. (외부 단편화 문제 발생)
• Best fit
• 처음부터 탐색을 시작해서 크기가 딱 맞는 블록이 어떤 것인지 추려내어 할당한다.
• 최고의 메모리 이용도를 가진다.
• 최저의 속도를 가진다.

분할 : 가용 블록을 할당하는 방법

할당기가 가용 블록을 찾아내어 할당하려고 할 때, 해당 가용 블록이 할당기가 요구하는 사이즈보다 크다면? 내부 단편화(Internal Fragmentation)가 발생할 수 있으므로 블록의 분할을 수행한다.

만약 4 word 만큼의 데이터를 할당하기 위해 할당기에게 요청했을 때, 할당기가 찾아낸 가용 블록의 크기가 6칸일 경우 2칸의 내부 단편화가 발생하게 된다. 하지만 여기서 필요한 만큼의 블록에만 할당을 하고 남을 블록을 또 다른 가용 블록으로 만들어 준다면? 약간의 추가적인 연산을 필요로 하겠지만 메모리의 이용도는 높아지게 된다고 볼 수 있다.

연결 : 블록 반환 시 인접 가용 블록(이전, 이후)들을 연결하는 방법

할당기가 free() 함수를 통해서 할당되어 있던 블록을 반환할 때, 반환하는 블록에 인접한 다른 가용 블록들이 존재할 수 있으며, 이 블록들을 병합해주지 않는다면 오류 단편화(False Fragmentation)가 발생할 수 있다.

그림 4 처럼 5칸의 메모리를 할당하고 싶을 때, 6칸의 가용 블록이 존재하지만 4칸과 2칸으로 분리되어 있기 때문에 할당기는 할당하지 못하고 다음 가용 블록을 탐색하려고 이동할 것이다. 이로 인해 4칸과 2칸의 가용 블록은 오류 단편화로 이어진다.

위 상황은 결국 메모리가 비효율적으로 관리되고 있다는 것을 뜻하며, 이때 4칸과 2칸의 가용 블록을 6칸의 가용블록으로 만들어 주기 위해 연결(coalescing)이라는 기법을 사용한다. 연결에는 두가지 방법이 있다.

• 즉시 연결 - 블록이 반환되었을 때 바로 앞과 뒤를 병합해주는 방법.
• 지연 연결 - 일정 시간 이후에 가용 블록들을 연결해준다. (할당 요청이 실패할 때 모든 가용 블록 검색을 병합해주는 방식)

즉시 연결 기법을 사용한 코드는 아래와 같다. (BUT 뒤만 병합 가능..)

void free_block(ptr p) { *p = *p & -2; // 헤더 정보를 수정한다. next = p + *p; // 이후 블록을 찾는다.

if((*next & 1) == 0) {
	// 만약 다음 블록이 가용 블록이라면 합친다.
	*p = *p + *next;
}

} 위 코드는 반환된 블록의 이후 블록이 가용 블록이라면 현재 반환된 블록과 연결을 해주는 연산을 수행하고 있다. 여기서 문제점은 반환된 블록의 이전 블록 또한 가용 블록이라면? 연결 해주지 못한다는 점이다.

가장 단순한 방법은 다시 처음부터 가용 검색해서 반환한 자리까지 오면서 이전 블록이 가용 블록인지 확인하고 연결해 주는 것이지만, 이 방법은 예상하듯 비효율적일 것이다. 그리하여 만약 반환된 블록의 이전 블록이 가용 블록일 경우에 연결을 위해 경계 연결(Boundary tags)이라는 기법을 사용한다.

경계 태그를 통한 연결 (Boundary tags)

가용 블록의 끝. 즉 마지막 블록에 헤더의 정보를 복제한 경계 블록(footer)을 추가한다. 이를 이용해서 기준 블록의 헤더에서 한 칸만 뒤로 간다면? 이전 블록의 할당 여부를 할 수 있게 된다.

결국 새로운 메모리를 header와 footer에 할당해야 하므로, 메모리 오버헤드가 발생할 수 있다. 이를 위해서 오로지 가용 블록일 때만 footer를 사용한다. 만약 할당된 블록일 경우에는 연결을 할 필요가 없기 때문이다.

하지만 여기서 또 문제가 하나 있다. 이전 블록이 할당 블록이라 footer가 존재하지 않는다면 이전 블록이 가용 블록인지 어떻게 확인할 수 있을까? 이를 위해 블록의 헤더에서 해당 블록의 할당 여부를 저장하는 자릿수 다음 자리에 이전 블록의 할당 여부를 저장해두기로 한다.

경계 연결을 사용할 경우에 반환할 블록과 인접한 블록들의 할당 여부에 따라 4가지 케이스로 구분할 수 있다.

Constant Time Coalescing

Boundary tags의 4가지 케이스

CASE 1: 이전, 이후 블록이 모두 할당된 상태이다. 이 경우 연결할 필요가 없으므로 해당 블록만 반환해주면 된다.

CASE 2: 이전 블록이 할당된 블록이고, 이후 블록이 가용 블록 상태인 경우 이후 블록이 가용 상태이므로 반환된 블록과 이후 블록을 연결시켜 준다.

CASE 3: 이후 블록이 할당된 블록이고, 이전 블록이 가용 블록 상태인 경우 CASE 2와 같이 반환된 블록과 이전 블록을 연결시켜 준다.

CASE 4: 이전, 이후 블록이 모두 가용 블록 상태인 경우 이전, 이후 블록과 반환한 블록을 연결해준다.

묵시적 가용 리스트의 불변하는 형식

• Prologue Block : 힙 영역의 시작을 알리는 경계를 뜻한다.
• Epilogue Block : 힙 영역의 끝을 알리는 경계를 뜻한다.
• 각각의 가용 블록들은 header와 footer를 갖는다.