Heap Memory Introduction(2)

Intro to Allocating

What is the silliest malloc and free implementation and what is wrong with it?

void* malloc(size_t size)
// Ask the system for more bytes by extending the heap space. 
// sbrk Returns -1 on failure
   void *p = sbrk(size); 
   if(p == (void *) -1) return NULL; // No space left
   return p;
}
void free() {/ Do nothing */}

위 코드는 두가지 단점이 있습니다.

1. system call은 library call에 비해 느립니다. 그러므로 많은 양의 메모리를 할당받아 온 후 다 사용하면 system에게 메모리를 요청하여 system call의 호출 횟수를 줄여야 합니다.

2. free된 메모리를 재사용하지 않고 있습나다. heap memory를 재사용하지 않고 더 큰 heap을 요청하기만 하고 있습니다.

만약 일반적인 프로그램에서 이러한 방식으로 allocator가 동작하면 프로세스는 빠르게 사용할수 있는 메모리를 모두 다 사용해 버릴 것입니다. 이러한 allocator 대신에 heap 공간을 더 효율적으로 사용하고 메모리가 더 필요할 때만 더 많은 메모리를 요청하도록 동작하는 alloctor가 필요합니다.

What are placement strategies?

프로그램이 동작하는 메모리가 할당되었다가 free되는 동안에 heap memory에는 나중에 할당 요청이 왔을때 사용할 수 있는 메모리의 구멍이 생기게 됩니다.  memory allocator는 heap의 어느 부분이 현재 할당되어 있는지, 어느 부분이 사용 가능한지 항상 추적해야 합니다.

 현재 heap size가 64K라고 가정해 봅시다. 하지만 이미 할당된 공간의 일부분이 free되어 모든 heap이 사용중이지는 않습니다. 

16KB free	10KB allocated	1KB free	1KB allocated	30KB free	4KB allocated	2KB free

heap이 이러한 상황에서 2KB의 메모리 할당이 요청되면(malloc(2048)) 메모리를 절약하기 위해서 어디에 할당되어야 할까요?

크기가 정확히 일치하는 맨 마지막 2KB hole에 할당되거나, 다른 두개의 free된 hole을 2개로 나눠 할당받을 수도 있습니다. 

어떤 hole이 선택되든 allocator는  새로 할당되어 프로그램에 return될 memory와 남아있는 여분의 memory 공간 두개로 나눌 필요가 있습니다.

perfect-fit strategy는 2KB가 들어가기에 충분한 가장 작은 hole을 찾습니다.

위의 경우라면 가장 끝에 2KB가 딱 맞으므로 그곳에 할당되게 됩니다.

16KB free	10KB allocated	1KB free	1KB allocated	30KB free	4KB allocated	'2KB HERE!'

Worst-fit strategy라면 남아있는 hole중 가장 큰 hole에 할당해 줍니다. 즉 위에서라면 30KB에 할당하여 둘로 나누어집니다.

16KB free	10KB allocated	1KB free	1KB allocated	2KB HERE!	28KB free	4KB allocated	2KB free

first-fit strategy라면 순서대로 찾다가 들어가기에 충분한 크기의 hole을 찾으면 바로 사용합니다. 즉 가장 처음 16KB에 할당해 2개로 나눌 것입니다.

2KB HERE!	14KB free	10KB allocated	1KB free	1KB allocated	30KB free	4KB allocated	2KB free

What is external fragmentation?

아래의 예처럼 64KB의 heap에서 실제로는 17KB만 할당이 되었고 나머리 47KB는 할당이 되지 않았지만 실제로 할당할 수 있는 가장 큰 크기는 30KB입니다. 아래의 그림처럼 heap memory가 작은 조각들로 fragmentation되었기 때문입니다.(alloc 후 free하여)

16KB free	10KB allocated	1KB free	1KB allocated	30KB free	4KB allocated	2KB free

What effect do placement strategies have on external fragmentation and performance?

Different strategies affect the fragmentation of heap memory in non-obvious ways, which only are discovered by mathematical analysis or careful simulations under real-world conditions (for example simulating the memory allocation requests of a database or webserver).

Best-fit이 얼핏 보기엔 가장 좋은 전략 같지만 이 전략은 딱 맞는 hole을 찾지 못한다면 사용할 수 없는 매우 작은 hole을 많이 만들어내 fragmentation이 심해질 것입니다. 또한 최적의 hole을 찾기 위해서는 모든 hole을 scan해야 하므로 performance도 좋지 못합니다.

First-fit은 가능한 모든 hole을 찾지 않아도 되므로 속도적인 측면에서 유리합니다.

Worst-fit은 할당되지 않은 공간 중 가장 큰 공간을 목표로 하므로 큰 공간 할당이 필요할 때는 좋지 못한 선택입니다(?) -->>이유를 좀 더 알아보자!!

실제로는 first-fit과 여기서는 소개되지 않은 next-fit이 많이 사용되어집니다. 이러한 hybird approaches나 다른 대안들이 존재합니다.

What are the challenges of writing a heap allocator?

• Fragmentation을 최소화할 수 있는 방법(memory utilization을 최대화 하기)
• High performance

• Linked list와 pointer 연산을 사용한 포인터 조작

 추가 코멘트

fragmentation과 performance는 평가할수는 있지만 예측할 수는 없는 application allocation profile에 의존합니다. 특정한 상황에서는 특정한 목적의 allocator가 일방적인 목적의 수행보다 더 뛰어난 성능을 발휘하기도 합니다

allocator는 프로그램의 memory allocation을 미리 알지 못합니다. 만약 그렇다고 해도 NP hard로 알려진 knapsack problem이 될 것입니다.