2-10장. 빈 공간 관리(메모리)

이 장에서는 구체적으로 빈 공간 관리에 관련된 문제를 논의할 것이다.

 

빈 공간 관리가 어려운 이유는 관리하는 공간이 변할 수 있는 가변적인 특성을 가진다는 점이다. malloc() 과 free() 에서처럼 사용자 수준 메모리 할당 라이브러리나 세그멘테이션으로 물리 메모리를 관리하는 운영체제가 이런 특성을 가지는 대표적인 예이다. 

 

빈공간은 다양한 크기의 작은 조각으로 분할되어 결국 단편화된다. 빈 공간들의 전체 크기가 요청된 것보다 크더라도 하나의 연속된 영역이 존재하지 않으면 요청을 실패할 수 있다. 

 

다음 그림은 이러한 문제의 예를 보여 준다. 이 경우 빈 공간의 전체 크기는 20바이트이다. 불행히도, 10바이트 짜리 두 조각으로 나누어져 있다. 그 결과, 20바이트의 빈 공간이 있지만 15바이트의 요청(메모리 할당)은 실패한다. 이것이 이 장에서 해결하고자 하는 문제이다.

 

저수준 기법들

분할과 병합

 

30 바이트 힙이 있다고 가정하자. 이 힙의 빈 공간 리스트에는 2개의 원소가 있다. 하나는 첫 번째 10바이트의 빈 세그멘트(0~9)를 설명하고 다른 하나는 나머지 빈 세그멘트(20~29)를 표현한다.

 

앞에서 언급한 바와 같이, 10바이트를 초과하는 모든 요청은 실패하여 NULL을 반환할 것이다. 요청한 크기에 해당하는 메모리 청크가 없기 때문이다. 10바이트에 대한 요청은 둘 중 하나의 빈 청크를 사용하여 쉽게 충족된다. 그러나 10바이트보다 적은 요청에 대해서는 어떤 일이 일어날까?

 

메모리를 1바이트만 요청했다고 가정하자. 이 경우 할당기는 분할(Splitting)로 알려진 작업을 수행한다. 요청을 만족시킬 수 있는 빈 청크를 찾아 이를 둘로 분할한다. 첫 번째 청크는 호출자에게 반환되고, 두 번째 청크는 리스트에 남게 된다. 따라서 위의 예에서 1바이트 요청이 발생하고 할당기가 리스트의 두 번째 원소를 사용하여 요청을 충족시키기로 가정하자. malloc()은 20(1바이트가 할당된 영역의 주소)을 반환하고 최종 빈 리스트는 다음과 같이 될 것이다. 

 

기본적인 리스트의 모습은 바뀌지 않았다는 것을 알 수 있다. 유일한 변경 사항은 빈 공간이 이제 20이 아니라 21에서 시작한다는 것과 빈 공간의 길이가 이제 9라는 것이다. 요청이 특정 빈 청크의 크기보다 작은 경우 분할 기법을 사용한다.

 

분할에 당연히 동반되는 기법은 빈 공간의 병합(Coalescing)이다.

 

위의 예를 다시 한번 보자. 응용 프로그램이 free(10)을 호출하여 힙의 중간에 존재하는 공간을 반환할 때 어떤 일이 일어날까? 빈 공간을 다시 리스트에 추가할 경우 다음과 같은 모양이 될 것이다.

 

무슨 문제가 있는지 살펴보자. 힙 전체가 비어 있지만, 10바이트 길이의 청크 3개로 나누어져 있다. 사용자가 20바이트를 요청하는 경우 단순한 리스트 탐색은 빈 청크를 발견하지 못하고 실패를 반환한다.

 

할당기가 이 문제를 방지하기 위하여 할 수 있는 일은 메모리 청크가 반환될 때 빈 공간들을 병합하는 것이다. 원리는 간단하다. 메모리 청크를 반환할 때 해제되는 청크의 주소와 바르 인접한 빈 청크의 주소를 살펴본다. 새로 해제된 빈 공간이 왼쪽의 빈 청크와 바로 인접해 있다면 그들을 하나의 더 큰 빈 청크로 병합한다. 그러면 다음과 같이 될 것이다.

 

이 상태는 할당이 한 번도 일어나지 않은 최초의 힙 리스트의 모양이다. 병합 기법을 사용하여 할당기가 커다란 빈 공간을 응용 프로그램에게 제공할 수 있다는 것을 더 보장할 수 있다.

 

할당된 공간의 크기 파악

free(void *ptr) 인터페이스는 크기를 매개변수로 받지 않는다는 것을 알고 있을 것이다. 그러면 할당받은 공간만큼 할당해제를 하기 위해 할당기는 그 크기를 어떻게 알 수 있을까? 

 

