メモリ回収の優先順位とLRUリスト管理

メモリ回収とは：空きフレームを作る選別作業

物理メモリが逼迫すると、カーネルは使われていなさそうなページを追い出して空きフレームを作ります。この作業が メモリ回収（reclaim, リクレイム） です。問題は「どのページを捨てるか」で、ここを誤ると必要なページを追い出して直後に読み直す スラッシング を招きます。理想は将来最も長く使われないページを捨てること（OPT）ですが未来は分からないので、現実には 最近の参照履歴から将来を予測 します。その近似が LRU（Least Recently Used）です。

回収対象には二種類あります。ファイルバックドページ（実行ファイルや mmap したファイル）は元データがストレージにあるため、クリーンならそのまま捨て、ダーティなら書き戻せば回収できます。匿名ページ（ヒープ・スタック等）は元データを持たないため、スワップへ退避しないと捨てられません。この差が回収の優先順位に直結します。詳細は スワッピングとページング機構の内部 を参照してください。

なぜ二段LRUなのか：active と inactive

厳密な LRU は、ページを参照するたびにリストの先頭へ移動する必要があり、ページアクセスのたびにリスト操作とロックが走るため現実的ではありません。Linux はこれを 二段の近似 LRU で置き換えます。各ページは次のいずれかのリストに属します。

さらにこれを 匿名（anon） と ファイル（file） で分けるので、実際には {active_anon, inactive_anon, active_file, inactive_file} の4本（メモリ cgroup ごと、NUMA ノードごと）が存在します。狙いは 頻繁に使われるワーキングセットを active 側に隔離 し、回収のスキャンを inactive 側に限定することです。これにより、毎回のアクセスでリストを触らずに済み、ロック競合とキャッシュ汚染を抑えます。近似 LRU の理論的背景は ページ置換アルゴリズム（LRU・Clock・WSClock） を参照してください。

昇格と降格：参照ビットによる二回参照ルール

ページがどう active と inactive を行き来するかが核心です。Linux は厳密に「直近1回の参照」ではなく、inactive にいる間に2回参照されて初めて active へ昇格 させる方式（おおむね second-chance / 二回参照ルール）を取ります。

新規ページ流入
  ↓
inactive list の先頭へ
  ↓ （末尾へ押し流される間に…）
  参照あり？──Yes──► PG_referenced を立てる
  ↓ No                  ↓ もう一度参照された
inactive 末尾で         active list へ昇格
回収候補に              （ホットと判定）

active list:
  圧力がかかると末尾を走査し、参照ビットが
  落ちているページを inactive 側へ降格

ポイントは、一度だけ参照されたページを安易に active へ昇格させない ことです。cat largefile のように一回読んで二度と使わないストリーミング読み込みで、ワーキングセット（本当に何度も使うページ）が active から押し出されるのを防ぎます。active と inactive のサイズは概ね均衡が保たれ、active が大きくなりすぎると古い active ページが inactive へ降格されます。

refault検出：捨てた後に分かるワーキングセット

二段 LRU の弱点は、inactive が小さいと、本当はまだ使うページを早すぎるタイミングで追い出してしまう ことです。これを補正するのが refault 検出（ワーキングセット推定） で、Linux の回収を現代的にしている要の機構です。

考え方はこうです。ページを inactive 末尾から追い出すとき、そのページを完全に忘れるのではなく、追い出した瞬間の「回収カウンタ（eviction の通し番号に相当するもの）」を shadow エントリとして address_space に残します。後でそのページが再び要求されてフォルトしたとき（これを refault と呼ぶ）、現在のカウンタと残しておいた値の差から、追い出してから再要求までの間にどれだけのページが回収されたか＝refault 距離 を計算できます。

追い出し時:    counter = E0 を shadow に記録して破棄
        ↓ （この間に他のページが回収されていく）
再フォルト時:  現在 counter = E1
        refault距離 = E1 - E0
            この距離 < activeリスト長 だったか？
              Yes → 「activeを少し小さくしていれば
                       このページは生き残れた」
                   → activeを保護対象に再昇格（active へ直接投入）
              No  → 本当にコールドだった（救済しない）

