页面置换算法模拟程序-附代码

1、页面置换算法模拟程序-附代码1 问题的提出31.1关于页面置换算法模拟程序问题的产牛 31.2任务分析32 需求分析33 方案设计44 .总体设计54.1程序N-S图54.2主要的函数54.3主要流程图及代码64.3.1 FIFO （先进先出）64.3.2 LRU （最近最久未使用）84.3.3 OPT （最佳置换算法）124.4实现结果155 程序测试185.1设计测试数据 185.2测试结果及分析 19页面置换算法模拟程序摘要随着计算机的普及人们的物质生活得到了极大的满足，人们在精神生活方面同样也需要 提高，所以越来越多的人进行着各种各样的学习。操作系统是计算机教学中最重要的环节之一，也是

2、计算机专业学生的一门重要的专业课程。操作系统质量的好坏，直接影 响整个计算机系统的性能和用户对计算机的使用。一个精心设计的操作系统能极大地扩 充计算机系统的功能，充分发挥系统中各种设备的使用效率，提高系统工作的可靠性。由于操作系统涉及计算机系统中各种软硬件资源的管理，内容比较繁琐，具有很强的实践性。要学好这门课程，必须把理论与实践紧密结合，才能取得较好的学习效果本课程设计是学生学习完操作系统教程课程后，进行的一次全面的综合训练， 通过课程设计，让学生更好地掌握操作系统的原理及实现方法，加深对操作系统基础理 论和重要算法的理解，加强学生的动手能力。熟悉页面置换算法及其实现，引入计算机系统性能评价

3、方法的概念。关键词：编制页面置换算法模拟程序、打印页面、FIFO页面算法、LRU页面置换算法、OPT页面置换算法。页面置换算法模拟程序引言1. 问题的提出1.1关于页面置换算法模拟程序问题的产生在各种存储器管理方式中，有一个共同的特点，即它们都要求将一个作业 全部装入内存方能运行，但是有两种情况：（1）有的作业很大，不能全部装入 内存，致使作业无法运行；（2）有大量作业要求运行，但内存容量不足以容纳 所有这些作业。而虚拟内存技术正式从逻辑上扩充内存容量，将会解决以上两 个问题。从内存中调出一页程序或数据送磁盘的对换区中，通常，把选择换出的页面的 算法称为页面置换算法（Page-Replacem

4、ent Algorithms ）。进而页面置换算法 模拟程序能客观的将其工作原理展现在我们面前。1.2任务分析首先，定义宏变量，设置所占最大内存长度。编辑以时间为种子，初始化 随即发生器。进行相关页面输入程序的编写以及页面的打印。尔后，寻找最近 最近最久未使用的页面、记录当前内存块中页面离下次使用间隔长度等相关程 序的代码编写。最后，进行）FIFO、LRU OPT三种算法的编写。2. 需求分析1. 用随机数方法产生页面走向，页面走向长度为L。2. 根据页面走向，分别采用FIFO和LRU算法进行页面置换，统计缺页率； 为简化操作，在淘汰一页时，只将该页在页表中抹去 ，而不再判断它是 否被改写过，

5、也不将它写回到辅存。3. 假定可用内存块和页表长度（作业的页面数）分别为m和k，初始时，作 业页面都不在内存。随机数产生程序:int i,j;j=time(NULL);页面置换算法模拟程序取时钟时间srand(j);以时钟时间x为种子，初始化随机数发生器coutvv输出随机数:;for(i=0;im;i+)pi.num=rand( )%10+1;产生1到10之间的随即数放到数组 p中pi.time=0;coutpi. num ;上述随机数发生函数产生的随机数为0.01.0，稍另变化就可得到0n 1之间的随机数。程序开始时，应对变量Seed (实型)赋初值。根据页面置换算法的理论操作及要求， 首

