Free-Space Management

메모리 가상화에서 조금 벗어나서, 메모리 관리 시스템의 기본적인 측면에 대해 알아보자 malloc 라이브러리나 운영체제 자체, 자유 공간(free-space) 관리와 같은 것들에 대해 논의할 것이다.
자유공간을 관리하는 것은 페이징(paging)으로 하면 간단할 수 있다.
자유 공간 관리가 어려워 지는 것은 공간이 변수 크기의 단위로 구성된 경우이다. 이는 malloc,free라이브러리나 세그멘테이션을 쓰는 운영체제에서 발생한다.
외부 단편화가 대표적인 문제이다. 연속적인 공간이 없어서 요청을 처리할 수 없다.

자유공간을 어떻게 관리해야 효율적은 운용이 가능해질까?

Assumptions 가정

malloc(), free() 와 같은 기본 인터페이스를 가정한다.
void *malloc(size_t size) 은 size 매개변수를 취해 포인터를 반환한다.
void free(void *ptr)은 포인터를 취하고 메모리 청크를 해제한다.

이 라이브러리가 관리하는 공간은 힙(heap)이다. 힙 내의 자유공간을 관리하기 위해 일반적으로 사용되는 데이터 구조는 자유 리스트(free list)이다.

내부 단편화라는 문제도 있다. 내부 단편화는 요청된 것보다 큰 메모리 청크를 할당할 경우 사용되지 않는 공간이다. 하지만 우리는 외부 단편화에 더 집중을 할 것이다.

또, 한 번에 메모리가 클라이어언트에게 전달되면, 메모리를 다른 위치로 재배치할 수 없다고 가정하자 예를 들어 malloc()으로 할당받은 메모리는 free()로 해제하기 전까지 해당 프로그램에게 종속된 것이다. 따라서 외부 단편화를 해결하기 위한 재배치와 압축은 불가능하다.

마지막으로, 할당기가 바이트의 연속적인 영역을 관리한다고 가정하자 메모리는 공간이 부족할때 확장될 수 있다. 하지만 간단함을 위해 항상 고정된 크기의 메모리를 가진다고 가정한다.

• 외부 단편화에 집중
• 메모리 재배치 X
• 메모리 할당시에 연속적인 공간을 할당하며 크기 변경 X

Low-level Mechanisms

대부분의 할당기에서 사용하는 분할과 통합(Splitting and Coalescing)에 대해 알아보자
그 후, 할당된 영역의 크기를 쉽고 빠르게 추적하는 방법과, 자유 공간 내부에 목록을 만들어 추적하는 방법을 알아보자

Splitting and Coalescing 분할과 통합

다음과 같은 30Byte 힙이 있다고 가정해보자

아래와 같은 free space를 나타내는 리스트도 있다. (우리가 찾고 싶은건 free space 이기에 free space 만 나타내는 자료구조가 있으면 된다.)

연속된 free space의 크기가 10Byte 이하이기에 그것보다 큰 메모리의 할당은 불가능하다. 그렇다면 그것보다 작은 메모리(예:1 Byte)의 할당은 할 수 있나? 이 경우 할당기는 분할(Splitting)을 수행한다.
분할을 통해 10의 크기의 메모리 청크를 1과 9로 나누어 다음과 같이 바뀌었다. (여기서 남은 free space 중 어느것을 선택하느냐도 따져야할 문제이다. 나중 포스팅에서 나온다.)

이 때, 모든 메모리를 해제한다면, (리스트에서 맨 앞에 놓으면 O(1) 맨 뒤에 놓으면 O(n)이라 앞에 놓았다.)

10의 크기의 free space 가 3개가 되었다. 이 경우 10보다 큰 메모리 할당이 불가능하기에 통합(Coalescing)을 수행한다.

Tracking The Size Of Allocated Regions 할당된 메모리 크기 추적

free()는 크기 매개변수를 취하지 않는다. 따라서 malloc() 라이브러리가 메모리 영역의 크기를 결정해야한다. 이를 위해 할당기는 메모리에 유지되는 헤더 블록에 정보를 저장한다.

20 Byte를 할당하면, 바로 앞의 헤더에, 할당된 영역의 크기, 무결성 검사(포인터가 다른 메모리를 침범하면 매직넘버가 일치하지 않는다.)를 위한 매직넘버등이 저장된다. free() 호출시 헤더의 정보를 보고 메모리를 해제한다.
메모리의 크기는 할당된 공간과 헤더의 크기를 더한 것이다. 따라서 N 바이트의 메모리를 요청하면 헤더의 크기+N의 자유 공간을 찾는다.

Embedding A Free List

free space 를 관리하기 위한 자료구조를 따로 만들면 그것을 위한 메모리가 필요하고 malloc을 하기 위한 malloc을 하는 꼴이 나올 수 있다. 그래서 프로세스 메모리 영역 내에서 메모리를 표현한다. 다음 예시를 보면 할당된 메모리의 헤더가 다음 메모리를 가리키는 것을 볼 수 있을 것이다.

힙 내의 자유 메모리 청크 목록인 자유 리스트(free list)가 어떻게 존재하는지 알아보겠다.

4096바이트의 메모리 청크(4KB의 힙)를 관리해야하고 힙이 mmap() system call로 얻은 freespace내에 구축되었다고 가정하자.

