磁盘调度

磁盘调度是在多个待处理 I/O 请求之间决定服务顺序的机制。机械硬盘移动磁头需要时间，把相邻位置的请求放在一起，可能减少来回寻道；但如果只照顾最近的请求，远处的请求又可能一直等下去。

面试中的调度算法题需要同时解释选择规则和代价。算出总移动距离只是其中一步，还要说明初始方向、边界和请求到达条件，以及为什么这套机械盘模型不能直接当作 SSD 的性能结论。

1. 面试核心

先记住这几条，再读正文

• 调度要在吞吐、等待时间、公平性和自身开销之间取舍。机械盘还要考虑寻道与旋转，移动距离不等于完整 I/O 延迟。卡 · 机械盘的访问成本
• FCFS 按到达顺序，SSTF 每次选最近请求；SCAN 沿一个方向服务到边界再折返，LOOK 只走到该方向最远请求。局部最近不保证全局最优。 卡 · 基本调度算法卡 · FCFS 与 SSTF
• C-SCAN、C-LOOK 只沿一个方向服务，返回时不服务沿途请求；返回移动也有代价，做题时要明确是否计入。卡 · SCAN 与 LOOK
• 有限静态队列会排完，不代表动态请求流不会饥饿。持续到来的近处请求可能让 SSTF 一直推迟远处请求，需要结合批次、等待时间或公平性约束。卡 · 动态到达与饥饿
• SSD 没有机械寻道，但仍有排队、并行度和资源竞争。不按磁道重排，不等于没有队列或调度问题。卡 · SSD 仍然需要管理请求
• 请求的提交顺序、派发顺序、完成顺序和持久化保证不同。不能靠调度算法替代文件系统与设备的同步约定。卡 · 调度顺序不等于持久化顺序

2. 请求为什么会排队

卡 · 磁头移动距离越短，一次 I/O 就一定越快吗？

块 I/O 请求描述对块设备某个逻辑地址范围的读写。应用同时读写文件，或者后台正在回写缓存时，底层可能积累多个请求；设备能并行处理多少请求又有上限，因此需要等待和选择。

应用的一次 read 或 write 不一定恰好对应一个设备请求。缓存命中可能不访问设备，一次操作也可能拆成多个请求，相邻请求则可能合并。文件名与数据块的组织见磁盘与文件系统排查。

调度关注的是「队列里下一步处理谁」。应用在等待期间是否阻塞、怎样获得完成结果，则属于 I/O 模型。采用异步接口后，设备队列仍然可能很长。

2.1 机械盘的访问成本

寻道是把磁头移动到目标磁道附近的过程，旋转等待是等待目标扇区转到磁头下方的过程，之后才传输数据。一次机械盘请求的响应时间，可以粗略拆成：

排队等待 + 寻道 + 旋转等待 + 数据传输 + 其他处理开销

磁头少移动一些，可以减少一部分寻道成本，但距离与时间并不严格成正比，旋转位置、请求大小和缓存等也会影响结果。因此，「总共移动 200 个磁道」不能直接换算成「耗时 200 毫秒」，也不能据此保证真实吞吐提升多少。

教材会用柱面号表示径向位置：多个盘面上半径相同的磁道组成一个柱面。下面用这个简化坐标计算移动距离。真实系统通常看到逻辑块地址，而不是完整的物理几何与磁头位置，设备内部也可能继续调度。

2.2 调度目标并不完全一致

减少总移动量有利于机械盘连续处理一批请求，但某个请求可能因此等得更久。评价时需要分别看：

目标	关注的问题
吞吐量	单位时间完成多少请求或多少字节
平均等待与尾部延迟	一般请求等多久，最慢的一部分是否被拖延
公平性与饥饿	某个进程或请求是否长期得不到服务
调度开销	为排序、合并和维护队列消耗多少 CPU 与同步成本

