빈 공간 관리

이번 포스트에서는 빈 공간을 관리하는 문제에대해 논의할 것입니다.

세그멘테이션으로 물리메모리를 관리할시에 빈 공간 관리는 어렵고, 외부 단편화가 어느 경우에도 존재하게 됩니다.

빈 공간은 다양한 크기의 작은 조각으로 분할되어 결국 단편화되기 때문입니다.

빈 공간들의 전체 크기가 요청된 것보다 크더라도, 하나의 연속된 영역이 존재하지 않으면 실패할 수 있습니다.

위 그림이 그러한 문제의 예시라고 볼 수 있습니다.

이 경우 빈 공간은 20byte이지만, 10byte의 두 공간으로 나뉘어있습니다.

만약 15byte 요청이 들어오면 실패하게 되는것이죠.. 이번 포스트는 이것을 해결 해볼 것입니다.

가정

이번 포스트에서는 여러 가정을 통해 빈 공간을 관리하는 것에 대해 배울 것입니다.

1. malloc()과 free() 에서 제공하는 기본 인터페이스를 가정할 것입니다.
2. 라이브러리가 관리하는 공간은 역사적으로 heap이라고 불렸으며, heap의 빈 공간을 관리하는데는 링크드리스트가 사용됩니다.
3. 외부 단편화 방지에 중점을 둘 것입니다. 물론 내부 단편화 문제도 있을 수 있지만, 논의를 단순화하고 더 흥미로운 논의인 외부 단편화에 중점을 두겠습니다.
4. 클라이언트에게 할당된 메모리는 다른 위치로 재배치될 수 없다고 가정하겠습니다. 즉, 빈 공간 압축과 같은 시도는 불가능해집니다.

저수준 기법들

분할과 병합

빈 공간 리스트는 힙에 있는 빈 공간의 집합입니다.

위와 같은 힙이 있다고 가정하면, 빈 공간 리스트는 아래와 같습니다.

앞서 언급한 바와 같이, 10byte를 초과한 요청은 모두 실패하여 NULL을 반환하게 될 것입니다.

10byte를 요청하면, 둘 중 하나의 빈 청크를 사용하여 쉽게 충족될 것입니다.

그런데 만약, 10byte보다 적은 요청이 들어온다면 어떻게 될까요?

예를 들어, 1byte만 요청했다고 가정하겠습니다.

이 때는 splitting ( 분할 ) 로 알려진 작업이 실행됩니다.

요청을 만족시킬 수 있는 빈 청크를 찾아 이것을 둘로 나누게 됩니다.

만약, 할당기가 빈 공간 리스트의 두 번째 원소를 분할하기로했다고 가정해봅시다.

그 결과 빈 공간 리스트는 위와 같은 형태로 변하게 됩니다.

두 번째 원소가 21번 주소를 가리키게되고, 길이가 9로 줄어들게 되었습니다.

분할에 동반되는 기법은 빈 공간의 병합입니다.

처음 예시로 들었던 힙에서 만약 10번 주소를 free하게 된다면, 어떻게 될까요?

일단, 처음으로는 위와 같은 빈 공간 리스트를 반환하게 될 것입니다.

하지만 이 빈 공간 리스트는 여전히 10byte를 초과하는 요청은 실패를 반환한다는 문제가 있습니다.

이를 해결하기 위해, 메모리 청크가 반환될 때 빈 공간을 병합 ( coalescing ) 하는 방식을 사용합니다.

그 결과, 위 빈 공간 리스트는 아래와 같아집니다.

할당된 공간의 크기 파악

free(void *ptr ) 인터페이스는 크기를 매개변수로 받지 않는다는 것을 알고 있을 것입니다.

그렇기에, 포인터를 받게 되면 malloc 라이브러리는 메모리 영역의 크기를 신속하게 파악하고 그 공간을 빈공간 리스트로 변경시킵니다.

이 작업을 위해 대부분의 할당기는 추가 정보를 헤더 ( header ) 에 저장합니다.

헤더 블럭은 보통 해제된 청크 바로 직전에 위치합니다.

위 그림을 보겠습니다.

이 예에서는 ptr이 가리키는 20byte의 블럭을 검토하고 있습니다.

헤더는 할당된 공간의 크기와 부가적인 무결성 검사를 제공하기 위한 매직 넘버를 저장할 수 있습니다.

다음과 같이 할당 영역의 크기와 매직넘버를 저장하는 간단한 헤더를 가정하겠습니다.

typedef struct {
	int size;
	int magic;
} header_t;

free를 호출하면 헤더의 시작 위치를 파악하기 위해 간단한 포인터 연산을합니다.

void free(void *ptr){
	header_t *hptr = (header_t *)ptr-1;
	...
}

