【Linux】メモリ断片化 (外部フラグメンテーション) あれこれ


記事概要

Linux OS におけるメモリ断片化 1 ( 以降、断片化 ) について、調査したことのまとめ。


要約


  • 断片化していると、空きメモリが十分あるにも関わらず、メモリ確保に失敗することがある。


  • 断片化の影響を受けるのは、DMA ( Direct Memory Access ) のように物理メモリ領域を直接参照する必要があるもの ( 仮想メモリを使える場合は、物理メモリ領域が連続している必要がないため影響なし )。


  • 断片化のレベルは /proc/buddyinfo/sys/kernel/debug/extfrag/unusable_index から確認可能。


  • 明示的に断片化を解消方法は、OS 再起動と、# echo 1 > /proc/sys/vm/compact_memory がある。



物理メモリ領域について

断片化の話の前に物理メモリ領域について整理する。


  • Linux では、図 1 のように物理メモリ領域をページサイズ単位 ( # getconf PAGE_SIZE )に分割して管理している。

  • 分割された領域をページフレーム ( あるいは、物理ページ、実ページ ) と呼ぶ。

  • 物理メモリの割り当てと解放はこのページフレームの単位で行われる。

  • 要求されるメモリ量によって、割り当てられるページフレームの個数も変わる。1個分のページフレームで済むこともあれば、2個分、4個分 ( あるいは、それ以上 ) 要求されることもある。

図 1 : 物理メモリ領域

init.jpg

   青 ... 割り当て済みのページフレーム

   白 ... 空きページフレーム


断片化とは

断片化とは、空きメモリが十分あるにも関わらず、メモリ確保に失敗する状態。

図 2 のような物理メモリ領域が、連続するページフレームの割り当てと解放の繰り返しにより、図 3 のような割り当て済みのページフレーム郡の間に、小さな空きページフレームが散らばって存在する状態 ( 「虫食い」状態 ) となる。図 2 では最大で4個分の連続する空きページフレームがあるのに対し、図 3 では、最大2個分で、単一の空きページフレームも多い。

図 2 : 断片化が進んでいない物理メモリ領域

init.jpg

図 3 : 断片化が進んだ物理メモリ領域

frag_explain.jpg

このように断片化が進むと、空きページフレームが十分 ( 空きメモリが十分 ) でも、連続するページフレームの割り当てに失敗 ( メモリ確保に失敗 ) することがある。たとえば 図 3 の状態では、最大でも2個分の連続する空きページフレームしかないため、それより多くの連続する空きページフレームが要求されると、メモリ確保に失敗する。

ここで重要なのは、連続する空きページフレーム ( 物理的に ) が要求された場合ということ。そもそも、Linux では仮想メモリ( ページテーブル ) があり、物理的に連続していなくとも、仮想メモリ上で連続しているように見せることができる。よって、仮想メモリを使用できる場合は、断片化の影響がない。影響があるのは、DMA のように物理メモリ領域を直接参照する必要があるもの ( デバイスドライバからの要求など ) 2


断片化のレベル

/proc/buddyinfo から確認できる。

これは、Buddy System という物理メモリ割り当てのアルゴリズムによって管理された連続する空きページフレームの状態。Buddy System では、連続する空きページフレームを2のべき乗の大きさ ( 2^0、2^1...2^10 )毎に分類、管理している。実行例 19569 などは、2^0 の大きさ ( 1個分の連続する空きページフレーム ) を持つ空きページフレームの総数を示す。

断片化のレベルが高い場合、実行例 1 にある 9569 55888 18209 など左側にある数値が大きく、右側にある数値が小さくなっていく。これは、小さな空きページフレームの総数が多く ( 1個や2個の連続する空きページフレームが多く )、大きな空きページフレームの総数が少ないということを示すため、断片化のレベルも高い。


実行例1

root@lnxmnt19:~# cat /proc/buddyinfo 

Node 0, zone DMA 4 2 1 3 2 2 0 0 1 1 3
Node 0, zone DMA32 64115 51522 24898 6071 604 19 0 0 0 0 0
Node 0, zone Normal 9569 55888 18209 1637 262 29 1 0 0 0 0
### comment: order 2^0 2^1 2^2 2^3 2^4 2^5 2^6 2^7 2^8 2^9 2^10

これらについて 図 4 で補足する。見て分かるとおり、 連続する空きページフレームは $2^{0}( 1個分)$ から $2^{10}(1024個分)$ までの 11 種類の大きさ ( 連続する空きページフレーム ) 毎に分類され、それぞれがリストを持っている。この図で言うと、$2^{0}$ の大きさを持つ空きページフレームの総数は4つ、$2^{1}$ なら4つ ... $2^{2}$ なら2つとなる ( 以降、省略 )。実行例 1 にある数値はこんなイメージ ( なお、DMA、DMA32、Normal とは、ZONE という用途ごとに分けられた物理メモリの領域。ページフレームは、この ZONE ごとに管理されている )。

図 4 : 連続する空きページフレームのリスト

contigous_free_pageframe.jpg


断片化のレベル ( その2 )


実行例2

root@lnxmnt19:~# cat /sys/kernel/debug/extfrag/unusable_index

Node 0, zone DMA 0.000 0.001 0.002 0.003 0.009 0.017 0.033 0.033 0.033 0.097 0.226
Node 0, zone DMA32 0.000 0.197 0.514 0.820 0.968 0.998 1.000 1.000 1.000 1.000 1.000
Node 0, zone Normal 0.000 0.160 0.688 0.925 0.980 0.995 0.999 1.000 1.000 1.000 1.000
### comment: order 2^0 2^1 2^2 2^3 2^4 2^5 2^6 2^7 2^8 2^9 2^10

基本的な見方は、/proc/buddyinfo と同じ。こちらの場合は、利用不可な連続する空きページフレームのブロックの割り合いを示す。値が 0.000 に近づくほど、利用可能なブロックの数が多く、1.000 に近づくほど、利用可能なブロックの数が少ない。


断片化を解消する術

断片化を解消する方法はいくつかある。


OS を再起動する

OS を再起動すれば、解消される。


OS を再起動しない方法

/proc/sys/vm/compact_memory に 1 を書き込む 3

# echo 1 > /proc/sys/vm/compact_memory

Linux kernel 内のドキュメント ( /Documentation/sysctl/vm.txt )によると、1 を書き込むと、すべての ZONE (用途別に分けられた物理メモリの領域) が圧縮され、可能な限りの連続する空きページフレームが利用可能になるとのことです。ただし、この機能を利用するには、CONFIG_COMPACTION を有効にする必要あり 4


何もしない

前述の Buddy System によりメモリ回収の際に、割り当て済みのブロックが解放されると、解放されたブロックは隣合う同じ大きさの塊と結合 ( Buddy...仲間、相棒の意味 )し、可能な限り、より大きな塊へ変わる動きをするため ( たとえば、$2^{0}$ の塊同士が結合し、1つ大きな $2^{1}$ の塊となる )、特に何もしなくても、自然と断片化が解消することもある。

明示的に断片化を解消したい場合 ( 緊急時など ) は、前述の方法を使う。


compact_memory の効果

# echo 1 > /proc/sys/vm/compact_memory の効果が気になったので確認。



環境情報

root@lnxmnt19:~# lsb_release -d

Description: Linux Mint 19.1 Tessa

root@lnxmnt19:~# uname -r
4.15.0-20-generic







効果確認用のスクリプト

#!/bin/bash

echo "--------------------------------------------------------------------------------"

cat /proc/buddyinfo

echo "--------------------------------------------------------------------------------"

cat /sys/kernel/debug/extfrag/unusable_index

echo "--------------------------------------------------------------------------------"

# 記事には説明なし。説明割愛。
cat /proc/vmstat | grep compact 

echo "--------------------------------------------------------------------------------"

# 記事には説明なし。説明割愛。
cat /proc/pagetypeinfo







実行前の状態

root@lnxmnt19:~# ./memory_fragment.sh 

--------------------------------------------------------------------------------
Node 0, zone DMA 4 2 1 3 2 2 0 0 1 1 3
Node 0, zone DMA32 50311 43673 29118 12645 2612 281 27 3 1 1 0
Node 0, zone Normal 19659 17036 8875 3676 184 4 2 0 0 0 0
--------------------------------------------------------------------------------
Node 0, zone DMA 0.000 0.001 0.002 0.003 0.009 0.017 0.033 0.033 0.033 0.097 0.226
Node 0, zone DMA32 0.000 0.123 0.336 0.621 0.868 0.970 0.992 0.997 0.998 0.998 1.000
Node 0, zone Normal 0.000 0.161 0.441 0.732 0.973 0.997 0.998 1.000 1.000 1.000 1.000
--------------------------------------------------------------------------------
compact_migrate_scanned 36380
compact_free_scanned 618680
compact_isolated 37028
compact_stall 0
compact_fail 0
compact_success 0
compact_daemon_wake 40
compact_daemon_migrate_scanned 36380
compact_daemon_free_scanned 618680
--------------------------------------------------------------------------------
Page block order: 9
Pages per block: 512

Free pages count per migrate type at order 0 1 2 3 4 5 6 7 8 9 10
Node 0, zone DMA, type Unmovable 4 2 1 3 2 2 0 0 1 0 0
Node 0, zone DMA, type Movable 0 0 0 0 0 0 0 0 0 1 3
Node 0, zone DMA, type Reclaimable 0 0 0 0 0 0 0 0 0 0 0
Node 0, zone DMA, type HighAtomic 0 0 0 0 0 0 0 0 0 0 0
Node 0, zone DMA, type CMA 0 0 0 0 0 0 0 0 0 0 0
Node 0, zone DMA, type Isolate 0 0 0 0 0 0 0 0 0 0 0
Node 0, zone DMA32, type Unmovable 1170 752 360 109 16 0 0 0 0 0 0
Node 0, zone DMA32, type Movable 45945 40069 26433 11110 2023 71 1 0 0 0 0
Node 0, zone DMA32, type Reclaimable 3196 2852 2325 1426 573 210 26 3 1 1 0
Node 0, zone DMA32, type HighAtomic 0 0 0 0 0 0 0 0 0 0 0
Node 0, zone DMA32, type CMA 0 0 0 0 0 0 0 0 0 0 0
Node 0, zone DMA32, type Isolate 0 0 0 0 0 0 0 0 0 0 0
Node 0, zone Normal, type Unmovable 364 227 194 3 0 0 0 0 0 0 0
Node 0, zone Normal, type Movable 18214 16217 8479 3387 119 0 0 0 0 0 0
Node 0, zone Normal, type Reclaimable 1077 602 190 280 60 0 0 0 0 0 0
Node 0, zone Normal, type HighAtomic 5 5 12 6 5 4 2 0 0 0 0
Node 0, zone Normal, type CMA 0 0 0 0 0 0 0 0 0 0 0
Node 0, zone Normal, type Isolate 0 0 0 0 0 0 0 0 0 0 0

Number of blocks type Unmovable Movable Reclaimable HighAtomic CMA Isolate
Node 0, zone DMA 1 7 0 0 0 0
Node 0, zone DMA32 15 1019 110 0 0 0
Node 0, zone Normal 124 2573 241 1 0 0







実行後の状態

root@lnxmnt19:~# ./memory_fragment.sh 

--------------------------------------------------------------------------------
Node 0, zone DMA 4 2 1 3 2 2 0 0 1 1 3
Node 0, zone DMA32 3914 3343 3081 2300 1471 983 637 416 262 182 57
Node 0, zone Normal 1471 1279 1387 916 417 215 141 86 50 45 31
--------------------------------------------------------------------------------
Node 0, zone DMA 0.000 0.001 0.002 0.003 0.009 0.017 0.033 0.033 0.033 0.097 0.226
Node 0, zone DMA32 0.000 0.009 0.025 0.056 0.101 0.158 0.235 0.335 0.465 0.629 0.857
Node 0, zone Normal 0.000 0.012 0.034 0.081 0.143 0.199 0.258 0.334 0.427 0.536 0.731
--------------------------------------------------------------------------------
compact_migrate_scanned 591336
compact_free_scanned 1933859
compact_isolated 379231
compact_stall 0
compact_fail 0
compact_success 0
compact_daemon_wake 40
compact_daemon_migrate_scanned 36380
compact_daemon_free_scanned 618680
--------------------------------------------------------------------------------
Page block order: 9
Pages per block: 512

Free pages count per migrate type at order 0 1 2 3 4 5 6 7 8 9 10
Node 0, zone DMA, type Unmovable 4 2 1 3 2 2 0 0 1 0 0
Node 0, zone DMA, type Movable 0 0 0 0 0 0 0 0 0 1 3
Node 0, zone DMA, type Reclaimable 0 0 0 0 0 0 0 0 0 0 0
Node 0, zone DMA, type HighAtomic 0 0 0 0 0 0 0 0 0 0 0
Node 0, zone DMA, type CMA 0 0 0 0 0 0 0 0 0 0 0
Node 0, zone DMA, type Isolate 0 0 0 0 0 0 0 0 0 0 0
Node 0, zone DMA32, type Unmovable 1158 747 363 108 17 1 0 0 0 0 0
Node 0, zone DMA32, type Movable 1198 1211 1354 1160 913 750 556 394 253 171 54
Node 0, zone DMA32, type Reclaimable 1558 1385 1364 1032 541 232 81 22 9 11 3
Node 0, zone DMA32, type HighAtomic 0 0 0 0 0 0 0 0 0 0 0
Node 0, zone DMA32, type CMA 0 0 0 0 0 0 0 0 0 0 0
Node 0, zone DMA32, type Isolate 0 0 0 0 0 0 0 0 0 0 0
Node 0, zone Normal, type Unmovable 453 227 186 3 1 0 1 1 1 1 0
Node 0, zone Normal, type Movable 664 622 672 531 349 211 138 85 49 44 31
Node 0, zone Normal, type Reclaimable 280 426 526 376 62 0 0 0 0 0 0
Node 0, zone Normal, type HighAtomic 5 5 12 6 5 4 2 0 0 0 0
Node 0, zone Normal, type CMA 0 0 0 0 0 0 0 0 0 0 0
Node 0, zone Normal, type Isolate 0 0 0 0 0 0 0 0 0 0 0

Number of blocks type Unmovable Movable Reclaimable HighAtomic CMA Isolate
Node 0, zone DMA 1 7 0 0 0 0
Node 0, zone DMA32 15 1019 110 0 0 0
Node 0, zone Normal 126 2571 241 1 0 0






結果

左が実行前、右が実行後。

order の小さな塊は減少し、大きな塊は増加している。たしかに断片化のレベルが緩和しているように見える。

diff.png


さいごに

個人的には、まだまだ調べ足りない気がしますが、この辺で一旦終了。もう少し中身の部分にまで触れたかったけど、調べれば調べるほどハマっていく感じがあり、終わりが見えないなあと。

以下、調べきれなかったこと / 調べたいこと


  • カーネルメモリ割り当てに使用する関数の違いが断片化に影響するかどうか。kmalloc() は物理的に連続する領域を確保することを保証するのに対し、vmalloc() は保証しない。つまり、断片化の影響があるのは、kmalloc() で vmalloc() では影響がないように見えるけど、実際はどうなんだろう。

  • IOMMU やスキャッターギャザー DMA なら、断片化の影響受けないっぽいけど本当かどうか。これらの仕組みの理解。


  • cat /proc/vmstat | grep compact で見える compact_migrate_scannedcompact_free_scannedcompact_isolated の意味。

  • Buddy System などの実装周り。

断片化を理解するには、もっと勉強が必要そうです。


参考





  1. タイトルのとおり、外部フラグメンテーションのこと。内部フラグメンテーションについて言及しない。 



  2. ただし、IOMMU やスキャッターギャザーを使っている場合は、物理メモリ領域が連続している必要がないため、問題とならない模様。 



  3. RHEL 6.4 (kernel-2.6.32-421.el6 未満) の環境で実行すると kernel panic が発生する問題 (全文読むにはログインが必要) が報告されていますので、RHEL 6.4 では実行しないか、kernel を 2.6.32-421.el6 (影響を受けないバージョン) 以降にアップデートしてから実行することをオススメ。 



  4. 手元の Linux Mint 19、Ubuntu 18.10、Fedora 28、CentOS 7.6、openSUSE Leap 15.0 ではデフォルトで有効化されていることを確認済み。