IO调度算法：CFQ/Deadline/NOOP/BFQ

可视化演示

展示系统处理流水线、实时性能指标曲线及多方案对比分析，包含数据流转、吞吐延迟监控与方案评估。

调度器基础

后厨的传菜员每天面对的不仅是“先来后到”，还有灶台的特殊脾气：炒锅从凉到热需要时间，换一道菜就要重新刷锅、烧油。在计算机里，这个“烧油”过程就是磁盘寻道——磁头从一个扇区移动到另一个扇区，是最昂贵的操作。传菜员的第一个任务，是决定把哪张菜单递给大厨，才能让厨房既有节奏又少刷锅。

Linux 中，文件系统发出的读写请求不是直接砸向磁盘，而是先进入一个请求队列。IO 调度器就站在队列出口，像传菜员一样挑出下一个请求。它位于通用块层和磁盘驱动之间，既管理队列排序，还负责合并相邻地址的请求。比如两块数据在磁盘上挨得很近，就可以当作一道菜一次出锅，减少磁头移动。

调度器的核心目标可以概括为三点：提高吞吐、降低延迟、兼顾公平。但这三个目标常常互相打架。为了减少寻道，最好把所有请求按扇区位置排序，可这样可能让某个进程等太久；为了公平，最好严格轮转，可磁头又会来回乱跑。不同的调度算法，本质是对“少走冤枉路”和“别让人饿着”这两个需求的折中。

理解了后厨的瓶颈，再看四种传菜员就清晰多了：有人选择信命不折腾，有人紧盯急单，有人搞平均主义，还有人精细到给每位客人配营养师。

NOOP算法

如果你的厨房用的是电磁炉，加热极快，刷锅几乎不耗时，传菜员还需要劳心费力地给菜单排序吗？NOOP 的思路就类似这样——我尽量少添乱。它维护一个简单的先进先出队列，菜单按到来顺序排队，传菜员不重新排列，只在两张菜单点的菜恰好来自同一个锅位时，把它们合并成一批递给大厨。

NOOP 并不追求“最优路径”，它只做低成本的相邻合并。在机械硬盘上，这种“佛系”会导致磁头在扇区之间反复横跳，随机读写性能惨不忍睹。但在 SSD、NVMe 这类闪存设备上，寻道时间接近于零，重排请求带来的收益远小于调度本身的开销。因此内核新版本里，闪存设备常常使用 none 模式，也就是 NOOP 的继承者。

NOOP 的优缺点非常鲜明：优点是零复杂、CPU 开销极小、不会意外引入延迟抖动；缺点是面对机械盘时毫无作为，无法优化寻道顺序。真实世界里，把它用在 U 盘、SD 卡、虚拟机的 virtio-blk 后端也相当合适。

所以，NOOP 不是“没有传菜员”，而是一个信任“电磁炉”速度的传菜员——你炒得快，我就不帮你挑单了，免得越帮越忙。

Deadline算法

有些客人点的是“下单后 5 分钟必出”的急单，传菜员不能再傻傻排队，否则差评会越来越多。Deadline 调度器就是那个给每张菜单贴上时限标签的传菜员。它把读请求和写请求分别放进两个队列，读队列的“最晚上菜时间”默认比写队列短得多，这样读请求通常会被优先处理。

Deadline 会为每个请求计算一个绝对期限：到达时间加上一个可配置的上限。调度时，它先检查是否有请求濒临超时，如果有，立刻优先处理；如果没有，就继续按扇区顺序批量出菜，保持磁头移动高效。这种“平时规规矩矩，急单插队”的策略，比单纯按扇区排序多了一层防饿死保护。

$$\displaystyle \Delta t = t_{\text{deadline}} - t_{\text{now}}$$

1. 计算请求的截止时刻：请求到达后，系统用到达时刻加该类型请求的超时上限，得出 deadline。

$$\displaystyle t_{\text{deadline}} = t_{\text{arrive}} + \text{expire}$$

2. 获取当前调度时刻：调度器每次选请求时都读取系统当前时间。

$$\displaystyle t_{\text{now}} = \text{current\_time}$$

3. 求剩余时间：用截止时刻减去当前时刻，得到剩余时间 Δt，Δt 越小代表越紧急，调度器优先选择。

