磁盘调度

为什么磁盘访问要调度？

机械硬盘（HDD）读取一个数据的时间：

访问时间 = 寻道时间 + 旋转延迟 + 传输时间
             │           │           │
         移动磁头     等待扇区      读取数据
         到目标磁道   旋转到磁头下
             │           │           │
          ~5-10ms     ~4-8ms      ~0.1ms

💡 寻道占据了磁盘访问时间的大头——所以磁盘调度的核心目标就是尽量减少磁头移动距离。

磁盘调度就是决定多个 I/O 请求的执行顺序，使磁头移动总距离最小。

🏫 类比：图书馆取书 你在图书馆接到 10 个取书单，分布在 10 个不同书架上：

• 随机取：A 区 → Z 区 → B 区 → Y 区 → …（来回跑断腿）
• 排序取：A 区 → B 区 → … → Z 区（一趟走完）

经典磁盘调度算法

1. 先来先服务（FCFS）

按到达顺序处理请求。

磁道请求：98, 183, 37, 122, 14, 124, 65, 67
当前磁头位置：53

磁头移动：
53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67
  +45  +85  +146  +85  +108  +110  +59   +2
总移动：640 个磁道

优点：公平，简单 缺点：磁头来回跑，效率极低

2. 最短寻道优先（ SSTF / SSF）

选择离当前磁头最近的请求先处理。

当前在 53：
离 53 最近的请求是 65（差 12）→ 先处理 65
然后离 65 最近的请求是 67（差 2）→ 先处理 67
然后离 67 最近的是 37（差 30）→ 处理 37
...

SSTF 顺序：53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183
移动：    +12  +2  +30  +23  +84  +24  +2   +59
总移动：236 个磁道（比 FCFS 的 640 好很多！）

问题：饥饿——如果不断有近处的请求到来，远处的请求可能永远得不到服务。

3. SCAN（电梯算法）

磁头沿一个方向移动，一路处理经过的请求，到终点后折返。

磁头从 53 开始向内移动→
53 → 37 → 14 （向内到 0）→ 折返 → 65 → 67 → 98 → 122 → 124 → 183

移动：53→0 + 0→183 = 53 + 183 = 236

优点：无饥饿，性能较好 缺点：刚经过的请求要等磁头从终点折返回来

4. C-SCAN（循环 SCAN）

磁头只沿一个方向处理请求，到终点后快速折返到起点（不处理请求），重新开始。

53 → 65 → 67 → 98 → 122 → 124 → 183 →（快速回到 0）→ 14 → 37

移动：53→183 + 183→0 + 0→37 = 130 + 183 + 37 = 350

优点：等待时间更均匀——所有磁道的等待时间近似相等

💡 C-SCAN 适合负载均衡的场景——数据库、文件服务器等需要公平对待所有 I/O 请求的系统。

算法对比

算法	总寻道距离	公平性	饥饿	适用场景
FCFS	最长	✅ 最好	❌	低负载
SSTF	较短	❌ 不均	⚠️ 可能	响应时间优先
SCAN	较短	✅ 较好	❌	通用
C-SCAN	中等	✅✅ 最好	❌	均衡负载
LOOK	短	✅ 好	❌	SCAN 改进（不到终点就折返）

LOOK 和 C-LOOK

LOOK 是 SCAN 的改进——磁头不一定要移动到磁盘端点，只移动到最远请求的位置就折返。

SCAN：53→0（到端点）→183（到端点）
LOOK：53→14（最内请求）→183（最外请求）

C-LOOK 同理——C-SCAN 的改进，只到最外请求就折返。

💡 现代调度器实际使用的是 LOOK/C-LOOK——Linux 内核的 CFQ（完全公平排队）和 deadline 调度器都实现了类似算法。

SSD 为什么不需要磁盘调度？

SSD（固态硬盘） 没有磁头，访问任何位置的延迟都是均匀的（~0.1ms）。

HDD 访问时间 = 寻道 + 旋转 + 传输 = 5-15ms
SSD 访问时间 = 传输 = 0.05-0.1ms

但是 SSD 需要别的调度：

• TRIM：通知 SSD 哪些块已不再使用，SSD 内部可以提前擦除
• 磨损均衡：将写入分布到所有闪存块，延长寿命
• 垃圾回收：回收已删除块的空间

💡 Linux 在 SSD 上仍然有 I/O 调度器——不是为了优化寻道，而是为了合并请求和 QoS（服务质量）。

Linux I/O 调度器

# 查看当前 I/O 调度器
$ cat /sys/block/sda/queue/scheduler
mq-deadline kyber [bfq] none

# 切换调度器
$ echo kyber > /sys/block/sda/queue/scheduler

调度器	类型	适用场景
mq-deadline	多队列 + 截止时间	通用场景
BFQ	完全公平排队	桌面交互（低延迟）
Kyber	自适应	快速设备（NVMe SSD）
none	无调度	高性能 NVMe（直接让硬件处理）

算法对比：同一工作负载下的性能

用前面的示例请求（98, 183, 37, 122, 14, 124, 65, 67），起始磁头位置 53：

算法	总移动距离	特点
FCFS（先来先服务）	640 个磁道	公平但低效——来回跑
SSTF（最短寻道优先）	约 236 个磁道	比 FCFS 快 ~2.7 倍——但可能”饿死”远处请求
SCAN（电梯算法）	约 208 个磁道	最均衡——无饥饿，性能好
C-SCAN（循环电梯）	约 383 个磁道	比 SCAN 多走了”折返路程”——但等待时间更均匀

取书员的视角：

• FCFS = 哪个单子先来就去取哪本——在 A 区→Z 区→B 区来回跑
• SSTF = 永远去最近的”那本书”——近的总是优先，远处的书等很久
• SCAN = 从东走到西，一路顺手取——走一趟取完所有

小结

概念	要点
磁盘调度的目标	最小化寻道时间，提高吞吐量
SSTF	选最近的先做（可能饥饿）
SCAN / LOOK	电梯算法，一个方向走到底（无饥饿）
C-SCAN / C-LOOK	单向 + 快速折返（等待时间均匀）
SSD	无寻道开销，但需要 TRIM 和磨损均衡
Linux 调度器	mq-deadline（通用）、BFQ（交互）、Kyber（NVMe）

为什么先学这个？ 磁盘调度是 I/O 子系统的核心优化——理解了它，你就知道为什么 SSD 让服务器 I/O 性能飞跃。接下来转向 I/O 的更大图景：I/O 硬件与驱动模型。