[sp] Dynamic Memory Allocation (1)

1. Dynamic memory allocation

(1) 프로그래머는 malloc 과 같은 dynamic memory allocator를 사용하여 런타임에서 VM을 얻음

 ; 크기가 런타임에서만 알려진 데이터 구조체에 경우

(2) Dynamic memory allocator는 heap이라고 불리는 프로세스 가상 메모리 영역을 관리

 

brk 포인터는 heap의 크기를 결정하며 heap의 공간을 늘릴 경우 위로 이동

 

(3) Allocator는 allocated이거나 free한 변경 가능한 크기의 블럭들의 집합으로 이뤄짐

(4) Types of allocator : Explicit allocator -> 직접 공간을 할당하고 해제함

   ex) malloc, free (C), new, delete (C++)

     : Implicit allocator -> 할당된 메모리 영역 중에서 사용하지 않는 영역이 있으면 자동으로 free

       ex) garbage collection (Java, ML, Lisp)

2. The malloc Package

#include <stdlib.h>

(1) void *malloc(size_t size)

  - successful : 8바이트 (x86)이나 16바이트(x86-64) 영역에 할당된 size 바이트 이상의 크기를 가진 메모리 블럭의 포인터를 리턴, size가 0이면 NULL을 반환

  - unsuccessful : return NULL, errno을 설정

 

(2) void free(void *p)

 - 사용 가능한 메모리의 pool에 p가 가리키는 블럭을 리턴

 - p는 malloc/realloc에 대한 이전 호출에서 나와야 함

 

(3) other functions

 - calloc : 할당된 영역을 0으로 초기화 하는 malloc 버전

 - realloc : 이전에 할당된 블럭의 사이즈를 변경

 - sbrk : heap의 크기를 늘리거나 줄이기 위해 내부적으로 사용됨, brk 포인터를 조절

 

ex. malloc Example

 

#include <stdio.h>
#include <stdlib.h>
void foo(int n) {
    int i, *p;
    
    /* Allocate a block of n ints */
    p = (int *) malloc(n * sizeof(int));
    if (p == NULL) {
        perror("malloc");
        exit(0);
    }
    
    /* Initialize allocated block */
    for (i=0; i<n; i++)
    	p[i] = i;
        
    /* Return allocated block to the heap */
    free(p);
}

n 바이트 만큼 heap 영역을 할당하고 포인터 p는 영역의 시작 부분을 가리킨다.

각 영역에 i 값을 넣어주고 free하여 영역을 해제한다.

영역이 해제되어도 안에 들어있는 i의 값은 없어지지 않는다.

 

3. Assumptions made in this lecture

(1) 메모리는 워드 단위

(2) 워드는 int 크기.

 

 블럭 한 칸의 크기는 word

 

(3) Allocation example

할당되는 코드의 순서는 변경할 수 없음

free(p2) 후 p4 = malloc(2)를 할 경우

빈 공간에서 영역을 선택하여 할당하게 되는데 알고리즘으로 구현 가능

 

(4) Constraints

- Applications : malloc 과 free의 요청에 대한 임의의 순서를 일으킬 수 있음

                   : free 요청은 malloc된 블럭에 대해 처리 됨

 

- Allocator : 할당된 블럭의 사이즈나 크기는 제어할 수 없음

               : malloc 요청에 대해 즉시 응답 -> 요청을 다시 수행하거나 버퍼링 불가능

               : 해제된 메모리로부터 블럭을 할당

               : 오직 해제된 메모리를 조작하거나 수정할 수 있음

               : malloc되면 할당된 블럭들은 이동할 수 없음 -> compaction x

 

 

 

4. Performance Goal : Throughput

(1) 일련의 malloc과 free 요청이 주어짐 : R0, R1,R2, ..., Rn-1

(2) 목표: throughput과 최대 메모리 활용량을 최대화

(3) throughput : unit 시간 당 완료된 요청의 수

    ex) 5000 malloc, 5000 free (10초) -> Throughput = 1000 operations/second

 

 

5. Performance Goal : Peak Memory Utilization

(1) 일련의 malloc과 free 요청이 주어짐 : R0, R1,R2, ..., Rn-1

(2) Aggregate payload Pk  ; payload - 실제 요청한 저장되는 데이터의 크기

   : malloc(p)는 p 바이트의 payload를 가진 블럭을 생성

   : 요청 Rk가 완료된 후, aggregate payload Pk는 최근에 할당된 payload의 합

(3) Current heap size Hk ; 현재 heap의 크기

   : Hk는 단조롭게 감소되지 않음 -> heap은 오직 allocator가 sbrk를 사용할 때 증가함

(4) Peak memory utilization after k+1 requests ; k+1의 요청 수행 후 최대 메모리 사용률

 

 

 

6. Fragmentation

(1) fragmentation으로 인한 메모리 사용률 감소

 - Internal Fragmentation

블럭이 주어졌을 때, internal fragmentation은 payload가 block size보다 작을 때 발생함

 

발생 원인 : heap 데이터 구조체 유지의 overhead, 정렬을 위한 패딩 (블럭의 뒷부분의 빈공간), Explicit policy decisions (작은 요청을 처리하기 위해 큰 블럭을 리턴)

 

이전 요청의 패턴에 의존함 -> 측정 쉬움

 

 

- External Fragmentation

aggregate heap memory가 충분할 때 발생하지만 싱글 free 블럭은 충분히 크지 않음

 

 

p4 = malloc(6)을 하기에 heap의 free한 블럭 수가 부족함

 

미래 요청에 대한 패턴에 의존함 -> 측정 어려움

 

 

 

7. 구현 문제점

(1) 주어진 포인터를 free하기 위해 얼마나 많은 메모리가 필요한지 우리는 어떻게 알 수 있을까

 

Naive한 구현은 forward하게 진행하여 뒷 부분에 할당되었다가 free된 부분을 재사용하지 않음

 

heap 영역에서 malloc(2)를 하면 2 블럭을 할당하고 포인터를 2칸 이동시킴

이전 포인터는 스택에 push하고 다시 pop하는데

ptr = malloc(2)에서 ptr에 pop한 이전 포인터를 할당

 

(2) free된 블럭을 어떻게 추적함?

(3) 존재하는 free 블럭보다 작은 구조체가 할당되었을 때, extra 공간으로 무엇을 해야함?

(4) 할당에 사용한 블럭을 어떻게 선택함? 많은게 좋나

(5) free된 블럭을 어떻게 다시 insert?