필자는 버디라는 것이 단어가 생소할뿐 그 알고리즘 자체는 생소하지 않았습니다. 버디알고리즘은 누구나 한번쯤 할당에 대해서 고려해본 사람이라면 충분히 만들수 있는 알고리즘이라고 확신합니다. 그리 어려운것도 아니고 논리적인 연속된 페이지를 어떻게 얻을것인가를 해결하기 위한 당연한 페이지 할당 전략일겁니다. 가볍게 읽어보세요.

1. 근본적으로 특정 page크기가 결정되고 모든 할당은 이것을 하나의 단위로 할당한다는 조건이 있습니다. 이 크기단위보다 작을때는 리눅스에서는 Slab 할당이라는 전략을 구사하게 되는데 이것또한 별로 중요한 알고리즘은 아닌듯 합니다.

0 1 2 3 4 5 6

2. 위와 같이 총 7개의 페이지가 존재한다고 가정합시다.

0 1 2 3 4 5 6

3. 여기서 일단 1페이지를 할당한다면 0번 페이지가 할당될것입니다.

0 1, 2 3 4 5 6

4. 여기서 다시 2페이지를 할당한다면 1,2번이 연속(중요한것이 바로 이 연속 개념입니다.) 할당되겠죠.

0 1, 2 3 4 5 6

5. 다시 1페이지를 할당한다면 3번이 할당될것입니다.

~0 ~1, ~2 3 4 5 6

6. 이제 첫번째와 두번째 할당했던 페이지를 해제합니다. 그렇다면 이제 0,1,2는 연속(!)적인 선상에 놓인 사용되지 않는 페이지가 됩니다.

0, 1 2 3 4 5 6

7. 여기서 다시 2페이지를 할당하고자 한다면 0,1번이 연속(!)으로 할당되겠습니다.

0, 1 2->4 3 ->4 5 6
0, 1 2 3 4, 5 6

8. 이제 2페이지를 한번더 할당하고자 한다면 2,4번이 할당되는 방법과 4,5번이 할당되는 2가지 방법으로 나뉘게 됩니다. 여기서 우선은 4,5번이 할당되는것이 우선순위가 높습니다. 하지만 페이지가 부족할때는 2,4번이 할당되겠죠. 바로 이러한 것이 버디알고리즘입니다.

9. 여기서 보다 핵심적인 내용은 1개페이지 단위 노드와 2개,3개, ... 페이지 단위의 노드가 별도로 루트를 형성하여 보다 빠른 접근성을 갖도록 처리하는 것이 기본선행조건이겠죠. 즉, 2개 페이지를 할당받고자 한다면 2개의 공간이 있는 페이지만을 연결리스트로 갖는 노드를 추적하여 해당 페이지를 할당하며 만약 이 노드가 비어있다면 그에 2배에 해당하는 4개페이지 단위 노드를 검색할것입니다.

10. Slab 할당도 비슷한 개념이지만 어떤것이 좋다라고 하기에는 섣부른 판단이 아닐까 생각합니다. 상황에 따른 성능차이가 다소 있겠죠.