如果两个方案只比较了一批静态请求的移动距离，就还没有比较在线到达时的尾延迟。设备指标与应用延迟也要结合起来解释，见 Linux 性能排查。

3. 基本调度算法

卡 · 磁盘调度解决什么问题，FCFS、SSTF 与扫描算法各怎样选择请求？卡 · SSTF 是否一定让整批请求的总移动距离最短？卡 · SCAN、LOOK、C-SCAN、C-LOOK 的距离计算有哪些区别？

3.1 FCFS 与 SSTF

FCFS（First-Come, First-Served，先来先服务）按请求进入队列的顺序处理。规则简单，后来的请求不会因为位置更近而插到前面，但相邻两次访问可能相距很远，造成磁头反复来回移动。

SSTF（Shortest Seek Time First，最短寻道时间优先）在当前位置选择最近的待处理请求。下面的教学模型用柱面距离代表寻道代价；实际最短访问时间还可能需要考虑旋转等因素。

SSTF 是贪心选择，只决定当前一步最近，不保证整批请求的总距离最短。例如从 50 出发，请求为 49、52、0：

• SSTF 走 50 → 49 → 52 → 0，距离为 1 + 3 + 52 = 56。
• 另一条顺序 50 → 52 → 49 → 0，距离为 2 + 3 + 49 = 54。

第二条先走得稍远，却避免了之后的一段折返。这已经足以否定「每一步最近，所以总体一定最优」。

3.2 SCAN 与 LOOK

SCAN 沿一个方向移动，依次服务沿途请求，到磁盘边界后反向，再服务另一方向的请求。它像电梯保持当前方向前进，而不是每服务一个请求就重新决定向哪边走。

LOOK 保留同方向依次服务的规则，但只走到该方向当前最远的待处理请求就折返，不为到达物理边界额外空走。

例如磁头在 50，先向大号方向走，这一侧最远请求在 190，磁盘边界是 199。还有另一侧请求时，SCAN 先走到 199 再折返，LOOK 可以从 190 就折返。计算前必须说明初始方向，否则同一队列也会得到不同路线。

3.3 C-SCAN 与 C-LOOK

C-SCAN（Circular SCAN）只沿一个方向服务请求。到达该方向的磁盘边界后，返回另一端，返回途中不服务请求，再开始下一轮同方向服务。

C-LOOK 把折返点收缩到待处理请求：服务到当前方向最远请求后，返回另一侧最远的待处理请求，再沿原服务方向继续。

例如只向大号方向服务，C-SCAN 可以走到 199，再回到 0；C-LOOK 则可能从 190 直接回到最小请求 16。这里的「返回」仍然要移动磁头，不是瞬间传送。循环扫描让位置上的服务周期更规则，但并不承诺每个请求等待完全相同，也不保证这批数据的总距离更短。

4. 同一批请求的推演

卡 · SSTF 是否一定让整批请求的总移动距离最短？卡 · SCAN、LOOK、C-SCAN、C-LOOK 的距离计算有哪些区别？

4.1 先固定计算条件

下面全部使用同一个静态模型，条件由本站给出：

• 柱面范围为 0…199，初始位置为 50，SCAN 系列初始方向为大号方向。
• 初始队列按到达顺序为 82、170、43、140、24、16、190，处理中没有新请求加入。
• 每次服务不另加固定时间，只统计相邻位置之差的绝对值之和；返回移动计入距离。
• 在最后一个请求完成处停止统计，不再为下一轮空闲扫描移动。到达边界但没有请求时，只记移动，不算完成请求。

算法	从 50 出发的移动路线	总距离
FCFS	50 → 82 → 170 → 43 → 140 → 24 → 16 → 190	642
SSTF	50 → 43 → 24 → 16 → 82 → 140 → 170 → 190	208
SCAN	50 → 82 → 140 → 170 → 190 → 199 → 43 → 24 → 16	332
LOOK	50 → 82 → 140 → 170 → 190 → 43 → 24 → 16	314
C-SCAN	50 → 82 → 140 → 170 → 190 → 199 → 0 → 16 → 24 → 43	391
C-LOOK	50 → 82 → 140 → 170 → 190 → 16 → 24 → 43	341

