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

华南农业大学信息（软件）学院

《操作系统分析与设计实习》成绩单

开设时间：2014学年第一学期

一、需求分析：

(1)输入的形式和输入值的范围：

在文本框输入序列长度，输入值为int类型

(2)输出的形式：

输出每种磁盘调度算法的服务序列

(3)程序所能达到的功能：

模拟实现FCFS、SSTF、电梯LOOK、C-SCAN 算法，并计算及比较磁头移动道数。

测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。

二、概要设计：

主程序流程图：

三、详细设计：

先来先服务算法（FCFS）:

按先来后到次序服务，未作优化。 最简单的移臂调度算法是“先来先服务”调度算法，这个算法实际上不考虑访问者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。 采用先来先服务算法决定等待访问者执行输入输出操作的次序时，移动臂来回地移动。先来先服务算法花费的寻找时间较长，所以执行输入输出操作的总时间也很长。

最短寻道时间优先算法（SSTF） :

最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个请求先执行的，而不管访问者到来的先后次序。与先来先服务、算法比较，大幅度地减少了寻找时间，因而缩短了为各访问者请求服务的平均时间，也就提高了系统效率。 但最短查找时间优先（SSTF）调度，FCFS会引起读写头在盘面上的大范围移动，SSTF查找距离磁头最短（也就是查找时间最短）的请求作为下一次服务的对象。SSTF查找模式有高度局部化的倾向，会推迟一些请求的服务，甚至引起无限拖延（又称饥饿）。

扫描算法（SCAN）：

SCAN 算法又称电梯调度算法。SCAN算法是磁头前进方向上的最短查找时间优先算法，它排除了磁头在盘面局部位置上的往复移动，SCAN算法在很大程度上消除了SSTF算法的不公平性，但仍有利于对中间磁道的请求。“电梯调度”算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。但是，“电梯调度”算法在实现时，不仅要记住读写磁头的当前位置，还必须记住移动臂的当前前进方向。

循环扫描（C-SCAN）：

循环扫描 CSCAN是为了减少 SCAN 算法造成的某些进程的请求被严重推迟，CSCAN 算法规定磁头单向移动。

函数调用关系图

:

四、调试分析：

(1) 调试过程中遇到的问题是如何解决的以及对设计与实现的讨论和分析；

通过对每一行的输出判断问题出现在哪里，然后把出问题的地方缩小到一定范围，然后解决问题，如若解决不出则上网查询，再不行就咨询同学。设计主要分为界面设计和算法设计，界面设计部分并没有进行过多的改进，算法部分SSTF算法实现的比较复杂，时间复杂度较高。

(2) 算法的时间复杂性(包括基本操作和其他算法的时间复杂性的分析)和改进设想；

FIFO算法经历一重循环，时间复杂度为O（n）,算法比较简单；

SSTF算法经历二重循环，时间复杂度为O（n^2），算法较为复杂

SCAN和CSCAN算法含多个一重循环，时间复杂度为O（n），动态数组存储服务序列；

(3) 设计过程的经验和体会；

设计过程必须要考虑时间复杂度，过高的时间复杂度会导致程序执行效率低下。必须要进行结构化设计，各个模块要很清晰的体现，能在代码中找到相关模块的代码，这样才便于程序的维护和调试。

(4) 实现过程中出现的主要问题及解决方法。

主要问题是SSTF算法的设计。解决方法是上网查询SSTF算法的代码，学习其中的算法思想，然后运用到自己的代码中去。

五、运行结果：

输入磁道范围、输入所选磁道个数、选择算法：

测试与运行结果：输出请求序列、平均寻道时间：

六、总结：

通过这次的操作系统课程设计，我懂得了许多，首先是让我对操作系统磁盘调度策略有了更加深刻的认识，自己动手操作比光看书能更加了解磁盘调度的策略和原理，同时对磁盘调度的四种算法——先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、有了更深刻的理解和掌握，使我能够为磁盘调度选择适当的算法，提高CPU工作效率。设计过程中遇到的困难在老师和同学的帮助下顺利解决并通过了验收，我深刻认识到算法的逻辑性对程序的重要影响，算法的准确度对程序运行结果的重要影响，这对我以后在操作系统的学习中有极大帮助。也增强了我写代码的能力，尤其是设计算法有了进步，知道了时间复杂度的重要性。由于这次的课程设计是单人做的，所以也增强了独立做程序的能力。不过，通过这次课程设计，我也了解到自己有很多不足，比如在设计界面方面明显经验不足，许多地方都需要上网查询，以至于界面的简陋，代码也不够工整明了。总的来说，这次课程设计不仅提升了自己的知识和能力，还让自己知道了自己的许多不足之处。

