操作系统——FIFO和LRU页面置换算法

一、算法介绍

1. 先进先出FIFO页面置换算法（来自百度百科-先进先出页面置换算法）

• 简介：优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。 
• 实现过程：假定系统为某进程分配了三个物理块，并考虑有以下页面号引用串：7, 0, 1, 2, 0, 3, 0,4,2,3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1。釆用FIFO算法进行页面置换，进程访问页面2时，把最早进入内存的页面7换出。然后访问页面3时，再把2, 0, 1中最先进入内存的页换出。由下图可以看出，利用FIFO算法时进行了12次页面置换。

• 缺点：FIFO算法还会产生当所分配的物理块数增大而页故障数不减反增的异常现象，这是由Belady于1969年发现，故称为Belady异常，如下图所示。只有FIFO算法可能出现Belady异常，而LRU和OPT算法永远不会出现Belady异常。

2. 最近最久未使用LRU页面置换算法（来自博客园-操作系统之页面置换算法）

• 简介：利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。所以，这种算法的实质是：当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。 
• 实现过程：对上面的实例釆用LRU算法进行页面置换，如图所示。进程第一次对页面2访问时，将最近最久未被访问的页面7置换出去。然后访问页面3时，将最近最久未使用的页面1换出。
• 补充说明：LRU性能较好，但需要寄存器和栈的硬件支持。LRU是堆栈类的算法。理论上可以证明，堆栈类算法不可能出现Belady异常。FIFO算法基于队列实现，不是堆栈类算法。

二、代码实现

#include
#include
#include
#include
using namespace std;
/*
2018.06.15
测试数据 
------------------------------------------- 
3
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 #
------------------------------------------- 
3
1 2 3 4 1 2 5 1 2 3 4 5 #
------------------------------------------- 
5
0 1 2 3 4 5 0 2 1 8 5 2 7 6 0 1 2 #
------------------------------------------- 
*/
int GetDistance(int currentPageID,int page);//按照页面编号获取在物理块内的页面最久未使用的时间（哪个距离当前pageID最远）
class BLOCK{
public:int blockNum;	//物理块总数int pageNum;	//物理块中的页面数量 int *pageID;	//页面号（大小为blockNum）int *stayTime;	//页面在物理块中的停留时间（与物理块ID对应）BLOCK(int num){int i;pageNum=0;blockNum=num;pageID=new int[num];stayTime=new int[num];for(i=0;iGetDistance(currentPageID,pageID[DestID]))DestID=i;}return DestID;}
};	//物理块数据结构定义//-----------------------全局变量-------------------------
int BLOCKNUM;		//物理块数
int *PVS;			//PageVisitSequence页面访问序列
int PVS_NUM;		//页面访问序列长度
int **replaceTable;	//页面置换表格（维度：BLOCKNUM*PVS_NUM）
int *replaceArray;	//页面置换标志数组（大小为访问页面的次数，存储每次访问是否进行页面置换） 
int *lackArray;		//缺页中断标志数组（大小为访问页面的次数，存储每次访问是否存在缺页中断） 
//-----------------------函数声明-------------------------
void showMenu();							//菜单显示
void InputAndInit();						//数据输入和变量初始化
void ReplaceFIFO(BLOCK block);				//FIFO页面置换算法
int FindPage(int pageID,BLOCK block);		//页面查找（按照页面编号在物理块中查找页面是否存在） 
void ShowReplaceTable();					//置换表格输出
void ReplaceLRU(BLOCK block);				//LRU页面置换算法
void InfoDisplay();							//初始化信息显示 
int GetReplaceTimes();						//获取页面置换总次数
int GetLackTimes();							//获取缺页中断总次数 
//-----------------------函数定义-------------------------
int main()
{int select;int i;cout<<"亲爱的召唤师，在使用本程序之前，请按提示输入算法模拟需要的数据..."<>select;while(1){switch(select){case 1:InfoDisplay();cout< FIFO页面调度算法正在执行......"< LRU页面调度算法正在执行......"<>select;}delete[] PVS;delete[] replaceArray;delete[] lackArray;for(i=0;i>BLOCKNUM;cout<<"请依次输入页面访问序列（0~9，以#结束）..."<>PVS_char[i];getchar();while(PVS_char[i]!='#'){i++;cin>>PVS_char[i];getchar();}PVS_char[i]='\0';					//设置字符串终止符PVS_NUM=i;PVS=new int[PVS_NUM];for(i=0;i0)cout<<"\t     ";for(j=0;j=0;i--)if(PVS[i]!=page)distance++;else break;return distance;
}
void InfoDisplay()							//初始化信息显示 
{int i;cout<<"本页面置换模拟算法中: "<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！