Daeseok's Blog

Linux kernel physical memory allocator (Buddy) - Part 2-1

Physical memory allocating 방식인 buddy algorithm에 관련된 소스 분석을 쓰는 과정에서 코드 분석에만 너무 초첨을 맞춘 상태라는 것을 다시 읽으면서 느끼게 되었다.

그래서 이번 part 는 Buddy 알고리즘에 대해 간략하게 한번 정리 하고 넘어 가도록 한다.

Buddy 란?

이 포스트를 다읽으시고 부족하신 분들은 wiki 의 buddy memory allocation 을 읽어보시길 바랍니다.

Buddy 란 의미는 "동료", "친구" 이정도 되겠다.

왜 이런 이름을 붙였냐면, 기존 포스트 part 1, part 2 를 보면 order 란 단어를 사용하고 2^order 의 개수로 free_list 에서 관리 되고 있다는 얘길 했었다. 

아래 그림을 한번 보자.

(그림을 보실 때, 조금 부연설명을 하자면, free_area 라고 되어 있는 주황색 박스 맨위에 0번은 신경쓰지 말고 박스안의 숫자는 order 를 나타낸다. 0~15로 되어 있는 부분은 실제 memory 인 것이다.)

총 16개의 page 가 시스템에 있다고 가정한 그림이다. 빨간색은 이미 할당된 상태인 것이고 파란색은 할당되지 않은 상태이다.

여기에서 buddy 라는 의미를 찾아보자.

기준은 order 로 한다. 기준이라는 의미는 몇개의 page 를 연속적으로 묶어 두느냐는 것이다. 예를 들어 order 0 의 입장에서는 0 과 1번이 서로 buddy 가 된다.

그렇다면 order 2 에서의 0번의 page 의 buddy 는 몇번 page 인지 알려면 <page number> + 2^order 하면 될 것이다. 즉 order 2 의 0번 page 의 buddy 는 0 + 2^2 = 4 번이 된다. 

(하지만 4번의 buddy는 4+2^2 = 8 이 아니다. 반대인 0이 된다. 현재 order 의 갯수 순서대로 buddy가 정해진다고 보면됨.) 현재 16개 page 에서의 buddy 를 알아보면

order 0 의 입장에서는 0, 1 이 서로 buddy,
                               2, 3 이 서로 buddy,

....

order 1 의 입장에서는 0, 2 이 서로 buddy,

                               4, 6 이 서로 buddy,

...

order 2의 입장에서는 0, 4 가 서로 buddy,

                              8, 12 가 서로 buddy,

... 

이런식으로 된다. 

이렇게 buddy 로 관리 하려는 이유는 buddy 알고리즘을 이용한 할당은 메모리 외부 단편화를 줄여주기 위한 방식이라고 알려드렸다. 이렇게 하면 연속적인 page 할당 관리가 용이 하고, 작은 단위의 order 0, 1,2 등(하위 order)의 할당/해제가 많이 있었다면 buddy 끼리 분리 및 합체(?) 등으로 메모리 관리가 가능하다는 것이다.

왜 그런지 그림으로 알아보도록 하자. 다시 위의 그림을 보았을 때, 시나리오를 보자.

Scene 1.

   a. 3번 page 할당 해제.

   b. 0번 page 할당 해제.

   c. 1번 page 할당 해제.

a 번 이후 상태를 보자.

3번이 해제 되고(파란색으로 변경) order 0번 list 에 추가적으로 add 가 된다.

3번의(order 0) 해제됨과 동시에 3번의 buddy 인 2번 page 가 해제 되어있는지 확인 한다. buddy(2번 page)가 할당 상태이다. 그냥 free_list 에 add만 하고 해제를 종료.

다음 b, c 번을 진행하면,

0번이 해제되는 시점에서 0번의 buddy인 1번page 가 할당 상태이지만, 1번이 해제되는 시점에 1번의 buddy 인 0번 page 가 해제 상태이다. 그럼 0, 1번은 병합이 가능한 상태인 것이다. 같은 buddy 끼리 합체 후 상위 order 로 함께 올라 가는 것이다. 

결과 적으로 아래의 그림 처럼 0번 page 가 order 1 (2^1) 로 add 된다. 

0번 1번 page 가 합체하여 상위 order 에 올라갔다. 그 다음 order 1에서 0번 page 의 buddy 를 확인하자. 2번이 할당 상태이다. 그럼 합체를 종료한다.

해제를 통해 buddy 들이 어떻게 합쳐지는지 확인 했다.

이번에는 할당을 통해 어떻게 buddy 알고리즘이 적용되는지 확인 해보자. 위의 마지막 상황을 다시 한번 그림으로 정리한다.

이제 할당을 요청한다 일반적으로 요청한 order 에 딱 그 pgae가 있으면 그 page 를 할당 해 주면 끝이다.

Scene 2.

  a, order 1 (page 2개)의 할당 요청

이는 order 1의 free_list 를 확인해서 "있냐?" 고 물어본다. "있어" 하면 그 page 를 주면 된다.

order 1에는 0번 page 가 있었다.(0,1번이 할당 상태가 되고 free_area[1].free_list 에서 delete 함)

결과는,

간단하다.

Scene 3.

Scene 2 가 완료된 상태에서, 다시

  a. order 1(page 2개)를 요청

order 1을 요청하는 시점에서는 order 1의 free_list 에 할당 해줄만한 page 가 없다. 이런 경우에는 상위 order 에서 갖고 오는데, 그냥 갖과 왔다가는 낭패다. 상위 order는 최소 2배가 많은 page 를 갖고 있기 때문이다. 추가 작업이 필요하다는 의미이다. 

현재 order 1 의 page 가 없으므로 상위 order 를 검사한다(order 2). order 2에 마침 12번 page가 있다. (이는 12번 + 2^2개의 page 포함). 그렇다면 12번~13번 page를 할당 해주면 된다. 그렇다면 14번 15번은 당연히 하위 order 에 안착(?) 을 하면 되는 것인데, 아래의 그림으로 확인 해보자. 

12번 page 를 할당 해주고 요청이 2개의 page였으므로 그냥 2개의 page까지만 사용한다고 생각하고 그냥 14번 부터는 하위 order 설정을 하는 겁니다.

위의 그림과 같이 12번 13번이 할당되고, 14번이 order 1로 연결되게 된다.

최종적으로 아래와 같이 나올 것이다.

이렇게 buddy 를 physical memory 할당/해제 에 어떻게 이용되는지 확인 해보았다. code도 이 logic 을 이용한 것이라고 보면된다.

이렇게 하면 최대한 할당을 연속적으로 할 수 있고, 해제 후 병합을 통해 지속적인 관리가 가능하다는 것이다.