磁盘调度算法实验是操作系统课里最值得动手写一遍的经典实验。有同学觉得这不就是给一堆磁道号排个顺序吗话是没错但当你真的把请求队列、磁头位置、方向状态、寻道距离这些变量搅在一起就会发现这个排序远没有表面那么简单。我当年做这个实验时代码逻辑写得很顺结果 SCAN 算法算出来的平均寻道距离和课本对不上查了半天才发现是方向维护的问题。这篇文章把 FCFS、SSTF、SCAN 三种算法从原理到实现到踩坑完整写一遍标题里的 FIFS 其实就是 FCFSFirst 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有分散两侧的也有距离非常近的相邻请求。三种算法的服务顺序和寻道距离如下表算法服务顺序总寻道距离平均寻道距离FCFS55 → 58 → 39 → 18 → 90 → 160 → 150 → 38 → 18449855.33SSTF90 → 58 → 55 → 39 → 38 → 18 → 150 → 160 → 18424827.55SCAN(先向大方向)150 → 160 → 184 → 90 → 58 → 55 → 39 → 38 → 1825027.78SSTF 和 SCAN 的差距只有 2这个结果其实很有讨论价值在这组数据下SSTF 的贪心策略和 SCAN 的电梯策略几乎一样好。但换个数据分布结论可能就不同了。实验报告里如果能点出这一点说明你真的理解了这两种算法的本质区别——SSTF 追求的是每一步最优SCAN 追求的是方向稳定避免来回震荡。3.2 边界情况与极端场景除了常规数据还必须测试边界情况这是区分程序写没写明白的关键磁头位于 0 号磁道或最大磁道号验证 SCAN 在反向时的边界处理是否正确。请求队列全在磁头的同一侧验证 SCAN 的反向逻辑——如果全部在右边磁头应当一路向右服务完后反向此时左边没有请求是否还需要继续向左走到边界。只有一个请求三种算法的结果应该完全一致都是直接移动过去。请求队列包含重复磁道号SSTF 的平局规则在这种情况下会频繁触发可以用来检验你的平局规则是否稳定。我实验时就因为请求全在一侧这个用例发现了 bugSCAN 实现里当前方向没有请求时直接反向但反向之前没有更新磁头位置到边界端点导致反向后的第一个服务距离计算错误。这类问题靠肉眼读代码很难发现多组极端测试数据一跑就现原形了。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 把服务顺序拉一遍都比代码输出错了之后回头查半天要快。我每次写完算法都会找一组小数据手工算确认无误后再跑正式的大数据。我在实际实验中发现这个实验真正难的不是写代码而是把算法行为和运行结果对应起来。如果你也遇到程序输出看起来没问题但就是和手工算的差那么一点的情况按上面说的方法把每一步的决策和距离打印出来逐行对照基本都能快速定位问题。做完这些你再看课本上的磁盘调度章节会发现那些算法描述不再是抽象的几段话而是变成了一幕幕磁头移动的画面。