前言

提示：本次实验在Linux(Ubuntu)中运行，程序中读取的文件需放在与c文件同一个文件夹中，或者自行在代码中修改路径。

一、实验目的

掌握几种基本的磁盘调度算法。

先来先服务法
最短寻道时间优先法
电梯法

二、实验内容和要求

采用模拟先来先服务法（First-Come, First-Served，FCFS），最短寻道时间优先法（Shortest Seek Time First， SSTF），电梯法三种磁盘调度算法，对一组请求访问磁道序列输出为每种调度算法的磁头移动轨迹和移动的总磁道数。
请求访问磁道序列的数据放在文件里，数据间以空格间隔。

三、实验程序

c语言代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <math.h>typedef int bool;
#define true 1
#define false 0int curTrack;    //当前磁道号
int trackNum;    //待调度磁道的数量
int *track;      //磁道号序列//快速排序
int position(int *a, int low, int high) {int key = a[low];while(low < high) {while(low < high && a[high] >= key) high--;a[low] = a[high];while(low < high && a[low] <= key) low++;a[high] = a[low];}a[low] = key;return low;
}
void quickSort(int *a, int low, int high) {if(low < high) {int pos = position(a, low, high);quickSort(a, low, pos - 1);quickSort(a, pos + 1, high);}
}//二分查找(只能查找有序序列)
int binaryFind(int *a, int flag, int target) {int left = 0;int right = flag - 1;while(left <= right) {int middle = (right + left) / 2;if(a[middle] < target) {left = middle + 1;} else if(a[middle] > target) {right = middle - 1;} else {return middle;}}return -1;  //查找失败
}void init(FILE *fp) {rewind(fp);		//fp回到开始位置//printf("请输入当前磁道号：");fscanf(fp, "%d", &curTrack);//printf("请输入待调度磁道的数量：");fscanf(fp, "%d", &trackNum);//printf("请输入磁道号序列：");track = (int*)malloc(trackNum  * sizeof(int));for(int i = 0; i < trackNum; i++) {fscanf(fp, "%d", &track[i]);}
}//判断数字是几位数，使得打印的轨迹好看
int digits(int num) {int result = 1;while(num / 10) {result++;num = num / 10;}return result;
}//打印磁头移动轨迹
void showTrack(int j, int cur, int *sortTrack) {for(int i = 0; i < digits(sortTrack[0]); i++) {printf(" ");}if(j < cur) {for(int i = 0; i < j; i++) {printf("    ");for(int k = 0; k < digits(sortTrack[i]); k++) {printf(" ");}}printf("\b<");for(int i = j; i < cur; i++) {printf("----");for(int k = 0; k < digits(sortTrack[i]); k++) {printf("-");}}}else {for(int i = 0; i < cur; i++) {printf("    ");for(int k = 0; k < digits(sortTrack[i]); k++) {printf(" ");}}printf("\b");for(int i = cur; i < j; i++) {printf("----");for(int k = 0; k < digits(sortTrack[i]); k++) {printf("-");}}printf("\b>");}printf("\n");
}//先来先服务算法（FCFS）
void FCFS() {printf("先来先服务算法（FCFS）\n");//对磁盘序列track进行排序int *sortTrack = (int*)malloc((trackNum + 1) * sizeof(int));for(int i = 0; i < trackNum; i++) {sortTrack[i] = track[i];}sortTrack[trackNum] = curTrack;quickSort(sortTrack, 0, trackNum);int curIndex = binaryFind(sortTrack, trackNum + 1, curTrack);printf("  磁盘序列:   丨");for(int i = 0; i < trackNum + 1; i++) {if(i == curIndex)printf("\033[1;32m%d    ", sortTrack[i]);    //给当前磁盘号的输出添加眼颜色//printf("%d    ", sortTrack[i]);elseprintf("\033[0m%d    ", sortTrack[i]);//printf("%d    ", sortTrack[i]);}printf("\n");printf("磁头移动轨迹: 丨");int temp = 0;int cur = curIndex;while(temp < trackNum) {if(temp != 0) {printf("              丨");}int j = binaryFind(sortTrack, trackNum + 1, track[temp]);showTrack(j, cur, sortTrack);cur = j;temp++;}printf("\n");int sum = 0;        //记录磁盘移动的磁道数double average = 0;    //平均寻找长度printf("依次访问的磁盘序列为：");for(int i = 0; i < trackNum; i++) {printf("%d  ", track[i]);sum += abs(curTrack - track[i]);curTrack = track[i];}printf("\n");printf("磁头移动的总磁道数为：%d\n", sum);average = (double)sum / trackNum;printf("平均寻找长度为：%f\n", average);free(sortTrack);
}//在当前磁道的左右两个方向中寻找距离最近的磁道，返回对应下标
int nearFind(int **markTrack, int curIndex) {//拷贝一份markTrackint **markTrack2 = (int**)malloc(2 * sizeof(int*));for(int i = 0; i < 2; i++) {markTrack2[i] = (int*)malloc((trackNum + 1) * sizeof(int));}for(int i = 0; i <= trackNum; i++) {markTrack2[0][i] = markTrack[0][i];markTrack2[1][i] = markTrack[1][i];}int leftIndex = -1;int rightIndex = trackNum + 1;int left = 0;   //在左边找第一个没访问过的磁道的距离int right = 0;  //在右边找第一个没访问过的磁道的距离for(int i = curIndex - 1; i >= 0; i--) {left += markTrack2[0][curIndex] - markTrack2[0][i];if(markTrack2[1][i] == 0) {leftIndex = i;markTrack2[1][i] = 1;    //修改访问位break;}}for(int i = curIndex + 1; i <= trackNum; i++) {right += markTrack2[0][i] - markTrack2[0][curIndex];if(markTrack2[1][i] == 0) {rightIndex = i;markTrack2[1][i] = 1;break;}}//printf("leftIndex = %d, rightIndex = %d\n", leftIndex, rightIndex);if(rightIndex == trackNum + 1) {markTrack[1][leftIndex] = 1;return leftIndex;}else if(leftIndex == -1) {markTrack[1][rightIndex] = 1;return rightIndex;}else {if(left <= right) {markTrack[1][leftIndex] = 1;return leftIndex;}else {markTrack[1][rightIndex] = 1;return rightIndex;}}free(markTrack2);
}//最短寻道时间优先法（SSTF）
void SSTF() {printf("最短寻道时间优先法（SSTF）\n");int sum = 0;        //记录磁盘移动的磁道数double average = 0;    //平均寻找长度int *temp = (int*)malloc(trackNum * sizeof(int));track[trackNum] = curTrack;quickSort(track, 0, trackNum);  //对磁盘track序列排序//建立二维数组，大小为 2 * trackNum，第一行元素存放排序后的sortTrack，第二行设置标记位，访问过的置为1，未访问过的置为0int **markTrack = (int**)malloc(2 * sizeof(int*));for(int i = 0; i < 2; i++) {markTrack[i] = (int*)malloc((trackNum + 1) * sizeof(int));}for(int i = 0; i <= trackNum; i++) {markTrack[0][i] = track[i];markTrack[1][i] = 0;}int curIndex = binaryFind(track, trackNum + 1, curTrack);markTrack[1][curIndex] = 1; //当前磁盘号被访问过printf("  磁盘序列:   丨");for(int i = 0; i < trackNum + 1; i++) {if(i == curIndex)printf("\033[1;32m%d    ", track[i]);    //给当前磁盘号的输出添加眼颜色//printf("%d    ", track[i]);elseprintf("\033[0m%d    ", track[i]);//printf("%d    ", track[i]);}printf("\n");printf("磁头移动轨迹: 丨");int cur = curIndex;for(int i = 0; i < trackNum; i++) {if(i != 0) {printf("              丨");}int j = nearFind(markTrack, cur);showTrack(j, cur, track);sum += abs(track[j] - track[cur]);cur = j;temp[i] = track[cur];}printf("依次访问的磁盘序列为：");for(int i = 0; i < trackNum; i++) {printf("%d  ", temp[i]);}printf("\n");printf("磁头移动的总磁道数为：%d\n", sum);average = (double)sum / trackNum;printf("平均寻找长度为：%f\n", average);free(temp);free(markTrack);
}//电梯算法（LOOK）
void LOOK() {printf("电梯算法（LOOK）\n");int sum = 0;        //记录磁盘移动的磁道数double average = 0;    //平均寻找长度track[trackNum] = curTrack;quickSort(track, 0, trackNum);  //对磁盘track序列排序//若此时磁头正在往磁道号增大的方向移动printf(" === ①  若初始时磁头正在往磁道号增大的方向移动\n");int curIndex = binaryFind(track, trackNum + 1, curTrack);int cur = curIndex;printf("  磁盘序列:   丨");for(int i = 0; i < trackNum + 1; i++) {if(i == curIndex)printf("\033[1;32m%d    ", track[i]);    //给当前磁盘号的输出添加眼颜色//printf("%d    ", track[i]);elseprintf("\033[0m%d    ", track[i]);//printf("%d    ", track[i]);}printf("\n");printf("磁头移动轨迹: 丨");for(int i = curIndex + 1; i <= trackNum; i++) {if(i != curIndex + 1)printf("              丨");showTrack(i, cur, track);sum += abs(track[i] - track[cur]);cur = i;}for(int i = curIndex - 1; i >= 0; i--) {printf("              丨");showTrack(i, cur, track);sum += abs(track[i] - track[cur]);cur = i;}printf("依次访问的磁盘序列为：");for(int i = curIndex + 1; i <= trackNum; i++) {printf("%d  ", track[i]);}for(int i = curIndex - 1; i >= 0; i--) {printf("%d  ", track[i]);}printf("\n磁头移动的总磁道数为：%d\n", sum);average = (double)sum / trackNum;printf("平均寻找长度为：%f\n", average);printf("\n\n");//若此时磁头正在往磁道号减小的方向移动printf(" === ②  若初始时磁头正在往磁道号减小的方向移动\n");sum = 0;average = 0.0;curIndex = binaryFind(track, trackNum + 1, curTrack);cur = curIndex;printf("  磁盘序列:   丨");for(int i = 0; i < trackNum + 1; i++) {if(i == curIndex)printf("\033[1;32m%d    ", track[i]);    //给当前磁盘号的输出添加眼颜色//printf("%d    ", track[i]);elseprintf("\033[0m%d    ", track[i]);//printf("%d    ", track[i]);}printf("\n");printf("磁头移动轨迹: 丨");for(int i = curIndex - 1; i >= 0; i--) {if(i != curIndex - 1)printf("              丨");showTrack(i, cur, track);sum += abs(track[i] - track[cur]);cur = i;}for(int i = curIndex + 1; i <= trackNum; i++) {printf("              丨");showTrack(i, cur, track);sum += abs(track[i] - track[cur]);cur = i;}printf("依次访问的磁盘序列为：");for(int i = curIndex - 1; i >= 0; i--) {printf("%d  ", track[i]);}for(int i = curIndex + 1; i <= trackNum; i++) {printf("%d  ", track[i]);}printf("\n磁头移动的总磁道数为：%d\n", sum);average = (double)sum / trackNum;printf("平均寻找长度为：%f\n", average);
}int main(int argc, char* argv[])
{FILE *fp = fopen(argv[1], "r");if(fp == NULL) {printf("读取文件失败！\n");return 0;}init(fp); //初始化printf("当前磁道号(curTrack)：%d\n", curTrack);printf("要访问的磁盘个数(trackNum)：%d\n", trackNum);printf("磁道号序列(track)：{ ");for(int i = 0; i < trackNum; i++) {printf("%d ", track[i]);}printf("}\n\n");FCFS();printf("\n\n");init(fp); //初始化SSTF();printf("\n\n");init(fp); //初始化LOOK();free(track);fclose(fp);return 0;
}

