SP - 6.1 Dynamic Memory Allocator

  지금부터는 '동적 메모리 할당(Dynamic Memory Allocation)'에 대해 다룰 것이다. C의 malloc을 떠올리면 된다.

  동적 할당은 'Heap Memory Manager'가 수행한다. 힙 메모리 관리자를 다르게 부르면 'Dynamic Memory Allocator'이다. Chapter6에선 이 친구에 대해 자세히 알아볼 것이다.

Dynamic Memory Allocation

  프로그래머는 C의 malloc과 같은 'Dynamic Memory Allocator'를 이용해 Run-Time에 동적할당을 지시한다.

• 위 그림은 어떤 Process에 대한 Virtual Memory Address Space이다.

  • 가장 아래에는 Code Segment가 있다(.text)
  • 그 위에는 Data Segment가 있다(.data)
  • 그 위에는 초기화되지 않은 Data들의 영역이 있다.(.bss)
  • 그 위에는 Heap Segment가 있다.
    • 위 방향으로 확장한다.
  • 맨 위에는 Stack Segment가 있다.
    • 아래 방향으로 확장한다.

• Process에서 malloc 함수를 통해 자신의 Heap 영역에 메모리 공간을 할당한다.

  • 프로그램이 Run-Time에 필요로 하는 메모리 공간을 요청하는 것이다.
    • 누가? Dynamic Memory Allocator가.

• Dynamic Memory Allocation은, Run-Time 시에만 그 Size를 알 수 있는 자료구조들의 메모리 할당에 쓰인다. ★★★

  • "For data structures whose size is only known at runtime"

• 각 프로세스마다 자신의 가상 메모리 공간을 가지고 있고, 그 안에 Heap 영역이 있으며, Heap 영역은 시작 주소부터 Break Pointer가 가리키는 주소까지의 영역을 점유한다.

  • Break Pointer가 Heap Segment의 크기를 결정한다.

  • Break Pointer, 약칭 brk는 Heap의 Top을 가리킨다.

    • OS가 각 프로세스의 brk 포인터를 관리한다. ★
      • brk Pointer는 Kernel Context 중 하나로, 각 프로세스마다 다 있다.

• 우리는 이때, sbrk라는 System Call을 통해 brk를 증가시킬 수 있다.

  • brk의 증가(위로 올라감)는 곧 Heap Size의 증가를 의미한다.

  • 기존에 할당된 Heap 영역이 Full이면, sbrk를 호출해 더 키울 수 있다.

    • 물론, 당연히 무한히 확장할 수 있는 것은 아니다. 상한이 존재한다.

• Dynamic Memory Allocator는 단일 프로세스의 가상 메모리 공간 내 Heap 영역에 메모리를 동적으로 할당하고 해제할 수 있다.

• Allocator 입장에서 Heap은 'Variable Sized Blocks(가변 사이즈 블록)'의 Collection이다. ★★

  • 각 Block은 Allocated 또는 Free 상태를 가진다. ★

• 또한, Heap은 '동일한 크기의 Chunk들로 이루어진 Array'라고 볼수도 있다. ★★

  • Heap이 있고, Chunk 3개 크기의 Block을 할당했다고 해보자.

  • 이어서 Chunk 2개 크기의 Block, 1개 크기의 Block을 할당한다고 해보자.

  • 아래 그림을 보자.

~> Heap은 이런식으로 구성된다. Array이며, 각 Block이 Allocated or Free이다.
~> 참고로, 기본 단위 칸이 Chunk이고, 같은 State의 Chunk들이 연속으로 묶여있는 영역을 Block이라고 부르고 있는 것이다. ★

• 하늘색 a 공간은 Allocated, 연두색 f 공간은 Free 공간이다.

Explicit Memory Allocation

  Dynamic Memory Allocater는 아래와 같이 두 가지 유형으로 분류할 수 있다.

• Explicit Memory Allocator : Application이 Allocate와 Free를 둘 다 직접 수행한다.

  • 즉, 프로그래머가 직접 할당/해제하는 Allocator를 의미한다. 명시적으로!
    • C의 malloc과 free가 여기에 해당한다.

• Implicit Memory Allocator : Application이 Allocate만 하고, Free는 하지 않는다.

  • 즉, 프로그래머가 직접 할당하지만, 메모리 해제는 내부적으로 자동 수행되는 방식이다.
  • 사용하지 않는 Heap 영역을 Programming Language가 직접 알아서 확인하고, 수거하는 것이다.
    • Java의 Garbage Collection이 여기에 해당한다.

  우리는 이번 포스팅에서 이 'Explicit' 방식에 집중한다.

malloc in C

#include <stdlib.h>
void *malloc(size_t size)

