本文共 3892 字，大约阅读时间需要 12 分钟。

【概念介绍&案例解析】

        >最佳(Optimal)置换算法

最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。

图示第五个物理块2,0,3，当要访问下一个页面也就是0，因为物理块包含所以不需要置换出来，接下来访问页面4因为物理块不包含页面4，所以需要看看页面4后面的哪些页面在物理块长时间未出现通过比较我们知道了页面4后面0是相对于2,3最晚出现所以将0替换就变成了2,4,3，后面的以此类推。

    >先进先出(FIFO)页面置换算法：

   FIFO算法是最早出现的置换算法、该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面给予淘汰。   

   假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：

   7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1  

     >采用FIFO置换算法的结果如下

     >缺页率=缺页次数/页面的总个数=12/20=60%

    【解析】

    我们从第四个物理块也就是2,0,1开始，因为FIFO置换算法的特点就是淘汰停留最久的页面，当进程访问页面2时，因为页面7最先进入停留的时间最久，所以把7置换出来，当访问页面0，因为2,0,1含有页面0所以不需要置换，当访问页面3的时候，因为物理块不含页面3则需要淘汰停留时间最久的页面0，所以此时的物理块变为2,3,1接下来进程访问页面0因为物理块不含页面0所以需要淘汰停留时间最长的页面1也就变成2,3,0，这里需要注意的一个问题就是物理块从0,2,3----->0,1,3，因为在4,2,3——————>0,2,3的时候最上面的页面置换一次所以当访问到页面1的时候不是置换0而是置换2

    >最近最久未使用(LRU)置换算法：

FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用(LRU)的页面置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。

    假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：

    7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1  

     >采用LRU置换算法的结果如下

     >缺页率=缺页次数/页面的总个数=9/20=45%

   【解析】

    >对于LRU置换算法我们采用的时选择最近最久未使用的页面给予淘汰，但这个最近最久该如何理解呢，这时候我们可以想到之前的最佳置换算法，它选择的时最远最久未使用的页面给予淘汰，所以呢我们可以这样理解LRU中的最近最久，就是当访问某个页面时候我们往左边看，比如我们就拿这个例子来进行剖析:我们从2,0,1看起，之前是7,0,1，我们往页面2的左边看有7,0,1，这三个页面所以最近的最久的就是7了所以将7置换出去，当进程访问页面3时，我们看页面3最左边 的那几个页面7,0,1,2,0在于物理块中的2,0,1作比较，那么最近最久未使用的不就是1吗，所以我们将1替换，以此类推....

好了上述就是虚拟内存的三种置换算法的题目解析了，接下来我们通过代码来验证下一个习题(注意:下面的代码运行在Vc++下的，用Devc++则会报错)

【代码展示】

头文件FIFO.h#include
   
    #include "iostream.h"const int MaxNumber=100;const int BlockNum=10;typedef struct Page_struct{    //定义页面结构快	int PageOrder[MaxNumber];  //保存作业的页面访问序列	int Simulate[BlockNum][MaxNumber];    //保存页面	int Block[BlockNum];        //物理块	int PageCount[MaxNumber];   //页面计数	int PageNum,LackNum;        //页面个数、缺页次数	double PageRate;            //缺页率	bool found;              }Page;Page p;bool PageShowEnable[BlockNum][MaxNumber];  //用于存储数组中的数据是否需要显示int N;   //页面个数int M;   //最小物理块数int LackCount;   //缺页计数void Pinput(){	cout<<"******************虚拟内存页面置换算法***********************"<
    
     >M;	while(M > BlockNum)   //大于数据个数	{		cout<<"物理块数超过预定值，请重新输入：";		cin>>M;	}	cout<<"请输入页面的个数：";	cin>>N;	while(N > MaxNumber)     //大于数据个数	{		cout<<"页面个数超过预定值，请重新输入：";		cin>>N;	}	cout<<"请输入页面访问序列："<
     
      >p.PageOrder[i];}void Poutput(){	int i,j;	for(i=0;i
      
       M)   		{			temp=0;			for(j=0;j
      
     
    
   

头文件Optimal.h#include
   
    void Optimal();  //Optimal函数void Optimal(){	int i,j,k;	int point;	int temp;   //临时变量,比较离得最远的时候用	LackCount=0;	for(j=0;j
    
     M)   		{			temp=0;			//获得要替换的块指针			for(j=0;j
    
   

头文件LRU.h#include
   
    void LRU(){	int i,j;	int point;	int temp;   //临时变量	LackCount=0;	for(j=0;j
    
     M)   		{			temp=0;			for(j=0;j
    
   

主程序Main.cpp#include
   
    #include "FIFO.h"#include "Optimal.h"#include "LRU.h"void Pinput();  //进程参数输入void Poutput();   //调度结果输出int main(int argc,char *argv[]){	Pinput();   //数据输入	int option;    while(true)	{		cout<
    
     >option;		switch(option)		{		case 1:			FIFO();			break;		case 2:			Optimal();			break;		case 3:			LRU();			break;		default:			break;		}		if(option != 1 && option != 2 && option != 3)			break;	}	return 0;}
    
   

【运行结果】

>缺页次数:8

>缺页率:40%

>缺页次数:12

>缺页率:60%

>缺页次数:14

>缺页率:70%