操作系统 设计说明书

1、操作系统 设计说明书学院名称： 计算机与信息工程学院 班级名称： 计 科 112班 学生姓名： 夏宗斌、柴远亮、王辉、王周军、陈敏 学 号： 、 、 题 目： 页面置换算法实现与分析 指导教师： 胡 成 祥 起止日期： 2013年6月3日2013年6月30日 目录1.选题背景32.方案论证32.1 任务分析32.2 任务目的32.3 方案设计43.过程论述53.1 FIFO(先进先出)53.2 LRU(最近最久未使用)83.3 OPT(最佳置换算法)104.结果分析144.1实现结果144.2程序测试185.结论19参考文献20代码201.选题背景随着计算机的普及人们的物质生活得到了极大的满足

2、，人们在精神生活方面同样也需要提高，所以越来越多的人进行着各种各样的学习。操作系统是计算机教学中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。操作系统质量的好坏，直接影响整个计算机系统的性能和用户对计算机的使用。一个精心设计的操作系统能极大地扩充计算机系统的功能，充分发挥系统中各种设备的使用效率，提高系统工作的可靠性。在各种存储器管理方式中，有一个共同的特点，即它们都要求将一个作业全部装入内存方能运行，但是有两种情况：（1）有的作业很大，不能全部装入内存，致使作业无法运行；（2）有大量作业要求运行，但内存容量不足以容纳所有这些作业。而虚拟内存技术正式从逻辑上扩充内存容量，将会解决以

3、上两个问题。从内存中调出一页程序或数据送磁盘的对换区中，通常，把选择换出的页面的算法称为页面置换算法（Page-Replacement Algorithms）。进而页面置换算法模拟程序能客观的将其工作原理展现在我们面前。2.方案论证2.1 任务分析首先，定义宏变量，设置所占最大内存长度。编辑以时间为种子，初始化随即发生器。进行相关页面输入程序的编写以及页面的打印。然后，寻找最近最久未使用的页面 、记录当前内存块中页面离下次使用间隔长度等相关程序的代码编写。最后，进行FIFO 、LRU、 OPT三种算法的编写。2.2 任务目的1. 通过模拟实现请求页式存储管理的几种页面置换算法，了解虚拟存储技术

4、的特点。2. 通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。3. 掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。2.3 方案设计1. 用随机数方法产生页面走向，页面走向长度为L。2. 根据页面走向，分别采用FIFO和LRU算法进行页面置换，统计缺页率；为简化操作，在淘汰一页时，只将该页在页表中抹去,而不再判断它是否被改写过，也不将它写回到辅存。3. 假定可用内存块和页表长度 (作业的页面数)分别为m和k，初始时，作业页面都不在内存。随机数产生程序： int i,j; j=time(NULL);/取时钟时间

5、srand(j);/以时钟时间x为种子，初始化随机数发生器 cout输出随机数: ; for(i=0;im;i+) pi.num=rand( )%10+1;/产生1到10之间的随即数放到数组p中 pi.time=0; coutpi.num ; 上述随机数发生函数产生的随机数为0.01.0，稍另变化就可得到0n-1之间的随机数。程序开始时，应对变量Seed (实型)赋初值。根据页面置换算法的理论操作及要求，首先要进行页面长度的确定，定义结构体用以储存数据，进行主界面代码及OPT、FIFO、LRU页面置换算法代码的编写。3.过程论述3.1 FIFO(先进先出)算法思想：需要进行页面置换，即把内存中

6、装入最早的那个页面淘汰，换入当前的页面。算法流程图：图3.1 FIFO算法流程图核心代码：if(c=1)/FIFO页面置换n=0;cout * endl;coutendl;cout FIFO算法页面置换情况如下: endl;coutendl;cout * endl;while(i=0)/当前页面在内存中 coutpi.num ;/输出当前页pi.numcout不缺页endl;i+;/i加1else /当前页不在内存中if(t=M)t=0;elsen+;/缺页次数加1paget.num=pi.num; /把当前页面放入内存中coutpi.num ;print(page); /打印当前页面t+;

7、/下一个内存块i+; /指向下一个页面cout缺页次数：n 缺页率：n/mendl;3.2 LRU(最近最久未使用)算法思想：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰该算法的主要出发点是，如果某页被访问了，则它可能马上还要被访问。或者反过来说如果某页很长时间未被访问，则它在最近一段时间也不会被访问。算法流程图：图3.2 LRU算法流程图核心代码：if(c=2)/LRU页面置换n=0;cout * endl;coutendl;cout LRU算法页面置换情况如下: endl;coutendl;cout * endl;while(i=0) /如果已在内存块中pag

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

