1. 概述

为什么需要磁臂调度算法？首先我们需要考虑读写磁盘块时间消耗。读写磁盘的时间主要由以下三个因素决定：

1. 寻道时间
   寻道时间主要是将磁盘臂移动到对应的柱面所需要的时间。
2. 旋转延迟
   磁臂等待对应的扇区移动到适当的柱面上所需要的时间。
3. 传输时间
   将磁盘块数据传输到内存区域所需的时间。

对于大多数磁盘而言，寻道时间与（旋转延迟和传输时间）相比，寻道时间远大于旋转延迟和传输时间之和，所以减少平均寻道时间可以充分的改善系统性能。

2. 调度目标

磁臂调度算法主要目标是为了降低平均磁盘服务时间，达到公平、高效的目标。

1. 公平
   一个I/O请求在有限时间内满足。
2. 高效
   减少设备机械运动带来的时间开销。

3. 调度算法

1. 先来先服务 FCFS (First Come First Served)
2. 最短寻道时间优先 SSF (Shortest Seek First)
3. 扫描算法(SCAN)/电梯算法 (Elevator algorithm)
4. 单向扫描调度算法 （C-SCAN）
5. N-Step-SCAN
6. FSCAN
7. 旋转调度
8. LOOK
9. C-LOOK

3.1 先来先服务 (FCFS)

按照访问磁盘的请求到达的先后次序服务。

优点

• 简单
• 公平

缺点

• 效率不高

举例:
磁盘访问序列：
98，183，37，122，14，124，65，67
读写头起始位置：53，那么磁臂移动的轨迹为：

3.2 最短寻道时间优先（SSF）

总是处理与磁头距离最近的请求以使寻道时间最小化。

优点

• 改善了磁盘的平均服务时间。

缺点

• 饥饿，可能导致一些访问请求得不到服务，因为可能会一直有距离磁头最近的请求达到。

举例：
磁盘访问序列：
98，183，37，122，14，124，65，67
读写头起始位置：53，
那么磁臂移动的轨迹为：

3.3 扫描算法(SCAN)

扫描算法又称为电梯算法（Elevator algorithm）,算法模拟电梯调度。
当设备无访问请求时，磁头不动；当有访问请求时，磁头按一个方向移动，在移动过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描；否则改变移动方向，并为经过的访问请求服务，如此反复。

优点

• 理解简单
• 无饥饿
• 性能比先来先服务高

缺点

• 实现较为复杂
• 较为不公平，因为可能先来的请求会可能是磁头刚刚扫描过的扇区

举例：
假设磁盘访问序列：
磁盘访问序列：
98，183，37，122，14，124，65，67
读写头起始位置：53，
那么磁臂移动的轨迹为：

3.4 单向扫描调度算法 （C-SCAN）

单向扫描算法（SCAN算法变种）：

• 总是从0号柱面开始向里扫描
• 按柱面(磁道)位置选择访问者
• 移动臂到达最后一个柱面后，立即带动读写磁头快速返回到0号柱面
• 返回时不为任何的等待访问者服务
• 返回后可再次进行扫描

优点：

• 磁盘负载中等情况下工作良好
• 提供了良好的响应时间和统一的等待时间

举例：

输入:
请求序列 = {176, 79, 34, 60, 92, 11, 41, 114}
读写头出事位置 = 50
方向 = 右侧(磁头从左向右移动)

磁头移动轨迹：

3.5 N-Step-SCAN

N-Step-SCAN算法（SCAN算法变种）：

• 把磁盘请求队列分成长度为N的子队列，每一次用SCAN算法处理一个子队列
• 在处理某一个队列时，新请求添加到其他子队列中  如果最后剩下的请求数小于N，则它们全都将在下一次扫描时处理
• N值比较大时，其性能接近SCAN；当N＝1时，即FIFO

3.6 FSCAN

FSCAN算法（SCAN算法变种）：

• 使用两个子队列
• 扫描开始时，所有请求都在一个队列中，而另一个队列为空 
• 扫描过程中，所有新到的请求都放入另一个队列中
• 对新请求的服务延迟到处理完所有老请求之后

3.7 旋转调度

旋转调度算法：
旋转调度：根据延迟时间来决定执行次序的调度
三种情况：

1. 若干等待访问者请求访问同一磁头上的不同扇区
2. 若干等待访问者请求访问不同磁头上的不同编号的扇区
3. 若干等待访问者请求访问不同磁头上具有相同的扇区

3.8 LOOK

LOOK调度算法是SCAN算法的增强版本。LOOK调度算法的寻道时间比FCFS、SSF、SCAN、C-SCAN的时间都短（FCFS->SRTF->SCAN->C-SCAN->LOOK）。LOOK调度算法服务访问请求和SCAN算法类似：磁头一直朝一个方向前进，如果在后续的请求中没有了这个方向的访问请求，那么磁头就朝相反的方向运动并处理相反反向的访问请求。SCAN算法的寻道时间长主要是因为SCAN算法中磁头一直朝向一个方向运动直到定位到磁盘的末尾，而LOOK算法则不会。

举例：
输入:
请求序列 = {176, 79, 34, 60, 92, 11, 41, 114}
磁头初始位置 = 50
方向 = 右侧 (磁头从左向右移动)

输出:
磁头初始位置: 50
总寻道次数 = 291
寻道序列：60 79 92 114 176 41 34 11

磁头移动轨迹：

3.9 C-LOOK

C-LOOK算法是SCAN算法和LOOK算法的增强版本。C-LOOK算法可以避免访问请求饥饿并统一服务所有访问请求。C-LOOK算法也是只在一个方向上服务所有请求，一个方向上所有的请求服务完成后磁头会移动到最远访问请求的位置重新进行一个方向上的访问请求服务。

举例：

输入: 请求序列 = {176, 79, 34, 60, 92, 11, 41, 114} 
磁头初始位置 = 50 
方向 = 右侧 (磁头从左向右移动) 
输出：磁头初始位置: 50 
总的寻道操作 = 156 
寻道序列： 60 79 92 114 176 11 34 41  
磁头移动轨迹：

4. 参考

1. 现代操作系统（原书第四版）
2. Coursera 操作系统原理 陈向群
3. https://www.geeksforgeeks.org/scan-elevator-disk-scheduling-algorithms/
4. https://www.geeksforgeeks.org/c-look-disk-scheduling-algorithm/?ref=lbp
5. https://www.geeksforgeeks.org/scan-elevator-disk-scheduling-algorithms/?ref=lbp
6. https://www.geeksforgeeks.org/c-scan-disk-scheduling-algorithm/?ref=lbp
7. https://www.geeksforgeeks.org/look-disk-scheduling-algorithm/?ref=lbp
8. https://www.geeksforgeeks.org/c-look-disk-scheduling-algorithm/?ref=lbp
9. https://www.geeksforgeeks.org/n-step-scan-disk-scheduling/?ref=lbp
10. https://www.geeksforgeeks.org/fscan-disk-scheduling-algorithm/?ref=lbp