一、实验目的
1、了解虚拟存储技术的特点，掌握请求页式存储管理的主要页面置换算法原理。
2、掌握请求页式存储管理中页面置换算法的模拟设计方法。
3、通过随机产生页面访问序列开展有关算法的测试及性能比较。
二、实验内容
设计一个虚拟存储区和内存工作区，并使用下述方法计算访问命中率。
①先进先出的算法（FIFO）；
②最近最少少使用算法(LRU);
③最佳淘汰算法(OPT):选淘汰最不常用的页地址;
④最少访问页面算法(LFR);
⑤最近最不经常使用算法(NUR).
（其中③④为选择内容）
命中率= 1 - 页面失效次数 / 页地址流长度
三、设计原理（或方案）及相关算法
1.fifo算法流程图
2.Lru算法流程图
3.opt算法流程图
运行结果及分析：
分析：通过多次运行结果发现，OPT算法淘汰页面最少，命中率始终最高，FIFO算法和LRU算法命中率差不多，但是淘汰页面大有不同。
源程序：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 320//随机数列的长度
#define B 4//内存的页面数
int IsInBuf(int buf[],int x)//返回某个数X有没有在缓冲区buf[]中
{int i,j=-1;for(i=0;i<B;i++){if(buf[i]==x){j=i;break;}else if(buf[i]==-1){buf[i]=x;j=i;break;}}return j;
}
int oldest(int list[],int buf[],int f[],int start)//返回最近最久未使用的页面的位置
{int i,j;for(i=0;i<B;i++){for(j=start;j<N;j++){if(buf[i]==list[j])break;}f[i]=j;}return oldest2(f);
}
int oldest2(int f[])//返回最长时间不使用的页面的位置
{int i,j=0,max=-1;for(i=0;i<B;i++){if(f[i]>max){max=f[i];j=i;}f[i]++;}return j;
}
void main()
{int list[N];int buf[B],f[B],i,j,k,max,min;int old=0;int change=0;printf("本程序假设内存为程序分配的内存块数是4!\n");srand((int)time(NULL));//生成一系列随机数并初始化环境for(i=0;i<B;i++)buf[i]=f[i]=-1;printf("产生的随机数列为:\n");for(i=0;i<N;i++){list[i]=(int)rand()%10;//产生随机数列printf("%2d",list[i]);}printf("\n");printf("\nOPT淘汰页面的序列为:\n");change=0;for(i=0;i<B;i++)buf[i]=f[i]=-1;for(i=0;i<N;i++){j=IsInBuf(buf,list[i]);if(j==-1){old=oldest(list,buf,f,i);printf("%2d",buf[old]);buf[old]=list[i];f[old]=0;change++;}else{printf("");}}printf("\nOPT算法的命中率为:%f\n",1-(float)change/320);printf("\nFIFO淘汰页面的序列为:\n");change=0;for(i=0;i<B;i++)buf[i]=-1;for(i=0;i<N;i++){j=IsInBuf(buf,list[i]);if(j==-1){if(buf[old]==-1)printf("");else printf("%2d",buf[old]);buf[old]=list[i];old=(old+1)%(int)B;change++;}elseprintf("");}printf("\nFIFO算法的命中率为:%f\n",1-(float)change/320);printf("\nLRU淘汰页面的序列为:\n");change=0;for(i=0;i<B;i++)buf[i]=f[i]=-1;for(i=0;i<N;i++){j=IsInBuf(buf,list[i]);old=oldest2(f);if(j==-1){printf("%2d",buf[old]);buf[old]=list[i];f[old]=0;change++;}else{f[j]=0;printf("");}}printf("\nLRU算法的命中率为:%f\n",1-(float)change/320);
}
