温州大学物理与电子信息工程学院PAGE\*MERGEFORMAT27物理与电子信息工程学院《操作系统》课程设计报告题目：1、页面淘汰算法2、磁盘调度算法班级：10计本完成日期：2012.9.13指导教师：曾令华操作系统课程设计设计目的：掌握基本操作系统理论根据操作系统理论算法编写相应的调度程序使用多种算法在特定的数据下比较其优点与缺陷尝试改进相应数据结构，使调度更加简易、明显锻炼实践能力为后继课程奠定基础设计环境：WindowsXp操作系统或者Linux（ubuntu12.04）MicrosoftVisualC++6.0编译器或者GUNG++，Matlab数学统计分析软件编辑插件：VAView、VimShell运行良好，无特殊异常设计内容（全部设计内容）：小组从进程调度算法实现页面淘汰算法实现磁盘调度算法实现实际磁盘管理方式演示实现二级文件系统设计实现经过小组参考与讨论，最终绝对选定b(页面淘汰算法实现)、c(磁盘调度算法实现)。设计要求：页面淘汰算法实现设计要求：设计随机页面序号产生程序，并说明随机的性能和其性能可能对算法的影响要求有一定的参数控制能力，可以用户自己调节随机性能编写页面淘汰算法本身结果数据的显示或提取结果数据的分析磁盘调度算法实现设计要求：设计随机磁道访问产生程序，并说明随机的性能和其性能可能对算法的影响要求有一定的参数控制能力，可以用户自己调节随机性能编写磁盘调度算法本身结果数据的显示或提取结果数据的分析设计原理：页面淘汰算法原理：页面淘汰算法定义与简介：在进程运行过程中，若其要访问的页面不在内存而需把它们调入内存，但内存已经无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面淘汰算法或者页面置换算法（Page-ReplacementAlgorithms）。置换算法的好坏，将直接影响到系统的性能。一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不会再访问的页面换出，或把那些在较长时间内不会再访问的页面调出。目前存在着许多页面置换算法，它们都试图更接近于理论上的目标。先进先出（FIFO）页面置换算法这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留实践最久的页面予以淘汰。该算法实现简单，只需把一个进程调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如含有全局变量、常用函数、例程等地页面，FIFO算法并不能保证这些页面不被淘汰。具体实现流程图如下：新的指令页面内存所有页面time++载入新页面time=0内存所有页面time++选择time最大的页面换出在内存理块？物理块已满？注：在FIFO算法中，无论有无发生缺页或者置换，都需要对每个在内存中的页面的time值进行增加操作，以保持最先进入的那个页面的time值是最大的；一个新进来的页面，其time值设置为0。算法也可以通过队列结构来实现，利用队列的先进先出（FIFO）特性完成，无需设置time字段。数据结构介绍：算法源程序：（见附录）。、最佳置换法（OPT）背景与简介：它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用此算法来评价其它算法。具体流程图如下：内存物理块集合已满载入该页面对内存中每个页面，前后遍历剩余指令集合，记录每个页面距离再次使用跨度选择跨度最大的页面换出存在所有集合已满注：distance用于记录内存物理块集合中每个页面距离再次被使用的页面跨度，缺省值为INT_MAX，如果某个页面在后续指令集合中不再出现，则用最大值INT_MAX缺省取代；如果页面再次被使用，则两次使用所跨的页面数，为页面跨度。用最大页面跨度表示以后永不使用或未来最长时间内不再被访问。1.3.1、数据结构介绍：1.3.2、算法源程序：（见附录）1.4、最近最久未使用（LRU）页面置换算法：最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来