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