Dynamic Memory Allocation

I. Static vs Dynamic

Static

pre-runtime에 무언가를 한다는 뜻이다.

Dynamic

runtime에 무언가를 한다는 뜻이다.

Static Memory Allocation

code segment, data segment의 경우 링킹 단계에서 memory address를 할당하기 때문에 static memory allocation을 한다고 볼 수 있다.

Static Memory Allocation은 변수의 lifecycle이 프로그램 시작/종료와 일치한다는 특징을 갖는다.

Dynamic Memory Allocation

stack segment, heap segment의 경우 runtime에 memory address를 할당하기 때문에 dynamic memory allocation을 한다고 볼 수 있다.

II. 왜 Dynamic Allocation이 필요한가?

예측 불가능성 때문이다.

#include <stdio.h>

void foo();
void bar();

int main(void) {
	int sum = 0;
	
	for (int i = 0; i < 10; i++) {
		sum += i;
	}

	if (sum > 50) {
		foo();
	}	
	else {
		bar();
	}

	return 0;
}

void foo() {
	int arr[1];
	printf("foo");
}

void bar() {
	int arr[1000000];
	printf("bar");
}

III. Heap

Fragmentation

alloc과 free가 반복되다 보면 힙에 작은 hole 들이 발생하게 되고 이로 인해 남은 공간이 충분함에도 메모리 할당을 할 수 없는 현상이 발생한다. 그리고 이 현상을 fragmentation 이라고 부른다.

fragmentation은 시스템 성능에 매우 안좋은 영향을 미친다. 충분한 메모리 용량을 갖고 있음에도 메모리 할당을 할 수 없어서 프로그램 실행이 중단되는 일이 발생하기 때문이다.

Anti-fragmentation approaches

buddy allocator, slab allocator, paging 등의 있고 리눅스에서는 buddy allocator 와 slab allocator를 섞어서 쓴다.

Free list

힙은 각 hole을 노드로 하는 list인 free list로 관리한다. 구체적으로 각 hole의 first word가 포인터로 사용된다.

computer scientist들은 memory request가 들어왔을 때 free list에서 어떤 hole을 할당할지 고민을 많이 했다.

best-fit

가능한 가장 작은 hole을 할당한다.

first-fit

가능한 첫 번째 hole을 할당한다.

worst-fit

가능한 가장 큰 hole을 할당한다.

얼핏 보면 best-fit이 가장 좋을 것 같지만 best-fit의 경우 발생하는 hole의 크기가 너무 작아진다는 문제가 있다.

policy만 가지고는 fragmentation 문제를 해결하기 힘들다는 결론을 내릴 수밖에 없다.

Memory Pool

fragmentation이 발생하는 근본적인 이유는 요구하는 메모리 사이즈와 홀의 사이즈가 딱 맞지 않기 때문이다. 이를 해결하기 위해서 unit size를 정해놓고 unit size로만 메모리 요청을 할 수 있도록 강제하는 방법을 생각해 볼 수 있다.

하지만, 이 방법으로도 fragmentation 문제는 해결할 수 없다.

unit size를 작게 잡는다면 unit size 보다 큰 memory request에 의해 외부 fragmentation이 발생하게 된다.

unit size를 크게 잡는다면 unit size 보다 작은 memory request에 의해 내부 fragmentation이 발생하게 된다.

그렇다면 memory request의 크기에 따라 유동적으로 메모리를 할당하는 것은 어떨까?

메모리 풀은 unit size로만 메모리 요청을 할 수 있도록 강제하되 다양한 unit size를 허용하는 기법이다. 예를 들어, 1.8K 크기의 메모리 요청이 들어온다면 2K free list에 있는 2K 크기의 노드를 할당하는 것이다.

하지만 메모리 풀 역시 fragmentation 문제를 완전히 해결할 수는 없다. 예를 들어, 1K 크기의 메모리 요청만 빈번하게 이루어진다면 1K free list가 소진되는 순간부터 1K 크기의 메모리를 할당할 수가 없게 된다.

그럼에도 불구하고 메모리 풀은 굉장히 유용하기 때문에 현실에서 많이 사용한다.