개념

• 런타임에서 가상메모리를 얻기 위해 동적 메모리 할당기를 사용한다.
  • 동적 메모리 할당기는 힙이라 하는 프로세스의 가상 메모리 영역을 관리한다.
  • 힙의 꼭대기를 brk(break)라 한다.
• 할당기는 힙을 다양한 크기의 블록의 집합으로 관리한다.
  • 각 블록은 할당되었거나 free되었다.
• 할당기는 두 종류가 있다.
  • 명시적 할당기
    • 할당과 free 둘다 가능하다.
    • C의 malloc 과 free
  • 묵시적 할당기
    • 할당만 가능하다. 자동으로 free를 해준다.
    • 자바의 가비지 컬렉션, ML, Lisp

malloc 패키지

• malloc, free, calloc, realloc, sbrk

할당과 free의 동작방식

동적 메모리 할당 사용 이유

• 프로그램을 실행시키기 전에는 자료 구조의 크기를 알 수 없는 경우들이 있어서다.

  #include "csapp.h"
  #define MAXN 15213
  
  int array[MAXN];
  
  int main() {
  	
  	int i, n;
  	
  	scanf("%d", &n);
  	if (n > MAXN)
  		app_error("Input file too big");
  	for (i = 0; i < n; i++)
  		scanf("%d", &array[i]);
  	exit(0);
  }
  

  • 임의로 MAXN을 정의하는 경우를 예로 든다.
    • MAXN은 임의로 정한 값으로 실제 머신에서 가용한 가상메모리 크기와 무관하다.
    • 사용자가 MAXN보다 더 큰 파일을 읽으려고 하면, 유일한 대책은 프로그램을 더 큰 MAXN을 사용하여 컴파일 하는 것이다.
    • 또한, 이렇게 임의로 정하게 되면 많은 케이스가 나뉘게 될 때 문제가 발생한다. (수백만라인의 코드, 수많은 사용자 등등)

  #include "csapp.h"
  
  int array[MAXN];
  
  int main() {
  	
  	int *array, i, n;
  	
  	scanf("%d", &n);
  	array = (int *)malloc(n * sizeof(int));
  	for (i = 0; i < n; i++)
  		scanf("%d", &array[i]);
  	free(array);
  	exit(0);
  }
  

  • 차라리 n값을 알 수 있을 때, 배열을 런타임에 동적으로 할당하는 게 낫다.

할당기의 제약

• 애플리케이션에서
  • malloc과 free의 호출이 무작위로 들어와도 처리 가능해야 한다.
  • free 요청은 malloc 된 block에 해야 한다.
• 할당기에서
  • 이미 할당된 블록들의 크기를 맘대로 조절할 수 없다.
  • malloc 요청에 즉시 응답해야 한다.
  • free된 메모리에 블록을 할당해야 한다.
  • 블록들을 정렬해야 한다. (?)
    • 모든 정렬 요건에 부합하도록 해야 한다.
  • free한 메모리만 조정하거나 수정해야 한다.
  • malloc 되면 block을 할당할 수 없다.

할당기의 목표

• 할당기의 처리량을 최대화한다.
  • 1초당 500개 malloc 요청 & 500개 free요청 처리 → 초당 1000 연산
• 메모리의 이용도를 최대화한다.
  • 최고 이용도라는 단위를 활용한다.
  • 최고 이용도
• 실제로 위의 두 지표들 사이에선 트레이드-오프가 좀 있다.

단편화