メモリコンパクションと断片化対策

なぜ空きはあるのに確保が失敗するのか

物理メモリの空き総量が数 GB あるのに、2MB の連続領域（巨大ページ1枚）の割当が失敗する——これが外部断片化（external fragmentation）の典型症状です。原因は、空きページが物理的に飛び飛びに散らばっていて、要求された大きさの連続したフレームとしてまとまらない点にあります。

カーネルの物理ページ割当を担うbuddy systemは、空きメモリを「2のべき乗ページ数のブロック」として管理します。次数（order）N のブロックは 2^N ページ分の物理的に連続した領域です。order 0 が1ページ（典型的に 4KB）、order 9 が512ページ＝2MB に相当します。割当はフリーリストから該当次数のブロックを取り、無ければ上位次数を半分に割って供給します。解放時は、隣接する同サイズの相棒（buddy）が両方空いていれば**統合（coalesce）**して上位次数へ戻します。

ここに弱点があります。高次数のブロックを作るには、統合の連鎖が成立する必要があり、それには相棒が空いていることが条件です。連続領域のど真ん中に解放されないページが1枚でも居座ると、その周辺は永遠に統合できず、上位次数のブロックが組み上がりません。

order-0 の空き(.)と使用中(X)が混在する1MB領域:
  . . X . . . X . . . . . X . . .   ← 空きは多いが…
順に統合を試みても X が相棒側にいると上位次数に上がれない
  → order-9(2MB連続) は1つも作れない

どのページが穴を空けるのか：移動可能性による分類

外部断片化を悪化させる主犯は、移動も回収もできないページです。なぜなら、空きを連続させたくても、そこに居座るページを動かせなければ穴は埋まらないからです。Linux はこの「動かしやすさ」でページを分類します。これが migratetype（マイグレーションタイプ） です。

なぜ MOVABLE は動かせて UNMOVABLE は動かせないのか。MOVABLE なページは、その内容を指す参照が仮想アドレス経由のページテーブルエントリ（PTE）だけです。ページを別フレームへコピーし、PTE を新フレームへ張り替えれば、ユーザー空間からは何も変わったように見えません。一方 UNMOVABLE なページは、カーネルが物理アドレスを直に握っている（線形マップ上の固定アドレスを参照している、進行中の DMA の宛先になっている等）ため、物理位置を動かすと参照が壊れます。

グルーピングによる予防：混ぜないという設計

コンパクションは事後の治療ですが、その前にコストの低い予防が効きます。Linux のページ割当は、要求された migratetype ごとに**別々の領域（ページブロック単位、典型的に巨大ページと同じ粒度）**から供給しようとします。これが antifragmentation（断片化防止）グルーピングです。

狙いは単純で、移動可能なページと移動不能なページを物理的に混ぜないこと。MOVABLE だけが集まったページブロックは、そこに UNMOVABLE な異物が無いため、後でまるごと寄せて連続空きにできます。逆に最初から両者を混在させると、後から救済できない領域が量産されます。

混在配置（悪い）:  [M U M M U M U M] [U M M U M M U M]  ← どのブロックもUを含む
グルーピング（良い）: [M M M M M M M M] [U U M M M M M M]  ← 左ブロックは丸ごと寄せられる
   M = MOVABLE, U = UNMOVABLE

ただし予防は万能ではありません。メモリ逼迫時に希望の migratetype の空きが尽きると、カーネルは別タイプのページブロックから**借りる（fallback）**しかなく、ここで混在が生まれます。とりわけ UNMOVABLE が MOVABLE 領域へ染み出すと、その領域はもう丸ごとは寄せられません。予防が破れた後の最後の砦がコンパクションです。

メモリコンパクション：動かして連続させる

メモリコンパクション（compaction）は、移動可能なページを領域の一方へ寄せ集め、もう一方に連続した空きを作り出す処理です。ディスクのデフラグの物理メモリ版にあたります。アルゴリズムは、ゾーン内を両端から走査する2つのスキャナで構成されます。

コンパクションの2スキャナ方式:
  migrate scanner →  （下位アドレスから上へ：移動可能ページを探す）
                          ↓ 見つけたページを空きへコピーしPTEを張り替え
            ← free scanner（上位アドレスから下へ：空きフレームを探す）
  両スキャナが中央で出会ったら1パス終了

• migrate scanner はゾーンの下端から上へ進み、移動可能（MOVABLE/一部 RECLAIMABLE）なページを収集します。
• free scanner はゾーンの上端から下へ進み、空きフレームを収集します。
• migrate 側で見つけたページを free 側のフレームへコピーし、PTE を張り替えて移動を完了します。

これを繰り返すと、ページは下端側に密に詰まり、上端側に連続した空きが生まれます。移動可能ページにしか手を出さないため、ユーザー空間からは PTE が透過的に付け替わるだけでデータの一貫性は保たれます（背景はデマンドページングとページフォルト処理で扱う PTE 操作と同じ機構です）。

コンパクションには契機の異なる2系統があります。割当が高次数で失敗したときにその場で同期的に走る direct compaction と、kcompactd カーネルスレッドが事前に非同期で連続領域を仕込んでおく proactive/background compaction です。前者はレイテンシを割当パスに直接乗せ、後者はそれを背景へ逃がします。

巨大ページ割当との関係

コンパクションが最も効くのは**巨大ページ（huge page）**の確保です。x86-64 の 2MB 巨大ページは order 9（連続512ページ）を要求するため、断片化したメモリでは成立しません。巨大ページの利点は、1エントリで広い範囲を覆うことでページングのテーブルウォーク段数と TLB エントリ消費を減らし、TLB ミス率を下げる点にあります。

hugetlb はシステム起動直後の断片化が少ない時点で連続領域を予約プールとして囲い込みます。早いほど成功しやすいのは、時間が経つほど UNMOVABLE が散らばり連続領域が枯れるためです。**透過的巨大ページ（THP, Transparent Huge Page）は、ユーザーが意識せずとも khugepaged が連続した4KBページ群を巨大ページへ昇格（collapse）**し、その昇格に必要な連続フレームをコンパクションが捻出します。THP が確保できなければ通常ページに静かにフォールバックするため動作は壊れませんが、フォールバックが多発すると TLB 効率の利得を取り逃します。

まとめ

• 外部断片化は空きページ総量が足りても連続フレームが取れない状態。buddy system の統合は隣接相棒の空きに依存するため、移動・回収できないページ1枚が高次数割当を阻む。
• Linux はページを migratetype（MOVABLE / RECLAIMABLE / UNMOVABLE）で分類し、移動可能と移動不能を混ぜずにグルーピングして配置することで、事前に連続領域を保ちやすくする。
• メモリコンパクションは migrate/free の2スキャナで移動可能ページを片側へ寄せ、連続した空きを捻出する。コストの本体はページコピーとTLB シュートダウンで、移動不能ページが多いと失敗する。
• これらは **巨大ページ（hugetlb / THP）**の高次数割当を成立させる土台。hugetlb は早期予約、THP は khugepaged による昇格＋コンパクションで都度捻出し、失敗時は通常ページへフォールバックする。