磁盘调度

前置知识#

• 机械硬盘由旋转盘片与移动磁头构成的基本结构；
• 一条 I/O 请求 = 读/写某个柱面的某个扇区；
• 队列与排序的基本概念。

学习目标#

• 说清一次机械磁盘 I/O 的三段时间构成，以及为什么寻道时间是主要矛盾；
• 掌握 FCFS、SSTF、SCAN、C-SCAN、LOOK、C-LOOK 六种调度算法的推演与总寻道计算；
• 理解各算法在吞吐量、响应时间、公平性上的取舍；
• 知道 SSD 时代调度问题的形态如何改变（TRIM、mq-deadline、bfq）。

1. 概念引入：电梯的调度智慧#

一个类比：一栋高楼只有一部电梯，10 个人在不同楼层按了按钮。聪明的电梯不会按按键先后逐趟飞（那会来回空跑），而是顺路接人、跑完一个方向再折返。磁盘调度算法就是给”电梯”（磁头）安排接客顺序的规则。

2. 磁盘结构与一次 I/O 的时间构成#

2.1 几何结构#

盘片高速旋转，表面划分成一圈圈磁道；所有盘片同一半径的磁道叠成一个柱面（磁头无需移动即可整体访问）；每条磁道等分成扇区（传统 512 字节，现代高级格式 4KB）。寻址顺序是：选磁头（柱面）-> 等旋转 -> 读扇区。

2.2 三段时间#

寻道时间：磁头臂移动到目标磁道，纯机械运动，典型 3-10ms，与移动距离近似线性相关
旋转延迟：目标扇区转到磁头下方，平均需要半圈，7200rpm 盘约 4.17ms
传输时间：数据真正读写，微秒级

一次随机 I/O 合计约 8-15ms，其中寻道占大头且最可优化——这就是磁盘调度算法的全部意义：通过重排队列中的请求，减少磁头来回奔跑的总距离。机械盘每秒约 100-200 次随机 I/O 的上限（IOPS），瓶颈正在于此。

3. 调度算法详解与推演#

统一用经典例子推演：磁头当前位于 53 号柱面，等待队列的柱面请求为

98, 183, 37, 122, 14, 124, 65, 67

3.1 FCFS：先来先服务#

按到达顺序服务。路径：53 -> 98 -> 183 -> 37 -> 122 -> 14 -> 124 -> 65 -> 67。

总寻道 = 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640 个柱面。

优点是绝对公平、实现零成本；缺点是磁头做无谓的全盘往返，吞吐量最差。适合请求稀少、无需优化的轻负载场景。

3.2 SSTF：最短寻道优先#

每次选择离当前磁头最近的请求。路径：53 -> 65 -> 67 -> 37 -> 14 -> 98 -> 122 -> 124 -> 183。

总寻道 = 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236 个柱面，比 FCFS 减少六成以上。

缺陷有二：

• 饥饿（starvation）：若队列源源不断地来 60-70 附近的请求，远端 183 号请求可能无限期得不到服务；
• 方向震荡：贪心只看最近，磁头可能在同一区域反复折返。

3.3 SCAN：电梯算法#

磁头沿一个方向一路服务到物理边缘，再反向扫描。假设当前向大柱面方向移动：

路径：53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 ->（到 199 边缘折返）-> 37 -> 14。

总寻道 = (199 - 53) + (199 - 14) = 146 + 185 = 331 个柱面。

SCAN 消除了方向震荡，且等待时间有上界（磁头最多扫两遍全盘），不会饥饿。刚被扫过的区域等待较久、中间区域等待较短，响应时间方差大于 SSTF。

3.4 C-SCAN：循环扫描#

SCAN 的反向回程不服务，等于”空驶”；C-SCAN 干脆让回程直接跳回另一端，只朝一个方向服务，把所有柱面的等待时间变得均匀：

路径：53 -> … -> 183 ->（199 边缘，跳回 0）-> 14。

总寻道 = (199 - 53) + 199 + 14 = 359 个柱面（含跨越全盘的空驶）。

3.5 LOOK 与 C-LOOK：不过度跑边缘#

SCAN/C-SCAN 硬性跑到物理边缘，但边缘往往没有请求。LOOK 只”望”到该方向最远的请求就折返：

路径：53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 37 -> 14，总寻道 = (183 - 53) + (183 - 14) = 299。

C-LOOK 同理：服务到 183 后直接跳到最小请求 14，再向上服务到 37：

总寻道 = (183 - 53) + (183 - 14) + (37 - 14) = 322。

3.6 六种算法对比#

实践结论：单方向扫描类（LOOK/C-LOOK）在吞吐与公平之间取得最佳平衡，是传统内核电梯算法（Linux 旧版 elevator/deadline）的思想底座。

4. 现代存储的调度#

4.1 从机械盘到 SSD#

SSD 没有磁头，任意逻辑块的访问延迟近乎一致（数十微秒量级），“减少寻道”的目标消失了。但调度并未退场，目标变成了：

• 合并相邻写：把对相邻块的多个小写合并，减少写放大；
• 防止饥饿：读请求必须优先于大批量顺序写（机械时代 deadline 的思想延续）；
• TRIM/Discard 透传：把”这些块已删除”的信息传给 SSD 主控，帮助其垃圾回收。

