이 장에서는 메모미 가상화 논의에서 약간 우회하여 메모리 관리 시스템의 근본적인 측면을 논의한다. 메모리 관리 시스템이란 malloc()(프로세스 힙 페이지 관리)일 수도 있고, 운영체제(프로세스 주소공간의 일부 관리)일 수도 있다.
특히, 빈 공간 관리에 초점을 둘 것이다.
페이징 개념을 다룰 때 논의하겠지만, 관리하는 공간이 고정된 크기를 가진다면 빈 공간 관리가 더 쉽다.
그러나 빈 공간들이 가변-크기를 가지게 된다면 재미있어진다. 이런 경우는 malloc() - free()를 사용하는 사용자 수준 메모리 라이브러리나, 세그멘테이션 기반 물리메모리 관리 시스템에서 발생한다. 어느 경우네는 외부 단편화가 존재하게 되기 때문에 빈 공간 관리가 중요하다.
1. 가정
- malloc(), free()에서 제공하는 것과 같은 기본 인터페이스를 가정
- 외부 단편화 방지에 초점을 둔다
- 클라이언트에게 할당된 메모리는 재배치될 수 없다.
2. 저수준 기법들
분할과 병합
다음과 같이 30바이트의 힙이 있다고 가정하자.
빈 공간 리스트에는 2개의 원소가 있다. 각 원소는 주소와 주소 공간의 길이를 가진다.
만약 10바이트가 초과하는 요청에 대해서는 실패하여 NULL을 반환하게 된다. 그러나 10바이트보다 작은, 1 바이트의 요청이 온다면 어떻게 될까?
분할 작업이 발생한다. 2번째 빈 공간이 1과 9의 청크로 나뉘어지게 되고, 1바이트 청크는 리턴되고 남은 청크는 리스트에 남게 된다. 시작 주소가 21이되고 길이가 9로 줄었다.
첫번째 예시에서 이번에는 free(10)이 발생한 상황을 생각해보자. 반환된 공간이 빈 공간 리스트에 들어갈 것이다.
이 경우 10 바이트가 넘는 요청에 대해서 처리를 하지 못하게 될 것이다. 이를 위해 병합 작업이 이루어진다. 새로 해제된 공간이 좌우의 청크와 인접해있다면 병합한다.
할당된 공간의 파악
free(void *ptr) 인터페이스는 크기를 매개변수로 받지 않는다. 포인터가 인자로 전달되면 메모리 영역의 크기를 알아서 파악하여 해당 공간을 빈 공간 리스트에 포함시킨다.
이를 위해 추가 정보를 header블럭에 저장한다.
헤더 블럭에는 할당된 공간의 크기, 무결성 검사를 위한 매직 넘버 등의 기타 정보를 저장한다.
그래서 만약 사용자가 N바이트의 메모리 청크를 요청하게 되면, 라이브러리는 N바이트의 빈 청크를 찾는 것이 아니라 N+헤더 크기 만큼의 메모리 청크를 탐색한다.
빈 공간 리스트 내장
링크드리스트 방식을 활용한다.
 |  |
