概述
置换策略LRU算法的实现
最近最少使用(LRU)
LRU策略置换内存中上次使用距当前最远的页。
根据局部性原理,这也是最近最不可能访问到的页。
实际上,LRU策略的性能接近于OPT策略。
该方法的问题在于比较难于实现。一种实现方法是给每一页添加一个最后一次访问的时间标签,并且必须在每次访问存储器时,都更新这个标签。即使有支持这种方案的硬件,开销仍然是非常大的。另一种可选择的方法是维护一个关于访问页的栈,但开销同样很大。
下图给出了关于LRU行为的一个例子。它使用与前面OPT策略的例子相同的页地址顺序。在这个例子中会产生4次缺页中断。
代码实现及注释
选择距最近的最远的项置换 最近一段时间最长时间没有被访问的页面置换 和OPT类似
2 3 2 1 5 2 4 5 3 2 5 2 测试数据
#include <deque>
#include <cstdio>
#include <algorithm>
#include<iostream>
using namespace std;
struct opt
{
int value;//值
int time;//时间
};
const int maxn = 105;
int a[maxn];
int main()
{
deque<opt> dq;//定义一个队列
deque<opt >::iterator pos;//定义一个迭代器
int numyk, numqueye = 0;
cout << "请输入物理页框块数:";
cin >> numyk;//页框的个数
int n;
cout << "请输入页面走向个数:";
cin >> n;//一共访问的页的个数
for (int i = 0; i < n; i++)//依次访问页
cin >> a[i];//依次输入页的页号
for (int i = 0; i < n; i++)//依次遍历页
{
int in;
in = a[i];//提取当前页的页号并赋值给in
if (dq.size() < numyk)//如果存在多余页框
{
int flag = 0;//初始化标记值为0
for (pos = dq.begin(); pos != dq.end(); pos++)//迭代器遍历队列
if ((*pos).value == in)//队列中存在元素和它相同
{
flag = 1;//标记值记为1
break;
}//存在该元素
if (!flag) //如果不存在此元素
{
opt temp;
temp.value = in;//把要放入的页的页号赋值给temp的value
temp.time = 0;//初始化时间距离值为0
dq.push_back(temp);//把当前的temp放入队列
}
}
else//如果不存在多余的页框
{
int flag = 0;//标记值初始化为0
for (pos = dq.begin(); pos != dq.end(); pos++)//迭代器遍历队列
if ((*pos).value == in)//将访问的页和队列中的某个元素页的页号相同
{
flag = 1;//标记值置为1
break;
}//存在该元素
if (!flag)//如果队列中不存在此页号的页
{
numqueye++;//缺页数+1
int m = dq.front().time;//获取队列的第一个元素页的时间距离值
deque<opt >::iterator mp = dq.begin();//注意此处千万注意初始化 否则有可能erase找不到对象崩溃
for (pos = dq.begin(); pos != dq.end(); pos++)//迭代器遍历队列
{
cout << (*pos).value << (*pos).time << endl;
if ((*pos).time > m)//找出队列中时间值最大的元素页的位置
{
cout << "迭代";
mp = pos;//时间距离值最大的页的位置
m = (*pos).time;
}
}
cout << "此时队列中所剩时间最长的元素为" << (*mp).value << endl;
opt temp;
temp.value = in;//把要换入的页的页号给temp的value
dq.erase(mp);//把时间最长的元素的页从队列中移除
temp.time = 0; //加进来之后,重置为0
dq.push_back(temp);//把当前的temp入队列
}
}
//每次之后重计算各对象的time
for (pos = dq.begin(); pos != dq.end(); pos++)//迭代器遍历队列
{
cout << "队列中的元素为:" << (*pos).value << endl;
for (int j = i; j >= 0; j--)//往前遍历页
if (a[j] == (*pos).value)//如果前面的页的页号和当前页的页号相同
{
(*pos).time = i - j;//计算出时间距离值
break;
}
cout << "距离上次时间为:" << (*pos).time << endl;
}
}
cout << "LRU缺页次数为:" << numqueye << endl;
cout << "LRU缺页中断率为:" << (double)numqueye * 1.0 / n << endl;
}
运行截图
回车!
最后
以上就是欢喜咖啡为你收集整理的307-置换策略LRU算法的实现的全部内容,希望文章能够帮你解决307-置换策略LRU算法的实现所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复