例如 SCAN 的距离为 (199 - 50) + (199 - 16) = 332；C-SCAN 则是 (199 - 50) + (199 - 0) + (43 - 0) = 391。加粗的 199、0 是本例中的额外边界位置，不是原队列里的请求。

SSTF 在这批数据中的距离最小，不代表它对任意队列都最优，更不代表它有最好的公平性。这里运行的是算法模型，没有测量真实设备的 IOPS、吞吐或延迟。

4.2 一个可运行的 SSTF 实现

下面保留重复请求，同距离时按原队列中的先后顺序选择；空队列返回空顺序和零距离。输入约定为整数柱面号，越界时拒绝执行。

def sstf(requests, head, last=199):
    pending = list(requests)
    if last < 0 or not 0 <= head <= last:
        raise ValueError("invalid disk range or head")
    if any(not 0 <= position <= last for position in pending):
        raise ValueError("request outside disk range")

    order = []
    distance = 0
    while pending:
        index = min(
            range(len(pending)),
            key=lambda i: (abs(pending[i] - head), i),
        )
        position = pending.pop(index)
        distance += abs(position - head)
        order.append(position)
        head = position
    return order, distance


requests = [82, 170, 43, 140, 24, 16, 190]
print(sstf(requests, 50))

输出为 ([43, 24, 16, 82, 140, 170, 190], 208)。pending 是输入列表的副本，每次 pop 只移除一个请求，因此两个请求即使位置相同，也不会因去重而丢失。选择最近请求需要扫描剩余队列，整个实现的时间复杂度为 O(n²)，适合推演机制，不是生产块设备调度器。

5. 动态到达与饥饿

卡 · 磁盘调度解决什么问题，FCFS、SSTF 与扫描算法各怎样选择请求？卡 · SSTF 为什么可能饥饿，有限静态队列能证明不会饥饿吗？

饥饿是一个请求虽然持续等待，却一直得不到服务。静态队列最终会被 SSTF 取空，因此只测一批固定请求，观察不到持续新请求引发的饥饿。

设磁头在 50，远处位置 0 的请求已经排队。每次选择前，又有一个位于 50 或 51 的近处请求到来，SSTF 总能先找到更近的请求。如果这种到达模式一直持续，位置 0 的请求就会一直被推迟。

有限模拟只能说明某个请求在这一段到达流中被延后。要推导无限饥饿，还要指出同样的到达模式可以持续重复；停止新请求后，远处请求最终仍会被处理。

防止长期等待，需要给位置优化增加约束。例如：

• 按扫描方向前进，并明确新请求什么时候能加入当前扫描。
• 冻结本轮处理的请求集合，把新到达请求留到下一批，避免当前批次被持续延长。
• 记录等待时间，对等待过久的请求提高服务机会；在吞吐与公平性之间作出取舍。

单说「使用扫描算法，所以有严格最大延迟」仍不充分。请求到达速率、单次服务时间、是否持续接纳新请求，以及设备是否正常工作，都会影响上界。若请求长期到达得比设备处理得还快，队列可能持续增长。

Linux 的 deadline 类调度同时考虑按位置服务与请求等待；BFQ 关注进程或组之间的服务份额。这些实现说明真实调度会加入更多约束，不能直接等同于上面的六个静态模型，也不需要把内核调参表当作算法定义。

6. SSD 与实际 I/O 层次

卡 · SSD 没有寻道，是否可以说它不需要 I/O 调度？卡 · 按顺序提交或派发两个写请求，能保证按顺序完成并持久化吗？

6.1 SSD 仍然需要管理请求

SSD 用闪存等固态介质存储数据，没有机械磁头的寻道与旋转等待。因此，按柱面距离比较 SSTF、SCAN 的方法，不适合直接预测 SSD 的耗时。

