一、实验目的
1、了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。
2、了解程序设计技术和内存泄露的原因
二、实验内容
1、模拟实现请求页式存储管理的几种基本页面置换算法
（1）最佳淘汰算法（OPT）
（2）先进先出的算法（FIFO）
（3）最近最久未使用算法（LRU））
思考题：
1、从几种算法的命中率看，哪个算法最高？哪个算法最低？对每个页面的执行结果进行分析。
2、OPT算法在执行过程中可能会发生错误，为什么？
三、实验原理
1、虚拟存储系统
UNIX中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页的存储管理方式。
当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺中断），由系统将其所需页面调入内存。这种页面调入方式叫请求调页。
为实现请求调页，核心配置了四种数据结构：页表、页框号、访问位、修改位、有效位、保护位等。
2、页面置换算法
当CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。该程序通过查找页表，得到该页所在外存的物理块号。如果此时内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。
（1）最佳淘汰算法（OPT）：选择永不使用或在未来最长时间内不再被访问的页面予以替换。
（2）先进先出的算法（FIFO）：选择在内存中驻留时间最久的页面予以替换。
（3）最近最久未使用算法（LRU）：选择过去最长时间未被访问的页面予以替换。
3、首先用srand( )和rand( )函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。
（1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：
A：50%的指令是顺序执行的
B：25%的指令是均匀分布在前地址部分
C：25%的指令是均匀分布在后地址部分
具体的实施方法是：
A：在[0，319]的指令地址之间随机选取一起点m
B：顺序执行一条指令，即执行地址为m+1的指令
C：在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m’
D：顺序执行一条指令，其地址为m’+1
E：在后地址[m’+2，319]中随机选取一条指令并执行
F：重复步骤A-E，直到320次指令
（2）将指令序列变换为页地址流
设：页面大小为1K；
用户内存容量4页到32页；
用户虚存容量为32K。
在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：
第 0 条-第 9 条指令为第0页（对应虚存地址为[0，9]）
第10条-第19条指令为第1页（对应虚存地址为[10，19]）
………………………………
第310条-第319条指令为第31页（对应虚存地址为[310，319]）
按以上方式，用户指令可组成32页。
四、实验中用到的系统调用函数（包括实验原理中介绍的和自己采用的），自己采用的系统调用函数要按照指导书中的格式说明进行介绍。
因为是模拟程序，可以不使用系统调用函数。
五、实验步骤
1、 画出每个页面置换算法流程图；
FIFO：
在这里插入图片描述
LRU:
在这里插入图片描述
OPT:
在这里插入图片描述
2、 对算法所用的数据结构进行说明；
int instruction[instructionNum];一维数组，用于存放指令序列
int page[pageNum];一维数组，用于存放指令序列对应的页面地址流
int phyMemory[blockNum]；一维数组，用于存放地址块中的页面
int flag[instructionNum];//一维数组，用于存放最久未被使用的页面
3、 测试数据随机产生。不可手工输入；
4、 编写程序并调试；
5、 多次测试程序，截屏输出实验结果；
6、 根据实验结果与理论课讲述的原理进行实验分析。
六、实验数据及源代码（学生必须提交自己设计的程序源代码，并有注释，源代码电子版也一并提交），包括思考题的程序。
include<stdio.h>
include<stdlib.h>
include<time.h>
define instructionNum 320 //总指令数
define MAX 2000
define pageNum 320
int instruction[instructionNum]; //指令序列
int blockNum;//可用内存块数
float count; //记录中断次数
int stayTime;//在内存中的停留时间
double FIFOmiss;//FIFO的缺失率
double LRUmiss;//LRU的缺失率
double OPTmiss;//OPT的缺失率
int *page=NULL;//指令序列对应的页面
int *phyMemory=NULL;//物理内存块
int flag[instructionNum]={0};//存放最久未被使用的页面
int max=-1, maxflag=0; //标记替换物理块进程下标
void initInstruction();//创建指令序列
void instructpage();//将指令序列变为页地址流
void initMemory(int n);//初始化内存块
int isExist(int target);//检测需要页面是否已经在内存中
int searchMemory();//寻找空闲内存块
void showPage();//输出页面
void delete();//释放内存
void FIFO();//FIFO算法
void LRU();//LRU算法
void OPT();//OPT算法
void main(){
initInstruction();//初始化指令序列
instructpage();//将指令序列转化为对应的页面地址流
srand((unsigned int)time(0));
int num=(rand()%29)+4;//内存块数随机生成，范围为4-32块
initMemory(num);//初始化内存块
printf("++++++++++++++++++++++++++++++++++++\n");
printf("先进先出的算法（FIFO）:\n");
FIFO();//FIFO算法
initMemory(num);//清空内存块
printf("++++++++++++++++++++++++++++++++++++\n");
printf("最近最久未使用算法（LRU）：\n");
LRU();//LRU算法
initMemory(num);//清空内存块
printf("++++++++++++++++++++++++++++++++++++\n");
printf("最近最久未使用算法（OPT）：\n");
OPT();//OPT算法
printf("内存可用块数为%d\n",num);//输出内存块
printf("FIFO算法缺页率为%f\n",FIFOmiss);//FIFO算法的缺失率
printf("LRU算法缺页率为%f\n",LRUmiss);//LRU算法的缺失率
printf("OPT算法缺页率为%f\n",OPTmiss);//OPT算法的缺失率
delete();//释放内存}
//创建指令序列
void initInstruction(){
srand((unsigned int)time(0));
for(int i=0;i<instructionNum;i+=4){
int temp=0;
temp=rand()%instructionNum; //在[0，319]的指令地址之间随即选取一起点mif(temp==319) break; //确保m点不能取319
instruction[i]=temp+1; //顺序执行一条指令，即执行地址为m+1的指令
temp=rand()%(temp+2); /*在前地址[0,m+1]中随机选取一条指令，该指令的地址为m’*/
instruction[i+1]=temp; //执行地址为m'的指令
instruction[i+2]=temp+1; //顺序执行一条指令，其地址为m’+1
temp=(rand()%(instructionNum-(temp+2)))+(temp+2); /*在后地址[m’+2，319]中随机选取一条指令*/
instruction[i+3]=temp; //执行该指令
}
}
//将指令序列变为页地址流
void instructpage(){
page=(int*)malloc(sizeof(int) * instructionNum);
int n=10;//每一页的指令数
for(int i=0;i<instructionNum;i++){
page[i]= instruction[i]/n;
}
printf("指令序列对应的页面地址流为：\n");//打印输出
for(int i=0;i<instructionNum;i++){
printf(">>%d",page[i]);
}
printf("\n");}
//初始化内存快
void initMemory(int n){//n为传进来的内存块数
blockNum=n;
phyMemory=(int*)malloc(sizeof(int)*blockNum);
for(int i=0;i<blockNum;i++){
phyMemory[i]=-1;
}
}
//寻找空闲内存块
int searchMemory(){
for(int i=0;i<blockNum;i++){
if(phyMemory[i]==-1){
return i;
}
}
return -1;}
//检测需要页面是否已经在内存中
int isExist(int target){//target为需求页面
for(int i=0;i<blockNum;i++){
if(phyMemory[i]==target){
return i;
}
}
return -1;}
//输出页面
void showPage(){
printf("当前所在内存块号：");
for(int i=0;i<blockNum;i++){
if(phyMemory[i]!=-1){
printf("%d ",phyMemory[i]);
}
}
printf("\n\n");}
//释放内存
void delete(){
free(page);
free(phyMemory);
printf("程序运行完毕，内存已释放！\n");}
//先进先出算法FIFO
//选择在内存中驻留时间最久的页面予以替换
void FIFO(){//n为物理快数
count=0;//重置中断次数
int exit;//空闲内存块号
int same=-1;//内存中是否存在需求页面的标志
for(int i=0;i<pageNum;i++){
same=isExist(page[i]);//先判断内存中是否存在该页
//找flag值最大的
for(int j = 0;j<blockNum;j++){
if(flag[j]>maxflag){
maxflag=flag[j];
max=j;
}
}
if(same!=-1){//存在该页
printf("当前请求页号%d已在内存中！\n\n",page[i]);
for(int j=0;j<blockNum;j++){
flag[j]++;
}
}
else{//产生缺页中断
count++;//中断次数加1
exit=searchMemory();//检查内存中有无空闲内存块
if(exit!=-1){//存在空闲物理块
phyMemory[exit]=page[i];
showPage();
flag[exit]=0;
for(int j=0;j<=exit;j++){
flag[j]++;
}
}
else{//无空闲内存块，需要换出调度
printf("当前请求页号%d请求换出页号%d\n",page[i],phyMemory[max]);
phyMemory[max]=page[i];//调换页面
flag[max]=0;
for(int j=0;j<blockNum;j++){
flag[j]++;
}
max=-1;
maxflag=0;
showPage();
}
}
}
FIFOmiss=(count/instructionNum)*100;
printf("FIFO算法缺页率为%f\n",FIFOmiss);}
//最近最久未使用算法LRU
//选择过去最长时间未被访问的页面予以替换
void LRU(){//n为物理快数
count=0;//重置中断次数
int exit;//空闲内存块号
int same=-1;//内存中是否存在需求页面的标志
for(int i=0;i<pageNum;i++){
same=isExist(page[i]);//先判断内存中是否存在该页
//找flag值最大的
for(int j = 0;j<blockNum;j++){
if(flag[j]>maxflag){
maxflag=flag[j];
max=j;
}
}
if(same!=-1){//存在该页
printf("当前请求页号%d已在内存中！\n\n",page[i]);
for(int j=0;j<blockNum;j++){
flag[j]++;
}
flag[same]=0;//该页面刚访问过，flag置0
}
else{//产生缺页中断
count++;//中断次数+1
exit=searchMemory();//检查内存中有无空闲内存块
if(exit!=-1){//存在空闲物理块
phyMemory[exit]=page[i];
showPage();
flag[exit]=0;
for(int j=0;j<=exit;j++){
flag[j]++;
}
}
else{//无空闲内存块，需要换出调度
printf("当前请求页号%d请求换出页号%d\n",page[i],phyMemory[max]);
phyMemory[max]=page[i];//调换页面
flag[max]=0;
for(int j=0;j<blockNum;j++){
flag[j]++;
}
max=-1;
maxflag=0;
showPage();
}
}
}
LRUmiss=(count/instructionNum)*100;
printf("LRU算法缺页率为%f\n",LRUmiss);}
//最佳淘汰算法OPT
//选择过去最长时间未被访问的页面予以替换
void OPT(){
count=0;//重置中断次数
int exit;//空闲内存块号
int same=-1;//内存中是否存在需求页面的标志
int distance[blockNum];//已在内存的页面对下次需要自己时的距离
for(int i=0;i<blockNum;i++){//重置距离
distance[i]=0;
}
for(int i=0;i<pageNum;i++){
same=isExist(page[i]);//先判断内存中是否存在该页
if(same!=-1){//内存中存在该页
printf("当前请求页号%d已在内存中！\n\n",page[i]);
}
else{//产生缺页中断
//每次中断重置distance数组
for(int i=0;i<blockNum;i++){
distance[i]=0;
}
count++;//中断次数+1
exit=searchMemory();//检查内存中有无空闲内存块
if(exit!=-1){//存在空闲块
phyMemory[exit]=page[i];
showPage();
}
else{//无空闲内存块，需换出调度
for(int j=0;j<blockNum;j++){
for(int k=i;k<pageNum;k++){
if(phyMemory[j]!=page[k]){
distance[j]++;
}
else
break;
}
}
int temp=0;
for(int i=0;i<blockNum;i++){
if(distance[i]>=distance[temp])
temp=i;
}
printf("当前请求页号%d换出页号%d\n",page[i],phyMemory[temp]);
phyMemory[temp]=page[i];//调换页面
showPage();
}
}
}
OPTmiss=(count/pageNum)*100;
printf("OPT的缺页率为%f\n",OPTmiss);}
七、实验结果分析（截屏的实验结果，与实验结果对应的实验分析）
指令序列对应的页面地址流：
FIFO算法：
（1）内存块为5：
（2）内存块为19：
LRU算法：
（1）内存块为5：
（2）内存块为19：
OPT算法：
（1）内存块为5：
（2）内存块为19：
通过多次运行测试，可以看出程序可已正确运行FIFO、LRU和OPT算法，其页面调换过程也可以清楚地看到。FIFO算法总是淘汰在内存中停留时间最长的一页，所以可以看到该算法的实用性较差，在只有5页内存块时缺页率高达百分之六十多。LRU算法是将最近最长一段时间内不曾使用的页面替换掉，但是由于在生成的页面走向中很多页面在过去用过在不久的将来又会需要，而这时该页面已经被替换出去了，所以该算法对于这个程序来说也没有表现得很好，和FIFO算法差不多。但是OPT算法相比于前面两个算法要好很多，因为该算法对将来的页面走向事先进行了遍历，并且它能知道内存中哪个页面是最久不被使用的，并且将它替换出去，所以它的缺页率很低。由于在我的程序里面内存块数我是用随机值的，而且该值的范围是4-32，所以存在很多种可能结果。除此之外，程序中还用到了很多全局变量，这些变量始终占用数据段上的空间，一定程度上造成了内存浪费，所以该程序的鲁棒性不佳。这些全局变量在任何地方都可以被更改，程序的安全性也就无法得到保证。
三种算法缺页率分析：
思考题：
1、从几种算法的命中率看，哪个算法最高？哪个算法最低？对每个页面的执行结果进行分析。
从上面的结果来看，可以看到OPT算法的缺页率最低，也就是命中率最高，命中率最低的有可能是FIFO算法，也有可能是LRU算法，两者的命中率都差不多，当内存块数较少时，大多数情况下是LRU算法比FIFO算法好一点，但是当内存块数逐渐增加时候，两者之间的差距开始逐渐增大，很少出现FIFO算法缺页率比LRU算法低的情况，所以总体来说LRU算法比FIFO算法要好。而OPT算法因为是对将来的页面进行了访问，已经预知了将来的页面走向，所以其良好性是不言而喻的，从数据中也可以看得出来，OPT算法比FIFO算法和LRU算法要好很多，但是随着内存块数的增加，其缺页率最终也只是稳定在10%左右。三者的唯一特性是命中率都随着内存块数的增加而增加，书本中介绍到FIFO页面置换算法存在Belady异常现象，也即缺页率随着内存块增加而增加，但是在我程序中并没有体现出来。因为导致Belady异常现象的页面走向实际上是很罕见的，即使我程序使用了随机生成的页面走向也没看到这种现象。
2、OPT算法在执行过程中可能会发生错误，为什么？
因为OPT最佳置换算法是选择将来不被使用，或者是在最远的将来才被访问，我的程序中因为是确定好的页面走向，所以可以对其进行预测。但是在实际中计算机要预先知道一个进程在整个运行过程中页面走向的全部情况是很困难的，所以OPT算法在执行过程中很难实现。
