磁盘调度算法实验，是操作系统课里最值得动手写一遍的经典实验。有同学觉得"这不就是给一堆磁道号排个顺序吗"，话是没错，但当你真的把请求队列、磁头位置、方向状态、寻道距离这些变量搅在一起，就会发现这个"排序"远没有表面那么简单。我当年做这个实验时，代码逻辑写得很顺，结果 SCAN 算法算出来的平均寻道距离和课本对不上，查了半天才发现是方向维护的问题。这篇文章把 FCFS、SSTF、SCAN 三种算法从原理到实现到踩坑完整写一遍，标题里的 FIFS 其实就是 FCFS（First Come First Served）的一个常见笔误，后面我都按 FCFS 来称呼。适合正在做操作系统实验、或者准备从零实现一个调度模拟器的同学。
1. 这个实验到底在验证什么
1.1 磁盘寻道的物理过程与调度问题的本质
要理解磁盘调度算法，先得明白磁盘读写慢在哪里。机械硬盘（HDD）读取一个扇区的数据，主要时间花在三个环节：寻道时间、旋转延迟、传输时间。其中寻道时间占比最大，也就是磁头从当前磁道移动到目标磁道所花的时间。磁头移动是纯机械动作，一臂甩过去，速度快慢取决于移动的磁道数。换句话说，总寻道距离越短，I/O 效率就越高。
磁盘调度算法的目标，本质上就是解决一个问题：当多个 I/O 请求同时到达，而磁头只有一个时，按什么顺序去服务这些请求，能让磁头走的冤枉路最少？
这个问题的难点在于，请求到达的顺序是随机的，磁头位置是动态变化的，不同调度策略在不同的请求分布下表现差异巨大。实验的意义不是背下三种算法的定义，而是亲手把"如何选择下一个服务对象"这条决策逻辑写清楚，用数据验证"调度策略直接影响系统性能"这个结论。
1.2 三种算法的核心区别一句话版
在动手写代码之前，先把三种算法的决策逻辑刻在脑子里：
- FCFS（先来先服务）：完全按请求到达顺序服务，不优化、不挑拣。实现最简单，但磁头可能来回跑冤枉路。
- SSTF（最短寻道时间优先）：每次从当前磁头位置出发，选一个距离最近的请求先服务。属于贪心策略，平均寻道距离通常很短，但可能出现"远处的请求一直等不到服务"的情况。
- SCAN（扫描算法，也叫电梯算法）：磁头先朝一个方向移动，沿途服务所有经过的请求，等走到最远端没有请求了，再反向移动，继续服务。像电梯一样"扫一遍再扫回来"。
这三者的选择逻辑完全不同：FCFS 看"谁先来"，SSTF 看"谁离我近"，SCAN 看"我当前朝哪个方向走"。代码实现上，三者的差异也完全体现在这几个判断条件里。
2. 三种算法的实现逻辑与代码骨架
2.1 FCFS：最朴素也最容易实现的基准线
FCFS 的实现没有任何算法含量，但它是实验里最重要的基准线。没有这个基准，你后面没法判断 SSTF 和 SCAN 到底优化了多少。
我习惯用一个结构体数组记录请求：
typedef struct { int track; // 磁道号 int arrived; // 到达序号，用于FCFS保持原始顺序 } Request;FCFS 的核心代码就一个循环：
int pos = start_pos; // 当前磁头位置 int total = 0; for (int i = 0; i < n; i++) { total += abs(requests[i].track - pos); printf("服务 %d: 磁头从 %d 移动到 %d，移动距离 %d\n", requests[i].track, pos, requests[i].track, abs(requests[i].track - pos)); pos = requests[i].track; }然后统计平均寻道距离：total / n。FCFS 的正确性很好验证，直接按请求数组的原始顺序走一遍就行。
这里有一个小细节容易忽略：总寻道距离的最后一段不需要回程。有些同学会在循环结束后额外加一段"磁头归位"的距离，这是不对的。实验统计的是服务完所有请求过程中磁头实际移动的距离，不需要虚拟一段返程。做实验时可以用手工计算核对程序输出，避免这种理解偏差。
2.2 SSTF：每次都要重新找最近
SSTF 的核心逻辑是：每次服务完一个请求，磁头位置更新了，再从剩余未服务的请求里重新找最近的一个。这个"重新找"是理解 SSTF 的关键——它不是一个排序排完就拉倒的算法。
实现上需要维护一个done[]标记数组，每个循环扫描所有未服务的请求，挑距离最小的那一个：
int pos = start_pos; int done[100] = {0}; int total = 0; for (int i = 0; i < n; i++) { int best = -1; for (int j = 0; j < n; j++) { if (!done[j]) { if (best == -1 || abs(requests[j].track - pos) < abs(requests[best].track - pos)) { best = j; } } } total += abs(requests[best].track - pos); pos = requests[best].track; done[best] = 1; }这里有个很容易掉进去的坑：平局怎么处理。比如当前位置在 50，同时存在 48 和 52 两个请求，距离都是 2。这时选哪个都会影响后续的寻道距离。我在实验中遇到这种情况时，统一按"磁道号小的优先"处理，并且在实验报告的说明里写清楚这个规则。不写清楚的话，后期对数据会非常头疼——同样的输入，你的程序和同学的程序差一个平局规则，结果就完全不一样了。
2.3 SCAN：方向状态才是核心
SCAN 算法实现起来比 SSTF 更绕，因为你需要维护一个当前移动方向。很多同学第一次写 SCAN 时容易把它理解成"先服务所有比我当前大的，再服务所有比我当前小的"，这种理解在方向设定为"先向大磁道号移动"时碰巧是对的，但如果初始方向改成"先向小磁道号移动"，结果就完全错了。
正确的 SCAN 实现要考虑三个要素：当前磁头位置、当前方向、每个方向上的请求。我推荐的实现方式如下：
int pos = start_pos; int dir = 1; // 1表示向磁道号增大的方向移动，-1表示减小的方向 int total = 0; int served = 0; while (served < n) { // 在当前方向上找最近的请求 int best = -1; int best_dist = INT_MAX; for (int j = 0; j < n; j++) { if (!done[j]) { int dist = (dir == 1) ? (requests[j].track - pos) : (pos - requests[j].track); if (dist >= 0 && dist < best_dist) { best = j; best_dist = dist; } } } if (best != -1) { total += best_dist; pos = requests[best].track; done[best] = 1; served++; } else { // 当前方向上没有请求了，反向 dir = -dir; } }这段代码有一个重要的边界问题：磁头走到最远端之后，是否需要移动到磁盘边界（0 号磁道或最大磁道号）再反向？严格意义上的 SCAN 算法，磁头会一直移动到磁盘的边界端点才反向，即使端点处没有请求也要"扫过去"。但 LOOK 算法则是在当前方向没有请求时立即反向，不需要走到边界。实验题目里如果只说 SCAN，不会特意区分这两种变体，我建议在实现时把两种都做了：用max_track参数控制是否走到边界，这样实验报告里可以直接对比讨论。
3. 数据设计：怎么准备测试用例才可信
3.1 一组能看出差异的请求序列
实验报告里不能只跑一组数据。一组数据说明不了任何问题，至少准备三组不同分布的请求序列，才能看出三种算法的特性。
我设计测试数据时习惯用一个"手工可计算"的序列，方便核对程序输出的正确性。比如假设磁盘磁道范围是 0-199，当前磁头位于 100，请求队列按到达顺序为：
55, 58, 39, 18, 90, 160, 150, 38, 184这组数据覆盖了几类典型情况：有比当前位置大的（90、160、150、184），有比当前位置小的（55、58、39、18、38），有分散两侧的，也有距离非常近的相邻请求。
三种算法的服务顺序和寻道距离如下表：
| 算法 | 服务顺序 | 总寻道距离 | 平均寻道距离 |
|---|---|---|---|
| FCFS | 55 → 58 → 39 → 18 → 90 → 160 → 150 → 38 → 184 | 498 | 55.33 |
| SSTF | 90 → 58 → 55 → 39 → 38 → 18 → 150 → 160 → 184 | 248 | 27.55 |
| SCAN(先向大方向) | 150 → 160 → 184 → 90 → 58 → 55 → 39 → 38 → 18 | 250 | 27.78 |
SSTF 和 SCAN 的差距只有 2，这个结果其实很有讨论价值：在这组数据下，SSTF 的贪心策略和 SCAN 的电梯策略几乎一样好。但换个数据分布，结论可能就不同了。实验报告里如果能点出这一点，说明你真的理解了这两种算法的本质区别——SSTF 追求的是"每一步最优"，SCAN 追求的是"方向稳定，避免来回震荡"。
3.2 边界情况与极端场景
除了常规数据，还必须测试边界情况，这是区分程序写没写明白的关键：
- 磁头位于 0 号磁道或最大磁道号：验证 SCAN 在反向时的边界处理是否正确。
- 请求队列全在磁头的同一侧：验证 SCAN 的反向逻辑——如果全部在右边，磁头应当一路向右服务完后反向，此时左边没有请求，是否还需要继续向左走到边界。
- 只有一个请求：三种算法的结果应该完全一致，都是直接移动过去。
- 请求队列包含重复磁道号：SSTF 的平局规则在这种情况下会频繁触发，可以用来检验你的平局规则是否稳定。
我实验时就因为"请求全在一侧"这个用例发现了 bug：SCAN 实现里，当前方向没有请求时直接反向，但反向之前没有更新磁头位置到边界端点，导致反向后的第一个服务距离计算错误。这类问题靠肉眼读代码很难发现，多组极端测试数据一跑就现原形了。
4. 算法实现里的典型坑和排查过程
4.1 SSTF 的"正确但不对"：平局规则引发的连锁误差
我第一次跑 SSTF 的时候，程序输出的平均寻道距离和手工计算结果差了 6。代码逻辑怎么看都是对的，每次确实选的是距离最近的请求。反复排查之后才发现问题出在平局处理上。
当时磁头在 40，请求队列里有 35 和 45 两个请求，距离都是 5。我的程序按数组顺序优先选了 35，手工计算时我下意识选了 45。后续的服务路径就完全分叉了，总寻道距离自然对不上。
排查思路很简单：在每次选择请求时打印当前磁头位置、所有候选请求及对应距离，手动模拟一遍决策过程。你会发现，SSTF 的结果严重依赖平局规则，而平局规则在算法定义里通常不会被强调，任何实现都会遇到。我的建议是：代码里固定一个规则（比如磁道号小的优先），实验报告里明确写出来，然后重新手工计算核对。
4.2 SCAN 方向维护不当：结果偏差的根源
SCAN 的坑比 SSTF 更隐蔽。我当时的实现是把请求按磁道号排序，然后先从小到大输出所有大于当前磁头位置的请求，再反向输出所有小于当前磁头位置的请求。这个实现跑常规测试数据完全正常，直到我改了初始方向。
实验题目没说 SCAN 的初始方向是什么，我默认"先向大磁道号方向"。但如果测试数据里当前磁头位置在 120，而请求都在 0-50 之间，按"先向大方向"的规则，磁头会先向右走到磁盘边界再回头，多走一大段冤枉路。而如果按"先向小方向"的规则，直接就能一路向左服务完所有请求。两个结果完全不一样。
真正的 SCAN 应该维护一个方向变量，而不是简单地"先大后小"或"先小后大"。这个方向变量会在每个请求服务完成后持续生效，直到当前方向确实没有请求了才翻转。排查时我打印了每一步的磁头位置和方向，立刻发现方向变量在服务完最后一个右侧请求后没有翻转，导致反向服务全部丢失。
4.3 一类通用的排查方法：打印每一步的移动过程
我在做这个实验时总结出一个通用排查法：任何调度算法的验证，都不要只看最终的平均寻道距离，要把每一步的服务顺序和移动距离打出来。具体来说，程序输出格式控制在：
当前磁头位置: X 选择请求: Y (距离=Z) 磁头移动: X -> Y，累计寻道距离: T这样每一行都对应算法决策的一次完整记录。手工模拟时逐行对照，哪里开始不一致，bug 就在哪里。这个方法对 FCFS、SSTF、SCAN 全适用，也适用于后面扩展 C-SCAN 和 LOOK。
5. 实验报告里的结果分析怎么写
5.1 数据呈现与结论提炼
实验报告光贴代码和运行截图是不够的。既然实验目的是理解调度策略对性能的影响，那数据分析就应该是报告的核心。
建议至少准备三组不同分布的请求序列，服务顺序和寻道距离做横向对比。我在自己的实验报告里按如下方式组织：
- 请求分布均匀且跨度大：SCAN 表现稳定，SSTF 与 SCAN 接近，FCFS 明显较差。
- 请求集中在磁头附近的小范围：SSTF 表现最佳，SCAN 因为需要走到边界再回头，会多出额外的行程。
- 请求集中在磁头的一侧：SCAN 的表现取决于初始方向，选对了方向非常高效，选错了方向会多出大量行程；SSTF 不受影响，始终按距离决策。
分析时要回答几个问题：为什么 SSTF 在绝大多数情况下都比 FCFS 好？SCAN 避免了哪种类型的"来回震荡"？SSTF 贪心策略的隐患（饥饿）在什么条件下会出现？
5.2 从三种算法到 C-SCAN、LOOK 的扩展思路
做完这个实验，如果还有余力，不妨把变体算法也实现一遍。这不是加工作量，而是理解上的一次质变：C-SCAN（循环扫描）的区别只在一点——磁头从一端到另一端后，直接快速返回起点，回程不服务任何请求；LOOK 的区别在于"不需要走到边界，当前方向没请求就立刻反向"。
实现变体时，你会发现核心架构大半可以复用。方向状态的维护、边界条件的处理、距离统计的逻辑，全都能直接沿用。唯一需要改的只是反向条件：SCAN 在"当前方向无请求且已到边界"时反向，LOOK 在"当前方向无请求"时直接反向，C-SCAN 在"到边界"时直接跳回起点且方向不变。
做完 SCAN 再做这几个变体，你对"调度策略的核心差异其实只有决策条件那几行"这句话会有更深的体会。
5.3 我在实际实验过程中的几个建议
最后说几个操作性很强的建议，都是我踩过之后觉得省时间的做法：
- 模块化设计：三种算法各写一个独立函数，输入是请求数组和初始磁头位置，输出是服务顺序和总寻道距离。这样后面扩展变体算法时，只需要复制函数框架，改中间的决策逻辑，不用动主程序。
- 用文件读测试数据：把请求序列放进文本文件，程序从文件读取，而不是编译时写死在代码里。改测试数据时不用重新编译，也方便批量跑多组实验。
- 一个坑：别把"已服务的请求"和"未服务的请求"混在一起。SSTF 和 SCAN 都需要判断某个请求是否已服务过，用
done[]数组标记是最简单的方案。不要删除已经服务的元素，因为删除操作会改变数组下标，导致后续引用时出错。标记法是最稳妥的。 - 运行前手工算一遍最终结果：哪怕只是用 Excel 把服务顺序拉一遍，都比代码输出错了之后回头查半天要快。我每次写完算法都会找一组小数据手工算，确认无误后再跑正式的大数据。
我在实际实验中发现，这个实验真正难的不是写代码，而是把算法行为和运行结果对应起来。如果你也遇到"程序输出看起来没问题，但就是和手工算的差那么一点"的情况，按上面说的方法，把每一步的决策和距离打印出来逐行对照，基本都能快速定位问题。做完这些，你再看课本上的磁盘调度章节，会发现那些算法描述不再是抽象的几段话，而是变成了一幕幕磁头移动的画面。
