[Kernel Analysis] MM - Buddy Allocator 분석
1. Page
리눅스는 물리 메모리는 프레임 단위로, 가상 메모리는 페이지 단위로 나눠 관리한다. 보통 한 페이지의 크기는 4KB이며, 페이지 크기에 대한 정보는 다음과 같이 getconf 유틸리티를 사용해 얻을 수 있다.
$ getconf PAGESIZE
4096
이때 페이지의 할당과 해제를 관리하는 시스템이 Buddy Allocator이다.
2. Buddy Allocator
Buddy 할당자는 외부 단편화를 줄이기 위해 페이지 할당 요청에 대해 최대한 연속적인 메모리를 할당하려고 한다. 예를 들어 2페이지 크기의 페이지 할당 요청이 들어온다면 인접한 2개의 페이지를 할당하고,
4페이지 크기의 할당 요청이 들어온다면 인접한 4개의 페이지를 할당하는 식이다. 버디 할당자는 이러한 목표를 달성하기 위해 bitmap과 free_list를 사용해 페이지를 할당한다.
2-1. Order
우선 버디 할당자는 페이지를 $2^n$개 단위로 묶어 관리한다. 이때 $n$을 order라고 한다. 일반적으로 리눅스 커널에서 order은 0부터 MAX_ORDER 상수까지의 값을 가진다. 이때 MAX_ORDER은 상수로써 10의 값을 가지기 때문에
커널은 최대 $2^{10}=1024$개까지 페이지를 묶어 관리한다. 다시 말하면,
order=0은 페이지를 1개 단위로 관리한다.order=1은 페이지를 2개 단위로 관리한다.order=2는 페이지를 4개 단위로 관리한다.
…order=10은 페이지를 1024개 단위로 관리한다.
위와 같다.
2-2. bitmap
다음으로 bitmap을 알아야 한다. 이는 페이지가 할당가능하면 0, 비어있으면 1로 기록해 이를 나열하는 방식이라고 생각하면 된다. 예를 들어 16페이지가 존재하는 메모리의 상태가 다음과 같다 하자(이때 MAX_ORDER=4라고 가정하자).
위에서 말했듯 0이면 사용가능, 1이면 사용중이다.
Page Number | 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
Availability | 1 0 0 1 0 0 0 0 0 1 0 1 1 1 0 0
2-2-1. order-0 bitmap
이제 order=0의 비트맵을 살펴보자. order=0은 페이지를 $2^0=1$개씩 관리하므로 당연히 Availability와 똑같을 것이다.
Page Number | 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
Availability | 1 0 0 1 0 0 0 0 0 1 0 1 1 1 0 0
-----------------------------------------------
Order 0 | 1 0 0 1 0 0 0 0 0 1 0 1 1 1 0 0
2-2-2. order-1 bitmap
이제 order=1의 비트맵을 살펴보자. order=1은 페이지를 인접한 $2^1=2$개씩 묶어 관리하므로 비트맵은 다음과 같을 것이다.
Page Number | 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
Availability | 1 0 0 1 0 0 0 0 0 1 0 1 1 1 0 0
----- ----- ----- ----- ----- ----- ----- -----
Order 1 | 1 1 0 0 1 1 1 0
여기서 bitmap은 할당할 수 있냐 없냐를 기준으로 하기 때문에,
00-01,02-03의 페이지처럼 인접한 두 페이지 중 하나라도 할당된 경우할당항 수 없음을 뜻하는1로 처리한다.12-13처럼 인접한 두 페이지가 전부 사용중이라면 당연히할당할 수 없음을 뜻하는1로 처리한다.04-05,06-07의 경우처럼 인접한 두 페이지가 전부 비어있다면할당가능을 뜻하는0으로 처리한다.
다만 여기서 주목해야 할 사실은
이다. 조금 풀어 설명하면 01-02 페이지 상태를 보면 인접한 두 개의 페이지가 전부 비어있기에 정의상 할당가능해 보인다. 그러나 01번 페이지는 첫 번째 구간?(무슨 용어를 사용해야할지 모르겠다)에 속하고, 02번 페이지는
두 번째 구간에 속한다. 즉 둘은 경계에 걸쳐 있고, 따라서 같은 구간에 속하지 않으므로 bitmap에서는 이런 상황을 고려하지 않고 order 경계에 맞춰 잘라버린다.
2-2-3. order-2 bitmap
이제 order=2의 비트맵을 살펴보자. order=2은 페이지를 인접한 $2^2=4$개씩 묶어 관리하므로 비트맵은 다음과 같을 것이다.
Page Number | 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
Availability | 1 0 0 1 0 0 0 0 0 1 0 1 1 1 0 0
------------- ------------- ------------- -------------
Order 2 | 1 0 1 1
위와 똑같은 원리이므로 설명은 생략해도 될 것 같다. order 경계대로 잘린다는 사실만 잘 기억하면서 따라가보자. order-3 bitmap, order-4 bitmap도 똑같으므로 직접 생각해 보자. 전체 bitmap을 표현하면 다음과 같다.
Page Number | 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
Availability | 1 0 0 1 0 0 0 0 0 1 0 1 1 1 0 0 (=order 0)
----- ----- ----- ----- ----- ----- ----- -----
Order 1 | 1 1 0 0 1 1 1 0
------------- ------------- ------------- -------------
Order 2 | 1 0 1 1
----------------------------- -----------------------------
Order 3 | 1 1
-------------------------------------------------------------
Order 4 | 1
2-3. free_area
버디 할당자는 bitmap이외에도 free_area라는 array를 사용해서 실제로 사용가능한 페이지를 관리한다. 이떄 free_area의 인덱스는 order로 사용된다. 예를 들어, free_area[0]은
single linked list로 연결해 둔 order-0 bitmap에서 0으로 표시된 페이지(즉, 사용가능한 페이지)를 가리키고 있다. 마찬가지로 free_area[2]는 single linked list로 연결된 order-2 bitmap에서 사용가능으로 표시된 페이지를
가리킨다. 다시 말해, free_area는 bitmap으로 표현된 페이지를 실제로 리스트로 연결해둔 것이라고 생각하면 편하다.
다만 여기서도 중요한 사실이 있는데,
예를 들어 위에서 예시로 든 상황에서 04-07 페이지는 4개의 인접한 페이지가 할당 가능한 상태이기 때문에 free_area[0]에 4개, free_area[1]에 2개, free_area[2]에 1개만 들어가는 것이
아니라, free_area[2]에 하나만 들어간다. 이는 중복 할당을 피하기 위함인데, 만약 이 페이지가 free_area[0]에도 들어있어서 하나의 페이지 할당 요청이 들어왔을 때 이 페이지를 할당해버리게 된다면,
이 페이지가 할당받았음에도 불구하고 2개의 페이지 할당 요청이나 4개의 페이지 할당 요청이 들어온 후 1개의 페이지 할당 요청이 들어왔을 때 재할당될 가능성이 존재하기 때문이다.
위와 같은 페이지 상황일 때, 위에서 말한 규칙을 고려해 free_area를 표현하면 다음과 같다.
free_area[0] = {1, 2, 8, 10}
free_area[1] = {14}
free_area[2] = {4}
free_area[3] = {}
free_area[4] = {}
3. page 할당
위에서 썼던 page 상황인
Page Number | 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
Availability | 1 0 0 1 0 0 0 0 0 1 0 1 1 1 0 0
을 다시 사용하자.
3-1. 2 page 할당 요청
앞서 말했듯 버디 할당자는 외부 단편화 최소를 위해 물리적으로 연속된 페이지를 할당하려고 한다. 이때 2개의 연속된 할당가능한 페이지는 order-1과 관계있고, 즉 free_area[1]을 탐색하면 쉽게 찾아낼 수 있다.
이해를 위해 앞서 작성해 둔 order-1 bitmap을 다시 살펴보자.
Page Number | 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
Availability | 1 0 0 1 0 0 0 0 0 1 0 1 1 1 0 0
----- ----- ----- ----- ----- ----- ----- -----
Order 1 | 1 1 0 0 1 1 1 0
order-1 bitmap에서 관찰 가능하듯 04-05 페이지가 할당 가능한 상태로 표시되어 있으나, 이 page는 이미 free_area[2]에 속한 상태이다. 즉 free_area[1]에는 14-15 페이지만 존재하므로, 이 페이지를 반환한다.
이후 두 패이지 모두 1로 표시해 중복 할당이 일어나지 않도록 한다. 할당한 이후 order-0 bitmap부터
order-4 bitmap까지 다시 그림으로 표현해 보면 다음과 같다.
Page Number | 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
Availability | 1 0 0 1 0 0 0 0 0 1 0 1 1 1 1 1 (=order 0)
----- ----- ----- ----- ----- ----- ----- -----
Order 1 | 1 1 0 0 1 1 1 1
------------- ------------- ------------- -------------
Order 2 | 1 0 1 1
----------------------------- -----------------------------
Order 3 | 1 1
-------------------------------------------------------------
Order 4 | 1
free_area는 다음과 같은 상황일 것이다.
free_area[0] = {1, 2, 8, 10}
free_area[1] = {}
free_area[2] = {4}
free_area[3] = {}
free_area[4] = {}
3-2. 4 page 할당 요청
4 페이지에 대한 할당 요청이 일어나면 당연히 free_area[2]에 대한 탐색이 이루어진다. 이떄 페이지 번호 04-07에 대한 할당이 가능하기 때문에 이 페이지를 반환하고 반환된 페이지들은
할당 불가능으로 표시되며 다시 한 번 전체 free_area에 대한 갱신이 이루어진다. 그림으로 표현하면 다음과 같다.
Page Number | 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
Availability | 1 0 0 1 1 1 1 1 0 1 0 1 1 1 1 1 (=order 0)
----- ----- ----- ----- ----- ----- ----- -----
Order 1 | 1 1 1 1 1 1 1 1
------------- ------------- ------------- -------------
Order 2 | 1 1 1 1
----------------------------- -----------------------------
Order 3 | 1 1
-------------------------------------------------------------
Order 4 | 1
free_area[0] = {1, 2, 8, 10}
free_area[1] = {}
free_area[2] = {}
free_area[3] = {}
free_area[4] = {}
3-3. free_area[N]에서 빈 페이지를 찾을 수 없을 때
예를 들어 페이지 할당 상황이 다음과 같다 하자.
Page Number | 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
Availability | 1 1 1 1 0 0 0 0 0 1 0 1 1 1 1 0
이런 상황에서 2개의 페이지에 대한 할당 요청이 들어온다면, free_area[1]은 비어있기 때문에 free_area[1]에 대한 검색은 실패할 것이다. (이는 위에서 말한 규칙을 잘 생각해보며
order-N bitmap과 free_area 잘 그려보면 이해할 수 있다. 이에 대한 설명은 생략해도 될 것 같다.)
이렇게 원하는 free_area에 할당 가능한 페이지가 없을 떄 버디 할당자는 하나 높은 free_area를 탐색한다. 즉 위의 상황에서는 free_area[1]에 대한 탐색이 실패했기 때문에
free_area[2]에 대한 탐색을 시도하고, free_area[2]에는 04-07에 해당하는 페이지가 존재하기 때문에 버디 할당자는 이 페이지들을 분할해 사용하게 된다. 즉
04-07에 해당하는 페이지를free_area[2]에서 삭제함04-05에 해당하는 페이지 중04-05애 해당하는 페이지를 반환함06-07에 해당하는 페이지를free_area[1]에 추가함
위와 같은 동작을 수행하게 된다. 이러한 작업을 분할이라고 한다. 이렇게 분할이 일어나며 free_area는 다음과 같이 갱신될 것이다. (여기서는 free_area[2]까지만 표현했다.)
// 분할 이전
free_area[0] = {10, 15}
free_area[1] = {}
free_area[2] = {4}
// 분할 이후
free_area[0] = {10, 15}
free_area[1] = {6}
free_area[2] = {}
4. page 해제
page 해제도 할당과 비슷한 과정을 거쳐 이루어지게 된다. 다시 한 번 위애서 말한 상황인
Page Number | 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
Availability | 1 0 0 1 0 0 0 0 0 1 0 1 1 1 0 0
을 사용해보자.
00 페이지에 대한 해제 요청이 들어온 상황이라고 가정하자. 이때 00 페이지가 해제된다면 자연스럽게 00-01 페이지가 order-1에 속할 수 있다는 것이 보일 것이다.
버디 할당자는 이러한 상황이 발생했을 때 01 페이지를 free_area[0]에서 삭제하고 00-01을 free_area[1]에 추가한다. 이후 03 페이지에 대한 해제 요청이 들어왔다고 가정하자.
이때 버디 할당자는 원래 free_area[1]에 들어 있던 00-01 페이지들을 삭제하고 free_area[2]에 00-03을 추가하려고 시도한다. 넓게 보면 00-07까지의 페이지가 전부 할당 가능한 상태이므로
원래 free_area[2]에 들어 있던 04-07 페이지를 제거하고 새로 free_area[3]에 00-07 페이지 전체를 추가한다.
이렇게 페이지들을 합치는 과정을 병합이라고 한다. 이렇게 분할이 일어나며 free_area는 다음과 같이 갱신될 것이다. (여기서는 free_area[3]까지만 표현했다.)
// 병합 이전
free_area[0] = {1, 2, 8, 10}
free_area[1] = {14}
free_area[2] = {4}
free_area[3] = {}
// 첫 번째 병합 이후 (00 페이지 해제)
free_area[0] = {2, 8, 10}
free_area[1] = {0, 14}
free_area[2] = {4}
free_area[3] = {}
// 두 번째 병합 이후 (03 페이지 해제)
free_area[0] = {8, 10}
free_area[1] = {14}
free_area[2] = {}
free_area[3] = {0}
5. slub allocator의 필요성?
버디 할당자는 최소 할당 단위가 page이다. 즉 수 비이트에 불과하지 않은 구조체에 대한 메모리를 할당받기 위헤서 버디 할당자를 사용한다면 심한 공간 낭비가 생기고,
내부 단편화가 굉장히 심해질 수밖에 없다. 이를 해결하기 위해서 slab allocator, slub allocator, slob allocator이 등장했고, 이를 한데 묶어
SLAB Allocator라고 부른다. 현재의 커널에서는 slub allocator가 기본적으로 쓰이기 때문에 이에 대한 내용을 다음에 다뤄볼 예정이다.
Leave a comment