1、 操作系统课程设计操作系统课程设计 磁盘调度模拟算法 学院： 专业： 学号： 姓名： 指导老师： 时间：2011/12/29 一、一、 实验内容实验内容 熟悉磁盘的结构以及磁盘的驱动调度算法的模拟， 编程实现简单常用的磁盘驱动调度算 法先来先服务（FIFO） 、电梯调度算法、最短寻找时间优先算法、扫描（双向扫描）算法、 单向扫描（循环扫描）算法等。编程只需实现两个算法。 题目可以选取教材或习题中的相关编程实例。 编程语言建议采用 c/c+或 Java。模拟程序鼓励采用随机数技术、动态空间分配技术，有条 件的最好能用图形界面展现甚至用动画模拟。 二、二、 设计目的设计目的 （1）在课本知识的基础
2、上，进一步了解操作系统的内容。 （2）提高学生的逻辑思维能力。 （3）培养学生能够独立编写程序的能力。 （4）熟悉磁盘各种调度算法及其各自的特点，能够区分不同的算法。 三、设计分析三、设计分析 1.先来先服务算法 （FCFS） 先来先服务 （FCFS） 调度:按先来后到次序服务， 未作优化。 最 简单的移臂调度算法是“先来先服务”调度算法，这个算法实际上不考虑访问 者要求访问 的物理位置， 而只是考虑访问者提出访问请求的先后次序。 例如， 如 果现在读写磁头正在 50 号柱面上执行输出操作，而等待访问者依次要访问的柱 面为 130、199、32、159、15、148、 61、99，那么，当 5
3、0 号柱面上的操作结束 后，移动臂将按请求的先后次序先移到 130 号 柱面，最后到达 99 号柱面。 采用先来先服务算法决定等待访问者执行输入输出操作的次序时， 移动臂来 回地移动。 先来先服务算法花费的寻找时间较长，所以执行输入输出操作的总时 间也很长。 2.短寻道时间优先算法（SSTF） 最短寻找时间优先调度算法总是从等待访问者中挑选寻找 时间最短的那个 请求先执行的，而不管访问者到来的先后次序。现在仍利用同一个例子来 讨论， 现在当 50 号柱面的操作结束后， 应该先处理 61 号柱面的请求， 然后到达 32 号 柱 面执行操作，随后处理 15 号柱面请求，后继操作的次序应该是 99、
4、130、148、 159、199。 采用最短寻找时间优先算法决定等待访问者执行操作的次序时， 读写磁头总 共移动了 200 多个柱面的距离，与先来先服务、算法比较，大幅度地减少了寻找 时间，因而缩短了 为各访问者请求服务的平均时间，也就提高了系统效率。 但最短查找时间优先（SSTF）调 度，FCFS 会引起读写头在盘面上的大范围移动， SSTF 查找距离磁头最短（也就是查找 时间最短）的请求作为下一次服务的对象。 SSTF 查找模式有高度局部化的倾向，会推迟 一些请求的服务，甚至引起无限拖 延（又称饥饿） 。 3.扫描算法（SCAN） SCAN 算法又称电梯调度算法。SCAN 算法是磁头前进方
5、向上的最 短查找时间 优先算法，它排除了磁头在盘面局部位置上的往复移动，SCAN 算法在很大程 度 上消除了 SSTF 算法的不公平性，但仍有利于对中间磁道的请求。 “电梯调度” 算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前 移动臂最 近的那个柱访问者，如果沿臂的移动方向无请求访问时，就改变臂的移 动方向再选择。这 好比乘电梯，如果电梯已向上运动到 4 层时，依次有 3 位乘客 陈生、伍生、张生在等候 乘电梯。 他们的要求是： 陈生在 2 层等待去 10 层； 伍 生在 5 层等待去底层； 张生在 8 层 等待 15 层。 由于电梯目前运动方向是向上， 所以电梯的形成是先把乘客张生从
6、 8 层带到 15 层，然后电梯换成下行方向，把 乘客伍生从 5 层带到底层，电梯最后再调换方向，把 乘客陈生从 2 层送到 10 层。 我们仍用前述的同一例子来讨论采用“电梯调度”算法的情况。由于磁盘移 动臂的初始 方向有两个，而该算法是与移动臂方向有关，所以分成两种情况来讨 论。 1.移动臂由里向外移动 开始时，在 50 号柱面执行操作的读写磁头的移动臂方向是由里向外，趋向 32 号柱面 的位置，因此，当访问 50 号柱面的操作结束后，沿臂移动方向最近的 柱面是 32 号柱面。 所以应先为 32 号柱面的访问者服务，然后是为 15 号柱面的 访问者服务。之后，由于在 向外移方向已无访问等待者，故改变移动臂的方向， 由外向里依次为各访问者服务。在这 种情况下为等待访问者服务的次序是 61、 99、130、148、159、199。 2.移动臂由外向里移动 开始时， 正在 50 号柱面执行操作的读写磁头的移动臂是由外向里 （即向柱 面号增大的 内圈方向）趋向 61 号柱面的位置，因此，当访问 50 号柱面的操作结 束后，沿臂移动
