最適なページ置換アルゴリズムのためのC++プログラム

与えられたページ番号とページサイズ。タスクは、最適なページ置換アルゴリズムを使用してメモリブロックをページに割り当てるときのように、ヒットとミスの数を見つけることです。

最適なページ置換アルゴリズムとは何ですか？

最適なページ置換アルゴリズムは、ページ置換アルゴリズムです。ページ置換アルゴリズムは、どのメモリページを置換するかを決定するアルゴリズムです。最適なページ置換では、実際には実装できませんが、近い将来に参照されないページを置換しますが、これは最適であり、ミスが最小限であり、最適です。

例を使って図式的に説明して理解しましょう。

ここで、1、2、3を割り当てた後、メモリがいっぱいになっているので、4を挿入するために、1、2、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-> In function int predict(int page[], vector<int>& fr, int pn, int index)
   Declare and initialize res = -1, farthest = index
   Loop For i = 0 and  i < fr.size() and i++
      Loop For j = index and j < pn and j++
         If fr[i] == page[j] then,
            If j > farthest
               Set farthest = j
            End If
            Set res = i
            break
         If j == pn then,
         Return i
   Return (res == -1) ? 0 : res
Step 2-> In function bool search(int key, vector<int>& fr)
   Loop For i = 0 and i < fr.size() and i++
   If fr[i] == key then,
      Return true
      Return false
Step 3-> In function void opr(int page[], int pn, int fn)
   Declare vector<int> fr
   Set hit = 0
   Loop For i = 0 and i < pn and i++
   If search(page[i], fr) then,
      Increment hit by 1
      continue
   If fr.size() < fn then,
      fr.push_back(page[i])
   Else
      Set j = predict(page, fr, pn, i + 1)
      Set fr[j] = page[i]
      Print the number of hits
      Print the number of misses
Step 4-> In function int main()
   Declare and assign page[] = { 1, 7, 8, 3, 0, 2, 0, 3, 5, 4, 0, 6, 1 }
   Set pn = sizeof(page) / sizeof(page[0])
   Set fn = 3
   opr(page, pn, fn)
Stop

例

#include <bits/stdc++.h>
using namespace std;
int predict(int page[], vector<int>& fr, int pn, int index) {
   // Store the index of pages which are going
   // to be used recently in future
   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;
         }
      }
      // Return the page which are
      // are never referenced in future,
      if (j == pn)
         return i;
   }
   // If all of the frames were not in future,
   // return any of them, we return 0. Otherwise
   // we return res.
   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++) {
      // Page found in a frame : HIT
      if (search(page[i], fr)) {
         hit++;
         continue;
      }
      //If a page not found in a frame : MISS  
      // check if there is space available in frames.
      if (fr.size() < fn)
      fr.push_back(page[i]);
      // Find the page to be replaced.
      else {
         int j = predict(page, fr, pn, i + 1);
         fr[j] = page[i];
      }
   }
   cout << "Hits = " << hit << endl;
   cout << "Misses = " << pn - hit << endl;
}
// main Function
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