虚拟内存页面置换算法实验报告

1、软件学院上机实 验报告课程名称：操作系统原理实验项目：虚拟内存页面置换算法实验室：地狱018姓 名： 死神 学 号：专业班级： 实验时间：2015/12/13实验成绩评阅教师实验目的及要求通过这次实验，加深对虚拟内存页面置换概念的理解， 进一步掌握先进先出FIFO 最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。结合 Linux的内层的分 析方法查看内存的分配过程及linux kernel的内存管理机制二、实验性质设计性三、实验学时4学时四、实验环境实验环境1.实验环境：C与C+®序设计学习与实验系统2.知识准备：(1)使用Linux的基本命令；(2) 了解Linux v

2、mstat、free、top等命令查看linux系统的内存分配 情况；(3)掌握虚拟内存页面置换算法 FIFO等基本算法理论。五、实验内容及步骤假设有n个进程分别在 T1,，Tn时刻到达系统，它们需要的服务时间分别为 S1,Sn=分别采用先来先服务FCF辞口短作业优先SJF51程调度算法进行调度，计算每 个进程的完成时间、周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。步骤通过已知最小物理块数、页面个数、页面访问序列、及采用置换方式可以得出页面 置换的缺页次数和缺页率，及每次缺页时物理块中存储。1 .输入的形式int PageOrderMaxNumber;/页面序歹!

3、Jint PageNum,LackNum=0,BlockNum;/页面个数，缺页次数,最小物理块数2 .输出的形式double LackPageRate/缺页率缺页个数每次缺页时物理块中存储程序所能达到的功能模拟先进先出FIF。最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程。 假设内存中分配给每个进程的最小物理块数为m,在进程运行过程中要访问的页面个数为n,页面访问序列为P1,Pn,分别利用不同的页面置换算法调度进程的页面访问序 列，给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。测试数据，包括 正确的输入及其输出结果和含有错误的输入及其输出结果。程序中用到的所有抽象数据

4、类型的定义、主程序的流程以及各程序模块之间的层次 （调用）关系。int PageOrderMaxNumber;/页面序歹!Jint PageCountMaxNumber=0;/计算内存内数据离下一次出现的距离int PageNum,LackNum=0,BlockNum;/页面个数，缺页次数,最小物理块数 double LackPageRate=0;bool found=false;整理范本头文件流程图六、实验数据及结果分析运行截图:图6.1 XC: UlSOFrCTursnt>inm e»p. eze图6.2明不续粕面八面4注1尊一是数数埋列 tiR个物序I 0 3 市；20救

5、 结据:坟，受X入套匚_' 3图6.3七、实验总结这次试验，让我加深了对虚拟内存页面置换算法的理解， 进一步掌握先进先出FIFO 最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。熟悉 Linux需要经过大 量的实验、改进与思考，在编写代码的过程中遇到了一些问题要积极面对并通过讨论上 网或者问老师解决。通过这次试验我了解了虚拟内存置换算法的一些知识，是我对于所 学习的专业知识得到了更好的巩固和提升。附录源程序清单#include <iostream>using namespace std;#define MaxNumber 100void OPI(int Page

6、OrderMaxNumber,int PageCountMaxNumber, int PageNum,int LackNum,int BlockNum, double LackPageRate,boo found)int moduleMaxNumber;int sum=0;int i,j,k,m;for(i=0;i<BlockNum;i+)/将内存填满 modulei=PageOrderi;sum+;for(j=0;j<=i;j+)cout<<modulej<<""cout<<endl;LackNum=BlockNum;for

7、(i=BlockNum;i<PageNum;i+)found=false;for(j=0;j<BlockNum;j+ )/遍历已存储，判断是否缺页if(modulej=PageOrderi)found=true;break;if(found=false)/缺页，选择替换for(j=0;j<BlockNum;j+) /计算内存内数据离下次出现的距离 PageCountj=0;for(k=i+1;k<PageNum;k+)if(modulej!=PageOrderk)PageCountj+;elsebreak;int max=PageCount0;int kind=0;fo

