扫码获取 VIP 码
添加管理员微信获取 VIP 码
磁盘调度算法是操作系统中I/O子系统的一个重要组成部分，也是软考系统分析师考试中几乎每年必考的高频知识点。对于大多数考生来说，这个专题表面上看起来不算太难，几种算法的规则几句话就能概括清楚，但到了考场上真刀真枪计算磁头移动距离的时候，往往因为粗心或者对算法的边界条件理解不透彻而丢分。本文将从磁盘的物理结构讲起，进而深入六种核心调度算法的原理和推演细节，再结合历年真题剖析命题人的挖坑套路，最后提炼出一套在考场上快速准确解题的方法论。读完这篇文章，你将对磁盘调度算法建立起从底层原理到考试技巧的完整认知体系。
要理解磁盘调度，首先得搞清楚磁盘究竟是怎么读写数据的。磁盘的物理结构由若干个圆形盘片叠加而成，这些盘片固定在同一根主轴上，以恒定速度旋转。每个盘片的两个表面都涂有磁性材料，用于存储数据。每个表面上有一个读写磁头，所有磁头连在同一组机械臂上，因此磁头只能同步移动，不能各自独立运动。盘片表面被划分为一个个同心圆环，每个圆环称为一个磁道。不同盘片表面半径相同的那一圈磁道，在垂直方向上正好对齐，合在一起称为一个柱面。每个磁道又被等分成若干段圆弧，每段称为一个扇区，扇区是磁盘读写的最小单位。
磁盘完成一次数据读写，需要经历三个步骤。第一步是寻道，磁头臂带动所有磁头一起移动到目标数据所在的柱面。磁头臂是机械部件，移动速度受惯性和摩擦的制约，因此寻道时间在三个步骤中通常占比最大。第二步是旋转延迟，磁头到达目标柱面后，盘片还需要继续旋转，直到目标扇区恰好转到磁头正下方。平均而言需要等待半圈，所以旋转延迟约等于磁盘旋转一周时间的一半。第三步才是实际的数据传输，磁头在盘片飞过的瞬间读取或写入磁信号。由于现代磁盘的传输速率远高于机械移动速度，传输时间在总时间中的占比相对较小。
操作系统在运行过程中，经常面临多个进程同时发起磁盘读写请求的场景。这些请求的目标柱面可能散落分布在磁盘的各个位置，如果操作系统不加干预，简单地按照请求到达的顺序逐一处理，磁头就会在磁盘两端来回跳跃，把大量时间浪费在无意义的机械移动上，大幅拉低系统的整体吞吐量。磁盘调度算法的任务，就是主动重排请求队列中各项请求的处理顺序，在保证每个请求最终都能得到服务的前提下，让磁头移动的总距离尽可能缩短，从而提升系统的I/O效率。
先来先服务算法，英文全称First Come First Served，是磁盘调度中最朴素、最容易理解的一种策略。它的核心思想不涉及任何复杂的判断逻辑，就是谁先到达就先为谁服务，完全按照请求进入队列的时间先后顺序依次处理。从实现角度看，FCFS只需要一个普通的先进先出队列，调度器每次从队头取出请求执行，新来的请求追加到队尾即可。FCFS最大的优势在于公平，任何请求都不会因为没有排在队列前端而被无限期搁置，也不存在某个请求被饿死的情况。程序员编写操作系统代码的时候，FCFS是代码量最少的调度器。
但FCFS的问题也恰恰出在它的简单上。请求到达的先后顺序与它们在磁盘上的物理位置没有任何关联，因此FCFS的磁头移动模式完全是随机的，移动距离可能非常巨大。假设磁头当前停留在50号柱面，请求队列中依次有待处理的请求位于100号、20号、180号、40号、150号这五个柱面。FCFS按照来单顺序处理，磁头从50移动到100，距离为50；从100再折返到20，距离为80；从20跳到180，距离为160；从180掉头到40，距离为140；最后从40到150，距离为110。五个请求处理完毕，磁头总共移动了50加80加160加140加110等于540个柱面，而实际请求的最远跨度不过从20号到180号之间160个柱面的范围。磁头白跑了大量冤枉路，典型的低效率调度。
最短寻道时间优先算法英文缩写为SSTF，全称Shortest Seek Time First。它在FCFS的基础上向前迈了一大步，引入了对请求物理位置的考量。SSTF的调度规则简单明了且极具攻击性：每次从请求队列中选出与当前磁头位置距离最近的那个请求，优先执行。这种策略本质上是一个贪心算法，每一次决策都只着眼于当下的局部最优，不去规划未来的全局效果。实现时需要在每次磁头完成一个请求后重新扫描整个队列，找出最小距离的那个请求作为下一个目标。
在大多数实际场景中，SSTF的性能远比FCFS出色。仍以磁头在50号柱面、请求分布在20号、40号、100号、150号、180号的案例来演示。SSTF的推演过程如下：磁头从50出发，距离最近的请求是40号柱面，距离为10，于是先处理40号；从40号出发，最近的变成了20号，距离为20；到了20号之后，剩下的请求中100号距离80最近，处理它；然后是150号距离50，再然后是180号距离30。总移动距离等于10加20加80加50加30，合计190个柱面。与FCFS的540相比，SSTF把总移动距离压缩到了原来的三分之一左右，优化效果非常显著。
然而SSTF有一个在软考中被反复考查的致命弱点，那就是饥饿问题。想象这样一个场景：磁头当前在50号柱面附近，而磁盘100号到150号这片区域持续有新的读写请求产生。由于这些请求始终离磁头更近，SSTF会一直优先处理它们，那些位于200号柱面之外甚至更远位置的请求则可能永远排不上号，一直在队列里等待直到进程超时或者被用户手动取消。这种某些请求长期得不到服务的现象就是饥饿。软考命题人特别喜欢在这个点上设问，给出一个请求序列让考生判断在SSTF策略下哪个请求会被饿死，或者要求分析SSTF是否一定优于FCFS。
扫描算法SCAN因其行为酷似大楼电梯的运行模式，也常被称作电梯算法。电梯在一栋楼里上下运行，沿途每个按下按钮的楼层都会按顺序停靠，到了最高层才调头下行，到了最低层再调头上行。SCAN完全复刻了这套逻辑：为磁头设定一个初始移动方向，磁头沿着这个方向一路前进，处理沿途遇到的所有请求，直到抵达磁盘的最外圈或最内圈物理边界，然后掉转方向，沿相反方向继续扫描并处理遇到的请求。
仍用前面的数据来推演：磁头在50号柱面，设为向0号柱面方向移动。请求队列中有20号、40号、100号、150号、180号。SCAN的处理顺序是：磁头从50向0移动，途中遇到40号处理它、遇到20号处理它；到达0号物理边界后掉头向199号方向移动，沿途依次处理100号、150号、180号。总移动距离为10加20加20加100加50加30，等于230个柱面。SCAN的表现通常略好于FCFS，但在一些特定请求分布下可能弱于SSTF。它最核心的价值在于彻底杜绝了饥饿问题，因为磁头无论如何都会扫遍整个磁盘范围，每一个柱面上的请求都有被照顾到的机会。
循环扫描算法C-SCAN在SCAN的基础上做了一道手术级别的改动。SCAN双向都有服务，但这也导致磁盘中间区域的请求平均等待时间偏短，而靠近内圈和外圈边缘的请求等待时间偏长，出现了地理位置的天然不公平。C-SCAN的设计者认为这种不对等不应该存在，于是把规则改成了这样：磁头始终只沿一个方向处理请求，到达最远端物理边界后不调头，而是快速空驶回到起点方向的最远端，在回程中不处理任何请求，然后从起点重新开始扫描。
同样的例子在C-SCAN下表现如何？磁头从50向0移动，沿途处理40号和20号请求；到达0号后不做停留，也不看沿路有没有请求，直接快速跳回到199号柱面（最外圈起点）；然后从199向0方向重新开始扫描，沿途处理180号、150号、100号这些剩下的请求。这个回程跳跃虽然白白浪费了一段寻道距离，但换来了所有位置等待时间的均匀分布，对需要保证各用户服务质量一致的场景来说，C-SCAN的公平性远胜于SCAN。
LOOK算法是对SCAN的一次务实改良。SCAN有个显而易见的浪费行为：磁头一定要走到磁盘的物理边界才掉头，如果最外圈到最内圈只有几十个柱面范围内有实际请求，SCAN仍然要走过完整的两百个柱面，多跑的那部分路程没有服务任何一个请求。LOOK的改进就是让磁头走到该方向最后一个有待处理请求的柱面就立刻掉头，不再死板地跑到物理边界。对应地，C-LOOK则是在C-SCAN基础上应用同样的优化，磁头到达最后一个有请求的位置后直接跳回反方向第一个有请求的位置。在实际操作系统的实现中，LOOK和C-LOOK反而比标准SCAN和C-SCAN更为常见，因为当请求集中在某个区间时，这一细节优化的收益相当可观。
磁盘调度算法在软考中的命题套路非常成熟，坑位也相对固
本篇完！