这不意味着 SSD 上每次访问代价都相同。读写类型、请求大小、内部并行度、闪存地址映射和垃圾回收等，仍会影响表现。队列过长也可能增加等待，所以调度仍要考虑公平性、延迟、合并机会和软件开销。

Linux blk-mq 使用软件队列与硬件派发队列，适应多核和设备并行处理。选择 none 表示该层不采用额外的 I/O 调度器重排策略，不表示应用、内核和设备之间已经没有排队，也不表示设备控制器不再安排请求。

要比较 SSD 上的具体策略，应明确设备、请求大小、读写比例、队列深度与负载，再看吞吐和尾延迟。本文的柱面模拟不能为任何生产设备选择提供性能保证。

6.2 调度顺序不等于持久化顺序

操作系统派发请求后，设备还可能并行执行，完成顺序也不必等于派发顺序。应用先后调用两次写入，更不能仅凭调用顺序推导数据在掉电后的状态。

正确性要由对应层次的同步机制表达。文件系统有写回与同步约定，块设备接口有缓存刷新和相关顺序约束；应用需要检查同步操作的结果。文件与目录的 fsync 边界见磁盘与文件系统排查。

因此，不能为了减少寻道就任意交换存在依赖的操作，也不能因为设置了某个调度器，就承诺数据库事务或文件更新已经持久化。

7 · 面试题卡片

先想答案，再翻面先在心里答一遍，再点开卡片对照参考回答。卡片之间可以左右切换，看完会回到这里。

逐张翻看 7 张 →

基本调度算法

磁盘调度解决什么问题，FCFS、SSTF 与扫描算法各怎样选择请求？

考察 1 点 · 相关 §3 §5未标记

机械盘的访问成本

磁头移动距离越短，一次 I/O 就一定越快吗？

本站自测

考察 1 点 · 相关 §2.1 §2.2未标记

FCFS 与 SSTF

SSTF 是否一定让整批请求的总移动距离最短？

本站自测

考察 1 点 · 相关 §3.1 §4.2未标记

SCAN 与 LOOK

SCAN、LOOK、C-SCAN、C-LOOK 的距离计算有哪些区别？

本站自测

考察 1 点 · 相关 §3.2 §3.3 §4.1未标记

动态到达与饥饿

SSTF 为什么可能饥饿，有限静态队列能证明不会饥饿吗？

本站自测

考察 1 点 · 相关 §5未标记

SSD 仍然需要管理请求

SSD 没有寻道，是否可以说它不需要 I/O 调度？

本站自测

考察 1 点 · 相关 §6.1未标记

调度顺序不等于持久化顺序

按顺序提交或派发两个写请求，能保证按顺序完成并持久化吗？

本站自测

考察 1 点 · 相关 §6.2未标记

未标记的卡读完后明天进入复习；已标记的按状态安排

本页题目与参考回答

7.1 磁盘调度解决什么问题，FCFS、SSTF 与扫描算法各怎样选择请求？

考察重点：请求选择规则、方向与边界，以及效率和公平性的取舍。

相关内容：基本调度算法、动态到达与饥饿。

参考回答

**磁盘调度决定多个待处理请求的服务顺序，要兼顾访问成本与等待。**FCFS 按到达顺序；SSTF 选择离当前位置最近的请求，但可能让远处请求饥饿。

SCAN 保持方向到边界再折返，LOOK 只走到该方向最远请求；C-SCAN、C-LOOK 只在一个方向服务，返回时不处理沿途请求。推演时要说明初始方向、边界、到达方式和返回距离是否计入，不能只背算法名称。

7.2 磁头移动距离越短，一次 I/O 就一定越快吗？

考察重点：寻道、旋转、传输与排队的不同成本。

相关内容：机械盘的访问成本、调度目标并不完全一致。

参考回答

