CSAPP 책은 쌩으로 읽는다면 이해하기 매우 어렵습니다.
따라서 소단원만 그대로 따라가되, 내용을 이해하기 쉽게 재구성했습니다.
9.9.14 분리 가용 리스트
1. 메모리 할당 최적화하기
1) 단일 연결 리스트의 한계
기본적인 메모리 할당 방식은 가용 블록을 하나의 연결 리스트로 관리하는 방식이다.
이 방식은 구조가 단순하다는 장점이 있지만, 블록을 할당할 때마다 리스트의 처음부터 끝까지 탐색해야 하므로 속도가 느리다.
특히 가용 블록의 수가 많아질수록 탐색에 걸리는 시간이 선형적으로 증가한다.
따라서 일반적인 용도로 사용하기에는 비효율적이다.
2) 분리 저장장치
이 문제를 해결하기 위해 등장한 방식이 분리 저장장치(segregated storage)이다.
이 방식은 블록 크기를 기준으로 여러 개의 가용 리스트를 나누어 관리한다.
각 리스트는 유사한 크기의 블록만 포함하며, 이를 크기 등급(size class)이라 부른다.
예를 들어, 블록 크기를 2의 거듭제곱 단위로 나누면 다음과 같은 등급을 만들 수 있다.
{1}, {2}, {3, 4}, {5-8}, ..., {1025-2048}, {2049-4096}, {4097-∞}또는 작은 블록은 1바이트 단위로 세분화하고, 큰 블록은 2의 제곱 단위로 묶는 방식도 가능하다.
{1}, {2}, {3}, ..., {1023}, {1024}, {1025-2048}, {2049-4096}, {4097-∞}이 구조에서는 할당자가 크기 순으로 정렬된 리스트 배열을 유지한다.
어떤 크기의 블록이 요청되면, 그 크기에 해당하는 리스트를 먼저 확인하고, 적절한 블록이 없으면 다음 등급 리스트를 차례대로 탐색한다.
이 방식은 전체 힙을 탐색하지 않고도 원하는 블록을 빠르게 찾을 수 있다는 장점이 있다.
분리 저장 방식은 구현 방식에 따라 다양한 변형이 존재한다.
예를 들어, 크기 등급을 어떻게 나누는지, 블록을 나눠도 되는지(split 허용 여부), 블록 병합(coalescing)을 언제 수행할지, 운영체제로부터 메모리를 어떤 조건에서 요청할지 등에 따라 전략이 달라진다.
이러한 요소들이 조합되면서 단순한 방식부터 고급 할당기까지 다양한 형태로 응용된다.
다음 글에서는 이러한 분리 저장 방식의 대표적인 두 구현인 단순 분리 저장장치와 분리 맞춤, 그리고 버디 시스템에 대해 하나씩 자세히 설명하겠다.
단순 분리 저장장치
1) 단순 분리 저장장치란?
단순 분리 저장장치(Simple Segregated Storage)은 크기 등급별로 가용 리스트를 나누되, 각 리스트 안에는 오직 같은 크기의 블록만 존재한다.
예를 들어, 크기 등급이 {17~32}로 정의되었다면, 해당 리스트에는 모두 32바이트 크기의 블록만 포함된다.
실제로는 가장 큰 값(이 예시에서는 32)에 맞춰 리스트를 구성하는 것이다.
할당자가 어떤 크기의 블록을 요청하면, 해당하는 크기 등급의 리스트를 확인하여 가장 앞에 있는 블록을 통째로 가져다 쓴다.
이 방식은 블록을 잘라서 사용하는 분할(split)을 지원하지 않는다.
리스트가 비어 있는 경우에는, 운영체제로부터 일정 크기의 메모리를 요청하여(보통 페이지 단위), 동일한 크기의 블록으로 나누고, 그것들을 다시 연결해서 새로운 가용 리스트를 구성한다.
블록을 해제할 때는, 해당 리스트의 맨 앞에 간단히 삽입한다.
2) 장점
단순 분리 저장 방식의 가장 큰 장점은 속도와 단순성이다.
할당과 해제 모두 상수 시간에 처리할 수 있다.
블록의 크기가 모두 같기 때문에, 헤더에 크기를 기록할 필요가 없다.
또한, 병합(coalescing)이나 분할(split)을 하지 않으므로 별도의 작업이 필요 없다.
병합을 하지 않기 때문에, 블록이 할당되었는지를 나타내는 flag도 필요 없고, 풋터도 생략할 수 있다.
구현 측면에서도 간단하다.
리스트는 단일 연결 리스트로 충분하며, 각 가용 블록은 다음 블록을 가리키는 포인터 하나만 가지면 된다.
결국, 하나의 succ 포인터만으로도 리스트를 구성할 수 있으므로, 최소 블록 크기가 한 워드면 충분하다.
3) 단점
하지만 단순한 만큼 단점도 존재한다.
가장 대표적인 문제는 단편화다.
블록을 나누지 않기 때문에, 예를 들어 20바이트만 필요하더라도 32바이트 전체를 할당하게 된다.
이처럼 요청한 크기보다 더 큰 블록을 사용하는 것이 반복되면, 내부 단편화가 누적된다.
또한, 병합을 하지 않기 때문에 여러 크기의 빈 블록이 여기저기 흩어지면 큰 블록을 할당할 공간이 없어지는 외부 단편화도 발생할 수 있다.
특히 특정 크기 블록만 반복적으로 할당되고 해제되는 패턴에서는, 사용 가능한 공간이 있어도 원하는 블록을 할당하지 못하는 상황이 생길 수 있다.
분리 맞춤
1) 분리 맞춤이란?
단순 분리 저장 방식은 모든 블록이 같은 크기를 가져야 했지만, 분리 맞춤 방식(Segregated Fits)은 같은 크기 등급 내에서도 서로 다른 크기의 블록을 포함할 수 있다는 점이 가장 큰 특징이다.
이 방식에서도 크기 등급별로 가용 리스트 배열을 유지하지만, 리스트의 구성은 보다 유연하다.
각 리스트는 명시적(explicit) 연결 리스트로 구성되거나, 묵시적(implicit) 방식으로 구현되기도 한다. 따라서 리스트 하나에 다양한 크기의 블록이 함께 들어갈 수 있다.
2) 블록 할당 과정
할당자가 블록을 요청받으면, 먼저 요청된 크기에 해당하는 크기 등급을 결정한다.
그런 다음 해당 리스트에서 first-fit 탐색을 수행하여 적절한 블록을 찾는다.
만약 찾은 블록이 요청된 크기보다 크다면, 블록을 나누고(split), 사용하고 남은 부분은 다시 적절한 크기 리스트에 삽입한다.
만약 해당 리스트에서 맞는 블록을 찾지 못한다면, 할당자는 다음으로 큰 크기 등급의 리스트를 탐색한다.
이런 탐색은 적절한 블록을 찾을 때까지 계속 반복된다.
만약 모든 리스트에서 할당 가능한 블록을 찾지 못하면, 운영체제로부터 새로운 힙 메모리를 요청한다.
받은 메모리 중 필요한 만큼을 할당하고, 남은 부분은 적절한 리스트에 넣는다.
3) 블록 해제와 병합
블록을 해제할 때는, 주변 블록들과 병합(coalescing)을 시도한다.
병합된 결과는 해당 크기 등급에 맞는 가용 리스트에 삽입된다.
이 과정을 통해 외부 단편화를 줄이고, 큰 블록도 다시 효율적으로 사용할 수 있게 된다.
분리 맞춤 방식은 실제 운영체제나 라이브러리에서도 많이 사용된다.
대표적으로 C 표준 라이브러리에 포함된 GNU malloc이 이 방식을 따른다.
그 이유는 분리 맞춤 방식이 속도와 메모리 효율을 동시에 만족하기 때문이다.
전체 힙을 탐색하는 것이 아니라, 필요한 크기 근처의 리스트만 탐색하면 되므로 속도가 빠르다.
또한, first-fit 탐색만으로도 결과적으로는 best-fit에 가까운 메모리 활용 효율을 기대할 수 있다.
3. 버디 시스템
1) 버디 시스템이란?
버디 시스템(Buddy System)은 분리 맞춤 방식의 특별한 형태로, 모든 블록 크기를 2의 거듭제곱으로 제한하여 관리한다.
이 방식에서는 처음에 워드 크기의 힙이 주어지고, 각 블록 크기 마다 하나씩의 가용 리스트를 유지한다. 여기서 k는 0 이상 m 이하의 정수다.
메모리 할당 요청이 들어오면, 요청된 크기를 초과하지 않는 가장 가까운 2의 거듭제곱 크기로 올려서 반올림한다.
예를 들어 36바이트가 필요하면, 64바이트 블록으로 할당된다.
초기에는 전체 힙을 하나의 큰 블록으로 보유하고 있다.
요청된 블록이 정확히 해당 크기의 가용 블록으로 존재하면, 그 블록을 그대로 사용하면 된다.
2) 블록 분할과 병합
만약 요청된 크기보다 큰 블록만 존재할 경우, 해당 블록을 반으로 나누는(split) 작업을 반복하여 원하는 크기의 블록을 만든다.
이 과정에서 생긴 나머지 절반은 버디(buddy) 블록이라 불리며, 해당 크기 등급의 가용 리스트에 삽입된다.
블록을 해제할 때는, 해당 블록의 버디가 free 상태인지 확인한다.
만약 버디가 사용되지 않은 상태라면, 병합(coalescing)을 수행하여 더 큰 블록으로 합친다.
이 병합은 가능한 한 반복되며, 더 이상 병합할 수 없는 상태가 되면 멈춘다.
3) 버디의 주소
버디 시스템의 중요한 특징은, 버디 블록의 주소를 매우 쉽게 계산할 수 있다는 점이다.
예를 들어 32바이트 블록의 주소가 xxx...x00000이라면, 그 버디는 xxx...x10000 주소에 위치하게 된다.
다시 말해, 버디 블록은 현재 블록과 정확히 한 비트만 다르다.
이 특성 덕분에 병합 과정이 빠르고 간단하며, 할당자 입장에서 관리가 수월하다.
4) 장단점
버디 시스템의 강점은 빠른 탐색과 빠른 병합 처리다.
특히 블록 크기가 일정하고 예측 가능한 환경에서는 효율적으로 동작한다.
또한 주소 계산만으로 병합 여부를 빠르게 판단할 수 있어 구현도 단순한 편이다.
하지만 모든 블록이 2의 제곱 단위로만 구성되기 때문에, 내부 단편화가 심하게 발생할 수 있다.
예를 들어 33바이트 요청에도 64바이트 블록을 할당해야 하기 때문에 낭비가 생긴다.
이러한 이유로 버디 시스템은 일반적인 목적의 메모리 할당에는 적합하지 않다.
하지만, 블록 크기가 사전에 정해져 있고, 대부분이 2의 제곱인 환경에서는 유용하게 사용될 수 있다.
예를 들어 커널 메모리 관리나 네트워크 버퍼 관리 등 특수한 목적의 시스템에서 활용된다.
