ページ置換アルゴリズム
仮想記憶で、物理メモリが満杯のときにどのページを追い出すかを決める FIFO・LRU・Clock・LFU・OPT を、同じ参照列で 1 参照ずつ見せます。ページフォルトの数を比べ、フレームを増やすと逆に増えるベラディの異常も確かめられます。
例
OS の教科書でよく使われる 20 個の参照列です。3 フレームで FIFO は 15 回、LRU は 12 回、OPT は 9 回のページフォルトになります。
フレームの数（物理メモリに置けるページの数）
最後に使ってから一番時間がたったページを追い出します。「最近使ったものはまた使う」という局所性を活かします。
時刻 19: ページ 1 を参照 → 枠 1 にあるので当たり（ヒット）
| 時刻 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 参照 | ||||||||||||||||||||
| 枠 1 | 7 | 7 | 7 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 枠 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 3 | 0 | 0 | 0 | 0 | 0 | |
| 枠 3 | 1 | 1 | 1 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 7 | 7 | 7 | ||
| 結果 | F | F | F | F | ○ | F | ○ | F | F | F | F | ○ | ○ | F | ○ | F | ○ | F | ○ | ○ |
| 追い出し | 7 | 1 | 2 | 3 | 0 | 4 | 0 | 3 | 2 |
ページフォルト（F）で読み込んだページ当たり（○）参照の数字を押すと、その時刻まで進めます
今の枠の状態
| 枠 | ページ | 最後に使った時刻 |
|---|---|---|
| 1 | 1 | 19 |
| 2 | 0 | 18 |
| 3 | 7 | 17 |
ここまでの結果
- ページフォルト
- 12
- 当たり
- 8
- ヒット率
- 40%
方式の比較
同じ参照列で、5 つの方式のページフォルトの数を比べます。表は 3 フレームのとき、グラフはフレームの数を 1〜7 に変えたときです。
| 方式 | ページフォルト | OPT との差 | |
|---|---|---|---|
| FIFO | 15 | +6 | |
| LRU | 12 | +3 | |
| Clock | 14 | +5 | |
| LFU | 13 | +4 | |
| OPT（最適） | 9 | — |
この参照列では、フレームを増やしてページフォルトが増える「ベラディの異常」は起きていません。
使い方
- 例を選ぶか、0〜9 のページ番号を並べた参照列を入力します。ランダムな参照列も作れます。
- フレームの数と置換アルゴリズムを選び、再生や ◀ ▶ で 1 参照ずつ進めます。キーボードの ← → でも動かせ、Home / End で最初と最後に移ります。
- 表の列が時刻、行がフレームの枠です。赤はページフォルトで読み込んだページ、緑は当たりです。参照の数字を押すとその時刻まで進みます。
- 下の「方式の比較」で、5 つの方式のページフォルトの数と、フレームの数を変えたときの変化を比べられます。
仮想記憶とページ置換
仮想記憶では、プログラムが使うメモリをページという決まった大きさの単位に分け、物理メモリ（フレーム）にはその一部だけを置きます。物理メモリにないページを参照するとページフォルトが起き、OS がディスクからそのページを読み込みます。フレームが満杯なら、どれか 1 つのページを追い出さなければなりません。どのページを追い出すかを決めるのがページ置換アルゴリズムです。
ディスクの読み込みはメモリの読み書きより何万倍も遅いので、ページフォルトの回数がそのまま性能に響きます。プログラムは「最近使ったデータをまた使う」（時間的局所性）傾向があるので、LRU やその近似の Clock がよく使われます。本物の LRU は参照のたびに時刻を記録する必要があって重いため、実際の OS ではハードウェアが付ける参照ビットを使う Clock の仲間が主流です。
ベラディの異常
ふつうはフレームを増やせばページフォルトは減りますが、FIFO では増えることがあります（1969 年に L. A. Belady らが報告）。LRU や OPT では、n フレームのときに置かれているページが、n + 1 フレームのときにも必ず置かれている（スタックアルゴリズム）ので、この異常は起きません。「ベラディの異常」の例で確かめられます。