存储管理之虚拟存储器实现(页面置换算法模拟)
页面置换算法
先进先出算法(FIFO): 先进先出算法是最简单的分页替换算法,是指每次有新的分页需要调入时,会选择调入内存时间最久的分页换出。它简单,容易实现,但这种绝对的公平方式容易导致效率的降低。
--------发生缺页中断时,即最先进来的淘汰出去
最近最久未使用算法(LRU)算法: 即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间 t,当须淘汰一个页面时,选择现有页面中其 t 值最大的。即最近最少使用的页面予以淘汰。
--------发生缺页中断时,选择未使用时间最长的页面置换出去
最佳置换算法(OPT): 这是一种理想情况下的页面置换算法,但实际上是不可能实现的。
--------发生缺页中断时,看后面在物理块中的页面序列,查看谁出现的最晚,谁被淘汰。
大家可以做几道例题就基本理解了。
以下是这三种算法的模拟,使用的是队列存储和set进行查询;对于效率不是特别好,只是一个基本的模拟
要求: 设计主界面以灵活选择某算法。2.用随机数方法产生页面走向。3.假定初始时页面都不在内存。
内容: 编程序实现先进先出算法(FIFO)、最近最久未使用算法(LRU)算法、最佳置换算法(OPT)的具体实现过程,并计算访问命中率。
代码如下:
#include<bits/stdc++.h>
using namespace std;
vector<int> a; //随机数产生的页面走向
queue <int> q; //存页面--模拟
unordered_set<int> se; //队列存在的数
int cnt; //缺页次数
int Size; //物理块数
int option; //菜单选择
int n; //页面序列的个数
void init()
{
cnt = 0;
se.clear();
while (!q.empty()) q.pop();
}
void Print(queue<int> qq)
{
while (!qq.empty())
{
printf("%d ", qq.front());
qq.pop();
}
puts("");
}
void FIFO()
{
init();
for (int i = 0; i < a.size(); i++)
{
if (se.count(a[i])) //此页面已存在,无需操作
{
printf(" 无中断,命中:");
Print(q);
continue;
}
se.insert(a[i]);
if (q.size() == Size)
{
se.erase(q.front());
q.pop();
}
cnt++;
q.push(a[i]);
printf(" 第%d次缺页中断:", cnt);
Print(q);
}
printf(" FIFO算法缺页次数:%d, 缺页率:%%%.2lf\n", cnt, 1.0*cnt/n*100);
printf(" FIFO算法命中次数:%d, 命中率:%%%.2lf\n", n-cnt, (1 - 1.0*cnt/n) * 100);
}
void LRU()
{
init();
for (int i = 0; i < a.size(); i++)
{
if (se.count(a[i])) //此页面已存在,进行更新
{
queue <int> p;
while (!q.empty())
{
int x = q.front();
q.pop();
if (x == a[i]) continue;
p.push(x);
}
q = p;
q.push(a[i]);
printf(" 无中断,命中:");
Print(q);
continue;
}
se.insert(a[i]);
if (q.size() == Size)
{
se.erase(q.front());
q.pop();
}
cnt++;
q.push(a[i]);
printf(" 第%d次缺页中断:", cnt);
Print(q);
}
printf(" LRU算法缺页次数:%d, 缺页率:%%%.2lf\n", cnt, 1.0*cnt/n*100);
printf(" LRU算法命中次数:%d, 命中率:%%%.2lf\n", n-cnt, (1 - 1.0*cnt/n) * 100);
}
void OPT()
{
init();
for (int i = 0; i < a.size(); i++)
{
if (se.count(a[i])) //已经存在,不进行操作
{
printf(" 无中断,命中:");
Print(q);
continue;
}
if (q.size() < Size)
{
cnt++;
se.insert(a[i]);
q.push(a[i]);
printf(" 第%d次缺页中断:", cnt);
Print(q);
continue;
}
unordered_set<int> t;
queue <int> p;
for (int j = i + 1; j < a.size(); j++)
{
if(!se.count(a[j])) continue;
if (t.size() == Size - 1) break;
t.insert(a[j]);
}
int f = 1;
while (!q.empty())
{
int x = q.front();
q.pop();
if (!t.count(x) && f)
{
se.erase(x);
f = 0;
continue;
}
p.push(x);
}
q = p;
q.push(a[i]);
se.insert(a[i]);
cnt++;
printf(" 第%d次缺页中断:", cnt);
Print(q);
}
printf(" OPT算法缺页次数:%d, 缺页率:%%%.2lf\n", cnt, 1.0*cnt/n*100);
printf(" OPT算法命中次数:%d, 命中率:%%%.2lf\n", n-cnt, (1 - 1.0*cnt/n) * 100);
}
void menu()
{
printf("-------------------------菜单-----------------------------\n");
printf(" 1、随机产生作业和物理块数\n");
printf(" 2、自己输入作业和物理块数\n");
printf(" 3、先进先出算法(FIFO)\n");
printf(" 4、最近最久未使用算法(LRU)\n");
printf(" 5、最佳置换算法(OPT)\n");
printf(" 6、重现菜单\n");
printf(" 0、退出系统\n");
printf(" 请注意:在选择过1或2后才能选择3、4、5,否则会发生错误!\n");
}
void random()
{
a.clear();
srand((unsigned) (time(NULL))); //随机数更新
Size = rand()%5 + 2; //随机数[2, 6]
n = rand()%20 + 5; //随机数[5, 24]
printf("分配的物理块数为%d,页面序列共%d个,如下:\n", Size, n);
for (int i = 0; i < n; i++)
{
int x = rand()%(n / 2) + 1; //随机数[1, n / 2]
a.push_back(x);
printf("%d ",x);
}
puts("");
}
void Scanf()
{
a.clear();
printf("请问输入分配的物理块数:") ;
scanf("%d", &Size);
printf("请问页面序列共多少个:");
scanf("%d", &n);
printf("请输入:");
for (int i = 0; i < n; i++)
{
int x; scanf("%d", &x);
a.push_back(x);
}
}
int main()
{
menu();
while(1)
{
printf("请选择:");
scanf("%d", &option);
if (option == 0)
{
printf("\n 成功退出!!\n");
break;
}
switch (option)
{
case 1: random(); break;
case 2: Scanf(); break;
case 3: FIFO(); break;
case 4: LRU(); break;
case 5: OPT(); break;
case 6: menu(); break;
default: printf("输入错误,请您确认无误后再次输入!\n");
}
}
return 0;
}
结果截图:
在此页面也可查看
https://blog.csdn.net/weixin_57780057/article/details/124456655?spm=1001.2014.3001.5501
- 点赞
- 收藏
- 关注作者
评论(0)