ページ置換アルゴリズム計算（FIFO・LRU・Optimal）

メモリがいっぱいなのに、プログラムが読み込まれていないページを必要とすると、OSは追い出すページを選ばなければなりません。この選択が、ページフォルトの発生回数を左右します。この計算ツールは、代表的な置換アルゴリズムであるFIFO・LRU・Optimal・LFU・Clock（セカンドチャンス）を参照列に適用し、参照ごとのフレーム、ヒット・フォルトを表示し、ヒット率を求め、すべてのアルゴリズムをフレーム数ごとに比較して、ベレイディの異常が起きていればそれを示します。

使い方

1. 参照列を入力します。使われる順に並べたページ番号です。
2. フレーム数を設定します。
3. アルゴリズムを選びます。
4. フレームの表、フォルト回数、フレーム数ごとの比較を確認します。

計算式

ヒット率 = ヒット ÷ 参照数 · フォルト率 = フォルト ÷ 参照数 · フォルトには空きフレームへの最初の読み込みも含む

FIFOは最も早く読み込まれたページを、LRUは最後の使用が最も古いページを、Optimalは次の使用が最も遠い（または二度と使われない）ページを、LFUは読み込み後の使用回数が最も少ないページ（同数なら先に読み込まれたもの）を追い出します。Clockはフレームを巡って参照ビットを消しながら進み、すでにビットが落ちている最初のページを追い出します。どのアルゴリズムも、教科書と同様に最初の読み込みをフォルトとして数えます。比較表は、フレーム1個から12個まで繰り返し実行した結果です。

計算例

教科書の参照列7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1とフレーム3個では、LRUのページフォルトは12回、ヒットは8回（ヒット率40%）で、FIFOは15回、Clockは14回、Optimalは下限の9回です。参照列1 2 3 4 1 2 5 1 2 3 4 5では、FIFOはフレーム3個でフォルト9回、4個で10回となります。これがベレイディの異常です。