typedef struct __node_t {
    int size;
    struct __node_t *next;
} node_t;

// mmap()은 자유 공간의 청크에 대한 포인터를 반환합니다.
node_t *head = mmap(NULL, 4096, PROT_READ|PROT_WRITE,MAP_ANON|MAP_PRIVATE, -1, 0);
head->size = 4096 - sizeof(node_t);
head->next = NULL;

이 코드를 실행하면, 하나의 free 청크에 힙이 생긴다.

여기서 100 바이트의 메모리 청크가 요청되었다면,
1. 청크 선택 (여기서는 청크가 하나이므로 이 청크가 선택된다.)
2. 청크 분할 (요청을 처리할 만큼의 크기와 남은 크기로 분할)
이 되어 다음과 같이 된다.

이제 100 바이트 세 개를 할당한다면,

중간의 메모리를 해제-free(16500)-한다면,

free space가 나눠지게 되었다.
마지막으로 모든 메모리가 해제된다면,

병합을 하지 않았기에 free space 들이 모두 떨어져있다. (단편화) 이것들을 모두 하나로 만들기 위해 병합을 해야한다. (free space들이 인접하다면 합친다.)

Growing The Heap 힙 확장

만일 구현한 힙 공간이 부족하다면 어떻게 해야할까? 메모리 할당 요청을 무작정 거절할 수도 있지만, 보통 할당자들은 작은 크기의 힙으로 시작하여 OS에 추가 메모리를 요청한다. 그러면 system call(예: UNIX의 sbrk)을 하여 새로운 청크를 할당한다. OS는 빈 페이지를 찾아서 요청 프로세스의 주소공간에 매핑하고 새로운 힙의 끝 값을 반환한다.

Basic Strategies 전략들

free space를 관리하기 위한 전략들을 알아보겠다. 이상적인 할당기는 빠르고 메모리 조각을 덜 내야한다.

• Best Fit
  자유 리스트를 검색하여 같거나 큰 자유 메모리 청크를 찾고 그 중 가장 작은 것을 반환한다. 자유 리스트를 한 번만 통과하면 올바른 청크를 찾을 수 있다. 요청된 크기와 가장 비슷한 청크를 반환해서 낭비되는 공간을 줄이려하지만 검색을 할 때 비용이 발생한다.
• Worst Fit
  Best Fit의 반대이다. 가장 큰 청크를 찾아 요청된 양을 반환하고 남은 청크는 자유 리스트에 유지한다. 이것 또한 검색에 비용이 발생하고 조각을 많이내며 성능이 안좋다.
• First Fit
  큰 블록 중 첫 번째 블록에서 요청된 양을 반환한다. 모든 공간을 검색하지 않기에 빠르다. 하지만 메모리 사용에 최적화된 방법은 아니다. 앞 쪽에서만 할당하느라 앞 부분은 단편화가 생겨서 결국은 뒤에 까지 검색해야할 수 있다.
  이는 할당기가 자유리스트 순서를 관리하는 방법이 문제가 되는 것인데, 주소 기반 순서를 사용함으로써 정렬된 리스트를 유지하고 병합을 하여 조각화를 줄일 수 있다.
• Next Fit
  First Fit 과 비슷하지만 마지막으로 할당된 위치 다음부터 검색한다.
• 예시
  다음과 같은 자유 리스트가 있다고 해보자
  
  크기가 15인 할당 요청이 있다면, Best Fit은 20을 찾을 것이다.
  
  Worst Fit 은 30을 찾는다.
  
  First Fit 도 30을 찾지만 30에서 검색이 멈추기에 비용이 더 적다.

Other Approaches 다른 접근들

• Segregated Lists 분리된 리스트
  자주 요청되는 메모리 크기가 있다면, 그 크기를 위한 목록을 유지하는 것이다. 검색에 비용을 많이 쓰지 않으며, 메모리가 나뉘는 것을 줄일 수 있다.
  특정 할당기인 Slab 할당기가 그것을 실현시킨다. 구체적으로, 커널이 부팅될 때 자주 요청될 것으로 예상되는 커널 객체에 대한 여러개의 객체 캐시를 할당한다. 이런 객체 캐시는 특정 크기의 free list이며 메모리 할당,해제 요청을 빠르게 처리한다.
  특정 캐시의 공간이 부족해지면 일반 메모리 할당기로부터 메모리를 요청한다. 반대로 특정 슬랩의 객체 참조 카운트가 0이면, 일반 할당시가 특수 할당기로부터 메모리를 회수할 수 있다.

• Buddy Allocation 친구 할당
  할당기에 있어서 병합은 중요하기에 일부 접근법을 병합이 간단해지게 설계하였다.
  Buddy Allocation은 메모리를 크기가 $2^n$인 하나의 큰 공간으로 생각한다. 메모리 요청이 있으면 요청을 수용할 수 있는 가장 작은 블록을 찾을 때 까지 재귀적으로 반으로 나눈다.
  
  메모리가 해제될 때는 할당될 때 쪼개진 한 쌍의 나머지 하나(버디)를 찾아 사용하고 있지 않다면, 병합한다. 버디 쌍의 주소가 한개의 비트만 차이남으로 특정 블록의 버디를 결정하는 것이 간단하다.(이진 트리)