이 작업을 위해 대부분의 할당기는 추가 정보를 헤더(Header) 블럭에 저장한다. 헤더 블럭은 메모리에 유지되며 보통 해제된 청크 바로 직전에 위치한다. 

 

위 그림은 ptr이 20바이트의 할당된 블럭을 가리키고 있다.

 

사용자는 malloc()을 호출하고 그 결과를 ptr에 저장하였다고 가정하자. 

 

헤더는 적어도 할당된 공간의 크기는 저장해야 한다. 또한 해제 속도를 향상시키기 위한 추가의 포인터, 부가적인 무결성 검사를 제공하기 위한 매직 넘버, 및 기타 정보를 저장할 수 있다. 다음과 같이 할당 영역의 크기와 매직 넘버를 저장하는 간단한 헤더를 가정하자.

 

그러면 다음과 같은 그림으로 헤더 정보가 저장될 것이다.

 

사용자가 free(ptr)을 호출하면 라이브러리는 헤더의 시작 위치를 파악하기 위해 간단한 포인터 연산을 한다. 

 

헤더를 가리키는 포인터를 얻어 내면, 라이브러는 매직 넘버가 기대하는 값과 일치하는지 비교하여 안전성 검사(Sanity check)를 실시한다. (assert(hptr->magic == 1234567)) 그리고 새로 해제된 영역의 크기를 간단한 수학을 통해 계산한다. (헤더의 크기를 영역의 크기에 더함)

 

주의할 점이 있다. 만약 4바이트의 메모리 할당을 한다고 하였을때 빈 영역의 크기는 4바이트가 아니라 4바이트 + 헤더의 크기 이다. 그러므로 사용자가 4바이트 메모리를 할당하면 라이브러리는 빈 청크를 찾을때  4바이트 + 헤더의 크기를 탐색한다.

 

빈 공간 리스트 내장

보통 새로운 노드를 위한 공간이 필요할 때 malloc()을 호출한다. 불행하게도 메모리 할당 라이브러리 루틴에서는 이것이 불가능하다. (이것이 구현될 리스트가 아직 안만들어져 있으므로) 대신 빈 공간 내에 리스트를 구축해야 한다. 

 

4096바이트 크기의 메모리 청크가 있다고 하자. 즉, 힙의 크기는 4KB이다. 이를 빈 공간 리스트로 관리하기 위해서 먼저 리스트를 초기화해야 한다. 처음에 리스트는 4096 길이의 항목 하나를 가지고 있다. 이 리스트의 노드 설명은 다음과 같다.

 

힙을 초기화 하고 힙에 빈 공간 리스트의 첫 번째 원소를 넣는 코드를 살펴보자. 힙은 시스템 콜 mmapp() (함수로 사용할 메모리의 주소를 얻게 해준다)을 사용하여 얻어진 영역에 구축된다고 가정한다. 코드는 다음과 같다.

 

이 코드를 실행 후 리스트는 크기 4088(4096 - 헤더 크기)의 항목 하나만을 가지게 된다. head포인터는 이 영역의 시작 주소를 담고 있다. 영역의 시작 주소를 16KB라고 가정하자. 이때 힙의 모양은 다음과 같을 것이다. 

 

이제 100바이트 메모리 청크가 요청되었다고 생각해보자. 이 요청을 처리하기 위해 라이브러리는 먼저 충분한 크기의 청크를 찾는다. 하나의 빈 청크만이 존재하기 때문에 이 청크가 선택된다. 빈 영역의 크기 + 헤더의 크기 만큼 청크와 나머지 빈 청크 두 개로 분할된다. 헤더의 크기를 8바이트라고 가정하면, 이제 힙의 공간은 다음과 같을 것이다.

 

100바이트에 대한 요청이 오면 라이브러리는 기존 하나의 빈 청크 중 108바이트를 할당하고 할당 영역을 가리키는 포인터(ptr)를 반환한다. 그리고 나중에 free()에서 사용할 수 있도록 할당된 공간 직전 8바이트에 헤더 정보를 넣는다. 그리고 빈 노드의 사이즈를 4088 - 108인 3980으로 축소한다.

 

이제 100바이트씩 할당된 3개의 공간이 존재하는 힙을 살펴보자. 다음과 같다.

 

그림에서 볼 수 있듯이 힙의 시작 부분 324바이트가 현재 할당되어 있다. 3개의 헤더와 할당된 3개의 100바이트 영역을 볼 수 있다. 빈 공간 리스트는 여전히 head가 가리키는 하나의 노드로 구성되어 있지만 세 번의 분할 이후 3764바이트로 축소된 모습이다. 이제 free()를 통해 일부 메모리를 반환하면 어떤 일이 벌어질까?

 

