《页面置换算法模拟程序》由会员分享，可在线阅读，更多相关《页面置换算法模拟程序（23页珍藏版）》请在金锄头文库上搜索。
1、目录1.1 关于页面置换算法模拟程序问题的产生1.2 任务分析 2需求分析 3 方案设计4 总体设计4.1程序N-S图4.2主要的函数43主要流程图及代码4.3.1 FIFO （先进先出）4.3. 2LRU （最近最久未使用）4.3. 3OPT （最佳置换算法）4.4实现结果5 程序测试5.1设计测试数据5.2测试结果及分析摘要随着计算机的普及人们的物质生活得到了极大的满足，人们在精神生活方面同样也需要提高，所 以越来越多的人进行着各种各样的学习。操作系统是计算机教学中最重要的环节之一，也是计算 机专业学生的一门重要的专业课程。操作系统质量的好坏，直接影响整个计算机系统的性能和用 户对计算机的
2、使用。一个精心设计的操作系统能极大地扩充计算机系统的功能，充分发挥系统中 各种设备的使用效率，提高系统工作的可靠性。由于操作系统涉及计算机系统中各种软硬件资源 的管理，内容比较繁琐，具有很强的实践性。要学好这门课程，必须把理论与实践紧密结合，才 能取得较好的学习效果.本课程设计是学生学习完操作系统教程课程后，进行的一次全面的综合训练，通过课程 设计，让学生更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。 熟悉页面置换算法及其实现，引入计算机系统性能评价方法的概念。关键词：编制页面置换算法模拟程序、打印页面、FIFO页面算法、LRU页面置换算法、O
3、PT页面置 换算法。引言1问题的提出1.1 关于页面置换算法模拟程序问题的产生在各种存储器管理方式中，有一个共同的特点，即它们都要求将一个作业 全部装入内存方能运行，但是有两种情况：(1)有的作业很大，不能全部装入 内存，致使作业无法运行；(2)有大量作业要求运行，但内存容量不足以容纳 所有这些作业。而虚拟内存技术正式从逻辑上扩充内存容量，将会解决以上两 个问题。从内存中调出一页程序或数据送磁盘的对换区中，通常，把选择换出的页 面的算法称为页面置换算法(Page-ReplacementAlgorithms )。进而页面置换算 法模拟程序能客观的将其工作原理展现在我们面前。1.2任务分析首先，定
4、义宏变量，设置所占最大内存长度。编辑以时间为种子，初始化 随即发生器。进行相关页面输入程序的编写以及页面的打印。尔后，寻找最近 最近最久未使用的页面、记录当前内存块中页面离下次使用间隔长度等相关程 序的代码编写。最后，进行)FIF0、LRU、OPT三种算法的编写。2 需求分析1. 用随机数方法产生页面走向，页面走向长度为L。2. 根据页面走向，分别采用FIFO和LRU算法进行页面置换，统计缺页率;为简化操作，在淘汰一页时，只将该页在页表中抹去，而不再判断它是否被改写过，也不将它写回到辅存。3. 假定可用内存块和页表长度(作业的页面数)分别为m和k,初始时，作业页面都不在内存。随机数产生程序：i
5、n ti,j;j=t ime(NULL);/取时钟时间srand(j);/以时钟时间x为种子，初始化随机数发生器cout输出随机数:；for(i=0;im;i+)pi.num=rand()%10+1;产生1到10之间的随即数放到数组p中pi.time=0;coutpi.num;上述随机数发生函数产生的随机数为0010,稍另变化就可得到0n 1 之间的随机数。程序开始时，应对变量Seed(实型)赋初值。根据页面置换算法的理论操作及要求,首先要进行页面长度的确定,定义结 构体用以储存数据，进行主界面代码及FIFO、LRU、OPT页面置换算法代码的编 写。3 方案设计首先，定义宏变量，设置所占最大内
6、存长度。编辑以时间为种子，初始化随 即发生器。进行相关页面输入程序的编写以及页面的打印。其次，寻找最近最近最久未使用的页面、记录当前内存块中页面离下次使用 间隔长度等相关程序的代码编写。最后，进行FIFO、LRU、OPT三种算法的编写。程序运行平台VC+6 0具体操作如下：在VC+6.0的环境下准备用时钟函数调用库函数 (#includetime.h)、取时钟时间并存入t调用库函数(t=time(NULL)、用 时间t初始化随机数发生器调用库函数(srand(t)返回一个110之间的随机数 (x=rand()%10+1)编写三种算法。4 总体设计4.1程序N-S图程序开始输入选择项(进行判断)
7、页面存在进入下一部操作此项不存在输入要输出的结果输出结果结束4.2主要的函数Input(intm,PropL)(打印页面走向状态)；voidprint(Pro*page1)(打印当前的页面)；intSearch(inte,Pro*page1)(寻找内存块中与e相同的块号)； intMax(Pro*page1)(寻找最近最长未使用的页面)；intCount (Pro*page1,inti,intt,PropL)(记录当前内存块中页面离下 次使用间隔长度)；intmainO (主函数)；随机数发生器#include#include time.h/准备用时钟函数调用库函数 t=time(NULL);
8、/取时钟时间并存入t调用库函数 srand(t);用时间t初始化随机数发生器调用库函数 x=rand()%10+1;返回一个110之间的随机数4.3主要流程图及代码4.3.1FIF0 (先进先出)设计原理：需要进行页面置换，即把内存中装入最早的那个页面淘汰，换入当前的页面。把page 口中最先+装入的l=J把pi的内容直接装入图4-1FIF0算法流程图代码：if(c=1)/FIF0页面置换n=0;cout*endl; coutendl;coutFIF0算法页面置换情况如下:endl;coutendl; cout*endl;while(i=0) 当前页面在内存中coutpi.num;/输出当前页
9、 pi.numcout 不缺页endl;i+;/i 加 1else/当前页不在内存中if(t=M)t=0;elsen+;缺页次数加1page t.n um=pi .num;/把当前页面放入内存中coutpi.num;print(page);/打印当前页面t+;/下一个内存块i+;/指向下一个页面cout缺页次数：n缺页率：n/mendl;4.3.2LRU （最近最久未使用）设计原理：当需要淘汰某一页时，选择离当前时间最近的一段时间-来源网络，仅供个人学习参考内最久没有使用过的页先淘汰该算法的主要出发点是，如果某页被访问了，则 它可能马上还要被访问。或者反过来说如果某页很长时间未被访问，则它在最
10、 近一段时间也不会被访问。算法流程图:i+YN把page中最近把pi的内最久未容直接装入 if出当前内存直接装入L流程图代码：if(c=2)/LRU页面置换n=0; cout*endl;coutendl;coutLRU算法页面置换情况如下:endl;coutendl;cout*endl;while(i=0)/如果已在内存块中pagettime=0;/把与它相同的内存块的时间置0 for(a=0;aM;a+) if (a!=t) pagea t ime+ ; /其它的时间加1 coutpinum;cout 不 缺页endl;else/如果不在内存块中n+;缺页次数加1t=Max(page);返回
11、最近最久未使用的块号赋值给t paget.num=pi.num ; /进行替换pagett ime=0;/替换后时间置为0coutpi.num;print(page);for(a=0;aM;a+)if(a! =t)pagea. time+;/其它的时间加 1 i+；cout缺页次数：n缺页率：n/mendl;4.3.3OPT （最佳置换算法）设计原理：需要进行页面置换，把内存中以后一段时间都不使用或 是使用时间离现在最远的页面换出。流程图：图 4-3OPT 流程图代码：if(c=3)/0PT页面置换n=0; cout*endl; coutendl;cout0PT算法置换情况如下:endl;co
12、utendl; cout*endl;while(i=0) 如果已在内存块中coutpi.num;cout不缺页endl; i+;else/如果不在内存块中inta=0;for(t=0;tM;t+)if(page t.num=0)a+;/记录空的内存块数 if(a!=0)/有空内存块intq=M;for(t=0;t t)q=t;把空内存块中块号最 小的找出来pageq.num=pi .num;n+;coutpi.num;pri nt( page);i+;elseinttemp=0,s;for(t=0; tM; t+)/寻找内存块中下次使用离现在最久的 页面if(tempCount(page,i,t,p)temp=Count(page,i,t,p);s=t;/把找到的块号赋给 s pages.num=pi.num;n+;coutpi.num;print(page);i+;cout缺页次数：n缺页率：n/mendl; 4.4实现结果程序在运行的情况下，进入主界面输入菜单，如图3-3所示： 输入14：图4-5输入14后的输出图输入25：图5-6输入数据25后输
