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