개요
Linux시스템 나아가, 일반적인 하드웨어는 메모리 할당의 최소단위가 존재하며 64비트 시스템의 경우 4KB를 최소한의 할당 크기로 사용한다. 만약 서로 다른 크기의 연속적인 페이지를 계속 할당하고 해제하게 되면 외부 단편화가 심해질 것이다. 이러한 시스템에서 물리 메모리를 외부 단편화를 최소화 하면서 할당하기 위한 방법중 하나로, Oder (즉 2의 지수승, 1, 2, 4, 8 ...)개의 페이지만을 할당받는 알고리즘을 Buddy Allocator라고 한다.
예를 들어서, 7개의 페이지를 요청하면 Buddy Allocator는 Order3의 페이지를 할당하게 된다.
특히 Buddy Allocator시스템에서는 Mitigration이 가능한 페이지와 불가능한 페이지가 구별되게 된다. Buddy System에서 Mitigration이 중요한 이유는, Mitigration이 가능한 페이지들을 최대한 연속적인 (제일 큰 order_)에 위차하도록 하여서 외부 단편화를 줄이고자 노력하기 때문이다.
- Mitigration이란 페이지 내부의 내용이 Copy가능하냐의 문제와도 연결되는데, Kernel은 보통 VA를 사용할때 PA + Constant의 VA와 PA가 Linear하게 연결되도록 구현한다. 즉 최대한 Address translation의 코스트를 줄이는 것인데, VA와 PA의 조합이 Fix되어 있기 때문에 Copy를 통해서 다른 영역으로 이동할 수 없다. 즉 Mitigration이 불가능하다. 그러나 User Memory와 같은 경우 이러한 제약이 없음으로 Mitigration이 가능하다. 리눅스에서는 enum migratetype으로 이러한 특성을 관리한다.
또한 Buddy System에서 Page_block이란 버디시스템이 관리하는 최소한의 단위이다. (관리와 할당은 전혀 다른 말이다.) 이 단위는 HUGE_PAGE의 크기와 일치하도록 설계되어 있는데 일반적인 시스템에서는 PageOrder9의 크기 즉 4MiB(1<<21)의 크기로 고정되어 있다.
이러한 Page_block은 다시 usemap이라는 구조체에 저장되게 되는데, usemap은 현재 시스템이 사용하고 있는 전체 Buddy System을 나타내게 된다.
장단점
메모리를 연속적인 Order로 구분하여 할당하고 해제하는 방식은 구현이 쉽고 매우 빠르다는 장점이 있다. 또한 외부 단편화를 줄일 수 있다는 장점이 있다. 그러나 내부단편화가 심하게 발생하는데, 예를 들어서 66KB를 할당받게 되면 무려 128KB의 메모리를 할당받아야 한다는 문제가 생긴다. 즉 62KB가 낭비되는 것이다. 이러한 문제를 해결하기 위해서 Buddy Allocator는 Slab Allocator과 같은 다른 메모리 할당 기법과 함께 사용될 수 있다. (실제로 커널에서 Slab Allocator는 내부적으로 Buddy Allocator을 이용하여 Physical Frame을 할당 받는다.)