意味を噛み砕くと、refault 距離が active リストの長さより小さいなら、「もし active をその分だけ小さく、inactive をその分だけ大きく取っていれば、このページは追い出されずに済んだ」と判断できます。つまり このページは正当なワーキングセットの一員だった ので、refault したページを active 側へ昇格させ、リストのバランスを inactive 寄りに調整します。逆に距離が大きければ、本当に長期間使われていなかったので救済しません。

ファイルと匿名の回収バランス

回収のもう一つの判断は 「ファイルページを捨てるか、匿名ページをスワップアウトするか」 です。両者はコストが非対称です。クリーンなファイルページは書き戻し不要で即捨てられますが、匿名ページは必ずスワップ I/O を伴います。一方でファイルキャッシュを削りすぎると read が毎回ディスクへ行き、性能が落ちます。

この配分を左右する第一の要素が vm.swappiness（0〜200、既定 60）です。直感的には大きいほど匿名側のスキャン（スワップアウト）に積極的、小さいほどファイル側の回収を優先します。ただしこれは固定比率ではなく、カーネルは 両者の最近の回収コスト を観測して動的に補正します。具体的には、各リストの refault 状況を見て、追い出してもすぐ戻ってくる（refault の多い）側のスキャンを控え、無駄の少ない側を多く削る ように anon:file のスキャン比を調整します。

スワップが無い環境では匿名ページは回収できないため、圧力はすべてファイルページに集中します。キャッシュを削り尽くしてもなお足りなければ、行き着く先は OOM killer です。この発動条件とオーバーコミットの関係は OOM killerとメモリオーバーコミット を参照してください。

direct reclaim と kswapd の役割分担

回収を いつ・誰が 行うかは二経路に分かれ、ここがレイテンシ特性を決めます。空きメモリには ウォーターマーク（min / low / high） が設定され、これを基準に動きます。

空きメモリ
  high ───── kswapd 停止（十分空いている）
  low  ───── kswapd 起床（背景で非同期に回収開始）
  min  ───── direct reclaim（割り当て要求スレッド自身が前景で回収）
              ↓ それでも作れない
            OOM killer

• kswapd（バックグラウンド回収）：NUMA ノードごとに常駐するカーネルスレッド。空きが low を下回ると起床し、high まで回復するまで非同期に回収する。割り当てを要求したスレッドとは別に走るので、アプリを止めない。先回りして空きを作るのが役割。
• direct reclaim（直接回収）：kswapd が間に合わず、割り当て要求の最中に空きが min を割ると、要求したスレッド自身がその場で回収 する。割り当てパスを 同期的にブロック するため、レイテンシスパイクの主因になる。

つまり健全な状態では kswapd が背景で需要を吸収し、direct reclaim は「kswapd が追いつかないほど割り当て速度が回収速度を上回った」ときの緊急手段です。direct reclaim が頻発しているなら、それはメモリ圧力が回収能力を超えているサインです。

まとめ

• メモリ回収は空きフレームを作る選別作業で、Linux は厳密 LRU を active/inactive の二段近似 LRU（さらに anon と file で別管理）で実装する。回収は inactive の末尾から行い、参照されたページは救済・昇格される。
• 昇格は 二回参照ルール に従い、一回だけ読まれたページは active へ上げない。これでストリーミング読み込みがワーキングセットを押し出すのを防ぐ。
• refault 検出 は shadow エントリで追い出し履歴を残し、再フォルトまでの refault 距離からワーキングセットを推定して、誤った回収を事後補正する。
• ファイルと匿名の回収バランス は swappiness と各リストの refault コストで動的に決まる。回収は kswapd（背景・非同期） が先回りし、間に合わなければ direct reclaim（前景・同期でブロック） が緊急対応、最後の砦が OOM killer。

土台は スワッピングとページング機構の内部 と ページ置換アルゴリズム（LRU・Clock・WSClock）、回収と表裏のキャッシュ側は ページキャッシュとライトバックの仕組み、最終手段は OOM killerとメモリオーバーコミット も合わせて読むと、メモリ管理の全体像が繋がります。