Linux 块层提供的现代调度器（cat /sys/block/nvme0n1/queue/scheduler 可查）：

机械盘推荐 mq-deadline 或 bfq；NVMe SSD 一般 none 或 kyber——“给 SSD 挂上为磁头设计的重型调度器”是历史遗留的性能反模式。

4.2 I/O 合并与预读#

调度之外，内核还有两招减少实际 I/O：合并（merge）把地址相邻的请求拼成一个大请求（一次传输多扇区远快于多次单扇区）；预读（readahead）检测到顺序读模式后提前把后续块读入页缓存，把多次磁盘访问折叠成一次。iostat -x 的 rrqm/s、wrqm/s 列即合并计数。

5. 完整示例：用代码算一遍寻道距离#

# disk_sched.py：同一请求队列上对比五种调度算法的总寻道距离
requests = [98, 183, 37, 122, 14, 124, 65, 67]
head, disk_max = 53, 199

def total(path):
    """路径上相邻点距离之和"""
    return sum(abs(b - a) for a, b in zip(path, path[1:]))

def fcfs():
    return [head] + requests

def sstf():
    cur, rest, path = head, requests[:], [head]
    while rest:                          # 每步贪心选最近请求
        nxt = min(rest, key=lambda r: abs(r - cur))
        path.append(nxt); rest.remove(nxt); cur = nxt
    return path

def scan(cscan=False):
    """SCAN 到物理边缘折返；C-SCAN 到上边缘后空驶回 0 再单向服务"""
    up   = sorted(r for r in requests if r >= head)
    down = sorted(r for r in requests if r < head)
    path = [head] + up + [disk_max]      # 向上扫到边缘
    if cscan:
        path += [0] + down               # 空驶回 0，再从小到大服务剩余请求
    else:
        path += sorted(down, reverse=True)
    return path

def look(clook=False):
    """LOOK 只到最远请求折返；C-LOOK 折返后跳到最小请求单向服务"""
    up   = sorted(r for r in requests if r >= head)
    down = sorted(r for r in requests if r < head)
    path = [head] + up
    if clook:
        path += down
    else:
        path += sorted(down, reverse=True)
    return path

for name, path in [("FCFS", fcfs()), ("SSTF", sstf()),
                   ("SCAN", scan()), ("C-SCAN", scan(True)),
                   ("LOOK", look()), ("C-LOOK", look(True))]:
    print(f"{name:>6}: {total(path)}")

运行 python disk_sched.py，输出：

  FCFS: 640
  SSTF: 236
  SCAN: 331
C-SCAN: 359
  LOOK: 299
C-LOOK: 322

与手推一致。试着把请求队列换成”集中在 50-70 的密集流 + 一个 183 的孤立请求”，即可复现 SSTF 的饥饿现象。

6. 常见陷阱与调试#

• 推演前未约定折返点：SCAN 到物理边缘还是最远请求、初始朝哪个方向，不同教材默认不同；先声明约定再计算，否则答案对不上。
• 混淆旋转延迟与寻道：本篇算法只优化寻道；旋转延迟由扇区排布与磁盘自带缓存处理，调度器管不到。
• 在 SSD 上纠结请求顺序：NVMe 上调整 I/O 顺序收益趋近于零，优化重心应转向队列深度、NUMA 亲和与文件系统层面。
• 误读 iostat 指标：await（平均单次 I/O 耗时）远超设备标称延迟才是瓶颈证据；util 在 SSD 与多队列设备上会高估饱和度，不能单独作为结论。

7. 实战场景#

• 数据库部署：把 redo 日志（顺序写、延迟敏感）与数据文件分盘；机械盘时代按”日志盘 LOOK 类调度、数据盘 deadline”调优。
• 虚拟机与容器宿主机：多租户混部时用 bfq 按 cgroup 分配 I/O 带宽，防止备份任务把交互 I/O 挤到饥饿。
• 故障定位：应用偶发卡顿且 iostat -x 1 显示 await 抖动，检查是否错误地为 SSD 启用了重型调度器，或队列深度设置过低。

小结#

初学者要点：

• 机械盘一次 I/O = 寻道 + 旋转 + 传输，寻道是主要矛盾；调度算法通过重排请求减少磁头移动。
• FCFS 公平但最慢；SSTF 贪心快但会饥饿；SCAN（电梯）与 LOOK 在吞吐与公平间平衡；C-SCAN/C-LOOK 让等待更均匀。
• 经典例子（磁头 53 起）六种算法总寻道：FCFS 640、SSTF 236、SCAN 331、C-SCAN 359、LOOK 299、C-LOOK 322。

进阶注意：

• SSD 上调度目标从”减寻道”变为”合并写、防饥饿、透传 TRIM”；NVMe 通常选 none 或 kyber，mq-deadline 是通用安全选择。
• 合并与预读在调度之前就消化了大量请求，iostat 的 rrqm/wrqm 与 await 是观察窗口。
• 考试与面试推演务必先确认约定（折返点、初始方向）。