[VIP专享](流程图)页面置换算法课程设计115303.pdf

《[VIP专享](流程图)页面置换算法课程设计115303.pdf》由会员分享，可在线阅读，更多相关《[VIP专享](流程图)页面置换算法课程设计115303.pdf（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1操作系统课程设计报告题目：页面置换算法模拟程序学院名称:专业班级：学生姓名：指导教师：成绩：2目录一、设计目的 3二、设计题目32.1 设计内容32.2 设计要求3三、设计过程43.1 FIFO（先进先出）43.2 LRU（最近最久未使用）53.3 OPT（最佳置换算法）63.4 随机数发生器7四、完整代码 7五、运行结果演示13 六、设计心3得16七、参考文献16一、设计目的 操作系统是计算机教学中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。操作系统质量的好坏，直接影响整个计算机系统的性能和用户对计算机的使用。一个精心设计的操作系统能极大地扩充计算机系统的功能，充分发挥系统中

2、各种设备的使用效率，提高系统工作的可靠性。由于操作系统涉及计算机系统中各种软硬件资源的管理，内容比较繁琐，具有很强的实践性。要学好这门课程，必须把理论与实践紧密结合，才能取得较好的学习效果。本课程设计是学生学习完计算机操作系统课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。熟悉页面置换算法及其实现，引入计算机系统性能评价方法的概念。二、设计题目：页面置换算法模拟程序 2.1 设计内容编制页面置换算法的模拟程序。2.2 设计要求1).用随机数方法产生页面走向，页面走向长度为 L(15=L=20)

3、,L 由控制台输入。2).根据页面走向，分别采用 Optinal、FIFO、LRU 算法进行页面置换，统计缺页率。3).假定可用内存块为 m(3=m=5)，m 由控制台输入，初始时，作业页面都不在4内存。4).要求写出一份详细的设计报告。课程设计报告内容包括：设计目的、设计内容、设计原理、算法实现、流程图、源程序、运行示例及结果分析、心得体会、参考资料等。3设计过程3.1 FIFO（先进先出）设计原理：需要进行页面置换，即把内存中装入最早的那个页面淘汰，换入当前的页面。算法流程图：开始页面走向存入数组 p中，内存块用 page表示初始化为 0当前 p中第 i 个元素是否已在内Page是否有空把

4、 page中最先装入的页面置换出去.i+把 pi的内容直接装入最上面一个空内存块，i+NNYYi+53.2 LRU（最近最久未使用）设计原理：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。该算法的主要出发点是，如果某页被访问了，则它可能马上还要被访问。或者反过来说，如果某页很长时间未被访问，则它在最近一段时间也不会被访问。算法流程图：输出当前内存块状态结束 开始页面走向存入数组 p中，内存块用 page表示初始化为 0当前 p中第 i 个元素是否已在内存Page是否有空把 pi的内容直接装入最上面一个空内存块，i+把 page中最近最久未使用的页面置换出去.i+i

5、+输出当前内存块状态NNYY63.3 OPT（最佳置换算法）设计原理：需要进行页面置换，把内存中以后一段时间都不使用或是使用时间离现在最远的页面换出。流程图 开始页面走向存入数组 p中，内存块用 page表示初始化为 0当前 p中第 i 个元素是否已在内存Page是否有空把 pi的内容直接装入最上面一个空内存块，i+把 page中以后一段时间都不使用或是使用时间离现在最远的换出.i+输出当前内存块状态NNi+YY73.4 随机数发生器#include#include /准备用时钟函数调用库函数 t=time(NULL);/取时钟时间并存入 t 调用库函数 srand(t);/用时间 t 初始化

6、随机数发生器调用 库函数 x=rand()%10+1;/返回一个 110 之间的随机数 四完整代码#include#include#include#include#define L 20/页面走向长度最大为 20int M;/内存块struct Pro/定义一个结构体 int num,time;Input(int m,Pro pL)/打印页面走向状态 cout请输入实际页面走向长度 L(15=Lm;if(m20|m15)cout实际页面长度须在 1520 之间;请重新输入L：;else break;while(1);int i,j;j=time(NULL);/取时钟时间 srand(j);/以

7、时钟时间 x 为种子，初始化随机数发生器cout输出随机数:;for(i=0;im;i+)8 pi.num=rand()%10+1;/产生 1 到 10 之间的随即数放到数组 p 中 pi.time=0;coutpi.num;coutendl;return m;void print(Pro*page1)/打印当前的页面 Pro*page=new ProM;page=page1;for(int i=0;iM;i+)coutpagei.num;coutendl;int Search(int e,Pro*page1 )/寻找内存块中与 e 相同的块号 Pro*page=new ProM;page=p

