306-置换策略OPT算法的实现

秒速五厘米 2023-01-20 08:05 41阅读 0赞

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

## 最佳（OPT） ##

**OPT策略选择置换下次访问当前时间最长的那些页**  
可以看出该算法能导致最少的缺页中断，但是由于它要求操作系统必须知道将来的事件。显然这是不可能实现的。但是它仍能作为一种标准来衡量其他算法的性能。  
**下图给出了关于OPT策略的一个例子**，该例子假设固定的为该进程分配3个页框（驻留集合大小固定）。进程的执行需要访问5个不同的页，运行该程序需要的页地址的顺序为：  
**2，3, 2, 1, 5, 2, 4, 5, 3 , 2 , 5 , 2**  
这意味着访问的第一个页是2，第二个页是3，依次类推。当页框分配满了以后，OPT策略产生3次缺页中断。  
![在这里插入图片描述][20210511200329245.png_pic_center]

## 代码实现及注释 ##

**选择永不使用或者未来最长时间不被使用的页面置换  
每次操作完之后重置队列  
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 << endl << "请输入页面走向个数：";
    	cin >> n;//一共访问页面的个数
    
    	for (int i = 0; i < n; i++)//依次输入页面的页号
    	{
        
    		cin >> a[i];
    	}
    
    	for (int i = 0; i < n; i++)//遍历要访问的页
    	{
        
    		cout << "第" << i << "个" << endl;
    		int in;
    		in = a[i];//获取当前页面的页号并赋值给in
    		if (dq.size() < numyk)//如果存在多余页框
    		{
        
    			int flag = 0;
    			for (pos = dq.begin(); pos != dq.end(); pos++)
    				if ((*pos).value == in)//存在元素和它相同
    				{
        
    					flag = 1;
    					break;
    				}  //存在该元素
    			if (!flag) //如果页框中不存在此元素
    			{
        
    				opt temp;
    				temp.value = in;//当前页号赋值给temp的value
    				int f = 0;//标记值初始化为0
    				for (int j = i + 1; j < n; j++)//依次遍历后面的页面的页号
    					if (a[j] == in)//如果匹配到了相同的页号
    					{
        
    						f = 1;//标记值置为1
    						temp.time = j - i;//记录距离即是时间距离
    						break;
    					}
    				if (!f)//后面没有找到和当前页面页号相同的页
    				{
        
    					temp.time = n;//时间距离置为最大值n
    				}
    				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) //如果不存在此元素 则置换time最大的项
    			{
        
    				numqueye++;//缺页数+1
    				int m = dq.front().time;//获取队列的头部元素
    				cout << "m初始值为" << m;
    				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;
    					}
    				}
    				opt temp;
    				temp.value = in;//把要换入的页面的页号赋值给temp的value
    				int f = 0;//初始化标记值
    				dq.erase(mp);//把队列中的这个页元素(时间距离最大的)删除出去
    				for (int j = i + 1; j < n; j++)//往后遍历页面的页号
    					if (a[j] == in)//后面找到和当前页面页号相同的页
    					{
        
    						f = 1;//标记值置为1
    						temp.time = j - i;//计算时间距离
    						break;
    					}
    				if (!f)//后面找不到和当前页面页号相同的页
    				{
        
    					temp.time = n;//把页面的个数赋值给时间
    				}
    				dq.push_back(temp);//把当前的temp入队列
    			}
    		}
    		//每次之后重置，重新计算
    		for (pos = dq.begin(); pos != dq.end(); pos++)//迭代器遍历队列
    		{
        
    			cout << "队列中的元素为" << (*pos).value << endl;
    			int f = 0;//标记值初始化为0
    			for (int j = i + 1; j < n; j++)//往后遍历页面的页号
    				if (a[j] == (*pos).value)//后面找到和当前页面页号相同的页
    				{
        
    					f = 1;//标记值置为1
    					(*pos).time = j - i;//计算出时间距离
    					break;
    				}
    			if (!f)//后面找不到和当前页面页号相同的页
    			{
        
    				(*pos).time = n;//把页面的个数赋值给时间
    			}
    		}
    
    	}
    	cout << "OPT缺页次数为:" << numqueye << endl;
    	cout << "OPT缺页中断率为:" << (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]

[20210511200329245.png_pic_center]: /images/20221021/1c6c45d1fd47413db2ca7b4aa188d53a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221021/1fe4d848008744b68dc9e9f35e1d6ae0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221021/fa7af133e6a142bdb0537274686e897a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221021/b11847b9661c468dbf0392f39f226ff5.png