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

《虚拟内存页面置换算法实验报告》由会员分享，可在线阅读，更多相关《虚拟内存页面置换算法实验报告（14页珍藏版）》请在装配图网上搜索。

1、虚拟内存页面置换算法学生姓名： 学生学号: 专业班级: 指导老师:2013年6月20日1、实验目的：通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌 握先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算 法的实现方法。2、问题描述：假设有n个进程分别在T,，T时刻到达系统，它们需要的服务1n时间分别为S,，S。分别采用先来先服务FCFS和短作业优先SJF 1n进程调度算法进行调度，计算每个进程的完成时间、周转时间和带权 周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。3、需求分析 通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌 握先进先出FIFO、最

2、佳置换OPI和最近最久未使用LRU页面置换算 法的实现方法。通过已知最小物理块数、页面个数、页面访问序列、及采用置换 方式可以得出页面置换的缺页次数和缺页率，及每次缺页时物理块中 存储！(1) 输入的形式int PageOrderMaxNumber;/页面序列int PageNum,LackNum=0,BlockNum;/页面个数，缺页次数，最 小物理块数(2) 输出的形式double LackPageRa te/缺页率缺页个数每次缺页时物理块中存储(3) 程序所能达到的功能模拟先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面 置换算法的工作过程。假设内存中分配给每个进程的最小物理块

3、数为 m,在进程运行过程中要访问的页面个数为n，页面访问序列为片，P分别利用不同的页面置换算法调度进程的页面访问序列， 1n给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。 测试数据，包括正确的输入及其输出结果和含有错误的输入及其输出 结果。(4) 测试数据页面个数：20 最小物理块数：3页面序列：9 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 14、概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以 及各程序模块之间的层次(调用)关系。int PageOrderMaxNumber;/页面序列int PageCoun tMaxNumber二0

