ページ置換アルゴリズム（LRU・Clock・WSClock）

問題設定：何を最小化するのか

物理メモリ（フレーム）が満杯のとき、ページフォルトで新しいページを読み込むには、既存のページを 1 つ 追い出す（evict） 必要があります。どれを選ぶかが ページ置換アルゴリズム です。目的は ページフォルト率の最小化、すなわち遅いディスク I/O の回数を減らすことに尽きます。

評価は 参照列（アクセスされるページ番号の並び）と フレーム数 を固定し、フォルト回数を数える形で行います。以下、参照列の例を 7 0 1 2 0 3 0 4 のように表記します。

FIFO とその落とし穴

最も単純なのは FIFO：最初に入れたページから順に追い出します。実装はキュー 1 本で済みますが、「古い＝もう使わない」とは限らないため、頻繁に使うページも順番が来れば追い出してしまいます。

さらに FIFO には直感に反する性質があります。

OPT：到達不能だが基準になる理想

理論上の最適は OPT（最適置換 / Beladyのアルゴリズム） で、「今後最も長い間、参照されないページ」を追い出します。これは証明上フォルト回数が最小ですが、未来の参照列を知る必要があり、実機では実装できません。意味があるのは「他のアルゴリズムがどれだけ理想に迫れているか」を測る 下限の物差し としてです。

LRU：過去から未来を推測する

実機で使える基準が LRU（Least Recently Used） です。「最も長く使われていないページ」を追い出します。直近の過去をそのまま未来の予測に使う、という 局所性（locality） への賭けです。

問題は実装コストです。厳密な LRU は「最後にアクセスした時刻順」を常に維持する必要があり、素朴にやると メモリアクセスのたびに 順序の更新が要ります。

要するに 厳密 LRU はハードウェア支援なしには重すぎる。そこで近似が要ります。

Clock（セカンドチャンス）：参照ビット1個での近似

CPU（MMU）は、ページが参照されると 参照ビット（reference bit, R） を 1 にする機能を持ちます。これ 1 個だけを使って LRU を近似するのが Clock アルゴリズム です。フレームを 円環（時計） に並べ、針が候補を指します。

追い出し探索（針が指すページを見る）:
  while true:
    if R == 0:          # 最近使われていない
        このページを追い出す
        針を1つ進めて終了
    else:               # R == 1 なら「もう一度チャンス」
        R = 0           # ビットを倒す
        針を1つ進める    # 次の候補へ

R=1 のページは即追い出さず、ビットを倒して 次の一周まで猶予 を与えます（これが「セカンドチャンス」の名の由来）。一周する間に再参照されれば R が再び 1 になり生き延び、されなければ次に針が来たとき R=0 で追い出されます。全ページの相対順序を保たずに、参照ビット 1 個で「最近使ったか否か」だけを近似 するのが要点です。

WSClock：ダーティとワーキングセットを足す

Clock は「最近使ったか」しか見ません。実務ではさらに 2 点が効きます。

• ダーティビット（D, 変更ビット）：書き換え済みページを追い出すには ディスクへの書き戻し が要る。クリーンなページなら捨てるだけで済むので、同条件ならクリーンを優先して追い出す ほうが速い。
• ワーキングセット年齢：そのページが ワーキングセット（直近の一定時間 τ に参照されたページ集合）に入っているか。

WSClock は Clock の円環走査に、各ページの 最終参照時刻 と ダーティビット を組み合わせます。

針が指すページ P を見る:
  if R == 1:
      R = 0; 最終参照時刻 = 現在時刻; 針を進める   # ワーキングセット内
  else:
      age = 現在時刻 - 最終参照時刻
      if age <= τ:                 # まだワーキングセット内
          針を進める
      else if D == 0:              # 窓外かつクリーン
          追い出して終了            # 書き戻し不要、即確保できる
      else:                        # 窓外だがダーティ
          書き戻しを発行（非同期）
          針を進める                # 一周後にクリーンになっていれば回収

ポイントは、τ より古い（ワーキングセット外）かつクリーンなページを最優先で追い出す こと。ダーティページは書き戻しを先に走らせ、後で回収します。これにより 書き戻しコスト と ワーキングセットの保護 を両立し、Clock より実務的にフォルトと I/O を抑えられます。

ワーキングセットとスラッシングの数理

なぜ「ワーキングセット」を守るのか。ここがスラッシングの核心です。プロセス i の時刻 t における ワーキングセット を、WS(i, t, τ) = 直近 τ 時間に参照した相異なるページの集合 と定義し、その大きさ（ページ数）を |WS(i, t, τ)| とします。

システム全体では、各プロセスのワーキングセットを同時に物理に載せられるかが分岐点になります。物理フレーム総数を m とすると、

Σ |WS(i, t, τ)|  ≤  m   → 各プロセスは作業集合を維持でき、フォルトは局所性内に収まる
Σ |WS(i, t, τ)|  >  m   → 作業集合が載り切らず、追い出した直後にまた要る＝スラッシング

τ の選び方も効きます。τ を大きく取ると古い参照まで「現役」とみなしワーキングセットが膨らみ、小さく取ると本来必要なページまで窓から外れて追い出してしまいます。WSClock の τ は、この 窓幅 を実時間（の近似）で表したものです。

まとめ

• 理想は OPT だが未来が要るため到達不能。実機では過去から推測する LRU が基準。
• 厳密 LRU は重いので、参照ビット 1 個で近似する Clock（セカンドチャンス） が主流。WSClock はダーティとワーキングセット年齢を足し、書き戻しとスラッシングを抑える。
• FIFO は Beladyの異常 を起こしうる。スラッシングは Σ|WS| > m で発生し、多重度を下げる のが本質的な対策。

前提となる仕組みは ページングとスワップ と 仮想記憶（ページング） を、確保・解放の方針は メモリ管理 を、多重度の制御は プロセススケジューリング も合わせて読むと理解が深まります。