[OSTEP] 스터디 7주차 - 메모리 가상화 3 - 빈 공간 관리

가정

이번 챕터의 논의의 대부분은 사용자 수준 메모리 할당 라이브러리에 존재하는 메모리 할당기의 발전 역사에 초첨을 맞춘다....

malloc()과 free()에서 제공하는 것과 같은 기본 인터페이스를 가정한다. 구체적으로 void *malloc (size_t size)는 응용 프로그램이 요청한 바이트 수를 나타내는 변수 size를 받아들인다. 이 함수는 요청된 크기와 같거나 큰 영역을 가리키는, 타입이 없는 또는 C 언어의 용어로 void 포인터를 반환한다. 대응되는 루틴 void free(void *ptr)는 포인터를 인자로 전달받고 해당 영역을 해제한다.

인터페이스의 의미에 주의하라 공간을 해제할 때 사용자는 라이브러리에게 크기 정보를 전달하지 않는다. 라이브러리는 포인터만으로 해제하고자 하는 메모리 영역의 크기를 파악해야 한다.

이 라이브러리가 관리하는 공간은 힙(heap)이다.  힙의 빈 공간을 관리하는 데는 일반적으로 링크드 리스트가 사용된다. 물론 반드시 리스트일 필요는 없고 빈 공간을 표현할 수 있는 자료 구조면 충분하다.

외부 단편화 방지에 특히 중점을 둘 것이다. 논의를. 단순화하기 위하여, 외부 단편화에 초점을 맞출 것이다.

클라이언트에게 할당된 메모리는 다른 위치로 재배치될 수 없다고 가정한다. 예를 들어, 프로그램이 malloc()을 호출하여 힙의 일부 영역에 대한 포인터를 받으면, 그 메모리 영역은 대응하는 free()를 통하여 반환될 때까지 프로그램이 소유하게 되고 라이브러리에 의해 다른 위치로 옮겨질 수 없다. 단편화 해결에 유용하게 사용되는 빈 공간의 압축은 이 경우에는 사용이 불가능하다. 운영체제가 세그먼트를 구현할 때는 단편화를 해결하기 위하여 압축을 사용할 수 있다.

---

저수준 기법들

할당기에서 사용되는 일반적인 기법에 대해 논의 한다.

첫 번째, 분할(splitting)과 병합(coalescing)의 개념에 대해 알아본다.

• 분할(Splitting): 큰 메모리 블록을 여러 개의 작은 블록으로 나누는 작업을 말한다. 메모리 할당 요청이 들어왔을 때, 요청된 크기보다 큰 블록을 찾아 그 블록을 분할하여 요청된 크기만큼 할당하고 남은 부분은 빈 공간으로 유지한다.
• 병합(Coalescing): 인접한 빈 메모리 블록들을 하나의 큰 블록으로 합치는 작업을 말한다. 메모리 블록이 해제되었을 때, 해제된 블록과 인접한 빈 블록들을 병합하여 더 큰 빈 블록을 만들 수 있다. 이를 통해 외부 단편화를 줄일 수 있다.

두 번째, 할당된 영역의 크기를 빠르고 상대적으로 쉽게 파악할 수 있는 방법을 설명한다.

마지막으로, 빈 공간과 사용 중인 공간을 추적하기 위해 빈 공간 내에 간단한 리스트를 구현하는 방법에 대해 설명한다.

---

기본 전략

이상적인 할당기는 속도가 빠르고 단편화를 최소화해야 한다. 할당과 해제 요청 스트림은 무작위로, 결국 프로그래머에 의해 결정되기 때문에, 어느 특정 전략도 잘 맞지 않는 입력을 만나면 성능이 매우 좋지 않을 수 있다. 최선의 정책을 설명하는 것이 아니라 몇 가지 기본 정책에 대해 이야기하고 각각의 장단점을 논의한다.

최적 적함(Best Fit)

