页面置换算法-课程设计报告

第第页课程设计报告设计题目：页面置换算法班级：科技一班组长学号：组长姓名：指导教师：设计时间：2017年3月设计分工组长学号及姓名：E11414103叶传军分工：算法设计，整体构架，课程实验报告成绩：95组员1学号及姓名：E11414101周坚坚分工：界面设计，代码整理，背景制作成绩：96目录摘要 ４1.设计目的 ５2.课设要求 ５3.系统分析 ６4.系统设计 ６4.1问题分析 ６4.2程序整体框图 ７4.3FIFO算法 ８4.4LRU算法 ９4.5OPT算法 １０4.6LFR算法 １１5.功能与测试 １２6.结论 １４7.心得体会 １５８.附录 １５摘要随着计算机的普及，人们生活得到极大改善，人们在精神方面也同样需要提高，所以越来越多的人进行着各种各样的学习。操作系统是计算机中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。操作系统的好坏，直接影响整个计算机系统的性能和用户对计算机的使用。一个精心的操作系统能极大的扩展计算机的性能，充分发挥系统中的各种设备的使用效率，提高系统的可靠性。由于操作系统中各种软硬件资源的管理，内容比较繁琐，具有很强的实践性，要学好这门课程，必须把理论和实践紧密结合，才能取得较好的学习效果。本次课程设计是在学完操作系统后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理以及实现方法，加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。熟悉页面置换算法及其实现，引入计算机操作性能评价方法的概念。关键词：页面置换算法，LRU算法，OPT算法，FIFO算法，LFR算法1.设计目的1、存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本次设计的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。2、提高自己的程序设计能力、提高算法设计质量与程序设计素质；2.课设要求设计一个请求页式存储管理方案。并编写模拟程序实现之。要求包含：1．过随机数产生一个指令序列，共320条指令。其地址按下述原则生成：①50%的指令是顺序执行的；②25%的指令是均匀分布在前地址部分；③25%的指令是均匀分布在后地址部分；具体的实施方法是：在[0，319]的指令地址之间随机选区一起点M;顺序执行一条指令，即执行地址为M+1的指令；在前地址[0，M+1]中随机选取一条指令并执行，该指令的地址为M’;顺序执行一条指令，其地址为M’+1；在后地址[M’+2，319]中随机选取一条指令并执行；重复A—E，直到执行320次指令。2．指令序列变换成页地址流设：（1）页面大小为1K；用户内存容量为4页到32页；用户虚存容量为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条—第9条指令为第0页（对应虚存地址为[0，9]）；第10条—第19条指令为第1页（对应虚存地址为[10，19]）；。。。。。。。。。。。。。。。。。。。。。第310条—第319条指令为第31页（对应虚存地址为[310，319]）；按以上方式，用户指令可组成32页。3.计算并输出下述各种算法在不同内存容量下的命中率。FIFO先进先出的算法LRU最近最少使用算法OPT最佳淘汰算法（先淘汰最不常用的页地址）LFR最不经常使用算法3.系统分析在多道程序环境下，要使程序运行，必须先为之创建进程。而创建进程的第一步是将程序和数据装入内存。存储器实现的功能主要是内存分配等功能，本模拟系统所要实现的就是将进程的程序和数据装入内存（物理块）。具体需要实现的功能如下：1、读入进程大小，进行分页，确定每一页的指令地址范围；2、读入一个指令，确定其所在页面，读入内存物理块中。物理块空闲直接读入，物理块已满，指向下步操作。3、物理块已满，将要淘汰原来首先进入到内存中的页面，即换出；然后将现在的指令地址页面读入物理块中，即换入。4.系统设计4.1问题分析分页存储管理，是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为物理块，在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应的关系。一个页表中包含若干个表目，表目的自然序号对应于用户程序中的页号，表目中的块号是该页对应的物理块号。请求页式存储管理方式是一种实现虚拟存储器的方式，是指在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面。当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面。请求页式存储管理主要需要解决以下问题：系统如何获知进程当前所需页面不在主存；当发现缺页时，如何把所缺页面调入主存；当主存中没有空闲的页框时，为了要接受一个新页，需要把老的一页淘汰出去，根据什么策略选择欲淘汰的页面。4.2程序整体框图Main()函数Main()函数LRULRU算法FIFO算法LFRLFR算法OPT算法图4-1程序整体框图由于该算法规模较小，可以将该系统划分为四块，分别是：FIFO算法模块、LRU算法模块、OPT算法模块、LFR算法模块。4.3FIFO算法基于程序总是按线形顺序来访问物理空间这一假设，总是淘汰最先调入主存的页面，即淘汰在主存中驻留时间最长的页面。开始开始初始化函数还有指令在队列中查找将数组中第一个数据移除，并置标志位找到了吗将新加入的指令加入数组尾部结束4.4LRU算法LRU置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预NYY是否有空闲页面？找到？在页面中查找是否存在开始还有指令吗？计算出页号count=0将该页导入内存页面，NYY是否有空闲页面？找到？在页面中查找是否存在开始还有指令吗？计算出页号count=0将该页导入内存页面，count=0所有页面count+1从内存页面找出count最大的页面做空闲页面计算出命中率结束NN4.5OPT算法NY是否有空闲页面？NY是否有空闲页面？按早指令队列查找以后指令出每一面命中的距离，找出最大的或没命中的当空闲页面找到？在面中查找是否存在开始还有指令吗？计算出页号将该页导入空闲页面计算出命中率结束NYYN4.6.LFR算法在缺页中断发生时，置换未使用时间最长的页面。NNYY是否有空闲页面？找到？在页面中查找是否存在开始还有指令吗？计算出页号count=0将该页导入内存页面，count=0所有页面count+1从内存页面找出count最大的页面做空闲页面计算出命中率结束NN５.功能与测试用户进入系统之后，会有一个选择算法的界面，如下图所示：选择页数，然后点击产生页地址流，生成随机地址流并转换成页面号，如下图所示：然后点开始计算，结果如下图所示：６.结论对于页面算法，我们平时上课时，只是知道了页面置换算法是怎么做的，并没有想如何去实现这些算法。在真正要做的时候才发现了问题。在这次课程设计的过程中，由于之前大家对可视化程序设计不怎么熟悉，在写代码的时候有了许多的麻烦。最后，在小组成员耐心看了一些C#的书，并且多方实践，终于完成了这次课程设计。通过该设计，我们学会了存储器的管理内容，利用C#语言实现进程装入内存的的过程，同时也对存储器管理的多种装入方式及内存分区有了更深的了解，特别是页面置换算法的应用。但也应看到对于实际的存储器应用还有很多地方不能实现真实，在今后的学习中应对所学知识做更深入的挖掘，对于各种算法应用更好的利用。７．心得体会本次课程设计不仅让我对操作系统这门课程有了更深入的研究、对很多重要的概念有了巩固和掌握。通过努力，三个页面置换算法程序都已经完成。虽然自己所做的很少也不够完善，但毕竟也是努力的结果。主要有以下几点收获：1.通过对上网和看书查阅相关资料，使自己对ＭＦＣ的基本框架有新的了解，加深了对可视化程序的认识。2.在使用Ｃ＋＋语言来实现功能时，不像以往用的其他语言，它比较简练，更容易理解，实用性很强。3.先进先出页面置换和LRU以及OPT算法各有特点，但是实践起来却很大，使自己对页面置换算法有了新的认识。另外，和同学的合作也让我收获了许多，本来做界面是我的短板，但却是同学的强项，和他合作让我在这方面也有很大收获，学到了不少东西。８.参考文献计算机操作系统第四版；基于VisualC++的ＭＦＣ编程；基于C8051F单片机直流电动机反馈控制系统的设计与研究基于单片机的嵌入式Web服务器的研究MOTOROLA单片机MC68HC（8）05PV8/A内嵌EEPROM的工艺和制程方法及对良率的影响研究基于模糊控制的电阻钎焊单片机温度控制系统的研制基于MCS-51系列单片机的通用控制模块的研究基于单片机实现的供暖系统最佳启停自校正（STR）调节器单片机控制的二级倒立摆系统的研究基于增强型51系列单片机的TCP/IP协议栈的实现基于单片机的蓄电池自动监测系统基于32位嵌入式单片机系统的图像采集与处理技术的研究基于单片机的作物营养诊断专家系统的研究基于单片机的交流伺服电机运动控制系统研究与开发基于单片机的泵管内壁硬度测试仪的研制基于单片机的自动找平控制系统研究基于C8051F040单片机的嵌入式系统开发基于单片机的液压动力系统状态监测仪开发模糊Smith智能控制方法的研究及其单片机实现一种基于单片机的轴快流CO〈,2〉激光器的手持控制面板的研制基于双单片机冲床数控系统的研究基于CYGNAL单片机的在线间歇式浊度仪的研制基于单片机的喷油泵试验台控制器的研制基于单片机的软起动器的研究和设计基于单片机控制的高速快走丝电火花线切割机床短循环走丝方式研究基于单片机的机电产品控制系统开发基于PIC单片机的智能手机充电器基于单片机的实时内核设计及其应用研究基于单片机的远程抄表系统的设计与研究基于单片机的烟气二氧化硫浓度检测仪的研制基于微型光谱仪的单片机系统单片机系统软件构件开发的技术研究基于单片机的液体点滴速度自动检测仪的研制基于单片机系统的多功能温度测量仪的研制基于PIC单片机的电能采集终端的设计和应用基于单片机的光纤光栅解调仪的研制气压式线性摩擦焊机单片机控制系统的研制基于单片机的数字磁通门传感器基于单片机的旋转变压器-数字转换器的研究基于单片机的光纤Bragg光栅解调系统的研究单片机控制的便携式多功能乳腺治疗仪的研制基于C8051F020单片机的多生理信号检测仪基于单片机的电机运动控制系统设计Pico专用单片机核的可测性设计研究基于MCS-51单片机的热量计基于双单片机的智能遥测微型气象站MCS-51单片机构建机器人的实践研究基于单片机的轮轨力检测基于单片机的GPS定位仪的研究与实现基于单片机的电液伺服控制系统用于单片机系统的MMC卡文件系统研制基于单片机的时控和计数系统性能优化的研究基于单片机和CPLD的粗光栅位移测量系统研究单片机控制的后备式方波UPS提升高职学生单片机应用能力的探究基于单片机控制的自动低频减载装置研究基于单片机控制的水下焊接电源的研究基于单片机的多通道数据采集系统基于uPSD3234单片机的氚表面污染测量仪的研制基于单片机的红外测油仪的研究96系列单片机仿真器研究与设计基于单片机的单晶金刚石刀具刃磨设备的数控改造基于单片机的温度智能控制系统的设计与实现基于MSP430单片机的电梯门机控制器的研制基于单片机的气体测漏仪的研究基于三菱M16C/6N系列单片机的CAN/USB协议转换器基于单片机和DSP的变压器油色谱在线监测技术研究基于单片机的膛壁温度报警系统设计基于AVR单片机的低压无功补偿控制器的设计基于单片机船舶电力推进电机监测系统基于单片机网络的振动信号的采集系统基于单片机的大容量数据存储技术的应用研究基于单片机的叠图机研究与教学方法实践基于单片机嵌入式Web服务器技术的研究及实现基于AT89S52单片机的通用数据采集系统基于单片机的多道脉冲幅度分析仪研究机器人旋转电弧传感角焊缝跟踪单片机控制系统基于单片机的控制系统在PLC虚拟教学实验中的应用研究基于单片机系统的网络通信研究与应用基于PIC16F877单片机的莫尔斯码自动译码系统设计与研究基于单片机的模糊控制器在工业电阻炉上的应用研究基于双单片机冲床数控系统的研究与开发基于Cygnal单片机的μC/OS-Ⅱ的研究基于单片机的一体化智能差示扫描量热仪系统研究基于TCP/IP协议的单片机与Internet互联的研究与实现变频调速液压电梯单片机控制器的研究基于单片机γ-免疫计数器自动换样功能的研究与实现基于单片机的倒立摆控制系统设计与实现单片机嵌入式以太网防盗报警系统基于51单片机的嵌入式Internet系统的设计与实现单片机监测系统在挤压机上的应用MSP430单片机在智能水表系统上的研究与应用基于单片机的嵌入式系统中TCP/IP协议栈的实现与应用单片机在高楼恒压供水系统中的应用基于ATmega16单片机的流量控制器的开发基于MSP430单片机的远程抄表系统及智能网络水表的设计基于MSP430单片机具有数据存储与回放功能的嵌入式电子血压计的设计基于单片机的氨分解率检测系统的研究与开发锅炉的单片机控制系统基于单片机控制的电磁振动式播种控制系统的设计基于单片机技术的WDR-01型聚氨酯导热系数测试仪的研制一种RISC结构8位单片机的设计与实现\t