6、先要进行页面长度的确定，定义结 构体用以储存数据，进行主界面代码及 FIFO、LRU OPT页面置换算法代码的编 写。3. 方案设计首先，定义宏变量，设置所占最大内存长度。编辑以时间为种子，初始化随即发生器。进行相关页面输入程序的编写以及页面的打印。其次，寻找最近最近最久未使用的页面、记录当前内存块中页面离下次使用间隔长度等相关程序的代码编写。最后，进行FIFO、LRU OPT三种算法的编写。.程序运行平台VC+6.0具体操作如下：在 VC+6.0的环境下准备用时钟函数调用库函数(#include )、 取时钟时间并存入t调用库函数(t=time(NULL)、用时间t初 始化随机数发生器调用库

7、函数(srand(t)返回一个 110之间的随机数(x=ra nd( )%10+1 )。编写三种算法。4. 总体设计4.1 程序N-S图程序开始输入选择项（进行判断）页面存在进入下部 操作此 项 不 存 在输入要输出的结果输出结果结束4.2 主要的函数Input（int m,Pro pL）（打印页面走向状态）；void print（Pro *page1）（打印当前的页面）；int Search（int e,Pro *page1 ）（寻找内存块中与 e相同的块号）；int Max（Pro *page1）（寻找最近最长未使用的页面）；int Cou nt（Pro *page1,i nt i,i n

8、t t,Pro pL）（记录当前内存块中页面离下次使用间隔长度）；int main（） （主函数）；随机数发生器#i nclude #i nclude /准备用时钟函数调用库函数t=time(NULL); 取时钟时间并存入t调用库函数 srand(t);用时间t初始化随机数发生器调用库函数x=ra nd( )%10+1; 返回一个110之间的随机数4.3主要流程图及代码4.3.1 FIFO (先进先出)设计原理：需要进行页面置换，即把内存中装入最早的那个页面淘 汰，换入当前的页面。算法流程图页面走向存入数组 p图4-1FIFO算法流程图代码：if(c=1)/FIFO n=0;coute ndl

9、;页面置换*把page中最先装入的把 pi的内容直coute ndl;coutvvFIFO算法页面置换情况如下:coute ndl; cout*=0)当前页面在内存中coutpi. num ;/ cout不缺页endl; i+;/i 加 1输出当前页pi.numelse /当前页不在内存中内存中if(t=M)t=0; elsen+;/paget. num=pi. num;/缺页次数加把当前页面放入prin t(page); t+;coutpi. num/IIi+;/打印当前页面 下一个内存块 指向下一个页面 cout缺页次数： nII缺页率：n/mendl;432 LRU （最近最久未使用）设

10、计原理：当需要淘汰某一页时，选择离当前时间最近的一段时间 内最久没有使用过的页先淘汰该算法的主要出发点是，如果某页被访问了，则 它可能马上还要被访问。或者反过来说如果某页很长时间未被访问，则它在最 近一段时间也不会被访问。Y把page中最近最久未把 pi的内容直代码：if(c=2)/LRUn=0;coute ndl; coute ndl; coute ndl; coute ndl; cout=0)/paget.time=0;间置0for(a=0;aM;a+) if(a!=t)pagea.time+; coutpi. num ; cout不缺页endl;else/n+; /缺页次数加t=Max(

11、page);/号赋值给tpaget. num=pi. num;/paget.time=0;/coutpi. num ; prin t(page); for(a=0;aM;a+) if(a!=t)pagea.time+;i+;cout缺页次数： *V/把与它相同的内存块的时/其它的时间加1如果不在内存块中1返回最近最久未使用的块进行替换替换后时间置为0/其它的时间加1缺页率： n/me ndl;433 OPT （最佳置换算法）设计原理：需要进行页面置换，把内存中以后一段时间都不使用或 是使用时间离现在最远的页面换出。流程图:页面走向存入把page中以后一段时间都不使把 pi的内容直图4-3 OP

12、T流程图if（c=3） /OPT代码：n=0;coute ndl;页面置换*coute ndl; cout coute ndl;coutOPT算法置换情况如下:=0) coutpi. num ; cout不缺页endl; i+；else/int a=0;for(t=0;tM;t+)/如果已在内存块中如果不在内存块中if(paget. num=0)a+;/记录空的内存块数if(a!=0)/有空内存块 int q=M;for(t=0;tt)q=t;/把空内存块中块号最小的找出来pageq. num=pi. num;n+;coutpi. num prin t(page);i+;elseint tem

