操作系统磁盘调度算法试验报告及代码

1、华南农业大学信息（软件）学院 操作系统分析与设讣实习成绩单 开设时间：2014学年笫一学期 小组成员、组内分工及各成员成绩 学 号 姓名 分工 成绩 实 验 题 目 题目二 磁盘调度算法的模拟实现及对比 自 我 评 价 通过这次的操作系统课程设计，我懂得了许多，首先是让我对操作系统磁盘调 度策略有了更加深刻的认识， 自己动手操作比光看书能更加了解磁盘调度的策 略和原理，同时对磁盘调度的四种算法一一先来先服务算法（FCFS）、最短寻 道时间优先算法（SSTF）、有了更深刻的理解和掌握，使我能够为磁盘调度选 择适当的算法，提高CPU工作效率。设计过程中遇到的困难在老师和同学的帮 助下顺利解决并通过

2、了验收，我深刻认识到算法的逻辑性对程序的重要影响， 算法的准确度对程序运行结果的重要影响，这对我以后在操作系统的学习中有 极大帮助。也增强了我写代码的能力，尤其是设计算法有了进步，知道了时间 复杂度的重要性。由于这次的课程设计是单人做的，所以也增强了独立做程序 的能力。不过，通过这次课程设计，我也了解到自己有很多不足，比如在设计 界面方面明显经验不足，许多地方都需要上网查询，以至于界面的简陋，代码 也不够工整明了。总的来说，这次课程设计不仅提升了自己的知识和能力，还 让自己知道了自己的许多不足之处。 教 师 评 评价指标： 题目内容和要求完成情况优口良口中口差口 对算法原理的理解程度优口良口中

3、口差口 语 程序设计水平优口良口中口差口 程序运行效果及正确性 优口良口中口差口 课程设计报告结构清晰优口良口中口差口 报告中总结和分析详尽优口良口中口差口 教师签名 1 1 1、需求分析： (1) 输入的形式和输入值的范围： 在文本框输入序列长度，输入值为int类型 (2) 输出的形式： 输出每种磁盘调度算法的服务序列 (3) 程序所能达到的功能： 模拟实现FCFS、SSTF、电梯LOOK、C-SCAN算法，并计算及比较磁头移动道 数。 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。 输入磁道范围 (Tiooo 输入所选磁道个数 01000 选择算法 广4 2、概要设计:

4、 主程序流程图: 3、详细设计： 先来先服务算法（FCFS）: 按先来后到次序服务，未作优化。最简单的移臂调度算法是“先来先服 务”调度算法，这个算法实际上不考虑访问者要求访问的物理位置，而只是考虑访 问者提出访问请求的先后次序。 采用先来先服务算法决定等待访问者执行输入输 出操作的次序时，移动臂来回地移动。先来先服务算法花费的寻找时间较长，所以 执行输入输出操作的总时间也很长。 最短寻道时间优先算法（SSTF）: 最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个请 求先执行的，而不管访问者到来的先后次序。与先来先服务、算法比较，大幅度地 减少了寻找时间，因而缩短了为各访问者请

5、求服务的平均时间，也就提高了系统效 率。 但最短查找时间优先（SSTF）调度，FCFS会引起读写头在盘面上的大范围 移动，SSTF查找距离磁头最短（也就是查找时间最短）的请求作为下一次服务的对象。SSTF查找模式有高度局部化的倾向，会推迟一些请求的服务，其至引起无 限拖延（又称饥饿）。 扫描算法（SCAN）: SCAN算法乂称电梯调度算法。SCAN算法是磁头前进方向上的最短查找时间 优先算法，它排除了磁头在盘面局部位置上的往复移动，SCAN算法在很大程度上 消除了 SSTF算法的不公平性，但仍有利于对中间磁道的请求。“电梯调度”算法 是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近

6、的那个柱访问 者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。但是，“电 梯调度”算法在实现时，不仅要记住读写磁头的当前位置，还必须记住移动臂的当 刖刖进方向。 循环扫描（c-SCAN）: 循环扫描CSCAN是为了减少SCAN算法造成的某些进程的请求被严重推迟， CSCAN算法规定磁头单向移动。 函数调用关系图： 4、调试分析: (1) 调试过程中遇到的问题是如何解决的以及对设汁与实现的讨论和分析； 通过对每一行的输出判断问题出现在哪里，然后把出问题的地方缩小到一定 范围，然后解决问题，如若解决不出则上网查询，再不行就咨询同学。设计主要分 为界面设计和算法设计，界面设计部分并没有

7、进行过多的改进，算法部分SSTF算 法实现的比较复杂，时间复杂度较高。 (2) 算法的时间复杂性(包括基本操作和其他算法的时间复杂性的分析)和改 进设想； FIFO算法经历一重循环，时间复杂度为0 (n)，算法比较简单； SSTF算法经历二重循环，时间复杂度为0 (F2),算法较为复杂 SCAN和CSCAN算法含多个一重循环，时间复杂度为0 (n),动态数组存储服 务序列； (3) 设计过程的经验和体会； 设计过程必须要考虑时间复杂度，过高的时间复杂度会导致程序执行效率低 下。必须要进行结构化设计，各个模块要很清晰的体现，能在代码中找到相关模块 的代码，这样才便于程序的维护和调试。 (4) 实

8、现过程中出现的主要问题及解决方法。 主要问题是SSTF算法的设计。解决方法是上网查询SSTF算法的代码，学习 其中的算法思想，然后运用到自己的代码中去。 5、运行结果： 输入磁道范围、输入所选磁道个数、选择算法: 测试与运行结果：输出请求序列、平均寻道时间: 4叶片用加 W JU *4 务 屹詔UT W UX fc l 91 W VI Mi7! r!i4A IX 6、总结: 通过这次的操作系统课程设计，我懂得了许多，首先是让我对操作系统磁盘 调度策略有了更加深刻的认识，自己动手操作比光看书能更加了解磁盘调度的策略 和原理，同时对磁盘调度的四种算法一一先来先服务算法（FCFS）、 最短寻道时间

9、优先算法（SSTF）、有了更深刻的理解和掌握，使我能够为磁盘调度选择适当的算 法，提高CPU工作效率。设计过程中遇到的困难在老师和同学的帮助下顺利解决并 通过了验收，我深刻认识到算法的逻辑性对程序的重要影响，算法的准确度对程序 return sum; /冒泡排序算法 int bubble(intcidao, intm) int i, j; int temp; for (i = 0; i m; i+) for (j 二 i + 1; j cidaoj) temp = cidaoi; cidaoi = cidaoj: cidaoj = temp;cout 排序后的磁盘序列为: for (i = 0

10、; i m; i+) cout cidaoi cout str; a = decide (str); 辻(a 二二 0) cout 输入数据类型有误，请重新输入！ endl; goto A; else now = trans (str, a); return now; int printoi (intcidaoEl, intnow, intm) int i; int sum = 0; cout 磁道扫描序列为：; for (i = m - 1; i = 0; i一一)cout cidaoi sum += abs(now - cidaoi); now = cidaoi; return sum;

11、/直接山内向外依次给予各请求服务 int printio(intcidao, intnow, intm) int i; int sum = 0; cout 磁道扫描序列为：； for (i = 0; i m; i+) cout cidaoi ； sum += abs(cidaoi - now); now = cidaoi; return sum; /直接从当前次磁道到最外，再山外向内依次给予各请求服务 int printioi(intcidao, intnow, intm) int i; int sum = 0; cout = 0; i-) cout cidaoi； sum += abs(now - cidaoi); now = cidaoi; return su