四、运行结果

运行结果截图

提示：此文件需与源文件放同一文件夹
在这里插入图片描述
带颜色的磁盘序列号表示初始磁道号

五、思考和分析

程序实现(思路)：

本次实验对磁盘号序列进行排序时我用了快排，查找指定序列的下标采用了折半查找。
执行三个算法之前分别先进行初始化操作。

1）先来先服务算法（FCFS）
轨迹的打印：先将磁盘序列数组track拷贝一份到新建的数组sortTrack中，将初始磁盘号放入其中，然后对sortTrack进行排序，找到初始磁道号在排序后track中的下标curIndex，然后依次访问track中的元素，找到他们在sortTrack中的下标，用cur记录当前磁头所在磁盘号的下标，根据这两个下标绘制出相应的轨迹，然后更新cur，重复执行，将所有轨迹绘制完毕。
因为先来的磁盘先访问，因此磁头依次访问的磁盘序列就是一开始的磁盘序列数组中的元素。
其余计算：用sum记录磁头移动的磁道数，遍历一遍track数组，将当前磁盘号与访问的磁盘号距离之差的绝对值加到sum中，然后更新当前磁盘号，遍历完后sum的值就是磁头移动的总磁道数，磁头平均查找长度average = sum / 磁道数量。

2）最短寻道时间优先法（SSTF）
轨迹的打印：直接将初始磁盘号curTrack放入磁盘序列数组track中并排序，找到初始磁道号在排序后track中的下标curIndex，然后建立一个带标记的磁道序列二维数组markTrack，第一行元素存放排序后的sortTrack，第二行设置标记位，访问过的置为1，未访问过的置为0，然后在当前磁道的左右两个方向中寻找距离最近的磁道，得到其下标，用cur记录当前磁头所在磁盘号的下标，根据这两个下标绘制出相应的轨迹，然后更新cur，重复执行，将所有轨迹绘制完毕。
建立一个临时数组temp，存放磁头依次访问的磁道号，在打印轨迹的时候将对应的磁道号插入到该数组中，最后打印这个数组的元素，就是磁头依次访问的磁道号。
其余计算：用sum记录磁头移动的磁道数，在打印轨迹的时候将移动的距离加到sum中，最终sum值就是磁头移动的总磁道数，磁头平均查找长度average = sum / 磁道数量。

