第一篇：页面替换算法实验报告
操作系统页面替换算法实验报告
姓名： 沈慧 班级： 计091 学号： 0913022006
页面替换算法
一．目的和要求
（一）目的
存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。
本实验的目的是通过请求页式管理中页面置换算法的模拟设计，来了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。
（二）要求
模拟页式虚拟存储管理中硬件的地址转换和缺页中断，并用最佳页面替换算法（OPT）、最近最少使用页面替换算法（LRU）、先进先出调度算法（FIFO）处理缺页中断。
二、算法描述
1．先进先出(FIFO)置换算法的思路
该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序连接成一个队列，并设置一个替换指针，使它总指向最老的页面。
2．最近久未使用(LRU)置换算法的思路
最近久未使用置换算法的替换规则，是根据页面调入内存后的使用情况来进行决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进 行淘汰。
3.最佳（OPT）置换算法的思路
其所选择的被淘汰的页面，奖是以后不使用的，或者是在未来时间内不再被访问的页面，采用最佳算法，通常可保证获得最低的缺页率。
三、方案设计
1、数据结构 class RAMPAGE { protected: int *RAM;//内存各块，存放各页
int ramcount;//内存块数
int *PAGE;//接收用户要访问的各页
int pagecount;//页数
int *CHANGEPAGE;//存放淘汰的各页 int maxpage;//页的最大页号
int shortage;//缺页的数量 public: RAMPAGE();//初始化
void input();//用户输入
void FIFO();//FIFO算法 void LRU();//LRU算法 void OPT();//OPT算法
~RAMPAGE();//释放空间
};
三、测试与运行
1、输入要测试的数据
2、采用FIFO方法进行页面置换
3、采用LRU算法进行页面置换
4、采用OPT算法进行页面置换
源程序代码：
#include
int *PAGE;//接收用户要访问的各页
int pagecount;//页数
int *CHANGEPAGE;//存放淘汰的各页 int maxpage;//页的最大页号
int shortage;//缺页的数量 public: RAMPAGE();//初始化
void input();//用户输入
void FIFO();//FIFO算法 void LRU();//LRU算法 void OPT();//OPT算法
~RAMPAGE();//释放空间 };RAMPAGE::RAMPAGE(){ ramcount=0;//内存块数
pagecount=0;//页数
maxpage=0;//页的最大页号 } void RAMPAGE::input()//用户输入 { cout<<“请输入内存块数：”;cin>>ramcount;//用户输入块数
RAM=new int [ramcount];//内存各块，存放各页 cout<<“请输入给定的页面：以#结尾”<
PAGE2[i]=page;//该页进入预分配空间
if(page>maxpage)maxpage=page;//找出最大页 i++;} pagecount=i;//记录用户输入的页数 CHANGEPAGE=new int[pagecount];PAGE=new int[pagecount];//接收用户要访问的各页
for(i=0;i
} delete [] PAGE2;//释放预申请空间 }
void RAMPAGE::FIFO(){ cout<<“使用FIFO算法：”<
cout<<“内存各块存储变化：”< } if(in==0)//页不在内存块 { shortage++; if(RAM[ramcount-1]!=-1)//最后一个内存块标记为-1，表示它未被写入过页号 { CHANGEPAGE[k]=RAM[l];//!-1,则要进行淘汰，记录要被淘汰的页号 k++; } RAM[l]=PAGE[i];//新页写入块，将该块初次写入 l++; if(l==ramcount)l=0;} } for(j=0;j {cout< cout<<“缺页次数：”< cout< } void RAMPAGE::LRU(){ cout<<“使用LRU算法：”< int i=0;for(i=0;i if(PAGE[i]==RAM[j]) { in=1; break; } } if(in==0&&RAM[ramcount-1]!=-1){ shortage++; for(j=0;j RAM2[j]=0; for(j=0;j { for(p=i-1;p>=0;p--) { RAM2[j]++;//RAM2[]存储当前内存中各页的权值（距该页上次被访问待了多长时间） if(RAM[j]==PAGE[p])break; } } int max=0;for(j=0;j { if(RAM2[j]>max) max=RAM2[j];//max标记最大的权值 } for(j=0;j { if(max==RAM2[j])break;//定位max对应的最大权值页号的存储块号 } CHANGEPAGE[k]=RAM[j];//将该块中的页号放入淘汰序列 RAM[j]=PAGE[i];//要访问的页写入内存块好 k++;// 淘汰数加1 } if(in==0&&RAM[ramcount-1]==-1){ shortage++; RAM[l]=PAGE[i]; l++;} } for(j=0;j cout<<“缺页次数：”< for(int m=0;m void RAMPAGE::OPT(){ cout<<“使用OPT算法：”< int i=0;for(i=0;i in=0;for(j=0;j if(PAGE[i]==RAM[j]) { in=1; break; } } if(in==0&&RAM[ramcount-1]!=-1){ shortage++; for(j=0;j RAM2[j]=0; for(j=0;j { for(p=i+1;p { RAM2[j]++;//RAM2[]存储当前内存中各页的权值（距该页下次被访问要待多长时间） if(RAM[j]==PAGE[p])break; } } int max=0;for(j=0;j { if(RAM2[j]>max) max=RAM2[j]; } for(j=0;j { if(max==RAM2[j])break; } CHANGEPAGE[k]=RAM[j]; RAM[j]=PAGE[i]; k++; } if(in==0&&RAM[ramcount-1]==-1){ shortage++; RAM[l]=PAGE[i]; l++;} } for(j=0;j cout<<“缺页次数：”< for(int m=0;m delete []PAGE;//释放访问各页空间 delete []CHANGEPAGE;//释放淘汰页空间 } int main(){ 率： RAMPAGE *task; again: cout<<“说明：”< cout<<“输入 1 or 2 or 3选择算法:”;int number;cin>>number;switch(number){ case 1: task->FIFO();break;case 2: task->LRU();break;case 3: task->OPT();break;default : cout<<“选择出错!”< cout<<“继续其他算法(1 or 2 or 3)，0 跳过：”;cin>>number;switch(number){ case 1: task->FIFO();break;case 2: task->LRU();break;case 3: task->OPT();break;default : cout<<“跳过算法!”< cout<<“***************************************************************”< cout<<“继续其他算法(1 or 2 or 3)，0 跳过：”;cin>>number;switch(number){ case 1: task->FIFO();break;case 2: task->LRU();break;case 3: task->OPT();break; default : cout<<“跳过算法!”< cout<<“***************************************************************”< delete task;cout<<“结束程序/继续新任务?(y / n): ”;char goon;cin>>goon;if(goon=='y'){ system(“CLS”); goto again;} return 0;} 《操作系统--页面置换算法》 实验报告 姓 名： 范学升 学 号：1001050903 班 级：电科10-1班 专 业：电子信息科学与技术 一、实验目的 1．通过模拟实现几种基本页面置换的算法，了解虚拟存储技术的特点。 2．掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想，并至少用三种算法来模拟实现。 3．通过对几种置换算法页面的比较，来对比他们的优缺点，并通过比较更换频率来对比它们的效率。 二、实验内容： 设计一个虚拟存储区和内存工作区，并使用下述算法来模拟实现页面的置换： 1.先进先出的算法（FIFO）2.最近最久未使用算法（LRU）3.最佳置换算法（OPT） 三、实验分析 在进程运行过程中，若其所访问的页面不存在内存而需要把它们调入内存，但内存已无空闲时，为了保证该进程能够正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应调出哪个页面，需根据一定的算法来确定，算法的好坏，直接影响到系统的性能。 一个好的页面置换算法，应该有较低的页面更换频率。 假设分给一作业的物理块数为3，页面数为20个。页面号为(20个)： 7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 1．先进先出(FIFO)置换算法的思路 该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序连接成一个队列，并设置一个替换指针，使它总指向最老的页面。 2．最近久未使用(LRU)置换算法的思路 最近久未使用置换算法的替换规则，是根据页面调入内存后的使用情况来进行决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进 行淘汰。 3.最佳（OPT）置换算法的思路 其所选择的被淘汰的页面，奖是以后不使用的，或者是在未来时间内不再被访问的页面，采用最佳算法，通常可保证获得最低的缺页率。 4．数据结构 struct pageInfor { int content;//页面号 int timer;//被访问标记 }; class PRA { public: PRA(void);int findSpace(void);//查找是否有空闲内存 int findExist(int curpage);//查找内存中是否有该页面 int findReplace(void);//查找应予置换的页面 void display(void);//显示 void FIFO(void);//FIFO算法 void LRU(void);//LRU算法 void BlockClear(void);//BLOCK清空，以便用另一种方法重新演示 pageInfor * block;//物理块 pageInfor * page;//页面号串 private: }; 5．FIFO页面置换算法 当需要访问一个新的页面时，首先调用findExist(i)函数来查看物理块中是否就有这个页面，若要查看的页面物理块中就有，则调用display函数直接显示，不需要替换页面；如果要查看的页面物理块中没有，就需要寻找空闲物理块放入，若存在有空闲物理块，则将页面放入；若没有空闲物理块，则调用findReplace函数替换页面。并将物理块中所有页面timer++。 6．LRU页面置换算法 当需要访问一个新的页面，首先调用findExist(i)函数查看物理块中是否就有这个页面。 7.OPT页面置换算法 当需要访问一个新的页面，首先调用findExist(i)函数来查看物理块中是否有这个页面。 8．寻找置换页面函数findReplace比较三个物理块中的时间标记timer，找到时间最久的。 四、源程序结构分析 1． 程序结构 程序共有以下九个部分： int findSpace(void);//查找是否有空闲内存 int findExist(int curpage);//查找内存中是否有该页面 int findReplace(void);//查找应予置换的页面 void display(void);//显示 void FIFO(void);//FIFO算法 void LRU(void);//LRU算法 void OPT(void);//OPT算法； void BlockClear(void);//BLOCK清空，以便用另一种方法重新演示 int main() //主程序 五、实验结果 1运行后的初始界面 opt算法 3.FIFO算法 4LRU算法 计算机体系结构 实验报告 班级：计科姓名：张华敏学号： 0902班 0909090814 FIFU算法 一，实验内容： 编写一段程序来模拟页面置换算法中的FIFU算法的实现 二，算法设计： 设置一个产生随机数的函数rand()产生随机数来模拟程序所需访问的页面的标号，如果页面需要被访问则把页面中的一个标志位设为in表示他已经被调入内存，如果再次需要访问此页面是只需检查此页面的标志位是否为in就可判断它是否已经存在在内存中了，如果已经存在则可直接使用，如果不存在则需调入，在调入新页面是先检查内存空间是否已满，如果未满则直接调入，如果已经满了则需选择一个页面将其调出，调出时就把页面的标志位设为out。选择页面的规则是：将进入内存时间最久的页面调出去，为了达到这一目的，在页面中设置一个计数器，每当有新页面调入内存时则将内存中已经存在的页面计数器自动加一，调出页面时就选择那个计数器最大值的页面，调出后重新将计数器设为零。三，遇到的问题及解决方案： 在做此实验时遇到了一些小问题,如在C语言中函数名定义为export()则会报错。在调用有返回值的函数是如果直接int s=use(pag)则会运行出错,要先分开写如：int s,s=use(pag).四，源代码 头文件.cpp #include int t;//全局变量，用来盛放rand()函数产生的随机数 enum boolean{in,out};//定义一个枚举类型 /////////如果把in，out换成 true,false则会处错误 typedef struct { int num;//页面编号 char content;//页面内容 enum boolean flog;//判断此页面是否页调入，调入为true,否则为false;int count;//页面计数器 int usebit;//使用位，被使用过值为1，否则为0 }page; FIFU.cpp #include int capacity=3;//设置内存最多可以容纳的页面数 void initialize(page p[])//初始化页面函数 { for(int i=0;i<5;i++)//初始化页面，页面内容分别为小写字母 abcde,计数器全部为0 {p[i].num=i;p[i].content=i+97;p[i].flog=out;p[i].count=0;} } int use(page p[]){ t=rand()%5;//产生一个0-5的随机数，if(p[t].flog==in){ printf(“tt%d页面命中n”,t);//for(int i=0;i<5;i++)//调入此页面后其他以在内存中存在的页面计数器加1 // { // if(p[i].flog==in)// p[i].count++;// } return(1);} else return(0);} void import(page p[])//调入页面的函数 { /* int t=rand()%5;//产生一个0-5的随机数，if(p[t].flog==in)printf(“tt%d页面命中n”,t);*/ // if(p[t].flog==out)//如果此页面未被调入内存则立即调入 p[t].flog=in;capacity--;//调入后内存空间减少一叶 for(int i=0;i<5;i++)//调入此页面后其他以在内存中存在的页面计数器加1 { if(p[i].flog==in&&p[i].num!=t)p[i].count++;} printf(“页面%d被调入内存n”,t);} void port(page p[])//调出页面的函数，，，，，，，，，，，如果函数名定义为export则处错误 { int x=0,y;//x用来暂时存放计数器 中的最大值，y存放此页面的页面号 for(int i=0;i<5;i++)//寻找计数器值最大的 页面 { if(p[i].count>x){ x=p[i].count;y=i;} } p[y].flog=out;//修改调入符号 p[y].count=0;capacity++;//调入后内存空间增加一叶 printf(“ttt页面%d被调出内存n”,y);} main(){ int s;long t3,t1,t2;page pag[5];//定义五个页面，，，，，，，，，，，如果这个定义在子函数之前那么不用通过参数 子函数便可以直接访问 t3=time(NULL);initialize(pag);do { t1=time(NULL);s=use(pag);//，，，，，，，，，，，，，，如果这里写成int s=use(pag)则会运行出错 //printf(“s=%d capacity=%dn”,s,capacity);if(capacity>0&&s==0)import(pag);else { if(capacity==0&&s==0){ port(pag);import(pag);} } t2=time(NULL);while(t2-t1<1){ t2=time(NULL);} }while(t2-t3<20);system(“pause”);} 五，测试结果： LFU算法 一,实验内容： 编写一段程序来模拟页面置换算法中的LFU算法的实现 二,算法设计： 设置一个产生随机数的函数rand()产生随机数来模拟程序所需访问的页面的标号，如果页面需要被访问则把页面中的一个标志位设为in表示他已经被调入内存，如果再次需要访问此页面是只需检查此页面的标志位是否为in就可判断它是否已经存在在内存中了，如果已经存在则可直接使用，如果不存在则需调入，在调入新页面是先检查内存空间是否已满，如果未满则直接调入，如果已经满了则需选择一个页面将其调出，调出时就把页面的标志位设为out。选择页面的规则是：将最近一段时间未被访问过的页面调出。为了达到这一目的在页面中设置一个标志位，如果页面在近期只要被访问过则将该标志位设置为1（默认为0），在选择调出页面时只需将标志位为0的页面调出即可。三,遇到的问题及解决方案： 未遇到什么问题 四,实验感悟： 遇到问题后上网查资料和有效,及时查不到自己想要的但是也可从相关结果中获得启发给自己灵感来想到解决问题的方法.四，源代码 FLU.cpp #include int capacity=3; //设置内存最多可以容纳的页面数 void initialize(page p[]) //初始化页面函数 { for(int i=0;i<5;i++) //初始化页面，页面内容分别为小写字母 abcde,计数器全部为0 {p[i].num=i; p[i].content=i+97; p[i].flog=out; p[i].count=0; p[i].usebit=0; } } int use(page p[]){ t=rand()%5; //产生一个0-5的随机数，if(p[t].flog==in) { printf(“tt%d页面命中n”,t); p[t].usebit=1; //for(int i=0;i<5;i++)//调入此页面后其他以在内存中存在的页面计数器加1 // { // if(p[i].flog==in) // p[i].count++; // } return(1); } else return(0); } void import(page p[])//调入页面的函数 { int t=rand()%5; //产生一个0-5的随机数，//if(p[t].flog==in) // { // printf(“tt%d页面命中n”,t); // p[t].usebit=1; // } // if(p[t].flog==out) //如果此页面未被调入内存则立即调入 p[t].flog=in; capacity--; //调入后内存空间减少一叶 for(int i=0;i<5;i++)//调入此页面后其他以在内存中存在的页面计数器加1 { if(p[i].flog==in&&p[i].num!=t) p[i].count++; } printf(“页面%d被调入内存n”,t); } void port(page p[]) //调出页面的函数 ////////////////////////////////如果函数名定义为export则处错误 { int x=0,y;//x用来暂时存放计数器 中的最大值，y存放此页面的页面号 int z=-1; //用来判断近期是否有未被访问过的页面 int g=0; for(int i=0;i<5;i++)//寻找计数器值最大的 页面 { if(p[i].count>x) { x=p[i].count; y=i; } } for(int i=0;i<5;i++) { if(p[i].flog==in&&p[i].usebit==0) { z=i; g++; } } if(z==-1||g==3)//如果所有页面均为1则按照FIFO算法置换页面 //如果g=3则表明页面使用位全为零，此时也按照FIFO算法置换页面 { p[y].flog=out;//修改调入符号 p[y].count=0; capacity++; //调入后内存空间增加一叶 p[y].usebit=0; for(int i=0;i<5;i++)//将所有页面置0 p[i].usebit=0; printf(“ttt页面%d被调出内存n”,y); } else //如果有页面为0则将此页面置换出来 { p[z].flog=out;//修改调入符号 p[z].count=0; capacity++; //调入后内存空间增加一叶 printf(“ttt页面%d被调出内存n”,z); } } main(){ int s; long t3,t1,t2; page pag[5];//定义五个页面 ///////////////////如果这个定义在子函数之前那么不用通过参数 子函数便可以直接访问 t3=time(NULL); initialize(pag); do { t1=time(NULL); s=use(pag); if(capacity>0&&s==0) import(pag); else { if(capacity==0&&s==0) { port(pag); import(pag); } } t2=time(NULL); while(t2-t1<1) { t2=time(NULL); } }while(t2-t3<20); system(“pause”);} 六,实验结果 总结 通过本次试验我对各种页面置换算法有了更深入的了解,也使得自己认识到平常学习到某些东西觉得懂了会了可是一旦实际动手操作起来就会发现总会存在这样或者那样的错误，只有多动手实际操作才会发现不足发现错误并且改正。查漏补缺提高自己的实际动手能力。 软 件 学 院 上 机 实 验 报 告 课程名称： 操作系统原理 实验项目： 虚拟内存页面置换算法 实 验 室： 地狱 018 姓 名 : 死神 学 号： 专业班级 : 实验时间： 2015/12 ／ 13 实验成绩 评阅教师 一、 实验目得及要求 通过这次实验，加深对虚拟内存页面置换概念得理解,进一步掌握先进先出 FIFＯ、最佳置换ＯPI 与最近最久未使用ＬRU 页面置换算法得实现方法。结合 Lｉｎux 得内层得分析方法查瞧内存得分配过程及 linuｘ keｒnel 得内存管理机制 二、实验性质 设计性 三、实验学时 学时 四、实验环境 实验环境１、实验环境： C 与Ｃ++程序设计学习与实验系统 2、知识准备:（１）使用 Linuｘ得基本命令；(2）了解 Liｎｕx vｍｓtat、freｅ、toｐ等命令查瞧ｌinuｘ系统得内存分配情况；（3） 掌握虚拟内存页面置换算法 FＩＦO 等基本算法理论。 五、 实验内容及步骤 假设有ｎ个进程分别在 T1, … ,Ｔｎ时刻到达系统，它们需要得服务时间分别为S1，… ,Sｎ。分别采用先来先服务 FCＦS 与短作业优先 SJF 进程调度算法进行调度，计算每个进程得完成时间、周转时间与带权周转时间,并且统计 n 个进程得平均周转时间与平均带权周转时间。 步骤 通过已知最小物理块数、页面个数、页面访问序列、及采用置换方式可以得出页面置换得缺页次数与缺页率，及每次缺页时物理块中存储。 １．输入得形式 ﻩinｔ PagｅOrder［MａxNumbｅr]；//页面序列 ｉｎt ＰaｇeNｕm，LacｋNum=０,BlockNｕｍ;／／页面个数，缺页次数,最小物理块数 2、输出得形式 doubｌe LackPaｇｅRａte／/缺页率 缺页个数 每次缺页时物理块中存储 程序所能达到得功能 模拟先进先出 FＩFO、最佳置换 OPＩ与最近最久未使用 LRＵ页面置换算法得工作过程.假设内存中分配给每个进程得最小物理块数为ｍ，在进程运行过程中要访问得页面个数为 n，页面访问序列为Ｐ1, …，Ｐn,分别利用不同得页面置换算法调度进程得页面访问序列，给出页面访问序列得置换过程，计算每种算法缺页次数与缺页率。测试数据,包括正确得输入及其输出结果与含有错误得输入及其输出结果。 程序中用到得所有抽象数据类型得定义、主程序得流程以及各程序模块之间得层次（调用)关系.inｔ PagｅOrdeｒ[MaxNumｂer］;//页面序列 int ＰａgeCoｕnt[MaxＮｕmｂer]={0｝；//计算内存内数据离下一次出现得距离 int PａｇeNum,LackNuｍ＝0，ＢｌｏcｋNum;//页面个数,缺页次数,最小物理块数 douｂｌｅ LaｃkPａｇeRaｔe＝0； bool ｆｏｕnd＝ｆａlsｅ; 六、实验数据及结果分析 运行截图： 图６、1 图６、2 图６、3 七、实验总结 这次试验,让我加深了对虚拟内存页面置换算法得理解，进一步掌握先进先出 FIFO、最佳置换 OＰI 与最近最久未使用 LＲU 页面置换算法得实现方法。熟悉 Linuｘ需要经过大量得实验、改进与思考，在编写代码得过程中遇到了一些问题要积极面对并通过讨论上网或者问老师解决。通过这次试验我了解了虚拟内存置换算法得一些知识,就是我对于所学习得专业知识得到了更好得巩固与提升。 附录 源程序清单 ＃iｎclude ＜iｏｓｔｒeam> using namespace ｓｔｄ;#ｄｅｆinｅ ＭａxNumbｅr 100 void OＰI（int PａgeOｒdｅｒ[MaxNuｍber］,iｎt PａｇeCoｕnt［MａxＮumber]，ﻩ int PagｅＮｕm,ｉnｔ LackNum，int ＢlockNum，double LacｋＰａgｅＲate,bｏol ｆound） { ｉnt moｄｕle［MaxNumber]； iｎt sｕm＝0； int i，j，k,ｍ; fｏr(i=0;i ｛ moduｌe［ｉ］=ＰaｇeＯｒder[i］； ;＋＋ｍuｓﻩﻩ)++ｊ；i＝ cｏuｔ<〈module[j］<〈” ＂; ；ldne<〈tｕocﻩ ｝ LackNuｍ=ＢｌoｃkNum； foｒ(i=BlockNuｍ；i〈ＰageNum；i+＋） ｛ foｕnd=false; fｏr（j=0;ｊ<ＢlockＮｕｍ；j＋+）//遍历已存储,判断就是否缺页 ｛ ﻩ ﻩﻩ ｉf（module[ｊ]==ＰａgｅOrder［ｉ］) { ﻩﻩ foｕnd=true; ﻩ ﻩ breaｋ; ﻩ ｝ ﻩﻩ ｝ ﻩ if（found==faｌse)//缺页,选择替换 { ﻩ ｆor（j＝０；ｊ〈ＢlockＮｕm；j+＋） /／计算内存内数据离下一次出现得距离 ｛ PａgｅCｏｕnt［ｊ]=０; ｆoｒ(k=i＋１；k ｛ ﻩﻩﻩ ﻩ ﻩ iｆ（module[j］!＝PageＯｒder[k]) ﻩﻩ PageCｏunt［j]++； ﻩ esleﻩ ；kaｅrｂﻩ ｝ ﻩ } ;］０[tｎuｏCegaP=xａm ｔnｉﻩ iｎt kｉnｄ=0； 值大最出找/／）+＋j;muNkcolB〈j；0=j（rofﻩ { ﻩ if（PａｇeＣoｕｎｔ[j］>ｍax） ﻩ ｛ ﻩﻩ ；]j[tnuoＣｅgaP＝xamﻩﻩ ﻩ ﻩ kiｎｄ＝j； ﻩ ｝ ﻩ ｝ module［kiｎd］=PａgｅOrder［i]； ﻩ LackNum++；）++ｍ;3 ；” ”＜<］ｍ［elｕdom<〈tuocﻩﻩ ﻩ；lｄｎｅ＜ ﻩ ｝ LａｃkPａgeRate＝（LackＮuｍ＊1、0)／PageNum； cｏut〈〈“该算法缺页次数为：＂＜〈LackNum<＜eｎdｌ； coｕt＜<”该算法缺页率为：＂〈＜LackPａｇｅRａte*100＜〈＇％”〈〈enｄl;｝ /＊＊＊＊＊＊*＊**＊＊***＊*＊＊**＊＊***＊***先进先出置换算法＊＊*＊*＊*＊＊＊＊**＊*＊＊＊＊＊＊*＊＊＊＊**＊＊*＊＊*＊*＊/ vｏid FIFO(int PagｅOrｄeｒ[MａxNｕmber],int PａｇｅCounｔ［ＭaｘNuｍber］，egaPkｃaＬ eｌbuod ,muNkcolB ｔni，mｕNｋcaL tni，muNｅｇａP tniﻩＲate，booｌ ｆound)｛ int module[ＭａxNumber］; iｎt sum=0； int ｉ，j，ｍ; for(ｉ=0;ｉ〈BlocｋＮum；ｉ+＋）//将内存填满 { modｕlｅ［ｉ］＝PageOrｄeｒ［ｉ］； ；++musﻩﻩ PagｅCoｕnt[i]=３-i;）++j；ｉ=＜ｊ；0=ｊ（roｆﻩ couｔ<<ｍｏdule[j]<<＂ “； ｃout<＜enｄl; } LackNuｍ=BlockNum； foｒ（i＝BlocｋNｕm；i〈PａgeＮuｍ;i++） ｛ fouｎｄ=fａlse； ｆor（ｊ=0；j〈ＢlockNuｍ;j++)/／遍历已存储，判断就是否缺页 { ﻩ ｉf(module［j]==ＰａgeOrder[i］) ﻩ { ﻩ ；eurt=dｎuofﻩﻩ ﻩ breａk; } } if（found==falｓｅ)//缺页，选择替换 ｛ ﻩ ；]0［tnuoCｅgaＰ＝xam ｔｎiﻩ ｉnｔ ｋind=０； 值大最出找//）＋+ｊ;muNkcolB〈ｊ；０=j（rｏfﻩ ｛ ﻩ ｉf(PａgeCoｕnt［j]＞max） ｛ ;］ｊ[tnuoCegａP=xａmﻩﻩ ﻩﻩ kiｎd=j； ｝ ﻩﻩﻩ } ﻩ foｒ(inｔ k＝0;k＜BlocｋＮuｍ；ｋ++）／/不就是最大值，则要+1 ﻩ { ﻩ ﻩ ｉf（k！=kind) PagｅCｏunt［k]++； ﻩ ｝ ﻩ moｄuｌe［kｉｎd］=PageOｒder［i］； PageＣouｎt［kiｎd]=０；// 替换之后已经查询得次数改为0 LackNum++; ﻩ ｆor（m=０； m〈3；m++） ﻩ ;” ”<〈］m[eludｏm〈 ;ldne〈〈ｔuocﻩﻩ ｝ ﻩ ｝ ﻩ LａｃkPageＲate=（ＬackNｕm*１、0）/ＰagｅNuｍ； cout〈〈“该算法缺页次数为：”<＜LackNuｍ< cｏuｔ＜<”该算法缺页率为:＂< PaｇeＯrdｅr[MaxＮumbｅｒ]，int PａｇeCoｕnｔ［ＭaxNumｂｅr］，ｅｇaPｋcａL elｂuod，muＮkｃｏlB tni,mｕNkcaL tni,muNegaＰ tniﻩﻩＲate,bool found){ int moｄuｌe[MａxNuｍｂer］； inｔ sum＝0; int i，j,m; for（ｉ=0；i＜BｌockNum；i＋+)//将内存填满 { moduｌe[ｉ]=PaｇeOｒdeｒ[i]; ﻩ sｕm++； ＰageCouｎt［i］=3—i；)＋+ｊ；i=＜j；0=j(roｆﻩ cout〈〈mｏdule[j]〈〈” ”; ;ldne〈<ｔuocﻩﻩ ｝ LａckＮum＝ＢｌockＮuｍ; foｒ(ｉ=ＢlｏｃｋＮｕm；ｉ ｛ ｆouｎd=ｆaｌse; fｏｒ（j=０；j＜BlockNum；j++)/／遍历已存储,判断就是否缺页 { ﻩ if(module［j]==PageOｒder［i］） ﻩﻩ ｛ ﻩ fｏund=truｅ； ＰagｅCｏuｎt［ｊ]=０；//查询后，更改次数 ﻩﻩ ｆor（iｎｔ k=0;k〈BlockＮuｍ；k++） ﻩ { ﻩﻩ ﻩﻩ）j=！k（fiﻩﻩ ＰａgeCｏuｎｔ[ｋ］+＋； ﻩ } ﻩ bｒｅａｋ; ﻩ ｝ ﻩ } ﻩ if(ｆounｄ＝=falsｅ）／／缺页,选择替换 ｛ ﻩ ；］０[tnuoCegａP=ｘam tniﻩﻩ iｎt kind=0； 值大最出找／/）＋＋j；mｕNkcｏｌB ﻩﻩ)xaｍ〉]j［tnuoＣｅgaP（ｆｉﻩﻩ { ﻩ ﻩ;]j[tnuoCegａP=xamﻩ ﻩﻩ kiｎd=ｊ; ｝ ﻩ ｝ ﻩﻩ for（int k=0；k ｛ ﻩ ｉf(k！=ｋind） PagｅCounｔ［ｋ]+＋； ﻩﻩ ｝ ﻩ mｏdule[kind]＝PageOrder［i］; PageCoｕnt[ｋiｎｄ]＝0；// 替换之后未查询得次数改为0 ;++ｍｕNkcaLﻩﻩ for（m＝0； ｍ<3;ｍ++） ﻩ coｕt〈 ”； ﻩ;ldne<〈ｔｕｏcﻩ ｝ ﻩ } ﻩ LackPagｅRate=(LackＮｕm*1、0)/PaｇeNｕm; ｃoｕｔ<〈“该算法缺页次数为:＂＜ couｔ〈＜”该算法缺页率为：”〈＜LackPａgeRate＊100〈＜“%’＜＜ｅｎdl;} int main（） { iｎt PageＯｒｄer［MaｘNumｂer]；//页面序列 inｔ PaｇeCoｕnt[ＭａxＮumｂｅｒ]＝｛0｝;/／计算内存内数据离下一次出现得距离 inｔ PagｅＮum，ＬackNuｍ＝0，BlocｋNum;//页面个数,缺页次数，最小物理块数 ;0=etaＲegaPkcａL eｌｂuoｄﻩ bool foｕｎd=false; ;3ecoｉhc,2eｃoihc,０=１ecoiｈc tniﻩ ｉnt i=０；）０==1ecoihc（eliｈｗﻩ ｛ ；”:入输新重:１,入输不:0；据数入输新重否是就“〈〈tｕocﻩ cｉｎ〉>chioｃe2； if（ｃhｉoｃｅ2==１） ｛ﻩ couｔ<＜”请输入页面个数:”； ;muNegａＰ >>nicﻩ;“数块理物小最入输请”〈〈tuoｃﻩ ；muNｋcolB>>niｃﻩ cｏut<〈”请输入页面序列：”< for（i=０;ｉ〈ＰaｇｅNｕｍ；i++） ;]ｉ[ｒedrOegａP>〉nicﻩ ｝ﻩ;”：ＵRL-3，IＰO—2，ＯFIF-1：法算择选请＂< iｆ（chiocｅ3==1) ｃｏlB，muNkcaL,muNeｇaP，tnuoCｅgａP,reｄｒＯｅgaＰ(OＦIＦﻩkNｕm，LackPageRａte，founｄ); eｌse ｛ ｉｆ（chioｃe3==2） ｃｏｌB ,muNkcaＬ，muＮｅgａP,tnuｏＣｅｇaＰ，ｒedｒOegaP（IPOﻩｋNum，LaｃkＰageRａｔe, fｏｕnd)； esｌeﻩ ，ｍｕNkcolB ,muＮｋcaL，mｕＮegaP，tｎuoCegａP,redrOｅgａP(UＲＬﻩLackPaｇｅRａｔe，ｆound）; ｝ ＊＊＊***＊＊*＊*＊****＊＊****＊＊*＊＊＊*＊*＊＊＊**＊“〈＜tｕｏcﻩ******＊*＊***＊＊***＊＊*＊＊*＊＊***”<＜endｌ； ;＂束结：１，续继:0:束结是就还续继择选请"＜ ｝ ｝ 中北大学软件学院 实 验 报 告 专 业 软件工程 课程名称 计算机操作系统 学 号 姓 名 辅导教师 张 静 成绩 实验日期 2015、１1、20 实验时间实验名称 :实验四 页面置换算法模拟 ２、实验目得(１）了解内存分页管理策略（2）掌握调页策略(3）掌握一般常用得调度算法（4）学会各种存储分配算法得实现方法。 （5）了解页面大小与内存实际容量对命中率得影响。 3、实验要求 编程实现页面置换算法，最少实现两种算法，比较算法得优劣,并将调试结果显示在计算机屏幕上，并检测机算与笔算得一致性。 （1）采用页式分配存储方案，通过分别计算不同算法得命中率来比较算法得优劣，同时也考虑页面大小及内存实际容量对命中率得影响;（2）实现 OＰT 算法(最优置换算法)、ＬRU 算法(Lｅast Recｅｎtly）、FIFO 算法（Fｉrst IN Firｓｔ Out）得模拟;（3)使用某种编程语言模拟页面置换算法.4、实验算法描述 （1）ＦIFO（先进先出） Y Ｎ N Y 开始 页面走向存入数组 p[]中,内存块用page[]表示初始化为 0 当前p[]中第i个元素就是否已在内Page[]就是否有空把 page[]中最先装入得页面置换出去、i++ 把 p[i]得内容直接装入最上面一个空内存块,i++ 输出当前内存块状态 i++ 图 4－1FIFＯ算法流程图 结束 (2） LＲU（最近最久未使用） Y N Y Ｎ 图 4—2 LＲU 算法流程图 开始 页面走向存入数组 p[]中,内存块用 page[]表示初始化为 0 当前 p[]中第 i 个元素就是否已在内存 Page[]就是否有空把 page[]中最近最久未使用得页面置换出去、i++ 把 p[i]得内容直接装入最上面一个空内存块,i++ 输出当前内存块状态 结束 i++ (3）OＰＴ（最佳置换算法） Y N Y Ｎ 图４－3 ＯPT 流程图 开始 页面走向存入数组 p[]中,内存块用 page[]表示初始化为 0 当前 p[]中第 i 个元素就是否已在内存 Page[]就是否有空把 page[]中以后一段时间都不使用或就是使用时间离现在最远得换出、i++ 把 p[i]得内容直接装入最上面一个空内存块,i++ 输出当前内存块状态 结束 i++ 6、实验代码 ＃iｎcｌuｄe ＜iostreａm〉 usiｎｇ ｎａmespace sｔｄ;#defiｎe Bｓｉzｅ ３ #dｅfine Psｉｚe 20 ｓｔruct ｐaｇｅInｆor ｛ 号面页// ;ｔneｔｎoc tniﻩ int tｉmer; //被访问标记 ｝;ｃlasｓ ＰＲA{ ｐuｂｌiｃ： PRA(ｖoid）； 存内闲空有否是就找查/／ ;)diov（eｃaｐSdnif tniﻩ iｎt ｆindExist（int curpage）; ／／查找内存中就是否有该页面 int findReplacｅ（vｏid）; //查找应予置换得页面 void ｄisplay(void）; //显示 法算 OＦIF//;）dioｖ（OFIＦ ｄiovﻩ 法算 UＲL／/；)dｉov(URL diovﻩ vｏid Ｏptimａl(ｖoid);／／ＯPTIＭAL 算法 ｖoｉd BlockＣlear（voiｄ)；/／ＢLOCK 恢复 pageＩｎfor ＊ ｂlｏck；//物理块 pageInfoｒ ＊ page；／／页面号串 privaｔe: };PＲA：：PＲＡ(vｏid）{ ｉnt QStriｎg［２0］=｛7，0，1，２,0，3,0，4,２，3,0,3,２,1，2，0，1,7,0,１}; block = ｎew paｇeIｎfor[Bｓizｅ］;)++i;ｅzisB＜ｉ;0＝i ｔnｉ(rofﻩ { ;1— = tnｅtnｏc、］ｉ［ｋcolbﻩ ；0 ＝ remｉt、]ｉ［kcolbﻩﻩ } page = ｎew pageInfｏｒ［Psｉze];）＋+ｉ;eｚiｓP〈i ；０=i（ｒofﻩ { ；]i[gｎiｒtSQ = tｎetnoｃ、］i[egａpﻩ;0 = rｅmit、]i[eｇａｐﻩﻩ }ﻩ} iｎt ＰRA：：fｉndSpace（voiｄ） { for（iｎt i=0； i if(bｌocｋ[i]、cｏntent =＝ －1） 置位中 KＣOLＢ回返，存内闲空到找//;i nrutｅｒﻩ;1— ｎruteｒﻩ｝ inｔ ＰRA：：fiｎｄExisｔ（iｎt cｕrpage） { ｆor（int i=0;ｉ<Ｂsizｅ； i++））tｎetnｏc、]egapruc［ｅgａp =＝ tneｔｎoc、］ｉ［kｃoｌb(fiﻩﻩ 置位中 KCOＬB 回返,面页该有中存内到找//;i nrｕterﻩ ；1— nruterﻩ｝ iｎt PRA：：findReplａce(void） { ;0 ＝ sop tｎiﻩ foｒ（iｎt i=0;i<Ｂsｉzｅ； ｉ+＋）)rｅmit、］soｐ[ｋcｏlb =＞ rｅmit、］i［kcｏlb（fiﻩﻩ ﻩ pos = i;//找到应予置换页面,返回 BLOCＫ中位置 ｒeturn pos； } voｉd ＰRＡ：:display（voiｄ） { for（inｔ i=0;i＜Ｂsiｚe； ｉ++） ｉｆ(bｌock［ｉ］、coｎteｎｔ!＝-１） ﻩ；” ”<〈ｔnetnoc、］i[kcｏlb〈〈tuocﻩ ；ldｎe＜＜tuocﻩ｝ void PRA：：Optimａｌ（ｖoid)｛ ； noｉtisop,ecapｓ，tsiｘe tｎiﻩ fｏr（ｉnt i=0； i ｛ﻩ;)i（tsixEdｎif = tｓｉxeﻩﻩ）1-=！ ｔsixe（fｉﻩ {ﻩ ;ｌdnｅ〈〈”页缺不“<<ｔｕoｃﻩ ｝ﻩﻩ esｌｅﻩ {ﻩﻩ ﻩﻩ spａｃe = findSpacｅ（）； ﻩ）1— ＝！ eｃaｐs（fiﻩ ﻩ {ﻩ ﻩ ；]i［egaｐ = ］eｃapｓ［kcolｂﻩ ﻩ ;）（yalpsidﻩﻩ ﻩ } ﻩ ｅslｅﻩ {ﻩﻩ ﻩ)+＋k ；ezisB<ｋ ；0＝k tｎｉ（roｆﻩ ﻩ for（iｎｔ j＝i； j＜Psize； ｊ+＋) ﻩ {ﻩﻩﻩ ﻩﻩ)ｔnetnoc、]ｊ［ｅgaｐ =!ｔnｅtnoc、］k[ｋcolb（ｆiﻩ ｛ 为 RＥMＩT 置设，用会不来将//};00０1 = ｒemiｔ、］k［kcoｌbﻩﻩ一个很大数 ﻩﻩ esleﻩ ﻩﻩ ｛ ﻩﻩ ﻩ ﻩ bloｃk［k]、ｔｉmeｒ = j; ﻩ ﻩﻩ ｂreaｋ； ｝ ﻩﻩﻩ }ﻩﻩﻩﻩﻩ ﻩ ｐoｓition ＝ fiｎdReｐｌａce（）； ﻩ ；］i［ｅｇap ＝ ]ｎｏiｔｉｓｏｐ[ｋcolｂﻩ ；）(yalｐsｉｄﻩﻩ ｝ﻩﻩ ﻩ } }ﻩ｝ voiｄ PRA:：LRU（ｖoid){ int ｅxｉsｔ,ｓpace，ｐositioｎ ； for(int ｉ ＝ 0； i < Psizｅ;ｉ++） ｛ﻩ ﻩ ｅxist = fｉndEｘｉst(i);)1－ =！ tsｉxｅ(ｆiﻩ { ﻩﻩ cout＜<”不缺页”＜ ﻩ blｏck［eｘisｔ］、tiｍｅｒ = —1；//恢复存在得并刚访问过得ＢLOCK 中页面 TＩMＥR 为－1 ﻩ } ﻩ else ｛ﻩ ﻩﻩ sｐace = fｉｎdSpace();ﻩ）１-=!ecaｐs（fiﻩ ﻩ {ﻩ;]i[ｅgａp = ］ecaｐs［ｋｃolｂﻩﻩ ﻩ ；)（ｙalpｓidﻩ ﻩﻩ ｝ ﻩ eｓleﻩ ｛ﻩﻩ ；）（eｃａｌｐeRｄｎif = noｉtiｓopﻩﻩ ﻩ bｌoｃk[positiｏn］ = ｐagｅ［i］； ﻩ ;）(yａlｐsidﻩ ｝ﻩﻩ ｝ﻩ for(int ｊ=0;j〈Ｂsizｅ;j++) ;+＋rｅmit、］j[kcolbﻩﻩ ｝ﻩ｝ ｖoｉd PRA:：ＦIFO（ｖoid） { int exｉｓt,ｓpace,position ； for（iｎt i=0;i ｛ﻩ exｉｓt ＝ findExist(ｉ）； ﻩ ｉf（eｘist!＝-１） {cout＜<＂不缺页＂＜ esleﻩ ｛ sｐａce = findSｐａｃe（）； ﻩ)1-=！ ecaｐs（ｆiﻩ ﻩﻩ ｛ ﻩ block［spaｃｅ］ = paｇe[ｉ]； ﻩ ﻩ displaｙ(); ｝ﻩﻩ ｅsｌeﻩﻩ ﻩ ｛ ﻩﻩ pｏsition = findReplaｃe（）； ﻩﻩ block［pｏsitioｎ] ＝ paｇe[i］； ;)（yａlｐsｉdﻩﻩ ﻩﻩ ｝ }ﻩ）＋+j;ezｉsB ｂlock[j］、tｉmｅr+＋；//BLOCK 中所有页面ＴIMER+＋ ｝ﻩ｝ void ＰＲA：：BlockＣleａr（vｏiｄ)｛ for(inｔ ｉ=０;i {ﻩ blocｋ[i］、contｅnt =-1； ﻩ ｂｌｏcｋ[i]、timeｒ = ０; ｝ } ｖoid mａｉn(vｏiｄ)｛ ;lｄne<〈”:法 算 换 置 面 页“＜＜tuｏcﻩ ｃｏｕｔ〈〈”页面号引用串：7,０,1,2，0,3,0，4,2，３，0，３,2,1,2，0，1，7，０,1＂<〈ｅndｌ； cout〈〈”选择<１＞应用 LＲU 算法”〈＜eｎdl； coｕt<＜”选择<２〉应用 FIFO 算法”〈 ｃout<<”选择＜3>应用 Optｉmａl 算法“<〈ｅndl; ；ldne<<＂出退>0〈择选”〈＜ｔuocﻩ int select； ＰRA tesｔ;ﻩ whｉle(seleｃｔ) ｛ ﻩ cｉｎ〉>select;）tcｅｌｅs（ｈctｉwsﻩ ｛ﻩ :0 esacﻩﻩ;ｋaerbﻩ :1 esａcﻩﻩﻩ;ｌdnｅ＜<“：下如果结法算ＵRL”＜〈tuocﻩ ;）（URL、tsetﻩﻩ ；)(raelCkｃｏｌB、tｓeｔﻩﻩ;ldne＜<”－－-—-—－-—-—--—-—－—－———“< ﻩ break； ：2 esacﻩ cｏut<〈”FIFO 算法结果如下:“<＜endl； tesｔ、FIFO();ﻩ；）（raelCｋcoｌＢ、ｔsetﻩ ﻩ cｏuｔ<〈”-——-－－－－－-—－—－－---－—－-”＜〈eｎdl; ﻩ ｂreak； caｓe 3: ；ｌdnｅ〈＜”：下如果结法算 lａmiｔｐＯ”< test、Optimal（）; ﻩ ；)（rａeｌCkｃolB、tｓetﻩﻩ；ldｎe＜<＂－-－-—－－--－-——-－————－－－＂〈〈tuocﻩﻩ;ｋaeｒbﻩ defaulｔ： ﻩ ；ldｎe〈＜”号能功确正入输请“＜＜tuoｃﻩ ;ｋaerbﻩﻩ }ﻩﻩ } ｝ 6、实验结果 7、实验心得 加深了对操作系统得认识,了解了操作系统中各种资源分配算法得实现，特别就是对虚拟存储，页面置换有了深入得了解，并能够用高级语言进行模拟演示。在这短短得两周时间里，通过浏览、阅读有关得资料，学到了很多东西,同时也发现仅仅书本得知识就是远远不够得,需要把知识运用到实践中去,能力才能得到提高。 使用 MFＣ可视化编程极大得减少了编写得代码量，直观得界面设计，不但便于修改，而且简化了界面程序代码得编写 两种页面置换算法 FIＦO 与ＬRＵ理解起来相当容易，但在实际编程实现得时候需要注意各种细节,需要耐心细致,实际编程中遇到一些细节上得小问题确实需要仔细考虑才行.第二篇：页面置换算法实验报告（精选）
第三篇：页面置换算法实验报告
第四篇：虚拟内存页面置换算法实验报告
第五篇：页面置换算法模拟,实验报告
点击咨询 