[WEEK07] 동적 메모리 할당

Dynamic Memory Allocation

• 개발자들은 런타임에서 VM을 취극하기 위해 (런타임에서만 그 크기를 알 수 있는 자료구조들을 위해) malloc과 같은 동적 메모리 할당기dynamic memory allocator (이하 DMA)를 사용한다.
• DMA는 heap이라고 알려진 프로세스 VM의 한 영역을 관리한다.
  • Heap은 아래에서 위로 성장하는 모습이며, heap의 top은 brk 포인터로 가리킨다.
• 할당기는 힙을 allocated 상태이거나 free 상태인 다양한 크기의 block들로 유지한다.
• 할당기의 종류
  • Explicit allocator (명시적 할당기) : 응용프로그램이 공간을 allocate하거나 free한다.
    (예: C의 malloc/free)
  • Implicit allocator (묵시적 할당기) : 응용프로그램이 공간을 allocate하지만 free하지는 않는다.
    (예: 자바의 가비지 컬렉터)

---

Malloc 패키지

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

• 성공 시 : 
  • 8바이트(x86) 또는 16바이트(x86-64)의 배수인 적어도 size 바이트 크기의 메모리 블록을 가리키는 포인터를 리턴
  • size == 0이면 NULL을 리턴
• 실패 시 : NULL(0)을 리턴하고 errno를 set함

void free(void *p)

• p가 가리키는 블록을 사용 가능한 메모리 풀로 리턴
• p는 malloc이나 realloc으로부터 얻은 것이어야 함

기타 함수들

• calloc : allocated된 블록을 0으로 초기화하는 malloc의 다른 버전
• realloc : 이전에 allocated된 블록의 크기를 변경
• sbrk : 힙을 늘리거나 줄이기 위해 할당기에 의해 내부적으로 사용됨

malloc 예제

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

void foo(int n) {
    int i, *p;

    p = (int *) malloc(n * sizeof(int));
    if (p == NULL) {
        perror("malloc");
        exit(0);
    }

    for (i=0; i<n; i++)
	p[i] = i;

    free(p);
}

Allocation 예시

[출처] CMU system programming chap.19

---

Performance Goal

• malloc과 free 요청의 주어진 시퀀스 {R₀, R₁, …, Rₖ, …, Rₙ₋₁}에 대해서
• 목표는 Throughput의 극대화와 높은 메모리 Utilization이다. (종종 둘이 상충되기도 한다.)

Throughput

• 단위 시간 당 완료된 요청의 수
• (예) 10초 동안 malloc calls와 free calls가 각각 5000회였다면, throughput은 1000 operations/sec

Peak Memory Utilization

• Aggregate payload Pₖ
  • malloc(p)의 결과는 p 바이트의 payload를 포함하는 블록이다.
  • Rₖ번째 요청이 끝난 후, aggregate payload Pₖ는 지금까지 allocated된 payload들의 합이다.
  • (cf) Aggregate란 '관련된 객체들의 집합'을 의미한다(참고).
• 현재 heap size Hₖ
  • Hₖ는 적어도 감소하지는 않는다고 가정한다.
  • 즉, heap은 할당기가 sbrk를 사용했을 때만 커진다.
• k+1 번째 요청 이후의 Peak memory utilization
  • Uₖ = (maxᵢ Pᵢ) / Hₖ

---

Fragmentation

Internal Fragmentation

• 주어진 block에서, internal fragmentation (내부 단편화)는 payload가 block size보다 작을 때 발생한다.

 

• Main memory 내 사용자 영역이 실행 프로그램보다 커서 프로그램의 사용 공간을 할당 후 사용되지 않고 남아있는 공간을 의미한다. (출처)
• 원인
  • heap 자료구조를 유지하는 오버헤드
  • alignment 목적의 padding
  • Explicit 정책 결정 (예: 작은 요청을 만족하기위해 큰 블록을 리턴)

• 오직 이전 요청의 패턴에만 의존한다.
  • 즉, 측정하기 쉽다. 문식이는 귀엽다.

External Fragmentation

• 충분한 aggregate heap memory가 있지만, 충분히 큰 single free block이 없을 때 발생한다.

6워드 크기의 free block이 없다!

• Main memory 내 사용자 영역보다 실행 프로그램이 커서 프로그램이 할당될 수 없어 사용되지 않고 남아있는 공간을 의미한다.
• 미래 요청의 패턴에 의존한다.
  • 즉, 측정하기 어렵다. 문식이는 세상에서 제일 귀여운 강아지다.

---

구현 이슈

• 포인터에 얼마나 많이 메모리를 free시켜야 하는지 어떻게 알 수 있는가?
• 어떻게 free blocks를 추적할 수 있는가?
• 안에 있는 free block보다 작은 구조를 allocate할 때의 추가적은 공간으로 무엇을 할 것인가?
• 어떻게 allocate할 때 사용할 block을 고를 것인가? (many might fit?)
• free된 block을 어떻게 reinsert할 것인가?

얼마나 Free할 지 아는 방법

• 선행 block의 word 길이만큼의 block을 유지하기
  • 여기서의 word를 header field 또는 header라고 부른다.
• 모든 allocated된 block에 대해 추가적인 word를 요청하기

Free Blocks 추적하기

1. length를 이용한 Implicit list : 모든 block들을 link함

2. 포인터를 이용한 free blocks 사이의 Explicit list

3. Segregated free list : 다른 size class마다 다른 free list 사용

4. Blocks sorted by size : 각 free block을 가리키는 포인터와 length를 key로 하는 RB 트리와 같은 균형 트리 사용 가능