|---|
3. 기본 전략
빈 공간 할당을 위한 여러가지 방식이 존재한다. 이상적인 할당기는 속도가 빠르고 단편화를 최소로 해야한다. 그러나 할당과 해제 요청은 무작위로 프로그래머에 의해 결정되기 때문에, 입력에 따라 성능이 달라게 된다. 그러니 많이 사용되는 전략들에 대해 논의만 해보겠다.
최적 적합(Best Fit)
빈 공간 리스트를 검색하여, 요청한 크기와 같거나 큰 메모리 청크를 찾고, 그 후보자 중에서 가장 작은 청크를 반환한다. 한번의 탐색으로 찾을 수 있다.
최적의 크기의 청크를 리턴하기 때문에 공간의 낭비를 줄일 수는 있겠지만, 항상 전체를 탐색하기 때문에 성능저하가 있을 수 있다.
최악 적합(Worst Fit)
최적 적합과 반대로, 가장 큰 빈 청크를 찾아 요청된 크기 만큼만 반환하고, 남은 부분은 빈 공간 리스트에 유지한다. 최적 적합에서 남기는 작은 청크들 방식과는 다르게 최대한 많은 큰 청크를 남기려고 시도한다.
마찬가지로 모든 리스트를 탐색하야하며, 대부분의 연구에서 엄청난 단편화가 발생하여 오버헤드 또한 크다.
최초 적합 (First Fit)
간단하게 요청보다 큰 첫번째 블럭을 찾아서 요청만큼 반환한다.
속도가 빠르다는 것이 장점이다. 그러나 리스트의 시작에 수많은 크기가 작은 객체가 생길 수 있다. 이를 해결하기 위해 주소-기반 정렬 방식을 통해 병합을 쉽게하여 단편화를 감소시킬 수 있다.
다음 적합 (Next Fit)
항상 리스트의 처음부터 탐색하는 것이 아니라, 이전에 찾았던 원소를 가리키는 포인터를 유지하고 그 부분부터 탐색을 진행한다. 전체 탐색 방식이 아니기 때문에 최초 적합의 성능과 비슷하다.
4. 다른 접근법
개별 리스트(Segregated Lists)
특정 응용프로그램이 자주 요청하는 청크 크기가 있다면, 그 크기의 청크를 관리하는 별도의 리스트를 유지하는 것이다. 다른 모든 요청들은 일반적인 할당기에 전달된다.
특정 크기의 요청을 위한 청크가 있기 때문에 메모리 단편화 가능성이 상당히 줄어든다. 또한 고정된 크기의 할당과 해제는 검색이 필요 없기 때문에 속도도 빠르다.
그러나 문제는, 특정 크기의 메모리 풀과 일반적인 메모리 풀에 각각 얼마만큼 메모리를 할당해야 할까?이다. Solaris 커널에서는 특수 목적 할당기인 슬랩 할당기(Slab allocator)를 통해 이런 문제를 해결했다.
커널이 부팅될 때, 커널 객체를 위한 여러 객체 캐시를 할당한다. 락, 파일 시스템 아이노드 등 자주 요청되는 자료구조를 캐시로 가진다. 객체 캐시란 지정된 크기의 객체들로 구성된 빈 공간 리스트이기 때문에 할당과 해제가 빠르다. 캐시 공간이 부족하면 추가 슬랩을 요청하고, 참조 횟수가 0이면 슬랩을 회수할 수 있다.
슬랩 할당기 방식은 빈 객체들을 사전에 초기화된 상태로 유지한다는 점에서 개별 리스트보다 우수하다.
→ 마치 스레드풀/커넥션풀과 같은 느낌?
버디 할당(Buddy Allocation)
빈 메모리를 개념적으로 의 크기 공간으로 생각한다. 요청에 대해 적절한 공간을 찾을 때까지 분할한다. 7KB의 요청에 대해서 3번의 분할을 거쳐 8KB의 메모리 블럭이 할당된다. 당연히 33KB 같이 애매하게 큰 요청에 대해서 내부 단편화가 발생할 수 있다.
버디 할당기의 꽃은 메모리 해제 과정이다. 할당된 공간이 다음 공간의 크기와 같다면 병합이 이루어진다. 병합된 크기가 또 다음 공간과 크기가 같다면 또 병합이 이루어지는 것이 반복된다.
그런 뒤 이 공간을 해제할 때는 바로 자신과 함께 쪼개진 메모리, 즉 buddy를 찾고 사용하고 있지 않다면 바로 합병한다. 이렇게 하면 합병을 쉽게 할 수 있다.
기타 아이디어
위 방법들을 확장성에 문제가 있다. 빈 공간의 개수가 늘어나면서 리스트 검색이 느려질 수 있다.
이를 위해 BST, 스플레이 트리, 부분 정렬 트리 등의 자료구조를 활용하기도 한다.