헤더를 가리키는 포인터 값을 얻게 되면, 라이브러리는 매직 넘버가 기대하는 값과 일치하는지 비교하여 안전 검사를 실시합니다. 그리고, 새로 해제된 영역의 크기를 간단한 수학을 통해 연산합니다. ( 헤더의 크기 + 헤더→size )

이제 주의할 점이 있습니다.

사용자가 N의 크기의 빈 공간을 요청하면, 할당기는 N+헤더의 크기 에 해당하는 빈 청크를 찾게된다는 것을 주의해야합니다.

빈 공간 리스트 내장

4096KB 크기의 힙이 있다고 가정하겠습니다.

이를 빈 공간 리스트로 관리하기 위해서 먼저 리스트를 초기화해야합니다.

시작시에는 리스트에 4096(빼기 헤더의 크기) 길이의 항목이 하나 존재합니다.

리스트 노드의 정의는 아래와 같습니다.

typedef struct __node_t {
	int              size;
	struct __node_t *next;
} node_t;

힙을 초기화하고 빈 공간 리스트의 첫 번째 원소를 넣는 코드를 살펴보겠습니다.

힙은 mmap()을 호출하여 얻어진 영역에 구축된다고 가정하겠습니다.

// mmap() returns a pointer to a chunk of free space
node_t *head = mmap(NULL, 4096, PROT_READ|PROT_WRITE,MAP_ANON|MAP_PRIVATE, -1, 0);
head->size = 4096 - sizeof(node_t);
head->next = NULL;

이 코드의 실행 후 리스트는 크기 4088의 항목 하나만을 가지게 됩니다.

매우 작은 힙이지만, 우리가 논의하기엔 충분합니다.

영역의 시작 주소를 16KB라고 가정하겠습니다.

이제 힙의 모양은 아래와 같습니다.

이제 위와 같은 빈 공간 리스트에서 100KB의 새로운 메모리 청크가 요청되었다고 가정하겠습니다.

우리는 현재 하나의 큰 빈 청크를 가지고 있기 때문에, 이 청크가 선택 될 것입니다.

빈 영역의 크기 + 헤더의 크기를 충족시킬 수 있는 청크와 나머지 빈 청크 두 개로 분할하게 됩니다.

헤더의 크기를 8 byte라고 가정한다면, 아래와 같을 것입니다.

100 byte의 요청이 오면 108byte를 할당하고, 할당 영역을 가리키는 포인터 ( ptr )를 반환할 것입니다.

그리고 나중에 free에서 사용할 수 있도록 할당된 공간 직전에 8byte 헤더를 넣습니다.

그런 후 남은 빈 노드를 3980byte로 축소합니다.

이제 100byte 3개의 공간이 존재하는 예를 보겠습니다.

아래 그림에서 볼 수 있듯이, 힙의 시작 부분에 324byte가 할당되어 있음을 알 수 있습니다.

빈 공간 리스트의 헤더는 세 번의 분할 이후 3764로 줄어들었음을 알 수 있습니다.

이제 여기서 free를 통해 일부 메모리를 반환하면 어떻게 될까요?

free(16500)을 호출하면 할당 영역중 가운데를 반환할 것입니다. 16KB ( 16384 ) + 이전 메모리 청크의 크기 ( 108 ) + 현재 메모리 청크의 헤더의 크기 ( 8 ) ⇒ 16500

라이브러리는 free 이후에, 빈 공간의 크기를 신속히 파악하고 빈 청크를 빈 공간 리스트에 삽입하게 됩니다.

빈 공간 리스트의 헤드 쪽에 삽입한다고 가정하면 아래와 같은 모양이 될 것입니다.

빈 공간 리스트는 첫 번째 원소 ( 100 byte ) + 두 번째 원소 ( 3764 byte ) 와 같은 구성이 될 것입니다.

아쉽지만 단편화가 발생하게 되었습니다.

마지막으로, 마지막 2개의 사용중인 청크를 해제한다고 가정하겠습니다.

현재 그림은 병합되어있지 않기 때문에 3개의 100byte 노드와 3764 byte 노드로 이루어질 것입니다.

이것을 해결하기위해, 병합을 하게되면 하나의 큰 청크가 될 것입니다.

힙의 확장

힙 공간이 부족하게 된다면 어떻게 해야할까요?

가장 쉬운 방법은 실패를 반환하는 것입니다.

그렇지만, 대부분의 전통적인 할당기는 적은 크기의 힙으로 시작하여 모두 소진하면 운영체제로부터 더 많은 메모리를 요청하게 됩니다. 할당기는 힙을 확장하기 위해 시스템콜을 호출하고, 확장된 영역에서 새로운 청크를 할당하게 됩니다.