• 메모리 할당이 성공적으로 수행된 경우

  • System의 Word Alignment의 규칙에 따라, Run-Time 시에 프로그래머가 명시한 Size를 최소로 커버할 수 있는 크기만큼 Memory Block을 할당하고, 그에 대한 Pointer를 반환한다.

    • 할당된 메모리 블록의 시작 주소 값을 반환하는 것이다.
    • x86 System의 경우 8Bytes-Alignment, x64 System의 경우 16Bytes-Alignment가 이루어진다.
      • 즉, x86 System에서 malloc을 통해 1바이트를 요청하면, 7바이트의 Padding이 함께 붙어서 총 8바이트 크기의 메모리 블록에 대한 포인터가 반환되는 것이다. ★

  • 만약, Size가 0이면, NULL을 반환한다.

• 메모리 할당에 실패한 경우
  • NULL(0)을 반환하고, errno를 세팅한다.

    • 할당할 수 있는 공간이 없다는 의미이다. ★

      • 이때, 할당할 공간이 없다는 것은, Free 상태인 Chunk가 없다는 것이 아니다.

      • 물론, 없을 수도 있지만, 대게 Free인 Chunk가 '할당하려고 요청한 크기'를 커버하지 못하는 상황에서 이런 에러가 발생한다.

free in C

void free(void *p)

• free를 호출할 경우, free의 Parameter로 넘어간 p라는 포인터가 가리키고 있는 Memory Block을 다 해제한다.

  • 메모리 해제란, 기존의 Allocated 상태인 공간이 Freed 상태로 바뀌는 것이다.
  • free 함수는 리턴값이 없다.
    • "Returns the block pointed at by p to pool of available memory!"
      • 여기서의 'Return'은 '메모리 해제'를 의미한다.

• 참고로, free에서 넘겨받는 p는 반드시 이전에 malloc이나 calloc, realloc 등으로 'Heap 영역 할당'이 이루어진 포인터여야 한다.

  • 그렇지 않으면, 중대한 시스템 문제가 발생할 수 있다.

• 잘 알려지지 않은 사실로, free 함수를 통해 해제한 공간의 Value(Contents)는 그대로 남아있는다. State가 Allocated에서 Freed로 바뀌는 것일 뿐이다. (물론, 이는 Compiler 및 OS Dependent한 내용이긴 하다) ★★★

Other functions

  알다시피, malloc 외에도 C에서는 다음과 같은 Heap Memory 할당을 수행하는 함수들을 제공한다.

• calloc : malloc과 동일한 기능을 수행하되, 할당과 함께, 할당된 메모리 공간을 0 Value로 초기화하는 기능이 추가되어 있다. ★

• realloc : 기존에 Allocated인 Block의 Size를 바꿀 때 사용한다.

• sbrk : Dynamic Memory Allocator가 내부적으로 사용하는 함수로, Heap 영역을 키우거나 줄일 때 사용한다.

  • Top of Heap, 즉, brk Pointer가 가리키는 높이를 위로 올리거나 내릴 때 사용하는 함수이다.
    • Heap Segment Size를 조절한다.

Example Code

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

void simple_example(int n) {
	int *p = (int *)malloc(n * sizeof(int)); // n*4 바이트 크기 메모리 공간 할당!
	if (p == NULL) {						  // 누가? DynamicMemoryAllocator가!
		perror("malloc");
		exit(-1);
	}

	for (int i = 0; i < n; i++)
		p[i] = i;						// 새롭게 할당된 공간을 초기화!

	free(p);							// 할당 영역 해제
}

~> Allocator는 모종의 Algorithm을 통해 Heap Segment에서 Proper 영역을 찾는다. 그 다음, 그 찾은 공간에다 할당하는 것이다.
~~> 우리는 앞으로 이 '모종의 Routine'에 대해 중점적으로 알아볼 것이다.

Prepare to study!

  이제 본격적으로 Dynamic Memory Allocation에 대해 공부할 것이다. 그런데, 공부에 앞서 잠시 준비하는 시간을 갖자. 앞으로의 학습에 필요한 지식을 충분히 쌓아두어야 이후 본격적 학습이 수월할 것이다.

  참고로, Dynamic Memory Allocation 개념은 상당히 중요하다. 물론, 이 이론 자체는 정립된지 꽤나 오래된 개념들이다. 하지만, 현대에도 이 개념은 충분히 의미가 있다. 그 이유는 다음과 같다.

Dynamic Memory Allocation 공부가 중요한 이유 : 현재 우리가 사용하는 Dynamic Memory Allocation은 'Heap'이라는 한정된 공간을 '어떻게' 효율적으로, 합리적으로 사용할지에 대한 오랜 고민의 결과물이다. 즉, '공간 관리'라는 측면에서 다양한 Insight와 Sense를 발견할 수 있는 것이다.

