磁盘调度算法
5.3.1 已经给出了本节的全部前提：一次磁盘访问的时间里，寻道时间占绝对大头。
因此磁盘调度的目标只有一个：让磁头少跑路。 六种算法都是在回答同一个问题——手上有一堆待处理的磁道请求，按什么顺序服务，磁头移动的总距离最短。
注意它们优化的全都是寻道，没有一个算法去管旋转延迟，原因见 5.3.1 那道题。
机制
图中用的是标准例子：磁道范围 0~199，磁头起始在 53 号磁道且正向磁道号增大的方向移动，待服务请求为 98、183、37、122、14、124、65、67。
先来先服务（FCFS）
严格按请求到达的先后顺序服务。
优点是公平——每个请求都能在有限时间内得到服务，不会有任何请求被无限期推迟。缺点是性能可能很差：若相继而来的请求分散在磁盘两端，磁头就要来回大幅移动。
它是唯一一个”完全不看磁头位置”的算法，这一点在下面那道真题里是关键。
最短寻道时间优先（SSTF）
每次选择距离当前磁头位置最近的那个请求。
性能明显优于 FCFS，但不能保证平均寻道时间最短（局部最优不等于全局最优）。更严重的问题是可能产生饥饿：若磁头附近不断有新请求到来，远处的请求就会被无限期地推迟。
扫描算法（SCAN，电梯算法）
磁头沿当前方向一直移动到磁盘的端点，途中顺路服务遇到的所有请求，到达端点后反向再扫。
它像电梯一样”到顶再返回”，因此又称电梯算法。 它避免了 SSTF 的饥饿问题——任何请求最多等磁头走一个来回就能被服务。
缺点是磁头必须走到端点，即使那个方向上已经没有请求了。
LOOK 调度
SCAN 的改进：磁头只走到当前方向上最远的那个请求处就返回，不必到达端点。
“LOOK”这个名字的含义是”先看一眼前面还有没有请求”——没有就掉头。它省掉了 SCAN 那段无意义的空跑。
循环扫描（C-SCAN）
SCAN 的另一个问题是”不公平”：磁头刚扫过的那一端，请求要等最久（因为要等磁头走到另一端再回来）；而磁头即将到达的那一端，请求马上就能被服务。
C-SCAN 的做法是只在一个方向上服务：走到端点后，直接快速返回到起始端，返回途中不服务任何请求，然后再次单向扫描。
这样每个磁道被访问的间隔就变得均匀了，代价是那次”空返回”。
C-LOOK 调度
C-SCAN 与 LOOK 的结合：单向扫描，但只走到当前方向最远的请求处，然后直接跳到另一端最远的那个请求，不必到达端点。
四个名字的构词法是有规律的，记住就不会混：
带 C（Circular）= 单向服务，返回时不服务；不带 C = 双向都服务。
带 LOOK = 到最远请求就掉头；不带 LOOK（即 SCAN）= 必须走到端点。
两个维度交叉，正好是 SCAN / LOOK / C-SCAN / C-LOOK 四种。
减少延迟时间的方法
调度算法解决的是寻道，而下面两种手段解决的是旋转延迟。
磁头读完一个扇区后，需要一小段时间做数据处理。若下一个要读的扇区在物理上紧挨着，等处理完，它已经转过去了，只能再等一整圈。
① 交替编号——让逻辑上相邻的扇区在物理上间隔若干个扇区（例如物理位置按 0、4、1、5、2、6、3、7 的顺序编号）。这样磁头处理完 0 号扇区时，1 号扇区正好转到磁头下方。
② 错位命名——让相邻盘面上的扇区起始位置错开一个角度。这样读完一个盘面的最后一个扇区、切换到下一个盘面时，不必等盘片转一整圈。
两者解决的是不同场景：交替编号针对同一磁道内的连续读，错位命名针对换盘面时的连续读。
磁盘地址结构的设计
地址结构设计为”柱面号 | 盘面号 | 扇区号”而非”盘面号 | 柱面号 | 扇区号”，理由与上面两种技巧一脉相承：都是为了让连续数据的访问尽量少付出机械代价。 完整论证见 5.3.1。
边界
哪种算法不会导致磁臂黏着
疑问点：不会导致磁头臂黏着的磁盘调度算法
32.【2018 统考真题】系统总是访问磁盘的某个磁道而不响应对其他磁道的访问请求，这种现象称为磁头臂黏着。下列磁盘调度算法中，不会导致磁头臂黏着的是（ ）。 A. 先来先服务（FCFS） B. 最短寻道时间优先（SSTF） C. 扫描算法（SCAN） D. 循环扫描算法（C-SCAN）
答案 A。
“磁臂黏着”是指磁头长时间停在某个磁道反复服务，而其他磁道的请求得不到响应。 判断某个算法会不会黏着，只需问一句：如果某个磁道上的请求源源不断地到来，这个算法会不会一直服务它。
SSTF 会：只要那个磁道就在磁头脚下，距离永远是 0，永远是”最短”，新来的请求会被无休止地优先服务。
SCAN 和 C-SCAN 也会：磁头扫描到某个磁道时，若该磁道上恰好持续有新请求到达，磁头就会停在那里不断服务——扫描算法只规定了”往哪个方向走”，并没有规定”在一个磁道上最多服务几个请求”。
FCFS 不会：它严格按请求到达的时间排队。某个磁道后来的请求，只能排在此刻队列中所有已有请求的后面，无论它离磁头多近。磁头服务完队首就必须去服务下一个，不可能停留。
这道题的本质是：FCFS 是唯一一个”完全不参考磁头当前位置”的算法，因此也是唯一一个不可能被局部密集请求绑架的算法。 它性能最差，但恰恰因为最”笨”，它对饥饿和黏着免疫。
SCAN 与 LOOK 的差别在哪里体现
两者的服务顺序完全相同，差别只在”要不要走到端点”，因此只在计算移动距离时才体现出来。
以图中的例子（起点 53，向磁道号增大方向，最大磁道号 199）为例：
SCAN 要走到 199 再返回，磁头移动总距离包含
做题时的注意点：题目若只说”SCAN”，就必须走到端点；只有明确说 LOOK 才可以提前掉头。这是移动距离计算题最常见的失分点。
C-SCAN 的”空返回”算不算移动距离
这一点题目口径不一，必须看题干。
按磁头的实际物理移动计算，那段返回当然要计入——磁臂确实从 199 移到了 0。
但有些题目只统计”服务请求过程中的有效移动”，或者认为返回是一次快速的整体复位而单独计时。
稳妥的做法是：题干若未特别说明，按实际移动距离计入。 图中的注释也标明了这一点。
算法选择的两个维度
六种算法可以放在两个维度上比较，选择题几乎都落在这两个维度上：
性能维度：FCFS 最差，SSTF 较优，SCAN 系列在实际系统中综合最好。
公平性维度：FCFS 最公平（严格按时间），SSTF 最不公平（可能饥饿），SCAN 居中（有上界但两端不均），C-SCAN 在 SCAN 基础上进一步均匀化。
两个维度恰好是相反的：越”聪明”的算法越容易不公平。这与进程调度中”短作业优先性能好但会饥饿”是完全相同的权衡。
对照速查
| 算法 | 做法 | 优点 | 缺点 |
|---|---|---|---|
| FCFS | 按请求到达顺序 | 最公平，不会饥饿也不会黏着 | 性能最差 |
| SSTF | 选最近的 | 性能较好 | 可能饥饿、会黏着 |
| SCAN | 到端点再反向 | 避免饥饿 | 端点空跑；两端等待不均 |
| LOOK | 到最远请求就反向 | 省掉端点空跑 | 两端等待仍不均 |
| C-SCAN | 单向服务，到端点后空返回 | 各磁道等待均匀 | 多一次空返回 |
| C-LOOK | 单向服务，跳到另一端最远请求 | 均匀且省空跑 | — |
| 构词法 | 含义 |
|---|---|
| 带 C（Circular） | 单向服务，返回途中不服务 |
| 不带 C | 双向都服务 |
| 带 LOOK | 到最远请求就掉头 |
| SCAN（不带 LOOK） | 必须走到端点 |
| 减少延迟的方法 | 解决什么 |
|---|---|
| 交替编号 | 同一磁道内连续读时错过下一扇区 |
| 错位命名 | 换盘面时要等一整圈 |
| 磁臂黏着 | 会不会 | 为什么 |
|---|---|---|
| FCFS | 不会 | 完全不看磁头位置，后来者只能排队 |
| SSTF | 会 | 脚下的距离永远是 0 |
| SCAN / C-SCAN | 会 | 只规定方向，未规定一个磁道最多服务几个 |
考点
- 所有磁盘调度算法优化的都是寻道，与旋转延迟无关
- 六种算法的服务顺序与移动距离计算；SCAN 必须到端点，LOOK 不必
- 构词法：带 C = 单向、带 LOOK = 到最远请求就掉头
- 只有 FCFS 不会导致磁臂黏着（2018 真题），因为它不参考磁头位置
- SSTF 可能饥饿；SCAN 有等待上界但两端不均；C-SCAN 使各磁道均匀
- 交替编号解决同磁道连续读，错位命名解决换盘面
- 性能与公平性是相反的两个维度
链接
- 🏠 返回总览：操作系统第 5 章：输入/输出管理总览
- ⬅️ 上一节：5.3.2 磁盘的管理
- ➡️ 下一节：5.3.4 固态硬盘
- 🔗 为什么只优化寻道，见 5.3.1 磁盘
- 🔗 同样的性能/公平权衡，见 2.2.5 CPU 调度算法
- 📖 名词库：第 5 章名词库