电梯调度 / 磁盘调度算法数据结构与算法

一. FCFS（First Come First Serve）

假设当前磁道在某一位置，依次处理服务队列里的每一个磁道，这样做的优点是处理起来比较简单，但缺点是磁头移动的距离和平均移动距离会很大。
这种方法在请求较少的环境下，性能尚可接受，但是在请求较多的情况下，这种算法的性能就会严重下降，甚至恶化。

二. SSTF（Shortest Seek Time First）

SSTF，最短寻道时间算法。这种算法的本质是利用贪心算法来实现，假设当前磁道在某一位置，接下来处理的是距离当前磁道最近的磁道号，处理完成之后再处理离这个磁道号最近的磁道号，直到所有的磁道号都服务完了程序结束。
它优点是性能会优于FIFO算法。而缺点是会产生距离当前磁道较远的磁道号长期得不到服务，也就是“饥饿”现象，因为要求访问的服务的序列号是动态产生的，即各个应用程序可能不断地提出访问不同的磁道号的请求。

三. SCAN

SCAN算法，也就是很形象的电梯调度算法。先按照一个方向(比如从外向内扫描)，扫描的过程中依次访问要求服务的序列。当扫描到最里层的一个服务序列时反向扫描，这里要注意，假设最里层为0号磁道，最里面的一个要求服务的序列是5号，访问完5号之后，就反向了，不需要再往里扫。结合电梯过程更好理解，在电梯往下接人的时候，明知道最下面一层是没有人的，它是不会再往下走的。
过程：
总是从磁臂当前位置开始，沿磁臂的移动方向去选择当前离磁臂最近的那个位置。
当沿磁臂方向无访问请求时，改变磁臂的移动方向。
需要为访问者设置两个队列，依据磁头的移动方向，能访问到的访问者由近及远排队。
背离磁头移动方向的访问者也由近及远排队。
先按磁头移动方向队列调度访问者访问磁盘，当该方向没有访问者时，再改变方向，选择还有一个访问者队列访问磁盘。

1. 代码

该代码是非实时实现的，直接给一个特定序列，而不是边调度边输入。

//SCAN磁盘调度算法 #include #include #include using namespace std; //这个实现是非实时的 //输入一个要访问的序列visit，函数返回最终真正访问顺序序列 //start是开始时磁头所在位置 //direct是开始时磁头走的方向，true是由里向外（从小到大），false是由外向里（从大到小） vector scan(vector visit,unsigned int start,bool direct) { vector ret; vector large, small; //维持两个vector，一个是大于开始点的，一个是小于开始点的 for (size_t i = 0; i < visit.size(); i++) { if (visit[i] == start) ret.push_back(visit[i]); else if (visit[i] > start) large.push_back(visit[i]); else if (visit[i] < start) small.push_back(visit[i]); } //先将两者排下序 sort(large.begin(), large.end()); sort(small.begin(), small.end()); //开始是从小到大访问 if (direct) { for (int i = 0; i < large.size(); i++) ret.push_back(large[i]); for (int i = small.size() - 1; i >= 0; i--) ret.push_back(small[i]); return ret; } //开始是从大到小访问 else{ for (int i = small.size() - 1; i >= 0; i--) ret.push_back(small[i]); for (int i = 0; i < large.size(); i++) ret.push_back(large[i]); return ret; } }int main() { vector in = { 98,183,37,122,14,124,65,67 }; vector out = scan(in, 53, false); for (size_t i = 0; i < out.size(); i++) cout << out[i] << " "; cout << endl; getchar(); return 0; }

2. 计算平均寻道长度以上面程序的输入为例：
①53为基准，向内移动。
②分为两个队列，按由近到远排序：
37 14
65 67 98……183
③先移动到37，再到14，共：53-14 = 39长度
14移动到183，共：183-14 = 169长度；
④则共需移动长度为：39+169 = 208，平均寻址长度为：208/8 = 26

参考文章：【算法】电梯调度算法/磁盘扫描算法
【电梯调度 / 磁盘调度算法】磁盘调度算法剖析(FIFO、SSTF、SCAN、CSCAN、FSCAN)