七、源代码： #include

#include

#include

#include

using namespace std;

#define maxsize 1000

//判断输入的数据是否有效

int decide(char str[])

{

}

//将字符串转换为数字

int trans(char str[], int a)

{

}

//冒泡排序算法

int *bubble(int cidao[], int m)

{

int i, j; int temp; for (i = 0; i cidao[j]) { temp = cidao[i]; cidao[i] = cidao[j]; cidao[j] = temp; int i; int sum = 0; for (i = 0; i '9') { } i++; return 0; break;

} } cout

//当前磁道输入

int printnow()

{

A:

}

int printoi(int cidao[], int now, int m)

{

}

//直接由内向外依次给予各请求服务

int printio(int cidao[], int now, int m) } return sum; int i; int sum = 0; cout = 0; i--) { cout > str; a = decide(str); if (a == 0) { } else now = trans(str, a); return now; cout

}

//直接从当前次磁道到最外，再由外向内依次给予各请求服务 int printioi(int cidao[], int now, int m)

{

}

//直接从当前次磁道到最内，再由内向外依次给予各请求服务 int printoio(int cidao[], int now, int m)

{

}

//先向磁道减小的方向，再向磁道增加的方向

int printsb(int cidao[], int now, int m) int i; int sum = 0; cout = 0; i--) { cout

}

//先向磁道增加的方向，再向磁道减小的方向

int printbs(int cidao[], int now, int m)

{

int k = 0; int l = 0; int r = 0; int j; int sum = 0; while (cidao[k]= 0; j--) { } now = cidao[0]; while (r

} } now = cidao[m - 1]; for (j = l; j >= 0; j--) { } return sum; cout

//先向磁道减小的方向，再从磁道最大的地方向减小的方向, int printsbs(int cidao[], int now, int m)

{

int k = 0; int l = 0; int r = 0; int j; int sum = 0; cout = 0; j--) { } now = cidao[0]; //sum += abs(cidao[0] - cidao[m - 1]); for (j = m-1; j>=r; j--) { } cout

} //先向磁道增大的方向，再从磁道最小的地方向向增大的方向 int printbsb(int cidao[], int now, int m)

{

}

//就近选择磁道方法

int nearbyselect(int cidao[], int now, int m) {

int k = 0; int l = 0; int r = 0; int sum1 = 0; int sum2 = 0; int suml = 0; int sumr = 0; int sum = 0; int k = 0; int l = 0; int r = 0; int j; int sum = 0; cout

while (cidao[k] 0 || r (cidao[r] - now)) { cout (cidao[r] - now)) { } sumr = sumr + sum2; //now = cidao[l + 1]; now = cidao[r]; cout

} } } cout

//1.FCFS先来先服务调度算法 void FCFS(int cidao[], int m) {

}

//2.SSTF 最短寻道时间优先调度算法 void SSTF(int cidao[], int m) {

int now; int sum = 0; int i, j; float ave; cout

} float ave; cidao = bubble(cidao, m); now = printnow(); if (cidao[m - 1] = now) if (now>cidao[0] && now

//3.SCAN扫描调度算法

void SCAN(int cidao[], int m) {

int k = 1; int now, d, sum; float ave; cidao = bubble(cidao, m); now = printnow(); cout > d; if (cidao[m - 1] = now) if (now>cidao[0] && now

} //4.C-SCAN扫描调度算法

void CSCAN(int cidao[], int m) {

int k = 1; int now, d, sum; float ave; cidao = bubble(cidao, m); now = printnow(); cout > d; if (cidao[m - 1] = now) { } //sum = printioi(cidao, now, m); if (now>cidao[0] && now

//主函数 void main() {

int a, c, m, n; int cidao[maxsize]; int i = 0; char str[10]; cout > m; if (m>65536) { } cout > n; cout

} } cin >> str; a = decide(str); if (a == 0) { } else { } switch (c) { case 1: } FCFS(cidao, n); break; SSTF(cidao, n); break; SCAN(cidao, n); break; CSCAN(cidao, n); break; exit(0); cout = 6) cout