**不一定，移动距离只近似描述一部分寻道成本。**机械盘还要等待目标扇区旋转到位并传输数据，请求也可能先在队列中等待。距离与寻道时间并不严格成正比，真实系统还有缓存与并行处理等因素。

比较移动距离可以帮助理解算法，但不能直接换算成毫秒或生产吞吐，更不能忽略单个请求的等待时间。

7.3 SSTF 是否一定让整批请求的总移动距离最短？

考察重点：局部贪心与整体目标的区别，能给出反例。

相关内容：FCFS 与 SSTF、SSTF 参考实现。

参考回答

**不保证，SSTF 只选择当前最近请求。**从 50 出发处理 49、52、0，SSTF 的距离为 56；先访问 52，再到 49、0，距离是 54，因此局部最近不能证明全局最短。

即使某批数据距离更短，也不能进一步推出动态到达时没有饥饿。

7.4 SCAN、LOOK、C-SCAN、C-LOOK 的距离计算有哪些区别？

考察重点：物理边界与请求端点、单向服务与返回移动、统计停止条件。

相关内容：SCAN 与 LOOK、C-SCAN 与 C-LOOK、先固定计算条件。

参考回答

**SCAN 系列到物理边界，LOOK 系列到待处理请求端点；循环版本返回时不服务，但返回不是零成本。**计算前还要确定磁头起点、初始方向、请求到达条件，以及最后一个请求完成后是否继续计距离。

按正文模型，SCAN 为 332，LOOK 为 314；C-SCAN 为 391，C-LOOK 为 341。不能漏掉 C-SCAN 的 199 → 0 或 C-LOOK 的 190 → 16，也不能把无请求的边界当作额外完成请求。

7.5 SSTF 为什么可能饥饿，有限静态队列能证明不会饥饿吗？

考察重点：动态到达、等待约束与有限实验的证明范围。

相关内容：动态到达与饥饿。

参考回答

**持续到来的近处请求可能让 SSTF 一直跳过远处请求，有限静态队列排空不能排除这一情况。**可以构造每次选择前都有更近请求到来的模式，说明旧请求如何被反复推迟。

扫描方向、冻结批次和等待时间约束可以改善这种偏向，但严格的最大等待保证还依赖负载和服务条件，不能只凭算法名称作出承诺。

7.6 SSD 没有寻道，是否可以说它不需要 I/O 调度？

考察重点：介质成本变化、队列、公平性、并行度和软件开销。

相关内容：SSD 仍然需要管理请求。

参考回答

**不能这样说。SSD 不需要优化机械寻道，但仍要管理请求排队、资源竞争、并行度和等待。**具体策略的收益要结合设备和负载验证，软件重排自身也有成本。

Linux none 表示该层不使用额外的调度器重排策略，不等于取消所有队列或设备内部调度。柱面距离模拟也不能用来预测 SSD 性能。

7.7 按顺序提交或派发两个写请求，能保证按顺序完成并持久化吗？

考察重点：提交、派发、完成与持久化的层次，操作依赖的表达。

相关内容：调度顺序不等于持久化顺序。

参考回答

**不能仅凭顺序提交或派发作出保证。**请求可能在多层缓存和队列中流转，设备可以并行执行，完成也不自动等于满足应用所需的持久化条件。

依赖顺序和持久化要求需要通过文件系统与设备提供的同步约定表达，并检查返回结果。选择调度算法只改变部分服务策略，不能替代这些正确性机制。

8. 参考资料

• Operating System Concepts 第 9 版配套资料：Mass-Storage Structure
• OSTEP 1.10：Hard Disk Drives
• OSTEP 1.10：Flash-based SSDs
• Linux 6.6：Multi-Queue Block I/O
• Linux 6.6：Deadline I/O scheduler、mq-deadline 实现
• Linux 6.6：BFQ

来源：Coding 101 原文 · 免费阅读，引用请保留出处。内容使用说明