数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律学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示例
#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+ 阅读量
广告