이 예에서 응용 프로그램은 free(16500)을 호출하여 할당 영역 중 가운데 청크를 반환한다. 16500은 메모리 영역의 시작 주소 16384(16KB), 이전 메모리 청크의 크기 108, 해제되는 청크의 헤더 8바이트를 모두 더해서 나온 값이다. 이 값은 sptr이 나타낸다. 

 

라이브러리는 신속히 빈 공간의 크기를 파악하고, 빈 청크를 빈 공간 리스트에 삽입한다. 빈 공간 리스트의 헤드 쪽에 삽입한다고 가정하면 공간의 모양은 위 그림과 같다.

 

이제 빈 공간 리스트의 첫 번째 원소는 작은 빈 청크이고 두 번째 원소는 큰 빈 청크이다. 드디어 리스트가 하나 이상의 원소를 가지게 되었다. 흔히 일어나는 단편화가 발생하였다.

 

마지막으로 2개의 사용 중인 청크가 해제된다고 하자. 병합이 없다면, 작은 단편으로 이루어진 빈 공간 리스트가 될 것이다. 다음 그림처럼 말이다.

 

그림에서 볼 수 있듯이, 아직 리스트를 병합하지 않았다. 모든 메모리가 비어 있긴 하지만, 전부 조각나 있기 때문에 한 청크가 아니라 단편으로 이루어진 메모리처럼 보인다. 해결책은 간단하다. 리스트를 순회하면서 인접한 청크를 병합하면 된다. 병합이 완료되면 힙은 전체 하나의 큰 청크가 된다.

 

힙의 확장

힙 공간이 부족한 경우에는 어떻게 할 것인가? 가장 쉬운 방법은 실패를 반환하는 것이다. 어떤 경우에는 이 방법이 유일한 대안이 될 수 있다. 

 

대부분의 전통적인 할당기는 적은 크기의 힙으로 시작하여 모두 소진하면 운영체제로부터 더 많은 메모리를 요청한다. 할당기는 힙을 확장하기 위하여 특정 시스템 콜(대부분 UNIX 시스템같은 경우는 sbrk)을 호출한다. 그런 후 확장된 영역에서 새로운 청크를 할당한다. sbrk 요청을 수행하기 위해 운영체제는 빈 물리 페이지를 찾아 요청 프로세스의 주소 공간에 매핑한 후, 새로운 힙의 마지막 주소를 반환한다. 이제부터 더 큰 힙을 사용할 수 있고 요청은 성공적으로 충족될 수 있다.

 

 

기본 전략

일부 기법에 대한 간략히 살펴보았으므로, 빈 공간 할당을 위한 기본 전략에 대해 살펴보자. 

 

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

 

최적 적합(Best Fit)

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

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

 

최악 적합(Worst Fit)

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

 

최초 적합(First Fit)

최초 적합은 간단하게 요청보다 큰 첫 번째 블럭을 찾아서 요청만큼 반환한다. 먼저와 같이 남은 빈 공간은 후속 요청을 위해 계속 유지된다.

최초 적합은 속도가 빠르다는 것이 장점이다. 원하는 블럭을 찾기 위해 항상 빈 공간 리스트 전체를 탐색할 필요가 없다. 그러나 때때로 리스트의 시작에 크기가 작은 객체가 많이 생길 수 있다. 따라서 할당기가 빈 공간 리스트의 순서를 관리하는 방법이 쟁점이다. 한 가지 방법은 주소-기반 정렬(Address-based ordering)을 사용하는 것이다. 리스트를 주소로 정렬하여 병합을 쉽게 하고, 단편화로 감소시킨다.

 

다음 적합(Next Fit)

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

 

기본전략의 예

위에서 언급한 전략이 동작하는 몇 가지 예를 들어보자. 크기가 각각 10, 30, 20인 세개의 원소를 가진 빈 공간 리스트를 생각해보자.

 

크기 15인 요청이 들어왔다고 가정하자. 최적 적합 방법은 전체 리스트를 검색하여 요청을 만족시킬 수 있는 청크 중 가장 작은 20을 선택한다. 할당 후 빈 공간 리스트는 다음과 같다.

 

최적 적합 방식

최적 적합의 경우에는 종종 작은 빈 청크가 남는다. 최악 적합 방식은 유사하지만 대신 가장 큰 청크를 찾는 데 여기서는 30이다. 할당 후 빈 공간 리스트는 다음과 같다.

 

최악 적합 방식

이 예에서 최초 적합과 최악 적합 전략은 같은 결과를 도출한다. 하지만 차이점은 탐색 비용이다. 최적 적합과 최악 적합은 리스트 전체를 탐색한다. 최초 적합은 단지 적합한 청크를 발견할 때까지만 빈 청크를 검사하기 때문에 탐색 비용이 감소된다.

 

