C++で学ぶ最適ページ置換アルゴリズム（OPT）の実装方法 ― ヒット数とミス数の求め方

ページ参照列とフレーム数が与えられたとき、最適ページ置換アルゴリズム（Optimal Page Replacement Algorithm）を用いてメモリブロックにページを割り当てた場合のヒット数とミス数を求めるのが本記事の目的です。

最適ページ置換アルゴリズムとは？

ページ置換アルゴリズムとは、「どのメモリページを入れ替えるか」を決定するアルゴリズムのことです。その中でも最適ページ置換アルゴリズムは、「今後最も長い間参照されないページ」を置き換え対象として選ぶ方式です。

理論上は最もミス（ページフォールト）が少ない理想的なアルゴリズムですが、将来のページ参照を正確に予測することは現実には不可能なため、実際のOSにそのまま実装されることはありません。ただし、他のアルゴリズム（FIFOやLRUなど）の性能評価における理論的な下限値（ベンチマーク）として非常に重要です。

具体例を使って図解的に見てみましょう。

この例では、まずページ1・2・3を割り当てた時点でメモリ（フレーム）が満杯になります。ここで新しいページ4を挿入する場合、現在フレーム内にある1・2・3の中から「近い将来に再び参照されないページ」を探します。このケースではページ3が該当するため、ページ3を追い出してページ4を格納します。以降も同様の手順をページ列の末尾まで繰り返します。

入力例と出力例

Input: page[] = { 1, 7, 8, 3, 0, 2, 0, 3, 5, 4, 0, 6, 1 }
    fn=3
Output: Hits = 3
    Misses = 10

Input: page[] = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 }
    fn = 4
Output: Hits = 7
    Misses= 6

解決のためのアプローチ

• ページ参照列を配列として受け取る。
• 割り当て済みのページが近い将来に再び参照されるかどうかを調べ、参照されないページを新しいページで置き換える。
• 要求されたページがすでにフレーム内に存在すればヒット数を、存在しなければミス数をそれぞれインクリメントする。
• 配列の最後の要素に到達するまでこの処理を繰り返す。
• 最終的なヒット数とミス数を出力する。

アルゴリズム

Start
Step 1-> 関数 int predict(int page[], vector<int>& fr, int pn, int index)
    res = -1, farthest = index を宣言・初期化
    i = 0 から fr.size() 未満の間ループ
        j = index から pn 未満の間ループ
            fr[i] == page[j] の場合、
                j > farthest なら farthest = j を設定
                res = i を設定し break
            j == pn の場合、
                i を返す
    (res == -1) ? 0 : res を返す
Step 2-> 関数 bool search(int key, vector<int>& fr)
    i = 0 から fr.size() 未満の間ループ
    fr[i] == key なら true を返す
    false を返す
Step 3-> 関数 void opr(int page[], int pn, int fn)
    vector<int> fr を宣言
    hit = 0 を設定
    i = 0 から pn 未満の間ループ
    search(page[i], fr) が真なら、
        hit を1増やして continue
    fr.size() < fn なら、
        fr.push_back(page[i])
    それ以外の場合、
        j = predict(page, fr, pn, i + 1) を設定
        fr[j] = page[i] を設定
    ヒット数を出力
    ミス数を出力
Step 4-> 関数 int main()
    page[] = { 1, 7, 8, 3, 0, 2, 0, 3, 5, 4, 0, 6, 1 } を宣言・代入
    pn = sizeof(page) / sizeof(page[0]) を設定
    fn = 3 を設定
    opr(page, pn, fn) を呼び出す
Stop

C++による実装例

#include <bits/stdc++.h>
using namespace std;
int predict(int page[], vector<int>& fr, int pn, int index) {
    // 今後使われるページのインデックスを記録する
    int res = -1, farthest = index;
    for (int i = 0; i < fr.size(); i++) {
        int j;
        for (j = index; j < pn; j++) {
            if (fr[i] == page[j]) {
                if (j > farthest) {
                    farthest = j;
                    res = i;
                }
                break;
            }
        }
        // 将来一切参照されないページがあれば、
        // そのページを返す
        if (j == pn)
            return i;
    }
    // すべてのフレームが将来使用される場合は
    // 最も遠くに使われるもの(res)を返す。
    // 該当がなければ0を返す。
    return (res == -1) ? 0 : res;
}
bool search(int key, vector<int>& fr) {
    for (int i = 0; i < fr.size(); i++)
    if (fr[i] == key)
    return true;
    return false;
}
void opr(int page[], int pn, int fn) {
    vector<int> fr;
    int hit = 0;
    for (int i = 0; i < pn; i++) {
        // フレーム内にページが見つかった場合：HIT
        if (search(page[i], fr)) {
            hit++;
            continue;
        }
        // フレーム内にページが見つからない場合：MISS
        // フレームに空きがあるか確認する
        if (fr.size() < fn)
        fr.push_back(page[i]);
        // 置き換えるべきページを決定する
        else {
            int j = predict(page, fr, pn, i + 1);
            fr[j] = page[i];
        }
    }
    cout << "Hits = " << hit << endl;
    cout << "Misses = " << pn - hit << endl;
}
// main関数
int main() {
    int page[] = { 1, 7, 8, 3, 0, 2, 0, 3, 5, 4, 0, 6, 1 };
    int pn = sizeof(page) / sizeof(page[0]);
    int fn = 3;
    opr(page, pn, fn);
    return 0;
}

実行結果

Hits = 3
Misses = 10

このように、最適ページ置換アルゴリズムでは「将来最も遠くにしか参照されないページ」を優先的に追い出すことで、ページフォールト（ミス）を最小限に抑えられます。計算量はO(ページ数 × フレーム数 × 参照列長)となりやや重いものの、他の置換アルゴリズムの評価基準として必ず押さえておきたい重要な概念です。