1、作操系统课程设计模拟页式存储管理大学论文操作系统课程设计报告 模拟页式存储管理院 系： 计算机科学技术学院 班 级： *班 姓 名： * 学 号： *指导教师： *8 2016年12月9日操作系统原理课程设计任务书一、题目：磁盘调度 二、设计要求（1）*（组长）、*负责设计与实现。（2）查阅相关资料，自学具体课题中涉及到的新知识。（3）采用结构化、模块化程序设计方法，功能要完善，具有一定的创新。（4）所设计的程序应有输入、输出。（5）按要求写出课程设计报告，并于设计结束后1周内提交。其主要内容包括：封皮、课程设计任务书，指导教师评语与成绩、目录、概述、软件总体设计、详细设计、软件的调试、总结、
2、谢启、附录：带中文注释的程序清单、参考文献。报告一律用A4纸打印，中文字体为宋体，西文字体用Time New Roma，一律用小四号字，行距采用“固定值”18磅，首行缩进2字符。总体设计应配合软件总体模块结构图来说明软件应具有的功能。详细设计应用传统或N-S流程图和屏幕抓图说明，调试的叙述应配合出错场景的抓图来说明出现了哪些错误，如何解决的。三、课程设计工作量由于是设计小组团结协作完成设计任务，一般每人的程序量在200行有效程序行左右，不得抄袭。四、课程设计工作计划2016年11月28日，指导教师讲课，学生根据题目准备资料；2016年11月29日2016年12月1日，进行总体方案设计；2016
3、年12月3日2016年12月5日，完成程序模块并通过独立编译；2016年12月6日2016年12月7日，将各模块集成为一个完整的系统，并录入足够的数据进行调试运行；2016年12月8日2016年12月9日，验收、撰写报告； 指导教师签章： 教研室主任签章 操作系统原理课程设计指导教师评语与成绩指导教师评语：课程设计表现成绩： 课程设计验收成绩： 课程设计报告成绩： 课程设计 总成绩： 指导教师签章 2016年12 月9日目 录第一章 引言 1第二章 设计目的及要求 12.1 设计目的 12.2 设计要求 1第三章 概要设计 23.1 系统功能结构 23.2 程序文件详细说明 33.3 整体流程
4、图 3第四章 详细设计 44.1 数据定义 44.2算法分析 44.3核心代码与运行效果 6第五章 软件调试 185.1 系统测试 185.2 算法效率分析和对比 19参考文献 19第六章 课程设计总结 20第七章 致 谢 21第一章 引言 在进程运行过程中，若其所要访问的页面不在内存，而需要把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送到磁盘的对换区中。单应将哪个页面调出，需根据一定的算法来确定。通常，把选择换出的页面的算法称为页面置换算法。页面置换算法的好坏直接影响到系统的性能。 不适当的算法可能会导致进程发生“抖动”，即刚被换出的页很
5、快又要被访问，需要将它重新调入，此时又需要再选一页调出；而此刚被调出的页面很快又被访问，又需将它调入，如此频繁地更换页面，以致一个进程在运行中把大部分时间都花费在页面置换工作上。 一个好的页面置换算法应具有较低的页面更换频率。从理论上讲，应将那些以后不再访问的页面换出，或把那些在较长时间内不会再访问的页面调出。目前已有多种页面置换算法，它们都试图更接近于理论上的目标。第二章 设计目的及要求2.1 设计目的 通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。2.2 设计要求 根据模拟的页式管理设计，掌握在页式存储管理中最基本的三种页面调度算法
6、FIFO、LRU以及OPT。但在三种算法中均要求在调度程序中产生的页面序列是随机产生的，而不是人为的输入，在执行时只需改变页面的大小及内存容量就可以得到不同的页面序列，另外还需要说明随机的性能和其性能可能对算法的影响，并对随机性要有一定的参数控制能力。此外，计算并输出FIFO、LRU以及OPT算法在不同内存容量下的命中率。根据方法的执行过程，编写一个解决上述问题的程序，显示访问每个值页面中的值。具体参数：访问串的长度，访问串，页面个数。分别用3种不同的方法实现页面的置换，并输出相关信息。第三章 概要设计3.1 系统功能结构图3-1 系统功能结构图3.2 程序文件详细说明软件内设置五个文件，其中
7、一个h文件，包含所有使用到的头文件，宏定义等等（此处不多加赘述），4个c文件，分别是main文件，function文件，init文件，algorithms文件。 1.main文件：main文件主要包含main函数的代码以及一些全局变量的定义。 2.init文件：该文件中有界面设计以及算法参数初始设置文件，其中包含两个函数。 3. function文件：该文件中主要包含一些算法要用到的底层函数。 4. algorithms文件：该文件中有三个算法设计分别是FIFO算法，LRU算法，OPT算法 3.3 整体流程图图3-3 系统整体流程图第四章 详细设计4.1 数据定义typedef struct
8、page bool flag10;/标志位，标志该页是否在内存中 int address10;/页内地址，初始为-1 int time10;/生存时间 ，初始为0 int times;Page;extern int a100; /extern表示此变量是在别处定义的要在此处引用 extern int memo100;extern int page_degree;/页面个数 extern int memo_degree;/内存大小extern int suanfa_flag;/算法标志 4.2算法分析要学成功实现算法，首先要知道各个方法是怎么做的，即原理是怎样的，下面是三种算法的原理。FIFO算
9、法是先进先出，当当前内存中没有正要访问的页面时，置换出最先进来的页面。LRU算法是最近最久未使用，当当前内存中没有正要访问的页面时，置换出在当前页面中最近最久没有使用的页面。OPT算法是未来最远出现，当当前内存中没有正要访问的页面时，置换出当前页面中在未来的访问页中最远出现的页面或再也不出现的页面。4.2.1 程序流程图本次课程设计的主要流程是3种置换算法的流程图，流程图如下所示：图4-2-1 FIFO算法流程图 图4-2-2LRU算法流程图 4.3核心代码与运行效果FIFO算法：int FIFO( int num) int i,j,time_loc,meflag=0,meloc=0; Pag
10、e fifo; fifo.times=0; for(i=0;inum;i+) memoi=-1; if(suanfa_flag=1) printf(页表初始状态n); printf(number address flag time n); for(i=0;i10;i+)/对页表初始化 fifo.flagi=false; fifo.addressi=-1; fifo.timei=0; if(suanfa_flag=1) printf(%6d ,i); printf(%7d ,fifo.addressi); printf(%4d ,fifo.flagi); printf(%4d n,fifo.ti
11、mei); if(suanfa_flag=1) printf(n); for(i=0;ipage_degree;i+) if(suanfa_flag=1) printf(enter进行页面置换n); system(pause); meflag=0;/初始化内存标志表示内存不空 for(j=0;jnum;j+)/判断内存是否为空 if(memoj=-1) meflag=1;/内存为空标志为1 meloc=j;/如果为空记下内存地址 break; if(meflag=1) if(fifo.flagai=true) if(suanfa_flag=1) printf(此时页面在内存中，不需要调入内存n
12、); else /加入内存 fifo.times+; fifo.flagai=true; fifo.addressai=meloc; memomeloc=ai;/内存保存页号 if(suanfa_flag=1) printf(本次内存未满，可直接调入,); printf(调入页面为：%dn,ai); else for(j=0;j10;j+) if(fifo.flagj=true) time_loc=j; break; /找到第一个在页内的页号 for(;j10;j+) if(fifo.flagj=true) if(fifo.timetime_locfifo.timej) time_loc=j;
13、 if(fifo.flagai=true) if(suanfa_flag=1) printf(%d号页面在内存中，不需要调入内存n,ai); else /淘汰页面 fifo.times+; fifo.flagtime_loc=false; fifo.timetime_loc=0; fifo.flagai=true; /memomeloc=ai; fifo.addressai=fifo.addresstime_loc; fifo.addresstime_loc=-1; memofifo.addressai=ai; if(suanfa_flag=1) printf(本次调入,内存已满,需要淘汰页面
14、,淘汰页面为:%d,调入页面为:%dn,time_loc,ai); for(j=0;j10;j+) if(fifo.flagj=true) fifo.timej+; if(suanfa_flag=1) printf(当前内存状态:); if(suanfa_flag=1) for(j=0;jnum;j+) printf(%5d,memoj); printf(n); printf(当前页表：n); printf(number address flag time:%d n,ai); for(j=0;j10;j+) printf(%6d ,j); printf(%7d ,fifo.addressj);
15、 printf(%4d ,fifo.flagj); printf(%4d n,fifo.timej); if(suanfa_flag=1) printf(FIFO算法缺页次数为：%dn,fifo.times); printf(FIFO算法缺页中断率为：%d%n,fifo.times*(100/page_degree); if(suanfa_flag=0) printf(ttFIFOtt%dtt%d%ttn,fifo.times,fifo.times*(100/page_degree); return 0; FIFO算法部分运行截图：LRU算法：int LRU( int num) int i,j
16、,time_loc,meflag=0,meloc=0,k; Page lru; lru.times=0; for(i=0;inum;i+) memoi=-1; if(suanfa_flag=3) printf(页表初始状态n); printf(number address flag time n); for(i=0;i10;i+)/对页表初始化 lru.flagi=false; lru.addressi=-1; lru.timei=101; if(suanfa_flag=3) printf(%6d ,i); printf(%7d ,lru.addressi); printf(%4d ,lru.
17、flagi); printf(%4d n,lru.timei); if(suanfa_flag=3) printf(n); for(i=0;ipage_degree;i+) if(suanfa_flag=3) printf(enter进行页面置换n); system(pause); meflag=0;/初始化内存标志表示内存不空 for(j=0;jnum;j+)/判断内存是否为空 if(memoj=-1) meflag=1;/内存为空标志为1 meloc=j;/如果为空记下内存地址 break; if(meflag=1) if(lru.flagai=true) if(suanfa_flag=3
18、) printf(%d号页面在内存中，不需要调入内存n,ai); else /加入内存 lru.times+; lru.flagai=true; lru.addressai=meloc; memomeloc=ai;/内存保存页号 if(suanfa_flag=3) printf(本次内存未满，可直接调入,); printf(调入页面为：%dn,ai); else for(j=0;j10;j+) if(lru.flagj=true) time_loc=j; break; /找到第一个在页内的页号 /time_loc = 0; for(j=0;jlru.timej) time_loc=j; if(
19、lru.flagai=true) if(suanfa_flag=3) printf(%d号页面在内存中，不需要调入内存n,ai); else /淘汰页面 lru.times+; lru.flagtime_loc=false; lru.timetime_loc=0; lru.flagai=true; /memomeloc=ai; lru.addressai=lru.addresstime_loc; lru.addresstime_loc=-1; memolru.addressai=ai; if(suanfa_flag=3) printf(本次调入,内存已满,需要淘汰页面,淘汰页面为:%d,调入页
20、面为:%dn,time_loc,ai); for(j=0;j10;j+)/更新time数组 for(k=0;k=i;k+) if(ak=j) lru.timej=k; if(suanfa_flag=3) printf(当前内存状态:); for(j=0;jnum;j+) printf(%5d,memoj); printf(n); printf(当前页表：n); printf(number address flag timen); for(j=0;j10;j+) printf(%6d ,j); printf(%7d ,lru.addressj); printf(%4d ,lru.flagj);
21、printf(%4d n,lru.timej); if(suanfa_flag=3) printf(LRU算法缺页次数为：%dn,lru.times); printf(LRU算法缺页中断率为：%d%n,lru.times*(100/page_degree); if(suanfa_flag=0) printf(ttLRUtt%dtt%d%ttn,lru.times,lru.times*(100/page_degree); return 0;LRU算法部分运行截图：第5章 软件调试5.1 系统测试初始化界面选择算法界面算法比较模块 5.2 算法效率分析和对比 从上述结果可知,在内存页面数较少(45
22、页面)时,3种算法的命中率差别不 大,都是50%左右。在内存页面为725个页面之间时,3种算法的访内命中率大致在52%至87%之间变化。但是,FIFO算法与0PT算法之间的差别一般在610个百分点左右。在内存页面为2532个页面时,由于用户进程的所有指令基本上都已装入内存,从而命中率已较大。从而算法之间的差别不大。 比较上述5种算法,以OPT算法的命中率最高,其次是LRU算法,再次是FIF0算法。参考文献【1】 张尧学, 史美林. 计算机操作系统教程(第2版). 北京: 清华大学出版社, 2000【2】张尧学, 史美林. 计算机操作系统教程(第2版)习题解答与实验指导. 北京: 清华大学出版社
23、, 2000【3】谭浩强, 张基温. C语言程序设计教程. 高等教育出版社,1991第6章 课程设计总结为期两周的操作系统课设在不断的探索、努力、尝试、成功中结束了。现在站在成功地顶峰，回顾着走过的一路，真是有很多的感触，但是也学到了很多东西。在本次课程设计中，我们组选择了完成页面置换算法的实现，在本算法实现的过程中，我们分别实现了FIFO、OPT、LRU三个页面置换的算法，并对实现的结果进行了不断的细化和验证，以保证程序的完美性和正确性；下面我说一下我们认为我们这次的优点和不足：首先，先谈谈我们程序的缺点：第一，我们设计的页面置换算法的实现过程中，的确欠缺性能上的解决；第二，我们设计的程序因
24、为是用c实现的所以页面看起来不是很好看；虽然现在课程设计已经到了验收的阶段，但是我们还是会在之后的时间里不管尝试优化我们的程序，使其在性能上面和与页面设计上面都得到好的提高和改善。然后，再来谈谈我们程序的优点：第一，我们的程序实现了与操作员的交互，可以是操作员手动输入页面和内存的个数；第二，虽然OPT算法原本上是不可实现的，但是我们虽然使用的方法不是最优的，最终却得到了OPT算法的初步模拟实现；第三，我们对程序实现了低内聚高耦合的原则，将各个算法的功能模块分离开来，真正实现了互不干扰的形式；第四，我们的三个算法全部模拟实现，经过测试结果完全正确，且对各方面的异常处理恰当不会出现乱码或者重新执行
25、的可能。最后，我们认为虽然我们本次的程序可能会存在着一些小的问题，但是我们对本算法的最终实现还是得到了不错的结果，对于此处课设期间我们为自己总结了四句话：敢于挑战，能够忍耐寂寞、枯燥和劳累，坚持不懈善于探求登峰捷径且百折不挠。第7章 致 谢 看看论文即将完成，我们此刻内心有着很多的情感。 首先，感谢我们的胡晓宏老师，她给了我们很多的意见，在我们进行本次课程设计上面，她给了我们很多的关心，支持和帮助，我们在课设进行的过程中遇到了很多的困难，都是她给予我们了帮助，并给了我们好的意见，本次课程设计我们的实现取得了良好的效果，都是因为老师给我们的指导。 其次，我们在本次课程设计中，曾遇到了种种的困难，但是我们没有放弃过，这都是因为我们队友之间的相互扶持、相互鼓励，才使得我们能够最终选择了坚持下去，在这里我感谢我的队友，是因为有了你们
