一、 实验目的

1、 了解磁盘调度的策略和原理；
2、 理解和掌握磁盘调度算法——先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、电梯扫描算法（SCAN）。

二、 实验环境

Windows操作系统、g++编译器

三、 实验内容

1、 模拟先来先服务法（First-Come, First-Served，FCFS），最短寻道时间优先法（Shortest Seek Time First， SSTF），电梯扫描算法（SCAN）三种磁盘调度算法；
2、 对三种算法进行对比分析。
3、 输入为一组请求访问磁道序列，输出为每种调度算法的磁头移动轨迹和移动的总磁道数。

四、 实验要求

1、 输入为一组请求访问磁道序列，该序列和所选磁道个数要求随机生成，输出为每种调度算法的磁头移动轨迹和移动的总磁道数；
2、输入磁道范围 0~1000 ，输入所选磁道个数0~1000；
3、画出主程序流程图；
4、编写程序并调试；
5、截屏输出实验结果；
6、根据实验结果与理论课讲述的原理进行实验分析。

五、 实验原理 实验中用到的系统调用函数（包括实验原理中介绍的和自己采用的），实验步骤

实验原理：

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

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

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

实验中用到的系统调用函数：

实验只是模拟实现磁盘调度功能，不需要系统调用函数。

实验步骤：

主程序的流程图如图所示：

3种算法的查询流程图如图所示：
①FCFS算法：

②SSTF算法：

③SCAN算法：

六、 实验结果分析（截屏的实验结果，与实验结果对应的实验分析）

1、实验结果与实验程序、实验步骤、实验原理、操作系统原理的对应分析；
2、不同条件下的实验结果反应的问题及原因；
3、实验结果的算法时间、效率、鲁棒性等性能分析。

随机生成的磁道序列，如下图所示：

FCFS算法：

SSTF算法：

SCAN算法：

实验结果分析：
①FCFS算法是最容易实现的算法，但是这个算法不考虑访问者要求访问的物理位置，只考虑访问者提出访问请求的先后次序，所以移动的总磁道数最大，远远超过SSTF和SCAN算法
②SSTF算法因为优先访问距离当前磁道最近的那个磁道，所以移动的总磁道数是最小的
③SCAN算法兼顾了FCFS算法和SSTF算法的特点，解决了SSTF容易造成的“饥饿”现象，移动的总磁道数也只是比SSTF算法多一点点

下面固定初始化的磁道个数为200，测试10组数据，并把“平均寻道长度”记录到表格中，结果如下：

实验结果分析：
①FCFS算法的寻道长度依然是最多的，远远超过SSTF和SCAN算法
②SSTF和SCAN算法的平均寻道长度都很低，有一定概率会出现相等的情况
③SSTF算法的平均寻道长度不一定是最低的，如上表中的第8列

如上面分析的第2点，我们可以发现，SSTF和SCAN算法的寻道长度一样的时候，访问序列也是一样的，这是因为SSTF在寻找最小距离的磁道时，寻找到的目标磁道都是在同一边，才会出现这样的情况。

再如上面分析的第3点，有时候会出现SCAN的移动磁道数比SSTF少的情况，分析查看磁头移动轨迹，可以发现移动轨迹部分重合，SSTF的磁头移动方向是上->下->上，而SCAN的磁头移动方向是上->下，SSTF算法因为调换多了一次磁头移动方向，导致寻道长度会有所增加：

七、实验数据及源代码（学生必须提交自己设计的程序源代码，并有注释，源代码电子版也一并提交），包括思考题的程序。

程序源代码：

#include <bits/stdc++.h>
using namespace std;
//所选磁道个数
int N;
//磁头的开始位置
int start;
//请求服务序列
int sequence[1024];
//记录数组，用于在SSTF和SCAN算法中记录序列中的磁道与当前磁道的距离，然后从中挑选最小的进行下一次访问
int record[1024];
//tag数组，用于记录序列中的磁道是否已经被访问过
bool tag[1024];

//先来先服务算法（FCFS）
void FCFS()
    int cnt,i;
    cnt = 0;
    printf("磁道移动顺序如下：\\n");
    printf("%d->%d",start,sequence[0]);
    cnt += abs(sequence[0] - start); //记录移动的磁道数
    for(i = 1;i < N;++i)
        printf("->%d",sequence[i]);
        cnt += abs(sequence[i] - sequence[i-1]);
    
    printf("\\nFCFS算法：一共移动了 %d 个磁道！平均寻道长度为 %lf\\n", cnt, cnt * 1.0 / N);