$$\displaystyle \Delta t = t_{\text{deadline}} - t_{\text{now}}$$

Deadline 调度器在机械硬盘时代非常流行，因为它既能保证交互式读操作的低延迟，又不会完全牺牲吞吐。它就像那个懂得“急单优先、顺路多做几个菜”的资深传菜员，是传统数据库服务器的常用选择。

CFQ算法

公司食堂里，如果有一个大胃王总在窗口前点十份菜，其他员工会排到崩溃。CFQ（完全公平队列）的思路是：把时间切成小片，每个员工轮流点菜，窗口绝不会被一个人独占。它给每个进程分配一个独立的请求队列，进程间按时间片轮转，谁也别想饿着谁。

每个进程队列在自己获得的时间片内可以提交若干请求。进程的优先级权重会影响时间片大小，权重越高，一次轮转能点到更多菜。CFQ 还支持 cgroup 分组调度，可以把一组进程打包成一个“部门”，部门内部再细分，非常适合多租户服务器场景。

我们可以用一个简化公式描述 CFQ 的时间片分配思想：

$$\displaystyle \text{slice}_i = \frac{w_i}{\sum_{j} w_j} \times T_{\text{round}}$$

1. 解释权重：每个进程有一个权重 w_i，代表它在调度器眼中的重要程度。

$$\displaystyle w_i = \text{priority weight of process } i$$

2. 计算总权重：分母是所有参与调度的进程权重之和，用于归一化。

$$\displaystyle \sum_{j} w_j = w_1 + w_2 + \dots + w_n$$

3. 得到时间片：进程 i 的时间片等于权重占比乘以一轮总时间 T_round。

$$\displaystyle \text{slice}_i = \frac{w_i}{\sum_{j} w_j} \times T_{\text{round}}$$

CFQ 的问题在于，它假设所有进程都是“人”，需要公平；但高速 SSD 上磁头移动不再昂贵，频繁切换进程队列反而带来额外开销。后来内核引入了 mq-deadline 和 none，传统 CFQ 逐渐淡出，但它“公平轮转”的思想依然影响着 BFQ 等新一代算法。

BFQ算法

如果 CFQ 是把时间片平均分给顾客，BFQ（预算公平队列）就是一位更精细的营养师：它不光看你排队次数，还看你每道菜的“份量”，再按你缴纳的会费（权重）分配上菜带宽。想象一个 VIP 包间总是点很多菜，普通散客只点一杯饮料——传菜员需要保证散客的饮料不会因为大宴席而等上一小时。

BFQ 会为每个进程计算“预算”，预算可以理解成允许上菜的总量。调度时，进程获得与其权重匹配的带宽，而且交互式小请求会被优先照顾，打开点菜平板、滑动界面这类操作几乎不会被大文件拷贝堵住。这就是为什么它非常适合桌面系统、平板电脑和低延迟交互场景。

但精细化管理也有代价：BFQ 需要维护更复杂的状态，CPU 开销明显高于 NOOP 和 Deadline。在纯高吞吐服务器上，它可能显得笨重。换句话说，这位营养师适合用在“顾客体验重要”的地方，而不是每分钟要出几百道菜的大排档。

性能评估

四种传菜员到底谁更强？不能光听自我介绍，得用数据说话。评估 IO 调度器主要看三类指标：吞吐量、延迟和公平性。吞吐量好比厨房一小时内能出多少道菜，延迟好比每道菜平均让客人等多久，公平性则看是不是有个别客人被长期冷落。

在 Linux 里，最常用的工具是 fio。我们可以用同一组随机读、顺序写负载，分别切换调度器后测量 IOPS、带宽和延迟分布。延迟不仅要看平均值，更要看 P99 甚至 P99.9，因为最惨的那百分之一个请求，往往就是用户感知卡顿的来源。

平均等待时间是一个基础指标，可以写成：

$$\displaystyle \text{avg\_wait} = \frac{1}{N} \sum_{i=1}^{N} (t_{\text{complete}, i} - t_{\text{arrive}, i})$$

1. 确认请求数量：N 代表本次统计中完成的 IO 请求总数。

$$\displaystyle N = \text{number of requests}$$

