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

我们用来解决上述问题的方法 -

  • 将页面作为数组输入。
  • 查找已分配的页面是否在将来短期内存在,如果不存在,则用新页面替换内存中的该页面,
  • 如果页面已存在,则命中次数加 1,否则未命中次数加 1。
  • 重复此操作,直到到达数组的最后一个元素。
  • 打印命中次数和未命中次数。

算法

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

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

示例

 现场演示

#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

更新于: 2019年12月20日

4K+ 阅读量

启动您的 职业生涯

通过完成课程获得认证

开始学习
广告