Interactive
ページ置換アルゴリズム可視化
物理メモリが満杯のとき、どのページを追い出すか——FIFO・LRU・Clock（セカンドチャンス）・OPT（最適置換）の 4方式を同じ参照列に同時に走らせ、1ステップずつ横並びで比較できます。 シナリオを切り替えると、フォルトの起き方がまったく違うことが見えてきます。特に「Beladyの異常」シナリオでフレーム数を3枠→4枠に増やすと、 普通は減るはずのフォルト数がFIFOだけかえって増える様子を実際に確かめられます。
フレーム数
フレーム数を3→4枠に増やすと、FIFOとClockはフォルト数がかえって増える（Beladyの異常）。LRUとOPTは必ず減るか変わらない。
参照 1 / 12（ページ 1）
FIFOフォルト 1
1
—
—
フォルト：空き枠に1を格納
LRU（最も長く未使用）フォルト 1
1
—
—
フォルト：空き枠に1を格納
Clock（セカンドチャンス）フォルト 1
1
1—
0▲次—
0フォルト：空き枠に1を格納
OPT（最適・未来を知っている前提）フォルト 1
1
—
—
フォルト：空き枠に1を格納
ここが分かる
- OPTは常に最少フォルト——未来の参照列を知っている前提の理論値なので、他の3方式のフォルト数は必ずOPT以上になる。実機では未来が読めないためOPTは実装できず、あくまで「どれだけ理想に近いか」を測る物差し。
- フレームを増やすと普通はフォルトが減るはずだが、FIFOは増えることがある（Beladyの異常）。原因はFIFOが「追い出す集合がフレーム数に対して入れ子になる」性質（スタックアルゴリズム）を満たさないため。LRUとOPTはスタックアルゴリズムなのでこの異常が起きない。
- Clockは参照ビット1個でLRUを近似するだけの手軽さと引き換えに、LRUほど正確な順序を持たない——この可視化のBeladyシナリオでは、Clockも増加を起こす場面がある。理論上の安全ネットが無い近似アルゴリズムの限界が見える一例。
- 「作業集合が効く例」では、同じページを繰り返す局所性があればどの方式でもすぐフォルトが収まる。「順次スキャン」では再利用が無いためFIFO・LRU・Clockはほぼ全参照でフォルトする——アルゴリズムの賢さは、参照列に活かせる局所性があって初めて効く。