2. 计算单个请求等待时间：用完成时刻减到达时刻，得到该请求在队列中等待的时间。

$$\displaystyle \text{wait}_i = t_{\text{complete}, i} - t_{\text{arrive}, i}$$

3. 求和并取平均：把所有请求的等待时间加起来除以 N，就是平均等待时间。

$$\displaystyle \text{avg\_wait} = \frac{1}{N} \sum_{i=1}^{N} \text{wait}_i$$

性能评估的真实价值在于防止“迷信算法名气”。NOOP 可能在 SSD 上吞吐极高，但在机械盘上惨不忍睹；BFQ 延迟表现优异，但高并发下吞吐可能不如 Deadline。只有拿数据代替直觉，才能选出最合适当前厨房的传菜员。

选型优化

不同餐厅需要不同性格的传菜员：快餐店灶台多且快，用 NOOP 最省心；传统西餐厅讲究出菜节奏，Deadline 能平衡急单和翻台率；公司食堂人多口杂，CFQ 的公平轮转能安抚大多数员工；私人会所需要极致体验，BFQ 的精细分配才够格。

落到实际选型，机械硬盘优先考虑 Deadline 或 mq-deadline，它能显著降低随机读延迟；NVMe SSD 建议使用 none 或 NOOP，避免调度开销；桌面或容器中的交互式应用，可以考虑 BFQ。传统 CFQ 在新内核中已被 mq-deadline 和 none 取代，但在老系统上仍然会见到。

参数调优也有讲究：Deadline 的 read_expire 可以调小以降低读延迟，但太小会频繁打断写批量扫描，牺牲吞吐；CFQ/BFQ 的权重和 slice 需要结合业务进程的重要程度设置。虚拟化环境中，宿主机和虚拟机内部的调度器还会叠加，通常建议宿主机用 NOOP，让虚拟机自己管理 IO 策略。

最后记住一个原则：没有最好的调度器，只有最适合当前存储介质和业务模型的调度器。像选传菜员一样，先看清厨房的灶台、客流和菜品结构，再决定让谁上场。

AI 应用场景

Python 演示

class IORequest:    def __init__(self, seq, sector, deadline=None, pid=0):        self.seq = seq        self.sector = sector        self.deadline = deadline        self.pid = pid  def simulate(scheduler, requests, start=0):    pending = list(requests)    current = start    order = []    while pending:        selected = scheduler(pending, current)        pending.remove(selected)        current = selected.sector        order.append(selected)    distance = 0    current = start    for r in order:        distance += abs(r.sector - current)        current = r.sector    return order, distance  def noop(pending, current):    return min(pending, key=lambda r: r.seq)  def deadline(pending, current):    return min(pending, key=lambda r: r.deadline)  def cfq(pending, current):    return min(pending, key=lambda r: (r.pid, r.seq))  def sstf(pending, current):    return min(pending, key=lambda r: abs(r.sector - current))  if __name__ == '__main__':    reqs = [        IORequest(0, 45, deadline=8, pid=1),        IORequest(1, 12, deadline=2, pid=2),        IORequest(2, 80, deadline=6, pid=1),        IORequest(3, 30, deadline=4, pid=2),    ]    for name, fn in [('NOOP/FIFO', noop), ('Deadline', deadline), ('CFQ', cfq), ('SSTF', sstf)]:        order, distance = simulate(fn, reqs)        print(name, [r.sector for r in order], 'seek distance', distance)

1. def simulate(scheduler, requests, start=0)通用调度模拟器，接收一个“选请求策略”函数，返回服务顺序和总寻道距离。
2. pending.remove(selected)模拟请求被磁盘服务后从队列移除。
3. def noop(pending, current)NOOP 严格按到达序号选择请求，即先进先出。
4. def deadline(pending, current)Deadline 选择剩余时间最短的请求，对应 deadline 值最小。
5. def cfq(pending, current)CFQ 先按进程分组，组内按到达序号选择，实现最简单的轮流效果。
6. def sstf(pending, current)最短寻道优先调度，可作为理论上的“吞吐最优”参照。
7. distance += abs(r.sector - current)累加每次磁头移动距离，用来比较不同调度器的机械盘开销。

常见误区

面试题