//最短寻道时间优先算法（SSTF）
void SSTF()
    int cnt,i,j,mv,mi,place;
    cnt = 0; //磁道移动距离
    //初始化record数组
    memset(record,1025,sizeof(record));
    //初始化tag
    memset(tag,0,sizeof(tag));
    place = start; //磁道位置
    printf("磁道移动顺序如下：\\n");
    printf("%d",start);
    for(i = 0; i<N;++i)
        //写record数组，记录序列中的磁道与当前磁道的距离
        for(j = 0;j < N;++j)
            record[j] = abs(sequence[j] - place);
        
        //从record中挑选出最小的
        mv = 1025; //记录当前最小值
        mi = -1;   //记录取最小值时的位置
        for(j = 0;j<N;++j)
            //当前位置没被访问过
            if(!tag[j] && mv > record[j])
                mv = record[j];
                mi = j;
            
        
        if(mi == -1)
            printf("error");
        
        //访问到sequence[mi]这个位置
        printf("->%d",sequence[mi]);
        cnt += abs(sequence[mi] - place);  //记录移动距离
        place= sequence[mi];  //更新当前磁道位置
        tag[mi] = 1;    //标识当前位置已访问
    
    printf("\\nSSTF算法：一共移动了 %d 个磁道！平均寻道长度为 %lf\\n", cnt, cnt * 1.0 / N);



//扫描算法（SCAN）
void SCAN()
    int cnt,i,j,mv,mi,place,direction;
    cnt = 0; //磁道移动距离
    direction = rand() % 2; //随机方向，0为向下，1为向上
    //初始化record数组
    memset(record,1025,sizeof(record));
    //初始化tag
    memset(tag,0,sizeof(tag));
    place = start; //磁道位置
    printf("磁道移动顺序如下：\\n");
    printf("%d",start);
    for(i = 0; i<N;++i)
        //写record数组，记录序列中的磁道与当前磁道的距离
        for(j = 0;j < N;++j)
            record[j] = abs(sequence[j] - place);
        
        //从record中挑选出最小的
        mv = 1025; //记录当前最小值
        mi = -1;   //记录取最小值时的位置
        for(j = 0;j<N;++j)
            //当前位置没被访问过，并且如果direction为1就往大了找，为0就往小了找
            if(!tag[j] && mv > record[j] && ((direction == 1 && sequence[j] >= place) || (direction == 0 && sequence[j] <= place)))
                mv = record[j];
                mi = j;
            
        
        if(mi == -1)
            //找不到了，需要调换方向
            direction = !direction;
            --i;
            continue;
        
        //访问到sequence[mi]这个位置
        printf("->%d",sequence[mi]);
        cnt += abs(sequence[mi] - place);  //记录移动距离
        place= sequence[mi];  //更新当前磁道位置
        tag[mi] = 1;    //标识当前位置已访问
    
    printf("\\nSCAN算法：一共移动了 %d 个磁道！平均寻道长度为 %lf\\n", cnt, cnt * 1.0 / N);



void init()
    int i;
    srand((unsigned long)time(0));
    N = rand() % 1001;     //随机磁道个数
    start = rand() % 1001; //随机磁头位置
    //随机初始化序列
    for(i = 0;i <N;++i)
        sequence[i] = rand() % 1001;
    
    printf("初始化磁道的个数为%d，序列如下：\\n",N);
    for(i = 0;i < N;++i)
        printf("%d ",sequence[i]);
    
    printf("\\n当前磁头的位置位于%d\\n", start);


int main()
    init(); //初始化数据
    printf("\\n================= FCFS =================\\n");
    FCFS();
    printf("\\n================= SSTF =================\\n");
    SSTF();
    printf("\\n================= SCAN =================\\n");
    SCAN();
    return 0;

八、思考题：

1、通过对每个算法进行时间复杂度分析对比，每个算法的效率如何？
答：
①FCFS算法：仅用一层循环就能完成，时间复杂度为O(n)，但是该算法的效率很差，通过上面的分析可以知道，FCFS算法移动的磁道数量是远远超过其他的两个算法的。
②SSTF算法：需要用两层循环才能实现，时间复杂度为O(n^2)，时间主要花费在寻找距离最短的磁道上。通过上面的分析可以知道，该算法的磁头移动数量在大多数情况下都是最低的，但是在实际上随时都可能会有新的请求加入，如果新的请求都是在当前位置附近，那么早期请求的距离当前磁道远的磁道将长时间得不到满足，造成“饥饿”现象。
③SCAN算法：我使用了两层循环实现，时间复杂度为O(n^2)，时间主要花费在寻找距离最短并且同方向的磁道上，可以通过排序算法使时间复杂度降低到O(nlogn)。通过上面的分析可以知道，该算法的移动磁道数量和SSTF算法的相差并不大，处于适中的水平，并解决了SSTF算法中容易出现的“饥饿”现象。

2、若所有硬盘全部设计成电子硬盘，哪个磁盘调度算法最合适？
答：电子硬盘的读取速度非常快，而且不存在物理寻道的操作，所以应该选择时间复杂度最低的FCFS算法。