4、;/计算内存内数据离下一次出现的距离最小物理块数double LackPageRate=0;bool found二false;流程图头文件最佳羞换 OPI (r先进先出 FIFO (L曰最近最久未使用LRUL-i返回用返回11调用/ 乙/ft用主国数main ()5、详细设计所指含义不同，在FIFO中max是指从进入物理块到本次存在最久，在LRU中是指从上一次访问到本次存在最久！6、调试分析(1) 调试过程中遇到的问题以及解决方法，设计与实现的回顾讨 论和分析；在FIFO和LRU中计算每个页面在物理块中所存在的“时间”时总 是出错，后来多次调试语句所处位置和计数方法，终于得出正确结果， 并且所

5、有算法都没有输出物理块中发生置换后的物理块中的内容，在 老师的提醒下更改程序输出其内容。(2) 算法的性能分析(包括基本操作和其它算法的时间复杂度和 空间复杂度的分析)及其改进设想；OPI:时间复杂度为O (J2)空间复杂度为：0(1)FIFO：时间复杂度为0 (J2) 空间复杂度为：0(1)LRU:时间复杂度为O (J2)空间复杂度为：O(1)(3) 经验和体会。首先要明确页面置换的原理及OPI、FIFO、LRU算法的主要思想， 画出算法流程图！这样在解决问题时更容易!7、用户使用说明程序的使用说明，列出每一步的操作步骤。(1) 输入页面总数(2) 输入最小物理块数(3) 输入页面访问序列(

6、4) 选择算法(5) 得出结果8、测试结果1:重新输入:2 0 1 7 0 1 3-LRU：!20003333否重新输女熬据；阳不输入 库列：R 1 20304230321选择算法:1-FIFO, 2-0PI ,11 2131110&S1 X :5 为:7 勢 初率 页页2 1 法法0 0BW-请选具法=1-FIFO, 2-0FI , 3-LRU：370 232013 3 20 0 0 09、心得体会通过使用C+程序设计语言对页面置换算法进行编程设计，使我 对该算法有了更深的了解和更完整的掌握，也在编程过程中对这种算 法的优缺点有了体会，并且加强了自己的编程能力。10、附录程序源代码：#inc

7、lude iostream.h#define MaxNumber 100void 0PI(int PageOrderMaxNumber,int PageCountMaxNumber,int PageNum,in t LackNum,in t BlockNum, double LackPageRa te,bool found)int moduleMaxNumber;int sum=0;int i,j,k,m;for(i=0;iBlockNum;i+)/将内存填满modulei=PageOrderi;sum+;coutmodulej ; coutendl;LackNum=BlockNum;for(

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

9、=PageCountj;kind=j; modulekind=PageOrderi;LackNum+;for(m=0; m3;m+)coutmodulem ;coutendl;LackPageRate=(LackNum*1.0)/PageNum;cou t该算法缺页次数为:LackNumendl;cou t该算法缺页率为：LackPageRa te*100endl;/*先进先出置换算法*/void FIFO(int PageOrderMaxNumber,int PageCountMaxNumber,int PageNum,int LackNum,int BlockNum, double Lac

10、kPageRate,bool found)int moduleMaxNumber;int sum=0;int i,j,m;for(i=0;iBlockNum;i+)/将内存填满modulei=PageOrderi;sum+;PageCounti=3-i;for(j=0;j=i;j+)coutmodulej ;coutendl;LackNum=BlockNum;for(i=BlockNum;iPageNum;i+)found=false;for(j=0;jBlockNum;j+ )/遍历已存储，判断是否缺页if(modulej=PageOrderi)found=true;break;if(fou

11、nd二二false)/缺页，选择替换int max=PageCount0;int kind=0;max=PageCountj;kind=j;for(in t k=0;kBlockNum;k+)/不是最大值，则要+1if(k!=kind)PageCountk+; modulekind=PageOrderi;PageCountkind=0;/替换之后已经查询的次数改为0LackNum+;for(m=0; m3;m+)coutmodulem ;coutendl;LackPageRate=(LackNum*1.0)/PageNum;cou t该算法缺页次数为:LackNumendl;cou t该算法缺

12、页率为：LackPageRa te*100endl;/*最近最久未使用置换算法*/ void LRU(int PageOrderMaxNumber,int PageCountMaxNumber,int PageNum,int LackNum,int BlockNum, double LackPageRate,bool found)int moduleMaxNumber;int sum=0;int i,j,m;for(i=0;iBlockNum;i+)/将内存填满modulei=PageOrderi;sum+;PageCounti=3-i;for(j=0;j=i;j+)coutmodulej ;

13、coutendl;LackNum=BlockNum;for(i=BlockNum;iPageNum;i+)found=false;for(j=0;jBlockNum;j+)/遍历已存储，判断是否缺页if(modulej=PageOrderi)found=true;PageCoun tj=0;/查询后，更改次数for(int k=0;kBlockNum;k+)if(k!=j)PageCountk+;break;if(found二二false)/缺页，选择替换int max=PageCount0;int kind=0;for(j=0jmax)max=PageCountj;kind=j;for(in

14、t k=0;kBlockNum;k+)if(k!=kind)PageCountk+;modulekind=PageOrderi;PageCountkind=0;/替换之后未查询的次数改为0LackNum+;for(m=0; m3;m+)coutmodulem ;coutchioce2;if(chioce2=1)cou t PageNum;cou t请输入最小物理块数；cinBlockNum;cout请输入页面序列：endl;for(i=0;iPageNum;i+)cinPageOrderi;cout请选择算法：1-FIFO, 2-OPI, 3-LRU:;cinchioce3;if(chioce3=1)FIFO(PageOrder,PageCount,PageNum,LackNum, BlockNum, LackPageRate, found);elseif(chioce3=2)OPI(PageOrder,PageCount,PageNum,LackNum, BlockNum, LackPageRate, found);elseLRU(PageOrder,PageCount,PageNum,LackNum, BlockNum, LackPageRate, found);cout*endl;cout请选择继续还是结束：0：继续，1：结束；cinchioce1;