[LWN 번역] Memory Compaction

예전부터 memory 단편화 문제는 여기서(LWN) 많이 다루어져왔다. 요약하면, system 이 수행되며 memory page 들은 흩어지는 경향이 있으며 이로 인해 물리적으로 연속적인 page 들을 할당하기가 어려워진다. 가능한 한 higher-order(multi-page)을 위한 요구를 피하기 위한 많은 작업들이 kernel 에 있었기에 대부분의 kernel 기능들은 page 단편화에 의해 문제가 발생하지 않았다. 하지만 아직까지 high-order page 할당이 요구되고 있으며, 이와 같은 code의 할당 요청은 단편화된 memory에 의해 실패하는 것이다. 

어떤 경우에는 이 같은 노력이 악화될 수도 있었다. 요즘 processor 는 4K page 로 제한을 두지 않고 더 큰 page(huge page) 를 process 의 address space에서 운영이 가능하다. huge page 사용을 통해 실제 성능향상을 얻을 수 있기 때문이다.(큰 page 로 운영되기 때문에 page fault 가 줄고-한번 fault 날때 크게 가져오기 때문-, 시스템 전체에 page 개수 운영이 많지 않아 TLB 를 통한 address변환이 빠르게 되어 성능향상이 있다.

참조:https://lwn.net/Articles/423584/) Huge page 를 사용할 경우 시스템에서는 충분히 크고 잘 정렬된 메모리 영역을 찾을 수 있어야 한다. 어느 시대에 수행되던 시스템이든 이런 영역을 찾는 것에 대해 고민이 많았을 것이다. 

몇년동안 커널 개발자들은 이런 메모리 단편화를 완화하기 위해 많은 시도를 해왔다. 그 결과로 ZONE_MOVABLE, lumpy reclaim 같은 기술이 나왔다. 

Mel Gorman 아저씨(?)가 memory comaction을 commit 했는데, 그 내용을 살펴 본다.

간략하게 시스템 메모리의 page 가 16개라고 가정하고 시작한다. 

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

시스템 운영 후 위와 같이 메모리를 사용하고 있다면(빨간색 블럭이 현재 사용되고 있는 메모리다) 실제 buddy 입장에서 보면 연속적인 2개의 page 조차도 할당 할 수 없다. buddy는 항상 블럭을 쌍으로 관리하고 있으며 앞에서 부터 0과 1을 상위 order page 로 보기 때문에 쌍을 맞춰 보면, 7번과 8번을 연속적으로 할당 해줄 수 있는 것처럼 보이지만 buddy 입장에서는 7번의 쌍은 6번이고 8번의 쌍은 9번 page 가 되므로 연속적으로 두개의 page를 할당 할 수 없는 상태이다. 

이런 상태에서 2개의 page 요청이 들어왔다면, memory compaction을 시도하게 된다. 알고리즘을 살펴보자

먼저 0(맨 하위)에서 부터 scan을 시작한다. scan하여 옮길수 있는 page를 찾는다.

Movable pages ----->  1  -----> 3, 4 ----> 5

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

반면에 15(상위)에서 역으로 free 상태의 page(migration 를 수행할) 들을 검색한다

Movable pages ----->  1  -----> 3, 4 ----> 5

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

                                                                                                                           7, 8 <----- 11, 12 <----- 14 <-- free pages

이렇게 하여 가운데 쯤에서 두 가지의 scan은 맞나게 되면 page migration을 시도한다. 사용되는 page 들은 뒷쪽으로 free한 page들은 앞쪽으로 모은다. 결과적으로,

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

위의 그림과 같이 8개의 연속적인 page 를 얻을 수 있다. 이로 인해 high order 의 page를 필요하다면 얻을 수 있게 된다. 

위의 그림은 간략하게 memory compaction을 표현한 것이다. 실제 시스템에서는 메모리도 크고 compaction이 하는 일이 많다. 그로 인해 큰 chunk의 연속적인 메모리를 확보할 수 있게 된다.

하지만 모든 page 들이 옮길 수 있는 것은 아니다!!! 퉤! 거의 모든 user space page 들은 옮길 수 있고, 옮겨진 page 로 인해 page table entry 들도 같이 수정이 필요하다. 그리고 kernel 이 direct 로 접근하는 메모리 영역의 page들은 옮길 수 없다. 하지만 이로 인해 kernel 이 접근하고 있는 non-movable page 들 때문에 연속적인 memory segment 를 가지지 못하는 경우가 발생하니, kernel 에서도 movable, non-movable page 들을 가질 수 있도록 하고 있다. 하지만 여기에도 문제가 있다고는 하는데 자세한 내용이 없어서 pass.

compaction은 언제 수행되는지 확인하면, 

   1. /proc/sys/vm/compact_node 에 node number 를 write 하면 compaction 이 수행된다. (NUMA system 이 아니라면 0인가?)

    2. system 이 high-order page 를 요청했는데 실패 한다면 수행된다. 실제 할당할 수 있는 memory 는 있지만 연속적인 공간의 부재로 memory allocation 이 실패하는 경우가 될 것이다. 

이런 경우가 아니라면 memory page migration은 시스템에게 많은 비용을 지불 하는 것으므로 compaction은 idle 상태로 유지한다. 사실 compaction을 피할 수 있다면 더 좋다고 한다.