8、r(j=0;j<BlockNum;j+)找出最大值if(PageCountj>max)max=PageCountj;kind=j;modulekind=PageOrderi;LackNum+;for(m=0; m<3;m+)cout<<modulem<<""cout<<endl;LackPageRate=(LackNum*1.0)/PageNum;cout<<”该算法缺页次数为："<<LackNum<<endl;cout<<”该算法缺页率为："<&

9、lt;LackPageRate*100<<'%'<<endl;先进先出置换算法*/*void FIFO(int PageOrderMaxNumber,int PageCountMaxNumber, int PageNum,int LackNum,int BlockNum, double LackPageRate,boo found)int moduleMaxNumber;int sum=0;int i,j,m；for(i=0;i<BlockNum;i+)/将内存填满modulei=PageOrderi;sum+;PageCounti=3-i;for

10、(j=0;j<=i;j+)cout<<modulej<<""cout<<endl;LackNum=BlockNum;for(i=BlockNum;i<PageNum;i+)found=false;for(j=0;j<BlockNum;j+ )/遍历已存储，判断是否缺页if(modulej=PageOrderi)found=true;break;if(found=false)/缺页，选择替换int max=PageCount0;int kind=0;for(j=0;j<BlockNum;j+)找出最大值if(Page

11、Countj>max)max=PageCountj;kind=j;for(int k=0;k<BlockNum;k+)/不是最大值，贝悭 +1if(k!=kind)PageCountk+;modulekind=PageOrderi;PageCountkind=0;/替换之后已经查询的次数改为 LackNum+;for(m=0; m<3;m+)cout<<modulem<<""cout<<endl;LackPageRate=(LackNum*1.0)/PageNum;cout<<”该算法缺页次数为："

12、<<LackNum<<endl;cout<<”该算法缺页率为："<<LackPageRate*100<<'%'<<endl;最近最久未使用置换算法*/*void LRU(int PageOrderMaxNumber,int PageCountMaxNumber,int PageNum,int LackNum,int BlockNum, doublefound)int moduleMaxNumber;int sum=0;int i,j,m;for(i=0;i<BlockNum;i+)/将内存填

13、满modulei=PageOrderi;sum+;PageCounti=3-i;for(j=0;j<=i;j+) cout<<modulej<<""cout<<endl;LackNum=BlockNum;for(i=BlockNum;i<PageNum;i+)found=false;for(j=0;j<BlockNum;j+)遍历已存储，判断是否缺页if(modulej=PageOrderi)found=true;PageCountj=0;/查询后，更改次数for(int k=0;k<BlockNum;k+) if

14、(k!=j)PageCountk+; break;if(found=false)/缺页，选择替换int max=PageCount0;int kind=0;for(j=0;j<BlockNum;j+)找出最大值if(PageCountj>max)max=PageCountj;kind=j;for(int k=0;k<BlockNum;k+)if(k!=kind)PageCountk+;modulekind=PageOrderi;PageCountkind=0;/替换之后未查询的次数改为 0LackNum+;for(m=0; m<3;m+)cout<<modu

15、lem<<""cout<<endl;LackPageRate=(LackNum*1.0)/PageNum;cout<<”该算法缺页次数为："<<LackNum<<endl;cout<<”该算法缺页率为："<<LackPageRate*100<<'%'<<endl;int main ()int PageOrderMaxNumber;/页面序歹!Jint PageCountMaxNumber=0;/计算内存内数据离下一次出现的距离int

16、 PageNum,LackNum=0,BlockNum;须面个数，缺页次数,最小物理块数 double LackPageRate=0;bool found=false;int chioce1=0,chioce2,chioce3;int i=0;while(chioce1=0)cout<<”是否重新输入数据；0:不输入，1：重新输入："cin>>chioce2;if(chioce2=1)cout<<"请输入页面个数："cin>> PageNum;cout<<"请输入最小物理块数"cin>>BlockNum;cout<<"请输入页面序列："<<endl;for(i=0;i<PageNum;i+)cin>>PageOrderi;整理范本cout<<"请选择算法：1-FIFQ 2-OPI, 3-LRU:"cin>>chioce3;if(chioce3=1)FIFO(PageOrder,PageCount,PageNum,LackNum, BlockNum, LackPageRate,整理范本found);elsei