3）电梯算法（LOOK）
因为初始状态磁头可能正在向磁道号增大的方向移动，也有可能正在向磁道号减小的方向移动，我将两种情况都做了相应的处理，这里的思路以向磁道号增大的方向移动为例。
轨迹的打印：将初始磁盘号curTrack放入磁盘序列数组track中并排序，找到初始磁道号在排序后track中的下标curIndex，用cur记录curIndex，然后从curIndex + 1开始遍历，根据当前遍历到的下标和cur下标绘制出相应的轨迹，更新cur为遍历到的下标，遍历完后，向磁道号增大方向的轨迹打印完毕，然后再从curIndex – 1开始从后往前遍历，根据当前遍历到的下标和cur下标绘制出相应的轨迹，更新cur为遍历到的下标，遍历完后，向磁道号减小方向的轨迹也打印完毕，即所有轨迹绘制完毕。
从curIndex + 1遍历到最后，在从curIndex – 1遍历到最前，遍历的磁道号就是磁头依次访问的磁道号。
若初始时以磁道号减小的方向移动，就反过来，先从curIndex – 1遍历到最前，再从curIndex + 1遍历到最后即可。
其余计算：用sum记录磁头移动的磁道数，在打印轨迹的时候将移动的距离加到sum中，最终sum值就是磁头移动的总磁道数，磁头平均查找长度average = sum / 磁道数量。

