Dymaic Memory Allocation

※ Dynamic Memory Allocation

 

프로그래머는 malloc 와 같은 dynamic memory allocator 를 사용하여 런타임때 VM 을 획득한다.

• 크기가 런타임에만 알려진 데이터 구조용이다.

Dynamic memory allocator 는 힙으로 알려진 프로세스 가상 메모리 영역을 관리한다.

Allocator 는 힙을 할당되거나 free 할 수 있는 가변 크기 블록의 모음으로 유지 관리한다.

Allocator 의 종류로는 다음과 같다.

• Explicit allocator : 응용프로그램이 공간을 할당하고 free 가능
  
  • 예: malloc 및 free in C
• Implicit allocator : 응용 프로그램이 공간을 할당하지만 free 는 하지 않음
  
  • 예: Java, ML 및 Lisp의 가비지 컬렉션

 

 

여기서 brk ptr 는 break pointer 를 의미하며 힙의 가장 상단부를 포인팅하는 포인터 역할을 한다.

위 메모리 영역은 물리적인 메모리 영역이 아닌 가상 메모리 영역임을 알아두고 넘어가자.

 

 

※ The malloc Package

 

#include <stdlib.h>

void *malloc(size_t size)

• Successful :
  
  • 8바이트(x86) 또는 16바이트(x86-64) 경계에 정렬된 최소 크기 바이트의 메모리 블록으로 포인터를 반환한다.
  • size 가 0이면 NULL을 반환한다.
• Unsuccessful : NULL을 반환하고 errno를 설정한다.

void free(void *p)

• 사용 가능한 메모리 풀에서 p 가 가리키는 블록을 반환한다.
• p는 malloc 또는 realloc에 대한 이전 호출에서 와야 한다.

Other functions

• calloc : 할당된 블록을 0으로 초기화하는 malloc 버전이다.
• realloc : 이전에 할당된 블록의 크기를 변경한다.
• sbrk : allocator 가 힙을 확장하거나 축소하기 위해 내부적으로 사용한다.

 

 

※ Constraints

 

Applications

• malloc 및 free 요청의 임의 시퀀스를 발행할 수 있다.
• free 요청은 malloc'd 블록에 있어야 한다.

Allocators

• 할당된 블록의 수 또는 크기를 제어할 수 없음
• malloc 요청에 즉시 응답해야 함
  
  • 즉, 요청을 다시 정렬하거나 버퍼링할 수 없다.
• 사용 가능한 메모리에서 블록을 할당해야 한다.
  
  • 즉, 할당된 블록만 free 한 메모리에 배치할 수 있다.
• 모든 alignment 요구 사항을 충족하도록 블록을 정렬해야 한다.
  
  • Linux boxes 의 8바이트(x86) 또는 16바이트(x86-64) 정렬
• free 한 메모리만 조작 및 수정할 수 있다.
• malloc 된 경우 할당된 블럭들을 이동할 수 없다.
  
  • 즉, compaction 이 허용되지 않음

 

※ Performance Goal: Throughtput

 

malloc 및 free 요청의 일부 시퀀스가 주어질 경우

• \(R_{0}, R_{1}, ..., R_{k}, ..., R_{n-1}\)

Goals : throughput 극대화 및 최대 메모리 활용률

• 이러한 목표들은 종종 충돌된다.

Throughput :

• 단위 시간당 완료된 요청 수
• 예:
  
  • 10초 안에 5,000건의 malloc 호출과 5,000건의 free 호출
  • 초당 1,000회의 작업 처리량

 

※ Performance Goal : Peak Memory Utilization

 

Def : Aggregate payload \(P_{k}\)

• malloc(p)는 p 바이트의 payload를 갖는 블록을 반환한다.
• 요청 \(R_{k}\)가 완료된 후, aggregate payaload \(P_{k}\)는 현재 할당된 payload의 합계이다.

Def: Current heap size \(H_{k}\)

• \(H_{k}\)가 단조롭게 감소하지 않는다고 가정하자.
• 즉, allocator 가 sbrk를 사용하는 경우에만 힙이 증가한다.

Def: Peak memory utilization after \(k+1\) requests

• \(U_{k} = (max_{i<=k} P_{i}) / Hk\)

 

예를 들어서 malloc, free 의 요청을 처리하도록 하는 sequence 가 \(R_{0} = 5\), \(R_{1} = 2\), \(R_{2} = 3\) 이라고 한다면, \(P_{0} = 5\), \(P_{1} = 7\), \(P_{2} = 10\) 이 된다. 

그리고 sbrk 는 heap 의 size 를 증가시키는데 이러한 size 가 virtual memory 의 size 를 넘어서게 되는 경우 swapping 이 일어나게 된다.

 

 

※ Internal Fragmentation

 

지정된 블록의 경우, payload가 블록 크기보다 작으면 internal fragmentation 이 발생한다.

Caused by

• 힙 데이터 구조 유지 관리 오버헤드
• alignment 목적을 위한 패딩
• 명시적 정책 결정 (예: 작은 요청을 만족시키기 위해 큰 블록을 반환하는 것)

이전 요청의 패턴에만 의존한다.

• 따라서 측정이 용이하다.

 

 

payload 는 실제 저장될 data 를 담당하고 있으며 양쪽에는 header, footer 로 block 의 metadata 를 담는 역할을 한다.

 

 

※ External Fragmentation

 

aggregate heap memory 가 충분하지만, free한 단일 블록이 충분히 크지 않을 때 발생한다.

향후 요청 패턴에 따라 다르기 때문에 측정이 어렵다.

 

 

위와 같이 contiguous 하게 block 을 채울 때, free 를 한 후에 malloc 을 시도할 때 블럭의 갯수가 연속적으로 free 된 최대 블럭의 수보다 클 경우 external fragmentation 이 발생된다.

 

 

※ Knowing How Much to Free

 

Standard Method

• 블록 앞의 word에서 block의 길이를 유지한다.
• 이 word는 종종 header field 또는 header 라고 불린다.
• 할당된 모든 블록에 대해 추가 word가 필요하다.

 

 

위와 같이 malloc(4) 를 호출하게 되면 4개의 block 갯수 만큼 메모리 할당이 이뤄져야 한다.

이때, payload 는 4개의 block으로 구성되며 payload 의 앞 주소를 포인트하고 있는 p0의 앞에 block 길이를 저장하고 있는 것을 알 수 있다.

이를 block size 으로 header field 라고도 한다.