3. 磁盘调度算法（一）：先来先服务（FCFS）与最短寻道时间优先（SSTF）的原理与对比
磁盘 I/O 是文件系统性能的关键瓶颈。当多个进程同时发起读写请求时，磁盘调度算法决定了磁头移动的顺序，直接影响寻道时间与整体吞吐量。本章深入拆解两种最基础的调度算法：先来先服务（FCFS）与最短寻道时间优先（SSTF），并通过定量对比揭示其适用场景与局限性。
3.1 先来先服务（FCFS）
FCFS 是最直观的调度策略：按照请求到达的先后顺序依次服务，磁头从当前柱面开始，逐一移动到每个请求所在的柱面。该算法实现简单，不存在“饥饿”现象，但寻道路径完全由请求顺序决定，往往导致磁头在磁盘上来回大幅移动，平均寻道长度较长。
3.1.1 算法流程
- 维护一个请求队列，按到达时间排序。
- 磁头从当前位置开始，移动到队列中第一个请求的柱面。
- 服务完成后，移动到下一个请求的柱面，直至队列为空。
3.1.2 示例计算
假设磁盘请求队列（柱面号）：98, 183, 37, 122, 14, 124, 65, 67，磁头起始位置为 53。FCFS 的寻道顺序与总移动距离如下：
| 步骤 | 当前柱面 | 下一柱面 | 移动距离 |
|---|---|---|---|
| 1 | 53 | 98 | 45 |
| 2 | 98 | 183 | 85 |
| 3 | 183 | 37 | 146 |
| 4 | 37 | 122 | 85 |
| 5 | 122 | 14 | 108 |
| 6 | 14 | 124 | 110 |
| 7 | 124 | 65 | 59 |
| 8 | 65 | 67 | 2 |
总寻道长度：45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640 柱面。
3.1.3 FCFS 寻道路径 SVG
下图展示了 FCFS 算法下磁头在柱面间的移动轨迹，可见路径杂乱无章，存在大量长距离跳跃。
3.2 最短寻道时间优先（SSTF）
SSTF 的核心思想是：每次选择距离当前磁头位置最近的请求进行服务。该算法通过局部贪心策略显著降低平均寻道时间，但可能导致“饥饿”问题——远离磁头的请求可能长时间得不到服务。
3.2.1 算法流程
- 磁头位于当前柱面，扫描所有未服务的请求。
- 计算每个请求与当前位置的距离，选择距离最小的请求。
- 移动到该请求柱面并服务，重复步骤 1~2 直至队列为空。
3.2.2 示例计算
使用与 FCFS 相同的请求队列（98, 183, 37, 122, 14, 124, 65, 67），起始柱面 53。SSTF 的寻道过程如下：
| 步骤 | 当前柱面 | 候选距离 | 选中柱面 | 移动距离 |
|---|---|---|---|---|
| 1 | 53 | 45,130,16,69,39,71,12,14 | 65（距离 12） | 12 |
| 2 | 65 | 33,118,28,57,51,59,2,2 | 67（距离 2） | 2 |
| 3 | 67 | 31,116,30,55,53,57,2,0 | 65（已服务）→ 37（距离 30） | 30 |
| 4 | 37 | 61,146,0,85,23,87,28,30 | 14（距离 23） | 23 |
| 5 | 14 | 84,169,23,108,0,110,51,53 | 98（距离 84）→ 122（距离 108）→ 124（距离 110）→ 183（距离 169） | 84 |
| 6 | 98 | 0,85,61,24,84,26,33,31 | 122（距离 24） | 24 |
| 7 | 122 | 24,61,85,0,108,2,57,55 | 124（距离 2） | 2 |
| 8 | 124 | 26,59,87,2,110,0,59,57 | 183（距离 59） | 59 |
总寻道长度：12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236 柱面。
3.2.3 SSTF 寻道路径 SVG
下图展示了 SSTF 的寻道轨迹，磁头移动更加集中，避免了大幅回退。
3.3 FCFS 与 SSTF 的全面对比
下表从多个维度对比两种算法的核心差异：
| 对比维度 | FCFS | SSTF |
|---|---|---|
| 调度依据 | 请求到达时间 | 与磁头当前距离 |
| 平均寻道长度 | 长（示例 640） | 短（示例 236） |
| 饥饿现象 | 无 | 有（边缘请求可能被无限推迟） |
| 公平性 | 完全公平 | 不公平，偏向中间柱面 |
| 实现复杂度 | 极低（FIFO 队列） | 中等（需维护距离计算） |
| 适用负载 | 低负载、顺序请求 | 中低负载、随机请求 |
| 最坏情况 | 请求顺序与柱面分布相反 | 持续有近距离请求到达，远距离请求饿死 |
3.4 饥饿问题深度分析
SSTF 的饥饿问题在以下场景中尤为突出：假设磁头当前位于柱面 100，队列中有柱面 101、102、103 的请求，同时有一个柱面 500 的请求。只要 101~103 的请求持续到达，柱面 500 的请求将永远无法被服务，因为每次选择时它都是最远的。
3.5 算法选择建议
- FCFS 适用场景：请求数量少、负载极低、对公平性有硬性要求的系统（如某些实时系统）。
- SSTF 适用场景：随机 I/O 为主、对平均响应时间敏感、能容忍个别请求延迟的通用系统。
- 折中方案：实际文件系统（如 Linux CFQ、Windows 的 I/O 调度器）通常混合使用多种策略，或采用基于优先级的变体。
3.6 本章小结
FCFS 和 SSTF 代表了磁盘调度设计的两个极端：公平 vs 效率。FCFS 实现简单、无饥饿，但寻道路径低效；SSTF 大幅降低平均寻道时间，却引入了不公平的饥饿风险。理解这两种基础算法的权衡，是掌握后续 SCAN、C-SCAN、LOOK 等高级调度算法的前提。在实际系统中，调度器的设计往往需要在公平性、吞吐量和响应时间之间寻找平衡点。