ページ置換：FIFOとLRUで差が出る

参照列とフレーム数を動かし、FIFO・LRU・OPT のページフォルトを並べて比較します。FIFO では枠を増やすと逆に悪化する Beladyの異常 も再現できます。

フレーム数（物理枠） 3 枠

参照列の長さ 12 個

使うページ種類数 5 種

アルゴリズム：

参照列：

FIFO フォルト

—

LRU フォルト

—

OPT フォルト（最良）

—

フォルト率（選択中）

—

置換の流れ（FIFO）── 赤=フォルト（ロード）、緑=ヒット、▲=このステップで追い出されたページ

ページフォルト（メモリに無く、ロード）ヒット（すでにメモリにある）そのフレームに常駐中

物理メモリ（フレーム）は限られているので、新しいページが必要なのに空きが無いとき、どれか1枚を追い出して入れ替えます。これがページ置換です。
FIFO は「最初に入れたページ」を追い出す。LRU は「最も長く使われていないページ」を追い出す。OPT は「この先いちばん遠くで使われるページ」を追い出す理論上の最良（未来が見える前提なので実装は不可）。
同じ参照列でも追い出すページが違うので、ページフォルトの回数に差が出ます。スライダーとボタンで動かしてみましょう。

いま何が起きている？

ここがポイント

OPT ≤ LRU・OPT ≤ FIFO ── OPT は未来を見られるので常に最小フォルト。実機では作れない理論下限。
LRU は局所性に強い ── 直近で使ったページを残すので、よく再利用するページがある列で FIFO より有利になりやすい。
Beladyの異常 ── FIFO はフレームを増やすとフォルトが増えることがある（例: 1 2 3 4 1 2 5 1 2 3 4 5）。LRU・OPT はスタック特性を持ち、この異常は起きない。
フォルト率 = フォルト数 / 参照回数 ── 同じ列・同じ枠数でもアルゴリズムで率が変わる。それが置換ポリシー選びの理由。