기본 전략

빈 공간 할당을 위한 여러 가지 기본 전략들도 알아보겠습니다.

최적 적합 ( best fit )

빈 공간 리스트를 검색하여 요청한 크기와 같거나 더 큰 빈 메모리 청크들을 찾습니다.

그 후보 그룹 중 가장 작은 크기의 청크를 반환합니다.

매번 전체를 검색해야하기 때문에 성능저하를 초래할 수 있습니다.

최악 적합 ( worst fit )

빈 공간 리스트를 검색하여 가장 큰 빈 청크를 찾아 요청된 크기 만큼만 반환하고 남은 부분은 빈 공간 리스트에 유지하는 방법입니다.

매번 전체를 검색해야하기 때문에 성능저하를 초래할 수 있습니다.

최초 적합 ( first fit )

요청보다 큰 첫번째 청크를 찾아서 요청만큼 반환하는 방법입니다.

나머지 빈공간은 빈 공간 리스트에 유지합니다.

빠르게 찾을 수 있다는 장점이 있지만, 빈 공간 리스트 앞 부분에 작은 청크들이 많이 생길 수 있다는 단점이 있습니다.

리스트를 주소기반으로 정렬하여 병합을 쉽게하고, 단편화를 감소시킬 수 있습니다.

다음 적합 ( next fit )

마지막으로 찾았던 원소를 가리키는 추가의 포인터를 유지하는 방법입니다.

빈 공간 탐색을 리스트 전체에 균등하게 분산시키는 방법입니다.

첫 부분에 단편화가 생기는 것을 방지하고, 최초 적합과 비슷한 성능을 보여줍니다.

예제

10, 30, 20의 세 청크를 가지는 빈 공간 리스트가 있다고 가정하겠습니다.

15인 요청이 들어왔다고 가정하면, 최적 적합은 전체 리스트를 검색하여 마지막 원소인 20을 선택하여 15를 할당하고 5를 반환하여 위와 같은 결과를 보여줄 것입니다.

최악 적합 방식은 가장 큰 청크를 찾는 방식이므로, 30을 찾아서 15를 사용하고 15를 반환합니다.

이 예에서는 최초 적합과 최악 접합은 같은 결과를 도출합니다.

하지만, 최악 적합은 전체를 다 탐색해야했고 최초 적합은 단지 적합한 원소를 찾을 때까지만 찾았다는 차이가 있습니다.

다른 접근법

개별 리스트 ( segregated list )

한 동안 유행했던 방법은 별도의 개별 리스트를 사용하는 방법입니다.

기본 아이디어는 다음과 같습니다.

특정 응용프로그램이 한 두개 자주 요청하는 크기가 있다면, 그 크기의 객체를 관리하기 위한 별도의 리스트를 유지하는 것입니다.

이 방법의 장점은 특정 크기의 요청을 위한 메모리 청크를 유지하기 때문에 단편화 가능성을 줄일 수 있습니다.

하지만 시스템에 새로운 문제를 야기합니다.

예를 들어..

얼마만큼의 메모리를 할당해야하는가?와 같은 고민을 해야합니다.

버디 할당 ( binary buddy allocator )

빈 공간의 합병은 할당기의 중요한 기능이기 때문에 합병을 간단히 하는 많은 좋은 방법이 존재합니다.

하나의 좋은 예는 이진 버디 할당기입니다.

빈 메모리는 처음에 개념적으로 크기 2^N인 하나의 큰 공간으로 생각합니다.

메모리 요청이 발생하면, 요청을 충족시키기에 충분한 공간이 발견될 때까지 빈 공간을 2개로 계속 분할합니다.

가장 작은 충분한 공간이 발견되면 요청된 블럭이 사용자에게 반환됩니다.

하지만, 이 방법은 2^N 단위로만 블럭을 할당할 수 있기 떄문에 내부 단편화로 고생할 수 있습니다.

이 할당의 아름다움은 병합될 때 있습니다.

8KB가 반환되면, "버디" 8KB가 비어있는지 확인하고 비어있으면 병합합니다.

그것을 재귀적으로 합병하여 가능할 때까지 병합하게 됩니다.

요약

이 포스트에소는 가장 기본적인 형태의 메모리 할당기를 논의했습니다.

이러한 할당기는 많은 곳에서 사용되고, C 프로그램 뿐만아니라 운영체제내에서도 사용됩니다.

워크로드를 정확히 이해할수록, 메모리 할당기가 더 잘 작동하도록 최적화가 가능하며 현대 컴퓨터 시스템에서 빠르고 효율적이며 확장석이 좋은 메모리 할당기의 개발은 언제나 풀어야할 문제입니다.