Splitting
힙 메모리를 관리하는 방법을 배워보자.
30바이트인 힙이 있다. malloc함수를 처리하기 위해 어느 위치가 free space인지 free list로 만들어 놓으면 관리하기 쉽다.
malloc은 연속된 공간을 반환해 주어야 한다.
만약 malloc(15);라고 요청이 들어온다면, 전체 free list는 20바이트긴 하지만 연속적인 공간이 아니어서 요청이 처리 될 수 없다.
malloc(1);요청이 들어오면 이 요청을 만족할 수 있는 free한 영역 두 공간이 있다. 운영체제는 정해진 정책에 의하거나 임의로 한 공간을 선택하게 된다. 그 후 요청한 사이즈 기준으로 공간을 나뉘게 된다. 1바이트를 요청했으니 1바이트와 9바이트로 나뉘게 된다. 그 후 1바이트를 malloc에게 반환해주고 9바이트를 free한 영역으로 관리해주게 된다.
이와 같이 요청한 사이즈가 free한 영역보다 작을 때, splliting 기법이 적용이 되며, splliting은 free chunk를 먼저 찾아 두 개로 쪼개는 기법이다.
Coalescing
위의 free list에서 malloc(15);를 요청하면 요청을 만족할 수 없다.
30바이트의 힙에서 모든 영역이 free하며, 이웃해있는 free 영역들을 하나로 묶어준다면, 10바이트가 넘어가는 메모리 요구도 수용할 수 있게된다.
Coalescing은 여러개의 free chunk가 서로 이웃해 있다면 이 free chunk를 합치는 기법이다.
Tracking The Size of Allocated Regions
free(void *ptr) 인터페이스는 크기를 매개변수로 받지 않는다. malloc이나 free가 구현되어 있는 c 라이브러리는 어떻게 할당된 사이즈를 알아서 free list에 넣어줄 수 있을까?
대부분의 allocators는 header라는 곳에 malloc을 수행할 때 사이즈의 정보를 저장하고, free가 수행될 때 header안에서 사이즈 정보를 꺼내와 그 사이즈만큼 힙에 다시 돌려주게 된다.
따라서 malloc함수가 호출이 되면 사이즈같은 extra information을 저장하기 위해 header도 같이 할당을 받아야 한다.
header의 크기가 8바이트라고 가정을 하면, malloc(20);의 요청을 했을 때 28바이트를 힙으로 부터 할당을 받게 된다.
The Header of Allocated Memory Chunk
헤더에는 할당되는 메모리의 사이즈 정보가 포함이 된다. 또한 free할 때 해제 속도를 향상시키기 위한 추가 포인터, 부가적인 무결성 검사를 제공하기 위한 매직 넘버 등 포함되어 있다.
header_t* h_ptr=(header_t *)hptr;
(*h_ptr).size=20;
(*h_ptr).magic=1234567;어떤 영역을 free할 때, 그 사이즈는 사용자에게 할당되는 사이즈와 헤더의 사이즈이다.
-> 만약 어떤 사용자가 n바이트의 malloc를 할당 받으면, malloc을 구현하는 c라이브러리는 n바이트와 헤더의 크기를 더한 사이즈를 만족시켜주는 free chunk를 찾고 그 free chunk를 splitting을 해주기 때문이다.
헤더의 포인터를 찾는 방법
void free(void *ptr) {
header_t *hptr = (header_t *)ptr -1;
}Embedding A Free List
malloc과 free를 구현하는 memory allocator을 제외한 typical memory-allocator은 free list를 구성하기 위해 각각의 노드를 동적으로 할당 받을 때, malloc를 호출하게 된다. 마찬가지로 노드가 필요없게되면 free함수를 호출해서 free list를 유지한다.
그럼 malloc과 free를 구현하는 memory allocator은 내부에 free list를 어떻게 관리할 수 있을까?
malloc과 free를 구현하는 memory allocator에서 free list의 각각의 노드는 size값과 next 포인터 값을 가지게 된다.
물리 메모리에서 4k 공간을 선택하고 그 공간을 현재 프로세스의 address space에 mapping해준다(힙 공간이 할당된다고 보면 됨). mapping한 곳의 시작주소를 mmap이 리턴해줘 head라는 포인터변수에 저장한다.
head포인터를 가지고 size와 next 값을 넣어준다. 전체적으로 4K의 free한 영역을 힙으로 할당했고 그 안에다가 free list node를 embedding 시키는 것을 볼 수 있다.
결과적으로 4kb의 힙을 할당 받았을 때 초기 모습은 다음과 같을 것이다.
이제 100바이트의 메모리 요청이 들어온다고 가정하자.
ptr = malloc(100);을 실행
malloc 라이브러리는 힙 영역에 the size header(8) + the allocated size(100) 바이트의 메모리 요청을 처리할 수 있는 free chunk를 free list에서 찾게된다.
첫번째 노드를 보면 4088바이트 만큼의 영역을 할당할 수 있으니 108바이트와 3980바이트로 splitting이 진행된다.
free list의 head는 16KB + 108의 값을 갖게 되고 size는 3980 next는 0값을 가지게 된다.
3번의 malloc함수가 수행되면 다음 그림과 같다.
이제 2번째 chunk를 free(sptr)하여 공간을 반환하려한다.
결과는 다음과 같다.
malloc이 호출되면 splitting이 발생할 수 있고, free가 호출되면 coalescing이 발생할 수 있다.
하지만 1번과 2번 영역은 인접해있지 않기에 coalescing이 불가능하다.
이제 남은 두 chunk를 free하게 되면 다음과 같다.
free가 호출 된 순서는 1 2 3 4번이므로, free list의 순서는 4 3 2 1 순서가 된다.
여기서 malloc(4000);을 하면 요청이 수행이 될 수 없다. (외부 단편화)
모든 노드가 인접해 있으니 coalescing 수행을 할 수 있고, coalescing이 마치게 되면 head에는 16384의 값이 size에는 4088, next에는 0의 값이 들어간다.
Growing The Heap
대부분의 memory allocator은 메모리 공간을 절약하기 위해 작은 사이즈의 힙으로부터 시작하게 된다.
예를들어 hello world와같은 프로그램을 짜게되면 이 프로그램은 힙을 거의 사용하지 않게 된다. 만약, 이러한 작은 프로그램한테 넓은 공간의 힙을 할당해 준다면 메모리를 낭비하게 될 것이다.
대부분의 memory allocator은 작은 공간의 힙에서부터 시작해서 동적인 메모리 요청이 증가할 때 마다 더 많은 힙 메모리를 달라고 OS에게 요청한다.
이때, sbrk(), brk() 시스템 콜을 통해 운영체제에게 요청하게 된다.
Managing Free Space: Basic Strategies
여기에 malloc(20);을 수행한다고 하자.
Best Fit: 리스트에 있는 노드들을 모두 검사해보고 20바이트를 만족시킬 수 있는 노드들 중 가장 작은 사이즈의 노드를 리턴
Worst Fit: 리스트에 있는 노드들을 모두 검사해보고 20바이트를 만족시킬 수 있는 노드들 중 가장 큰 사이즈의 노드를 리턴. 3번째 노드가 리턴되고 splitting이 발생한다.
First Fit: free list를 전부다 선회하지 않고, 앞에서부터 찾아보다가 사용자의 요청을 만족시키는 노드가 나오면 바로 리턴.
장점: 리스트의 모든 내용을 순회하지 않아 속도 빠름
단점: 앞에서부터 리스트를 검사하기 때문에 앞쪽에는 splitting이 많이 발생해 사이즈가 작은 노드들만 남게되고, 뒤쪽에는 사이즈가 큰 노드들만 남는다.
Next Fit: First Fit 보완한다. 리스트 전체를 순회하지 않아도 된다.
Other Approaches: Segregated List
Segregated List는 같은 사이즈의 malloc 요청을 반복적으로 수행했을때 이것을 어떻게 효율적으로 수행할까?
Segregated List는 일반적으로 힙에서 어느정도 큰 크기의 메모리를 한꺼번에 할당받고, 이 메모리를 자주 사용되는 바이트의 사이즈의 맞게 쪼개서 배열로 만들어 두게 된다. 만약 반복문 안 malloc(2);이 수행되면, 바로 힙으로 보내지 않고 만들어 두었던 배열에 메모리를 크기에 맞게(2바이트)에 쪼개서 처리한다.
Other Approaches: Buddy Allocation
