(流程图)页面置换算法课程设计(总17页)

1、操作系统课程设计报告题目：页面置换算法模拟程序学院名称: 专业班级： 学生姓名： 指导教师： 成绩： 目录一、 设计目的 3二、设计题目32.1设计内容32.2设计要求3三、设计过程43.1 FIFO（先进先出）43.2 LRU（最近最久未使用）53.3 OPT（最佳置换算法）63.4 随机数发生器7四、完整代码 7五、运行结果演示13 六、设计心得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).要求写出一份详细的设计报告。课程设计报告内容包括：设计目的、设计内容、设计原理、算法实现、流程图、源程序、运行示例及结果分析、心得体会、参考资料等。 3 设计过程3.1 FIFO（先进先出）设计原理：需要进行页面置换，即把内存中装入最早的那个页面淘汰，换入当前的页面。算法流程图：Yi+把pi的内容直接装入最上面一个空内存块，i+把page中最先装入的页面置换出去.i+Page是否有空当前p中第i个

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

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

6、+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);/以时钟时间x为种子，初始化随机数发生器c

7、out输出随机数: ; for(i=0;im;i+) 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=page1; for(int

8、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,Pro

9、pL)/记录当前内存块中页面离下次使用间隔长度 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： ;else b

10、reak;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; 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;coutendl; cout LRU算法页面置换情况如下: endl; coutendl;cout * endl; while(i=0)/如果已在内存块中 paget

12、.time=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;cout 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;

14、for(t=0;tM;t+)/寻找内存块中下次使用离现在最久的页面if(tempCount(page,i,t,p)temp=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; 五运行结果演示 六.设计心得通过这次课程设计，不仅让我了解了三种页面置换算法，即FIFO（先进先出）、LRU（最近最久未使用）、OPT（最佳置换）算法。开始我对源代码一味的进行调试，但发现总是有点错误，于

15、是调试了若干次还是没有编译成功。又重新分析了几次设计要求，发现自己事先没有完全弄清楚这三种算法的做法，接着便是暂时停下程序的编译，将学习资料仔细地将这三种不同的算法研究了一下，待到基本弄懂它们具体怎么实现的时候，我才再一次去研究当初总是有问题的代码，结合课本知识与详细的流程图分析，经过不断的调试，多次尝试后，编译成功了，运行后发现此功能正是本次课程设计所需要的。本次课程设计不仅让我对操作系统这门课程有了更深入的研究、对很多重要的概念有了巩固和掌握。通过努力，三个页面置换算法程序都已经完成。虽然自己所做的很少也不够完善，但毕竟也是努力的结果。主要有以下几点收获：1.通过对上网和看书查阅相关资料，使自己对VC +语言的基本框架有新的了解，加深了对可视化程序的认识。2.在使用VC+语言来实现功能时，