빈 공간 관리#
가정[1]#
이 논의의 대부분은 사용자 수준 메모리 할당 라이브러리에 존재하는 메모리 할당기의 발전 역사에 초점을 맞출 것입니다.
malloc()과 free()에서 제공하는 것과 같은 기본 인터페이스를 가정합니다. 구체적으로 void *malloc (size_t size)는 응용 프로그램이 요청한 바이트 수를 나타내는 변수 size를 받아들입니다. 이 함수는 요청된 크기와 같거나 큰 영역을 가리키는, 타입이 없는 또는 C 언어의 용어로 void 포인터를 반환합니다. 대응되는 루틴 void free(void *ptr)는 포인터를 인자로 전달받고 해당 영역을 해제합니다.
인터페이스의 의미에 주의하세요. 공간을 해제할 때 사용자는 라이브러리에게 크기 정보를 전달하지 않습니다. 라이브러리는 포인터만으로 해제하고자 하는 메모리 영역의 크기를 파악해야 합니다. 크기를 알아내는 방법에 대해 나중에 논의할 것입니다.
이 라이브러리가 관리하는 공간은 역사적으로 힙(heap)으로 불리며, 힙의 빈 공간을 관리하는 데는 일반적으로 링크드 리스트가 사용됩니다. 이 자료 구조는 영역 내의 모든 빈 청크에 대한 주소를 갖고 있습니다. 물론, 이 자료 구조는 반드시 리스트일 필요는 없고 빈 공간들을 표현할 수 있는 자료 구조면 충분합니다.
우리는 위에서 언급한 것처럼 외부 단편화 방지에 특히 중점을 두겠습니다. 물론, 내부 단편화 문제도 있을 수 있습니다. 할당기가 요청한 크기보다 더 큰 메모리 청크를 할당할 경우, 요청되지 않은 사용되지 않는 공간에 대해서는 할당 청크의 내부에서 낭비가 일어났기 때문에 내부 단편화라고 간주됩니다. 할당 공간 낭비의 또 다른 예라고 할 수 있습니다. 논의를 단순화하기 위하여, 그리고 두 유형 중 더 흥미롭기 때문에 외부 단편화에 초점을 맞출 것입니다.
외부 단편화(External Fragmentation): 메모리에 할당되지 않은 작은 빈 공간들이 여러 곳에 산재해 있는 현상을 말합니다. 이러한 작은 빈 공간들은 새로운 메모리 할당 요청을 만족시키기에는 충분히 크지 않아서 메모리 낭비를 초래합니다.
내부 단편화(Internal Fragmentation): 할당된 메모리 블록 내부에서 발생하는 낭비를 말합니다. 할당된 블록의 크기가 요청된 크기보다 클 경우, 사용되지 않는 공간이 블록 내부에 존재하게 되는데 이를 내부 단편화라고 합니다.
우리는 또한 클라이언트에게 할당된 메모리는 다른 위치로 재배치될 수 없다고 가정합니다. 예를 들어, 프로그램이 malloc()을 호출하여 힙의 일부 영역에 대한 포인터를 받으면, 그 메모리 영역은 대응하는 free()를 통하여 반환될 때까지 프로그램이 소유하게 되고 라이브러리에 의해 다른 위치로 옮겨질 수 없습니다. 단편화 해결에 유용하게 사용되는 빈 공간의 압축은 이 경우에는 사용이 불가능합니다. 운영체제가 세그멘트를 구현할 때는 단편화를 해결하기 위하여 압축을 사용할 수 있습니다. 이에 대해서는 세그멘테이션에 관해 논의한 장에서 언급하였습니다.
저수준 기법들[2]#
세부 정책에 대해 자세히 설명하기 전에 먼저 대부분의 할당기에서 사용되는 일반적인 기법에 대해 논의합니다.
첫 번째, 분할(splitting)과 병합(coalescing)의 개념에 대해서 알아봅니다.
분할(Splitting): 큰 메모리 블록을 여러 개의 작은 블록으로 나누는 작업을 말합니다. 메모리 할당 요청이 들어왔을 때, 요청된 크기보다 큰 블록을 찾아 그 블록을 분할하여 요청된 크기만큼 할당하고 남은 부분은 빈 공간으로 유지합니다.
병합(Coalescing): 인접한 빈 메모리 블록들을 하나의 큰 블록으로 합치는 작업을 말합니다. 메모리 블록이 해제되었을 때, 해제된 블록과 인접한 빈 블록들을 병합하여 더 큰 빈 블록을 만들 수 있습니다. 이를 통해 외부 단편화를 줄일 수 있습니다.
두 번째, 할당된 영역의 크기를 빠르고 상대적으로 쉽게 파악할 수 있는 방법을 설명합니다.
마지막으로, 빈 공간과 사용 중인 공간을 추적하기 위해 빈 공간 내에 간단한 리스트를 구현하는 방법에 대해 설명합니다.
기본 전략#
이상적인 할당기는 속도가 빠르고 단편화를 최소화해야 합니다. 할당과 해제 요청 스트림은 무작위로, 결국 프로그래머에 의해 결정되기 때문에, 어느 특정 전략도 잘 맞지 않는 입력을 만나면 성능이 매우 좋지 않을 수 있습니다. 최선의 정책을 설명하는 것이 아니라 몇 가지 기본 정책에 대해 이야기하고 각각의 장단점을 논의합니다.
최적 적합(Best Fit)#
가장 작은 남는 공간에 할당합니다.
빈 공간 리스트를 검색하여 요청한 크기와 같거나 더 큰 빈 메모리 청크를 찾습니다. 그 후, 후보자 그룹 중에서 가장 작은 크기의 청크를 반환합니다. 이 청크는 최적 청크라고 불립니다. 최소 적합이라고도 불릴 수 있습니다. 빈 공간 리스트를 한 번만 순회하면 반환할 정확한 블록을 찾을 수 있습니다.
최적 적합의 배경은 사용자가 요청한 크기에 가까운 블록을 반환함으로써 최적 적합은 공간의 낭비를 줄이려고 노력합니다. 그러나 비용이 수반됩니다. 정교하지 않은 구현은 해당 빈 블록을 찾기 위해 항상 전체를 검색해야 하기 때문에 엄청난 성능 저하를 초래합니다.
최악 적합(Worst Fit)#
가장 큰 남는 공간에 할당합니다.
최적 적합의 반대 방식입니다. 가장 큰 빈 청크를 찾아 요청된 크기만큼만 반환하고 남는 부분은 빈 공간 리스트에 계속 유지됩니다. 최적 적합 방식에서 발생할 수 있는 수많은 작은 청크 대신에 커다란 빈 청크를 남기려고 시도합니다. 그러나 다시 한번 항상 빈 공간 전체를 탐색해야 하기 때문에 역시 높은 비용을 지불해야 합니다. 대부분의 연구에서 단편화가 발생하면서 오버헤드도 여전히 크다는 것을 보이고 있습니다.
최초 적합(First Fit)#
첫 번째로 충분히 큰 공간에 할당합니다.
간단하게 요청보다 큰 첫 번째 블록을 찾아서 요청만큼 반환합니다. 남은 빈 공간은 후속 요청을 위해 계속 유지됩니다. 속도가 빠르다는 것이 장점입니다. 원하는 블록을 찾기 위해 항상 빈 공간 리스트 전체를 탐색할 필요가 없습니다. 그러나 리스트의 시작에 크기가 작은 객체가 많이 생길 수 있습니다. 따라서 할당기가 빈 공간 리스트의 순서를 관리하는 방법이 쟁점입니다.
주소 기반 정렬(address-based ordering)을 사용하면 리스트를 주소로 정렬하여 병합을 쉽게 하고, 단편화를 감소시킵니다.
다음 적합(Next Fit)#
마지막으로 할당된 공간의 다음부터 충분히 큰 공간을 찾아 할당합니다.
항상 리스트의 처음부터 탐색하는 대신 다음 적합 알고리즘은 마지막으로 찾았던 원소를 가리키는 추가의 포인터를 유지합니다. 아이디어는 빈 공간 탐색을 리스트 전체에 더 균등하게 분산시키는 것입니다. 리스트의 첫 부분에만 단편화가 집중적으로 발생하는 것을 방지합니다. 전체 탐색을 하지 않기 때문에 최초 적합의 성능과 비슷합니다.
다른 접근법[3]#
이 외에도 메모리 할당을 향상시키기 위한 기술과 알고리즘이 있는데, 그 중 몇 가지를 여기서 소개하려고 합니다. 단순히 최적 적합 할당에 그치지 않고, 그 이상에 대해서 생각해 보는 것이 목적입니다.
개별 리스트(Segregated List)#
특정 응용 프로그램이 자주 요청하는 크기의 객체를 관리하기 위해 별도의 리스트를 유지하는 것을 개별 리스트라고 합니다.
이 방법의 장점은 특정 크기의 요청을 위한 메모리 청크를 유지하기 때문에 단편화 가능성을 상당히 줄일 수 있다는 것입니다. 요청된 크기의 청크만이 존재하기 때문에 복잡한 리스트 검색이 필요하지 않으므로 할당과 해제 요청을 신속히 처리할 수 있습니다.
문제점 지정된 크기의 메모리 풀과 일반적인 풀에 얼마만큼의 메모리를 할당해야 하는가?
슬랩 할당기(Slab Allocator)#
위의 문제는 특수 목적 할당기인 슬랩 할당기가 더 나은 방법으로 해결했습니다. 커널이 부팅될 때 커널 객체를 위한 여러 객체 캐시(object cache)를 할당합니다.
여기서 커널 객체란 락, 파일 시스템 아이노드 등 자주 요청되는 자료 구조들을 일컫습니다. 객체 캐시는 지정된 크기의 객체들로 구성된 빈 공간 리스트이고, 메모리 할당 및 해제 요청을 빠르게 하기 위해 사용됩니다.
기존에 할당된 캐시 공간이 부족하면 상위 메모리 할당기에게 추가 슬랩을 요청합니다. 슬랩 내 객체들에 대한 참조 횟수가 0이 되면 상위 메모리 할당기는 이 슬랩을 회수할 수 있습니다.
슬랩 할당 방식은 빈 객체들을 사전에 초기화된 상태로 유지한다는 점에서 개별 리스트 방식보다 우수합니다. 반납된 객체들을 초기화된 상태로 리스트에 유지하여 슬랩 할당기는 객체당 잦은 초기화와 반납의 작업을 피할 수 있어서 오버헤드를 현저히 감소시킵니다.
슬랩(Slab): 커널 객체를 저장하기 위해 할당된 연속적인 메모리 블록입니다. 슬랩은 동일한 크기의 객체들로 구성되며, 각 객체는 미리 초기화된 상태로 유지됩니다.
객체 캐시(Object Cache): 동일한 크기와 타입의 객체들을 관리하는 캐시입니다. 각 객체 캐시는 해당 객체의 할당과 해제 요청을 처리합니다. 객체 캐시는 여러 개의 슬랩으로 구성될 수 있습니다.
버디 할당(Buddy Allocation)#
빈 공간의 합병을 간단히 하는 방법을 버디 할당이라고 합니다.
이진 버디 할당기(Binary Buddy Allocator)#
빈 메모리는 처음에 개념적으로 2ⁿ인 하나의 큰 공간으로 생각하면, 메모리 요청이 발생해 그 요청을 충족시키기에 충분한 공간이 발견될 때까지(그리고 더 분할하면 공간이 너무 작아져서 요청을 만족시킬 수 없을 때까지) 빈 공간을 2개로 계속 분할합니다.
위 사진의 예에서 7KB 크기의 요청이 들어와서 가장 왼쪽 8KB 블록이 될 때까지 분할하고 사용자에게 반환됩니다. 이 방식은 2의 거듭제곱 크기의 블록만 할당할 수 있기 때문에 내부 단편화가 발생할 수 있습니다.
블록 해제 시 해제한 블록 옆에 있는 “버디” 블록을 확인합니다. 만약 비어있다면 두 블록을 병합하고, 이 재귀 합병 과정은 트리를 따라 전체 빈 공간이 복원되거나 버디가 사용 중이라는 것이 밝혀질 때까지 계속 올라갑니다.
버디 할당이 잘 작동하는 이유는 특정 블록의 버디를 결정하기 쉽기 때문입니다. 특정 블록과 그 블록의 버디의 주소는 오직 한 비트만 다릅니다. 어느 위치의 비트가 다른가는 버디 트리의 수준에 따라 달라집니다.
버디(Buddy): 버디 할당에서 인접한 두 개의 블록을 버디라고 합니다. 버디는 항상 동일한 크기를 가지며, 주소가 인접해 있습니다. 버디 블록은 병합과 분할 과정에서 함께 처리됩니다.
기타 아이디어#
위에 설명한 접근 방식들의 한 가지 문제점은 확장성입니다. 빈 공간들의 개수가 늘어남에 따라 리스트 검색이 매우 느려질 수 있습니다.
균형 이진 트리(balanced binary tree), 스플레이 트리(splay tree), 부분 정렬 트리(partially ordered tree)와 같은 복잡한 자료구조를 할당기에 적용하여 성능을 높일 수 있습니다. 단순함과 성능은 반비례한다는 것이 문제입니다.
요약#
이 장에서는 가장 기본적인 형태의 메모리 할당기에 대해 논의해봤습니다. 이러한 할당기는 많은 소프트웨어 및 운영체제에서 사용되고 있습니다. 할당기를 구축할 때는 다양한 선택사항이 있으며, 워크로드를 이해하고 그에 맞게 조정하는 것이 중요합니다. 다양한 워크로드에 대해 빠르고 효율적이며 확장 가능한 할당기를 만드는 것은 현대 컴퓨터 시스템의 숙제라 할 수 있습니다.
할당기를 설계할 때는 다양한 전략과 기법들을 고려해야 합니다. 최적 적합, 최악 적합, 최초 적합, 다음 적합과 같은 기본 전략들은 각각 장단점을 가지고 있습니다. 이러한 전략들을 적절히 조합하고, 개별 리스트, 슬랩 할당, 버디 할당과 같은 발전된 기법들을 활용하여 할당기의 성능과 효율성을 향상시킬 수 있습니다.
또한, 할당기의 성능은 사용되는 자료구조에 크게 영향을 받습니다. 단순한 링크드 리스트부터 균형 이진 트리, 스플레이 트리, 부분 정렬 트리 등의 복잡한 자료구조까지 다양한 옵션이 있습니다. 적절한 자료구조를 선택하여 빠른 검색과 삽입, 삭제 연산을 지원하는 것이 중요합니다.
메모리 할당기를 설계하고 구현할 때는 항상 트레이드오프(trade-off)를 고려해야 합니다. 단편화를 최소화하면서도 할당과 해제의 속도를 높이는 것, 메모리 오버헤드를 줄이면서도 효율적인 관리가 가능하도록 하는 것 등이 중요한 과제입니다. 이를 위해서는 다양한 전략과 기법들을 적절히 활용하고, 시스템의 특성과 요구사항에 맞게 할당기를 튜닝해야 합니다.
효과적인 메모리 할당기를 개발하는 것은 시스템의 전반적인 성능과 안정성에 큰 영향을 미칩니다. 따라서 운영체제 개발자와 시스템 프로그래머는 메모리 할당 문제에 대해 깊이 이해하고, 최적의 솔루션을 설계하고 구현할 수 있어야 합니다. 이를 통해 시스템 자원을 효율적으로 활용하고, 사용자에게 더 나은 경험을 제공할 수 있을 것입니다.