이는 현대 Big Data 시대에서 여전히 활발히 이뤄지고 있는 고민이다. 큰 개발부터 작은 개발까지 두루두루 말이다. 따라서, 우리가 이 개념을 잘 이해하면, 분명 어떻게든 도움이 될 것이다.

  각설하고, 본격적인 학습을 위한 '본격적인 준비'에 들어가자.

Frequent Questions

Q) realloc의 경우, 기존의 Heap Segment 및 Memory Block 할당 상태가 '확장할 크기'를 커버할 수 없다면 다른 위치에 새로 할당한다고 들었는데, 이게 맞는가?
A) 정확하다.

Q) malloc이 실패하는 경우는 sbrk로 Heap Segment Size를 최대로 늘렸음에도 불구하고 부족해서 발생하는 것인가요?
A) 그렇다. sbrk는 malloc 내부적으로 자동 수행된다고 했다. 더 이상 할당 가능 공간이 없으면 Allocator가 sbrk를 호출해 Heap 영역을 늘리고, 늘어난 영역에 대해 새롭게 공간을 할당해서 반환하는 것이다.
  malloc을 끊임없이 반복한다면 언제가는 더 이상 sbrk를 호출해서 영역을 늘릴 수 없는 순간이 온다. 보통 그 실패 지점은, OS Kernal이 필요로 하는 공간 크기가 침범될 위험이 발견될 때이다. "더 이상 Heap 영역을 키울 수가 없어ㅠㅠ OS가 제대로 돌아가려면 이만큼은 필요하단 말야ㅠㅠ 이제 그만 늘리자ㅠㅠ"하는 것이다.

즉, 요약하자면, sbrk가 실패하는 순간이 곧 malloc이 실패하는 순간이 되는 것이다.

Simple Simulation

  가상의 Heap Memory Space가 있다. 기본 단위를 Chunk 크기로 하는 Byte Array가 있다. 최우측이 Top of Heap이다. 이 상황에서, malloc을 이용해 4Bytes, 5Bytes, 6Bytes를 연속으로 요청했다고 해보자.

• 이제 Free를 하자. p2를 해제한다. 5Bytes 공간이 Freed가 된다. 곧바로 이어서 malloc을 한다. 이때, 새로운 공간은 어디에 할당될까?

• 위 그림과 같이, '가능한 공간 중 가장 맨 앞'에 할당한다. 모종의 Algorithm을 통해서 말이다. 우리는 다음 포스팅부터 이 Routine에 대해 알아볼 것이다.

Constraints

"현재는 1985년이다. 아직 이 세상엔 malloc과 같은 Dynamic Memory Allocator가 등장하지 않았다. 당신은 이제부터 최초의 Dynamic Memory Allocator를 설계해야하는 개발자다."

  그 당시를 기준으로 보면, 다음과 같은 제약 사항들을 상정할 수 있다(현대에는 조금 더 발전되었는데, 일단 이는 차치하자).

• Application이 malloc과 free를 어떤 순서로 수행할지 미리 알 방법이 없다. Allocator를 설계할 때 말이다.

  • 즉, malloc과 free의 Sequence는 Arbitrary할 것이다. ★

• 한 가지 확실히 정할 수 있는 것은 있다.

  • free는 반드시 malloc된 공간을 해제해야할 것이다. ★

• Allocator가 이미 할당한 Memory Block의 크기와 개수는 따로 스스로 Control할 수 없다. 이미 이뤄진 일이기 때문이다. ★

  • Allocator는 요청에 응답해서 메모리 공간을 할당할 뿐, 자기가 이전에 할당한 공간을 통제할 권한은 없다.

    • 한 번 Allocate된 Block의 위치는 바뀔 수 없다. ★★
      • Compaction(Allocated Block 위치를 바꿔가면서 꼭꼭 압축하는 행위)은 허용하지 않는다.

  • Allocator는 Free Memory만 컨트롤(Manipulation & Modification)할 수 있다. ★★

• 한 가지 확실한 것이 두 개 더 있다.

  • Allocator는 반드시 malloc Request에 즉각 Respond해야한다.

    • 즉, malloc(4)라는 요청이 오면, 바로 응답(할당)해야 한다는 것이다.

      • Dynamic Memory Allocation의 의미를 고려하면 당연하다.

    • 이 말은 즉슨, Buffering이나 Reordering이 불가능하다는 것이다. ★★

  • Allocation은 반드시 Free State의 공간에 수행되어야 한다. ★

• Memory Allocation은 Word Alignment를 Satisfy해야한다. ★

  • x86는 8바이트, x64는 16바이트에 맞게!
    • 이 과정에서 Padding이 사용된다.

  우리의 학습 역시 위의 Constraints를 그대로 적용한다. 그리고, 한 가지 더 가정하자. Word Alignment의 Word 기준은 4Bytes로 가정하자. Chunk Size가 4Bytes라고 가정하는 것이다. 이 제약 사항들을 기반으로 학습을 이어가자.