가장 작은 남는 공간에 할당한다.

빈 공간 리스트를 검색하여 요청한 크기와 같거나 더 큰 빈 메모리 청크를 찾는다. 그 후, 후보자 그룹 중에서 가장 작은 크기의 청크를 반환한다. 이 청크는 최적 청크라고 불린다. 최소 적합이라고도 불린다. 빈 공간 리스트를 한 번만 순회하면 반환할 정확한 블록을 찾을 수 있다.

최적 적합의 배경은 사용자가 요청한 크기에 가까운 블록을 반환함으로써 최적 적합은 공간의 낭비를 줄이려고 노력한다. 그러나 비용이 든다. 정교하지 않은 구현은 해당 빈 블록을 찾기 위해 항상 전체를 검색해야 하기 때문에 엄청난 성능 저하를 초래한다.

---

최악 적합(Worst Fit)

가장 큰 남는 공간에 할당한다.

가장 큰 빈 청크를 찾아 요청된 크기만큼만 반환하고 남는 부분은 빈 공간 리스트에 계속 유지된다. 최적 적합 방식에서 발생할 수 있는 수많은 작은 청크 대신에 커다란 빈 청크를 남기려고 시도한다. 그러나 다시 한번 항상 빈 공간 전체를 탐색해야 하기 때문에 역시 높은 비용을 지불해야 한다. 대부분의 연구에서 단편화가 발생하면서 오버헤드도 여전히 크다는 것을 보이고 있다.

---

최초 적합(First Fit)

첫 번째로 충분히 큰 공간에 할당한다.

간단하게 요청보다 큰 첫 번째 블록을 찾아서 요청만큼 반환한다. 남은 빈 공간은 후속 요청을 위해 계속 유지된다. 속도가 빠르다는 것이 장점이다. 원하는 블록을 찾기 위해 항상 빈 공간 리스트 전체를 탐색할 필요가 없다. 그러나 리스트의 시작에 크기가 작은 객체가 많이 생길 수 있다. 따라서 할당기가 빈 공간 리스트의 순서를 관리하는 방법이 쟁점이다.

주소 기반 정렬(address-based ordering)을 사용하면 리스트를 주소로 정렬하여 병합을 쉽게 하고, 단편화를 감소시킨다.

---

다음 적합(Next Fit)

마지막으로 할당된 공간의 다음부터 충분히 큰 공간을 찾아 할당합니다.

항상 리스트의 처음부터 탐색하는 대신 다음 적합 알고리즘은 마지막으로 찾았던 원소를 가리키는 추가의 포인터를 유지한다. 아이디어는 빈 공간 탐색을 리스트 전체에 더 균등하게 분산시키는 것이다. 리스트의 첫 부분에만 단편화가 집중적으로 발생하는 것을 방지한다. 전체 탐색을 하지 않기 때문에 최초 적합의 성능과 비슷하다.

---

다른 접근법

이 외에도 메모리 할당을 향상시키기 위한 기술과 알고리즘이 있다.

개별 리스트(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)를 고려해야 한다. 단편화를 최소화하면서도 할당과 해제의 속도를 높이는 것, 메모리 오버헤드를 줄이면서도 효율적인 관리가 가능하도록 하는 것 등이 중요한 과제다. 이를 위해서는 다양한 전략과 기법들을 적절히 활용하고, 시스템의 특성과 요구사항에 맞게 할당기를 튜닝해야 한다.

효과적인 메모리 할당기를 개발하는 것은 시스템의 전반적인 성능과 안정성에 큰 영향을 미친다. 따라서 운영체제 개발자와 시스템 프로그래머는 메모리 할당 문제에 대해 깊이 이해하고, 최적의 솔루션을 설계하고 구현할 수 있어야 한다. 이를 통해 시스템 자원을 효율적으로 활용하고, 사용자에게 더 나은 경험을 제공할 수 있을 것이다.