9、算法)算法思想：需要进行页面置换，把内存中以后一段时间都不使用或是使用时间离现在最远的页面换出。算法流程图：图3.3 OPT算法流程图核心代码：if(c=3) /OPT页面置换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;t

10、t)q=t; /把空内存块中块号最小的找出来pageq.num=pi.num;n+;coutpi.num ;print(page);i+;elseint temp=0,s;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;4.结果分析4.1实现结果程序在运行的情况下，进入主界面输入菜单，如图4.1所示：输入11：图4

11、.1输入11的输出图输入24：图4.2输入24的输出图输入16：图4.3输入16的输出图输入2：图4.4输入2的输出图输入6：图4.5输入6的输出图输入3：图4.6输入3的输出图选1，进入FIFO页面置换：图4.7 FIFO的输出图选2，进入LRU页面置换：图4.8 LRU的输出图输入3，进入OPT页面置换：图4.9 OPT的输出图4.2程序测试设计测试数据：A 11 24 16；B 2 6 3；B 1C 2D 3测试结果及分析：1）测试A结果及分析 进入主菜单后输入11、24，显示输入不满足要求。输入16显示相关信息;输入2、6不满足要求，输入3显示出相关信息。2）测试B结果及分析：显示出F

12、IFO页面置换算法的缺页信息及缺页率。3）测试C结果及分析：显示出LRU页面置换算法的缺页信息及缺页率。4）测试D结果及分析：显示出OPT页面置换算法的缺页信息及缺页率5.结论这次实验的目的是模拟虚拟存储的页面置换算法，请求页式虚存管理是常用的虚拟存储管理方案之一。通过请求页式虚存管理中对页面置换算法的模拟，有助于理解虚拟存储技术的特点，并加深对请求页式虚存管理的页面调度算法的理解。这次实验我采用的是先进先出算法。在程序中主要是设计了如下几个数据结构：pv_type用来表示虚页的有关信息，pf_type用来表示内存中实页的有关信息。同时还用到了两个链表free和busy，分别用来表示空闲实页面

13、和已经存有虚页的忙页面。在进行页面置换时，要同时更改free和busy链表中的虚页号和实页号，free链表中的虚页号应该改到默认状态。当内存中不存在下一个要调入内存的虚页且内存中已经没有空闲页面时，那么将发生页面置换。 通过这次实验使我对页面置换算法有了进一步的了解，加强了自己的动手能力和编程的能力，巩固了课堂上所学的知识。参考文献计算机操作系统第三版，编著人：梁小兵，梁晓丹，唐子瀛等。C+语言程序设计第四版，编著人：董渊，何江舟等。代码#include#include #include #include #define L 20/页面走向长度最大为20int M; /内存块struct Pr

14、o/定义一个结构体 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为种子，初始化随机数发生器cout输出随机数: ; for(i=0;im;i+) pi.num=rand( )%10+1;/产生1到10之间的随即数放到数组p中 pi.time=0;coutpi.num ; coutendl; re

15、turn 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 i=0;iM;i+)if(e=pagei.num)return i;/返回i值 return -1;int Max(Pro *page1)/寻找最近最长未使用的页面 Pro *page=new ProM;

16、 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 pL)/记录当前内存块中页面离下次使用间隔长度 Pro *page=new ProM; page=page1; int count=0; for(int j=i;jL;j+) if(paget.num=

17、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 break;while(1); Pro *page=new ProM; do for(int i=0;iM;i+)/初试化页面基本情况 pagei.num=0; pagei.time=m-1-i; i=0

18、; cout1:FIFO页面置换endl; cout2:LRU页面置换endl; cout3:OPT页面置换endl; cout按其它键结束程序；c; system(cls); if(c=1)/FIFO页面置换 n=0;cout * endl;coutendl; cout FIFO算法页面置换情况如下: endl;coutendl; cout * endl; while(i=0) /当前页面在内存中 coutpi.num ; /输出当前页pi.numcout不缺页endl;i+; /i加1 else /当前页不在内存中 if(t=M)t=0; else n+; /缺页次数加1 paget.nu

19、m=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.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