Throughput

  우리가 Dynamic Memory Allocator를 설계하고자 할 때, 성능적 측면에서 고려해볼만한 요소는 두 가지가 있다. 하나는 '처리율(Throughput)', 다른 하나는 'Peak Memory Utilization'이다.

Throughput : 단위 시간 당 '처리 완료한 Request' 개수

Dynamic Memory Allocator 설계 시 이 처리율을 높여야 성능을 향상시킬 수 있다.

We need to maximize Throughput!

• 이때, Request란, malloc/free 요청을 의미한다.

  • 즉 우리는 malloc과 free Request들로 이루어진 Sequence를 생각해볼 수 있다.

    • R0, R1, ..., Rk, ..., Rn-1

  • 만약, 5000번의 malloc과 5000번의 free 호출이 10초간 이어졌다고 해보자. 모두 처리 완료한 상태이다.

    • 이때의 Throughput은 '1000operations/sec'이다. (10000/10)

Peak Memory Utilization

• Payload : 실제로 요청한 메모리의 크기 (원하는 크기)

  • 우리가 malloc(p)라 하면, p Bytes의 Payload를 가진 Block이 할당된다.
    • ex) Payload가 10바이트인 Block은 x86나 x64 System 기준으로 총 16바이트의 크기만큼 할당된다. ★

• Aggregate Payload (Pk) : 현재 할당된 Payload의 총 합. 현재까지 얼마만큼 할당 요청이 이뤄졌는지를 나타낸다.

• Current Heap Size (Hk) : Heap의 시작 주소부터 brk Pointer가 가리키는 위치까지의 Heap 크기

  • malloc을 할 때의 Heap Size가 바로 Hk이다.
  • sbrk로 Hk를 늘릴 수 있는 것이다.

• 여기서 k라 함은, R0, R1, ..., Rk, ..., Rn-1의 Requests Sequence에서의 Index를 의미한다. ★

  • 우리가 Rk Request를 수행하고 나서, Aggregate Payload 값을 Pk로 나타내고, 그 때의 Heap Size를 Hk라고 나타내는 것이다.

Peak Memory Utilization (Uk)

Uk : Peak Memory Utilization after 'k+1' Requests

Uk = (max_Pi) / Hk

• max_Pi = k 이전의 i Index에 대해서, 가장 큰 Aggregate Payload Pi 값을 의미한다.

• 이 Uk 값이 높다는 것은 무엇을 의미할까?

  • Uk를 Maximize하는 것은, brk를 움직이지 않고, 현재 주어진 크기 내에서 최대한 꾸겨꾸겨 내실있게 할당하는 것을 의미한다. ★★★

• Throughput과 Peak Memory Utilization은 서로 Conflict하는 Trade-Off 관계이다.

  • Peak Memory Utilization을 높이려면 '빈 공간'을 찾는 별도의 작업이 필요하다. 따라서, 시간이 느려지고, 나아가 처리율도 낮아지는 것이다. Overhead가 있으므로.

  • 반대로, '빈 공간'을 찾는 루틴을 없애면 없앨수록 기본적으로 처리 속도가 빨라지는 것이다.

• 프로그래머가 이 둘을 적절히 조화시켜야하는 것이다.

Fragmentation

  국문으로 '단편화'라고 하는 이 개념은 'Poor Memory Utilization'으로부터 비롯된다. 내부 단편화와 외부 단편화 문제가 있다.

• Internal Fragmentation : Payload가 '실제 할당 크기(Block Size)'보다 작은 상황

  • 공간 효율과 밀접하게 관련된다.

  • 원인

    • Heap 자료구조 유지 과정의 Overhead
      • ex) Header, Footer, Tag 등 (추후 설명)
    • Alignment를 지키기 위한 Padding
    • Explicit Policy

  • 이전 Request들의 패턴에 종속적이다.

    • 외부 단편화에 비해 다루기 쉽다. '이전'만 고려하면 되기 때문!

  • 예를 들어보자.

    • 내가 실제로 '요청'한 크기는 10바이트이고, 실제 '할당'한 크기는 16바이트라 하자(8Bytes or 16Bytes Alignment)
      • 6바이트 Padding이 사용되었다. (Overhead)

• External Fragmentation : Aggregate Heap Memory는 충분한데, 개별적인 Single Free Block의 크기들이 충분하지 않은 상황을 의미한다.
  • 앞 뒤를 모두 고려해야하기 때문에 다루기 어렵다.

  우리는 다음 포스팅부터 이러한 개념들을 토대로 Dynamic Memory Allocation의 전반에 대해 깊이 있게 학습할 것이다. 기대해도 좋다.