307-置换策略LRU算法的实现

淡淡的烟草味﹌ 2023-01-20 08:06 122阅读 0赞

## 置换策略LRU算法的实现 ##

## 最近最少使用（LRU） ##

**LRU策略置换内存中上次使用距当前最远的页**。  
**根据局部性原理，这也是最近最不可能访问到的页**。  
**实际上，LRU策略的性能接近于OPT策略**。  
该方法的问题在于比较难于实现。一种实现方法是给每一页添加一个最后一次访问的时间标签，并且必须在每次访问存储器时，都更新这个标签。即使有支持这种方案的硬件，开销仍然是非常大的。另一种可选择的方法是维护一个关于访问页的栈，但开销同样很大。  
**下图给出了关于LRU行为的一个例子**。它使用与前面OPT策略的例子相同的页地址顺序。在这个例子中会产生4次缺页中断。  
![在这里插入图片描述][20210511203606628.png_pic_center]

## 代码实现及注释 ##

**选择距最近的最远的项置换 最近一段时间最长时间没有被访问的页面置换 和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;
    }

## 运行截图 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]  
**回车！**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]

[20210511203606628.png_pic_center]: /images/20221021/b692bac14eb9457ab683a850c2abbe12.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221021/c8b5ee8cb74447e1a2acf356f1d4f84a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221021/73e92b44937e45a0b81b624d53213507.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221021/4d424011acbc48f6b922b3ab03184842.png