分析几种算法：

1）先来先服务算法（FCFS）：
优点：公平；如果请求访问的磁道比较集中的话，算法性能还算过的去
缺点：如果有大量进程竞争使用磁盘，请求访问的磁道很分散，则FCFS在性能上很差，寻道时间长。

2）最短寻道时间优先法（SSTF）：
优点：性能较好，平均寻道时间短
缺点：可能产生“饥饿”现象，在附录给的测试文件中，假设在处理18号磁道的访问请求时又来了一个38号磁道的访问请求，处理38号磁道的访问请求时又来了一个18号磁道的访问请求。如果有源源不断的18号、38号磁道的访问请求到来的话，150、160、184号磁道的访问请求就永远得不到满足，从而产生“饥饿”现象。

3）电梯算法（LOOK）：
LOOK算法可以说是扫描算法（SCAN）的优化版，扫描算法中，只有磁头到达最边上的磁道时才能改变磁头移动方向，在测试例子中，184号磁道后还存在一些磁道，只是我们不需要访问，若使用扫描算法，磁头还需要访问这些额外的磁道，事实上处理了184号磁道的访问请求之后就不需要再往右移动磁头了，而LOOK算法就是为了解决这个问题，如果在移动方向上已经没有别的请求了，就可以立即改变磁头移动的方向。
优点：性能较好，平均寻道时间较短，不会产生饥饿现象。
缺点：对于各个位置磁道的响应频率不平均（如：假设此时磁头正在往右移动，且刚处理过90号磁道，那么下次处理90号磁道的请求就需要等磁头移动很长一段距离;而响应了184号磁道的请求之后，很快又可以再次响应184号磁道的请求了）。