308-置换策略FIFO算法的实现

喜欢ヅ旅行 2023-01-20 09:47 31阅读 0赞

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

## 先进先出（FIFO） ##

**FIFO策略把分配给进程的页框看做是一个循环缓冲区，按循环方式移动页。**  
**它所需要的只是一个指针，这个指针在该进程的页框中循环。**  
因此这是一种实现起来最简单的页面置换策略。除了它的简单性，这种选择方法所隐含的逻辑是置换驻留在内存中时间最长的页：一个在很久以前取入内存的页，到现在可能已经不会再用到了。这个推断常常是错误的，因为经常会出现一部分程序或数据在整个程序的生命周期中使用频率都很高的情况，如果使用FIFO算法，则这些页会反复地需要被换入换出。  
**下图的例子，FIFO策略导致了6次缺页中断**  
2 3 2 1 5 2 4 5 3 2 5 2 测试数据  
![在这里插入图片描述][2021051212495368.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;
    
    const int maxn = 105;
    int a[maxn];
    int main()
    {
        
    	deque<int>  dq;//定义一个队列
    	deque<int >::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;//标记值初始化为0
    			for (pos = dq.begin(); pos != dq.end(); pos++)//遍历队列 
    				if ((*pos) == in)//队列中的某个元素页的页号和当前访问的页的页号一致
    				{
        
    					flag = 1;
    					break;
    				}
    			if (!flag) //队列中不存在此页面元素
    			{
        
    				dq.push_back(in);//放入队列 
    			}
    		}
    		else //不存在多余页框
    		{
        
    			int flag = 0;//标记值初始化为0
    			for (pos = dq.begin(); pos != dq.end(); pos++)
    				if ((*pos) == in)
    				{
        
    					flag = 1;
    					break;
    				}//存在该元素
    			if (!flag)//不存在此元素 则置换最先进入的项 
    			{
        
    				numqueye++;//缺页数+1
    				dq.pop_front();//最先进入的出队列 
    				dq.push_back(in);//进队列 
    			}
    		}
    	}
    	cout << "FIFO缺页次数为:" << numqueye << endl;
    	cout << "FIFO缺页中断率为:" << (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]

[2021051212495368.png_pic_center]: /images/20221021/bc12bf8c24cf445aa94e6971452ca439.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221021/c804a21e1fa44b5e892d82be92528d19.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221021/cb94211a85a4486293d8b8907888da71.png