13、p=0,s;for(t=0;tM;t+)/寻找内存块中下次使用离现在最久的页面if(tempCo un t(page,i,t,p) 页面置换算法模拟程序temp=Co un t(page,i,t,p);s=t; /把找到的块号赋给spages. num=pi. num;n+;coutpi. num ;prin t(page);i+;cout缺页次数：*缺页率：=童 =L请请 J f LB-目 -曰、 会 聘20 n-ffi- W廉实图5-6输入数据25后输出图输入数据18:“ *C: Docuents and Setting5Adinist rat orWDcbuos. exef随机25181

14、 3 2 10 4请输入实际贞面走向长度凯 回儿 M b I面*度须在15 浙之间匸请重訓皱 陵昧员回纟度须在1523之亦请重新蛊 输出随呱数二79 10 9312 10 76 睛输天可理内存T面数曲5”页面置换算法模拟程序图5-7输入数据18后的输出图25181 354 L L 6 1I.1.S 4- 儿输输- - - ! 2 耒隶 7ITlm -a W =L请请i -薯 c 3 wf 2 Lb列司1 r. 1 L之之 密；r 长 0数可可0 33请！2 9m面须须？存二换.P亠于输入数据:贝度度-内E3E3 际用籬 实面面机可航磁 入賁随入块块 律留薯存图5-8输出图选1,进入FIFO页面

15、置换:图5-9 FIFO的输出图选2,进入LRU页面置换:U;UocuBEntsincsAdaxnxst cat deWebugXosIBU鼻法页面置换情况如下,7 0 0 0? 9 0 0? ? 10 0不快瓦7 9 10 31 9 16 319 2 31 10 2 31 10 2 7& 10 2 7& 10 8 7132104缺页次数 16不缺頁& S S ?& 6 S 1& 5 3 12 S 3 12 10 3 1缺页率：8.888SS92 13 3 4lJFIFO2JLRU_ 3：oprS面詈换KMEW结東程序咅图5-10 LRU的输出图输入3,进入OPT页面置换:; _uoGiuen

16、t s目na:、區口儿“丄呂弋 1:且t 口壬片耒mK K Jt J JCK JC XM： M：MKM：M KXJCXlt JCKJlOC JtZK M： It J K U JC 1C MTM： H K K K X M： XXOPT算法置换情况如下，:MNJtaiElCJCaCKJtiCManEKXaiilOEHiaaiEKWJtJEmtiMKJCMiJCJEaCMIiMKWEXXH7 7 0 0 09 7 9 0 0id ? ? IB 0?不缺页3 791031 711032 711021B烝坂7不缺页6 6 1 10 2H 6 1 8_26不缺页55 18 2s不缺页3 3 18 22不缺

17、页1B 10 1 e 24 4 18 2缺贝次数：12 缺贝率=0-6tttt7l：FIF0jl Ik. W2：LWfi HO3：0TT m面置唤檢其它糠纟隸稈序;图5-11 OPT的输出图5. 程序测试5.1设计测试数据A 14 25 18； 2 6 4B 1C 25.2测试结果及分析1）测试A结果及分析进入主菜单后输入14、25,显示输入不满足要求。输入18显示相关信息； 输入2、6不满足要求，输入4显示出相关信息。2）测试结果及分析显示出FIFO页面置换算法的缺页信息及缺页率。3）测试C结果及分析显示出LRUM面置换算法的缺页信息及缺页率。4）测试D结果及分析显示出OPT页面置换算法的缺

18、页信息及缺页率结论通过这次课程设计，不仅让我了解了页面置换算法，开始我一味的进行 调试，急切的想侥幸调试出来，但由于没有进行深入的考虑，我调试了很久都 没没有成功，我仔细的分析题目，分析材料，在原由的基础上我进行了改正， 我最后还是调试成功了，还是经过了一翻努力，这次操作系统实习，不仅让我 对操作系统这门课程有了更深入的研究、对很多重要的概念有了巩固和掌握。 通过努力，三个页面置换算法程序都已经完成，此时此刻，我心里多了些成就 感。虽然自己所做的很少也不够完善，但毕竟也是努力的结果。主要有以下几点收 获：1. 通过对上网和看书查阅相关资料，使自己对 VC+语言的基本框架有新的 了解，加深了对可

19、视化程序的认识。2. 在使用VC+语言来实现功能时，不像以往用的其他语言，它比较简练， 更容易理解，实用性很强。3. 先进先出页面置换和LRU以及OPT算法各有特点，但是实践起来却很大， 使自己对页面置换算法有了新的认识。一周半的课程设计就要结束了，不但对专业知识有了更深的理解，更使的自己 认识到实践的重要性，理论、实践相结合才能达到很好的学习效果，特别是程 序语言的学习。致谢本次课程设计能顺利完成，感谢学校的大力支持，感谢数学与计算机学院为 我们提供实练的机会，感谢老师的细心教导。此次的课程设计收获很多，虽然经过了一段漫长而又痛苦的过程，但是自己还是完成了，这是与自己的努力是分不开的，但是自

20、己在调试过程当中遇到 的一些问题，自己仍然不懂，是在同学、老师的帮助下完成的，在这里还要再 次对他们的付出表示崇高的敬意。页面置换算法模拟程序参考文献面向对象程序设计与VisualC+6.0教程陈天华编著C 程序设计（第三版） 谭浩强编著C+入门经典面向对象程序设计与C+实现 刘晋萍编著计算机操作系统教程 徐甲同等编著操 作 系 统 罗宇等编著操作系统实验教程 张丽芬,刘利雄,王全玉编著 计算机操作系统梁红兵、哲风屏、汤子瀛编著操!作系统教程陈向群、杨芙清编著代码：#in clude#in elude #in elude #in elude #defi ne L 20页面走向长度最大为20in

21、t M;/内存块struct Pro/定义一个结构体int n um,time;lnput(i nt m,Pro pL) 打印页面走向状态coutvv请输入实际页面走向长度L(15v=L m;if(m20|m15)coutvv实际页面长度 须在1520之间;请重新输入L :else break;while(1);int i,j;j=time(NULL); 取时钟时间srand(j);/以时钟时间x为种子，初始化随 机数发生器cout输出随机数：;for(i=0;im;i+)pi.num=rand( )%10+1;/ 产生 1 至到 10 之间 的随即数放到数组p中pi.time=0;coutp

22、i. nu m;coute ndl; return m; void print(Pro *page1)打印当前的页面Pro *page=new ProM; page=page1;for(int i=0;iM;i+) coutpagei. nu m; coute ndl;int Search(int e,Pro *page1 )寻找内存块中 与e相同的块号Pro *page=new ProM; page=page1;for(i nti=O;iM;i+)if(e=pagei.num)return i;返回 i 值return -1;int Max(Pro *page1)寻找最近最长未使用的页 面P

23、ro *page=new ProM;page=page1;int e=page0.time,i=0;while(ivM)找出离现在时间最长的页面if(epagei.time) e=pagei.time;i+；for( i=O;iM;i+)if(e=pagei.time)returni;找到离现在时间最长的页面返回其块号return -1;int Count(Pro *page1,int i,int t,Pro pL) 记录当前内存块中页面离下次使用间隔长度Pro *page=new ProM;page=page1;int coun t=0;for(i nt j=i;jL;j+)if(paget

24、.num=pj.num)break; 当前页面再次被访问时循环结束else count+;否贝V count+1return count;/ 返回 count 的值int main()in t c;int m=0,t=0;float n=0;Pro pL;m=I nput(m,p); 调用in put函数，返回 m值 cout5|M3)cout内存块m须在35之间，请重新 输入m:;else break;while(1);Pro *page=new ProM;dofor(int i=0;iM;i+) 初试化页面基本情况pagei.time=m-1-i;i=0; cout1:FIFO 页面置换e

25、ndl; cout2:LRU 页面置换endl; cout3:OPT 页面置换endl; cout按其它键结束程序； c;system(cls);if(c=1)/FIF0 页面置换 n=0;cout*e ndl;coute ndl;coutFIFO 算法页面置换情况如下:endl;coute ndl;cout*=O)当前页面在内存中ii. coutpi. num 输出当前页pi.numcout不缺页endl;i+;/i 加 1else当前页不在内存中if(t=M)t=0; elsen+;缺页次数加1paget. num=pi. num;/ 把当前页面放入内存中coutpi. nu m;prin t(page);打印当前页面t+;下一个内存块i+;指向下一个页面cout缺页次数：n 缺页率：n/mendl;if(c=2)/LRU 页面置换n=0;cout*e ndl;coute ndl;cout面置换情况如下:LRU算法页e