8、age1;for(int i=0;iM;i+)if(e=pagei.num)return i;/返回 i 值 return-1;int Max(Pro*page1)/寻找最近最长未使用的页面 Pro*page=new ProM;page=page1;int e=page0.time,i=0;while(iM)/找出离现在时间最长的页面 if(epagei.time)e=pagei.time;i+;for(i=0;iM;i+)if(e=pagei.time)return i;/找到离现在时间最长的页面返回其块号 return-1;int Count(Pro*page1,int i,int t,P

9、ro pL)/记录当前内存块中页面离下次使用间隔长度9 Pro*page=new ProM;page=page1;int count=0;for(int j=i;jL;j+)if(paget.num=pj.num)break;/当前页面再次被访问时循环结束 else count+;/否则 count+1 return count;/返回 count 的值 int main()int c;int m=0,t=0;float n=0;Pro pL;m=Input(m,p);/调用 input 函数，返回 m 值 coutM;if(M5|M3)cout内存块 m 须在 35 之间，请重新输入 m：;

10、else break;while(1);Pro*page=new ProM;do for(int i=0;iM;i+)/初试化页面基本情况 pagei.num=0;pagei.time=m-1-i;i=0;cout1:FIFO 页面置换endl;cout2:LRU 页面置换endl;cout3:OPT 页面置换endl;10 cout按其它键结束程序；c;if(c=1)/FIFO 页面置换 n=0;cout *endl;coutendl;cout FIFO 算法页面置换情况如下:endl;coutendl;cout *endl;while(i=0)/当前页面在内存中 coutpi.num ;/

11、输出当前页 pi.numcout不缺页endl;i+;/i 加 1 else/当前页不在内存中 if(t=M)t=0;else n+;/缺页次数加 1 paget.num=pi.num;/把当前页面放入内存中 coutpi.num ;print(page);/打印当前页面 t+;/下一个内存块i+;/指向下一个页面 cout缺页次数：n 缺页率：n/mendl;if(c=2)/LRU 页面置换 n=0;cout *endl;11coutendl;cout LRU 算法页面置换情况如下:endl;coutendl;cout *endl;while(i=0)/如果已在内存块中 paget.time

12、=0;/把与它相同的内存块的时间置 0for(a=0;aM;a+)if(a!=t)pagea.time+;/其它的时间加 1 coutpi.num ;cout不缺页endl;else/如果不在内存块中 n+;/缺页次数加 1 t=Max(page);/返回最近最久未使用的块号赋值给 t paget.num=pi.num;/进行替换 paget.time=0;/替换后时间置为 0 coutpi.num ;print(page);for(a=0;aM;a+)if(a!=t)pagea.time+;/其它的时间加 1 i+;cout缺页次数：n 缺页率：n/mendl;if(c=3)/OPT 页面置

13、换 n=0;cout *endl;coutendl;12cout OPT 算法置换情况如下:endl;coutendl;cout *endl;while(i=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 ;print(page);i+;elseint temp=0,s;for(

14、t=0;tM;t+)/寻找内存块中下次使用离现在最久的页面if(tempCount(page,i,t,p)13temp=Count(page,i,t,p);s=t;/把找到的块号赋给 spages.num=pi.num;n+;coutpi.num ;print(page);i+;cout缺页次数：n 缺页率：n/mendl;while(c=1|c=2|c=3);return 0;五运行结果演示 141516六.设计心得通过这次课程设计，不仅让我了解了三种页面置换算法，即 FIFO（先进先出）、LRU（最近最久未使用）、OPT（最佳置换）算法。开始我对源代码一味的进行调试，但发现总是有点错误，于

15、是调试了若干次还是没有编译成功。又重新分析了几次设计要求，发现自己事先没有完全弄清楚这三种算法的做法，接着便是暂时停下程序的编译，将学习资料仔细地将这三种不同的算法研究了一下，待到基本弄懂它们具体怎么实现的时候，我才再一次去研究当初总是有问题的代码，结合课本知识与详细的流程图分析，经过不断的调试，多次尝试后，编译成功了，运行后发现此功能正是本次课程设计所需要的。本次课程设计不仅让我对操作系统这门课程有了更深入的研17究、对很多重要的概念有了巩固和掌握。通过努力，三个页面置换算法程序都已经完成。虽然自己所做的很少也不够完善，但毕竟也是努力的结果。主要有以下几点收获：1.通过对上网和看书查阅相关资料，使自己对 VC+语言的基本框架有新的了解，加深了对可视化程序的认识。2.在使用 VC+语言来实现功能时，不像以往用的其他语言，它比较简练，更容易理解，实用性很强。3.先进先出页面置换和 LRU 以及 OPT 算法各有特点，但是实践起来却很大，使自己对页面置换算法有了新的认识。一周半的课程设计就要结束了，不但对专业知识有了更深的理解，更使的自己认识到实践的重要性，理论、实践相结合才能达到很好的学习效果，特别是程序语言的学习。7参考文献计算机操作系统教程 徐甲同等编著 操作系统 罗宇等编著 操作系统实验教程 张丽芬,刘利雄,王全玉编著 计算机操作系统 梁红兵、哲风屏、汤子瀛 编著18