다른 접근법

기본적인 방식 이외에 메모리 할당을 향상시키기 위한 기술과 알고리즘이 제안되었다. 그 중 몇가지를 살펴보자.

 

개별 리스트

한 동안 유행했던 방법은 별도의 개별 리스트(Segregated list)를 사용하는 것이다. 기본적인 아이디어는 간단하다. 특정 응용 프로그램이 한두 개 자주 요청하는 크기가 있다면, 그 크기의 객체를 관리하기 위한 별도의 리스트를 유지하는 것이다. 다른 모든 요청은 더 일반적인 메모리 할당기에 전달된다.

 

이 방법의 장점은 분명하다. 특정 크기의 요청을 위한 메모리 청크를 유지함으로써 단편화 가능성을 상당히 줄일 수 있다. 요청된 크기의 청크만이 존재하기 때문에 복잡한 리스트 검색이 필요하지 않으므로 할당과 해제 요청을 신속히 처리할 수 있다. 

 

하지만 역시 다른 방법들과 같이 새로운 문제를 야기한다. 예를 들어, 지정된 크기의 메모리 풀과 일반적인 풀에 얼마만큼의 메모리를 할당해야 하는가? 특수 목적 할당기인 슬랩 할당기(Slab allocator)는 이 문제를 더 나은 방법으로 해결한다.  

 

슬랩 할당기

커널이 부팅될 때 커널 객체를 위한 여러 객체 캐시(Object cache)를 할당한다. 커널 객체란 락, 파일 시스템 아이노드 등 자주 요청되는 자료 구조들을 일컫는다. 객체 캐시는 지정된 크기의 객체들로 구성된 빈 공간 리스트이고 메모리 할당 및 해제 요청을 빠르게 서비스 하기 위해 사용된다. 아이노드들로 구성된 객체 캐시가 있고, 락 구조만을 담고 있는 객체 캐시도 있다. 기존에 할당된 캐시 공간이 부족하면 상위 메모리 할당기에게 추가 슬랩을 요청한다. 요청의 전체 크기는 페이지 크기의 정수배이다. 반대로, 슬랩 내 객체들에 대한 참조 횟수가 0이 되면 상위 메모리 할당기는 이 슬랩을 회수할 수 있다. 

 

슬랩 할당 방식은 빈 객체들을 사전에 초기화된 상태로 유지한다는 점에서 개별리스트 방식보다 우수하다. 반납된 객체들을 초기화된 상태로 리스트에 유지하여 슬랩 할당기는 객체당 잦은 초기화와 반납의 작업을 피할 수 있어서 오버헤드를 현저히 감소시킨다.

 

버디 할당

빈 공간의 합병은 할당기의 매우 중요한 기능이기 때문에 합병을 간단히 하는 방법들이 설계되었다. 하나의 좋은 예가 이진 버디 할당기(Binary buddy allocator)이다. 빈 메모리는 처음에 개념적으로 크기 2^N인 하나의 큰 공간으로 생각된다. 메모리 요청이 발생하면, 요청을 충족시키에 충분한 공간이 발견될 때까지 반 공간을 2개로 계속 분할한다. 이 시점에서 요청된 블럭이 사용자가에게 반환된다. 다음은 64KB 빈 공간에서 7KB 블럭을 할당하는 예이다.

 

이 예에서 가장 왼쪽의 8KB 블럭이 할당되고 사용자에게 반환된다. 이 방식은 거듭제곱 크기 만큼의 블럭만 할당할 수 있기 때문에 내부 단편화로 고생할 수 있다는 점에 유의해야 한다. (또한 외부 단편화도 있을 수 있다)

 

버디 할당의 진가는 블럭이 해제될 때에 있다. 8KB 블럭을 빈 공간 리스트에 반환하면 할당기는 또 다른 8KB 블럭 비어 있는지 확인한다. 비어 있다면 두 블럭을 병합하여 16KB 블럭으로 만든다. 할당기는 다음 16KB의 버디가 비어 있는지 확인한다. 비어 있다면 또 다시 두 블럭을 합병한다. 이 재귀 합병 과정은 트리를 따라 전체 빈 공간이 복원되거나 버디가 사용 중이라는 것이 밝혀질 때까지 계속 올라간다. 

 

버디 할당이 잘 작동하는 이유는 특정 블럭의 버디를 결정하는 것이 쉽다는 데 있다. 앞에서 빈 공간에 존재하는 블럭의 주소를 한 번 생각해보자. 각 버디 쌍의 주소는 오직 한 비트만 다르다.

(단 어느 위치의 비트가 다른가는 버디 트리의 수준에 따라 달라진다)