Linux Deadline 调度器实现机制

第 1 章：Deadline 调度器概述与设计目标

1.1 Deadline 调度器的起源与目标

    Deadline 调度器（Deadline I/O Scheduler）是 Linux 内核中用于块设备的请求调度算法之一。它最初设计的目标是解决传统 CFQ（Completely Fair Queuing） 调度器在高负载情况下出现的延迟不可控问题。CFQ 更强调公平性，但在对实时性和延迟敏感的应用场景下（如数据库、虚拟机磁盘 I/O），其随机延迟可能过大。Deadline 调度器通过引入 请求过期机制（deadline），保证每个请求不会被无限期延迟，从而在提供较高吞吐量的同时确保 I/O 延迟上限。

其核心设计思想包括以下几点：

1. 延迟保证：每个请求都有一个最大等待时间（deadline），超时的请求会优先调度。

2. 读写分离：读请求通常延迟敏感，写请求可以稍微延迟，Deadline 调度器维护独立的队列以区分两类请求。

3. 顺序访问优化：对于顺序磁盘访问，Deadline 通过 扫描算法 尽量减少磁头寻道时间，提高顺序吞吐性能。

Deadline 调度器主要适用于 SSD/HDD 均可，但对旋转盘（HDD）尤其有效，因为磁头移动代价较高。它在 Linux 内核中是 内核默认提供的调度器之一，可以通过命令：

cat /sys/block/sda/queue/scheduler

查看可用调度器，并通过：

echo deadline > /sys/block/sda/queue/scheduler

切换当前设备使用 Deadline 调度器。

1.2 Deadline 调度器的数据结构

Deadline 调度器核心依赖三个主要的数据结构：

1. sort_list（按扇区排序的队列）

• 维护按逻辑块号（sector）排序的请求，支持顺序扫描，减少磁头移动。

• 读队列和写队列都有独立的 sort_list。

2. fifo_list（按到达顺序的队列）

• 维护请求的到达顺序，用于过期检查。

• 对每个请求计算 deadline = jiffies + max_latency，超时的请求优先处理。

3. rbtree 或链表结构

• 内核实现中，Deadline 调度器的 sort_list 通常基于红黑树（rbtree）实现，保证插入和查找复杂度为 O(log n)。

• FIFO 队列使用链表，保证快速插入和删除。

这种双队列设计保证了调度器在同时优化延迟和顺序访问的能力。通过 sort_list 提供快速顺序调度，通过 fifo_list 提供延迟保证。

第 2 章：Deadline 调度器请求插入机制

2.1 请求到达与插入流程

当一个 I/O 请求到达 Deadline 调度器时，它会经过以下流程：

1. 区分读写类型

• 内核会根据请求的 bio->bi_rw 字段判断是读请求还是写请求。

• 读请求通常比写请求更敏感，因此读队列更优先处理。

2. 计算请求 Deadline

• read_expire（默认 500ms）

• write_expire（默认 5s）

• Deadline 调度器有两个参数：

• 新请求的 expires 时间 = 当前时间 + 对应类型的 max_latency。

• 超时的请求会在调度时优先被选中。

3. 插入 sort_list

• 按扇区号插入红黑树或链表，实现顺序调度。

• 内核中使用 elv_rb_insert() 或类似函数完成插入。

4. 插入 fifo_list

• 按到达顺序插入尾部链表，便于过期检查。

• 此操作 O(1)，保证低开销。

通过上述流程，每个请求同时存在 顺序队列和超时队列，实现延迟控制和顺序扫描优化双目标。

2.2 插入优化与内核实现细节

Deadline 调度器的实现还包含一些优化细节：

• 批量插入内核会尝试批量将连续逻辑块号的请求插入 sort_list，减少红黑树旋转操作。

• 写请求滞后机制写请求不会立即插入请求队列的前端，而是有一个小延迟窗口（write_back_window），允许写请求暂时排队，以优先处理读请求，降低读请求延迟。

• 内核函数分析

  staticvoiddeadline_add_request(struct request_queue *q, struct request *rq){    struct deadline_data *dd = q->elevator->elevator_data;    if (rq_data_dir(rq) == READ)        dd_add_sorted(&dd->r_rb_root, &dd->r_fifo, rq);    else        dd_add_sorted(&dd->w_rb_root, &dd->w_fifo, rq);}

    这些设计保证了 Deadline 调度器在面对随机 I/O 或顺序 I/O 的混合负载时，既能保证延迟上界，又能充分利用磁盘顺序吞吐能力。

第 3 章：Deadline 请求调度策略

3.1 调度器核心策略

Deadline 调度器的核心调度策略是 “按 deadline 优先 + 扫描顺序”，具体规则如下：

1. 超时请求优先

• 检查 FIFO 队列头部的请求是否已过期。

• 过期请求优先调度，即使它在扇区顺序上不是最优。

2. 顺序扫描选择

• 若没有过期请求，调度器选择 sort_list 中距离当前磁头位置最近的请求。

• 类似 SCAN（电梯算法），减少磁头寻道。

3. 读写混合处理

• 默认优先处理读请求，以降低延迟。

• 写请求被延迟调度，但仍需保证不会无限期延迟（最大 write_expire）。

这种策略兼顾了实时性和顺序优化，特别适用于数据库、Web 服务等对 I/O 延迟敏感的场景。

3.2 代码实现与选择逻辑

Deadline 调度器在内核中的核心选择函数通常为：

static struct request *deadline_dispatch(struct request_queue *q, int force){    struct deadline_data *dd = q->elevator->elevator_data;    struct request *rq;    // 1. 检查读请求过期    rq = dd_first_expired(&dd->r_fifo);    if (rq)        return dd_dispatch_request(dd, rq);    // 2. 检查写请求过期    rq = dd_first_expired(&dd->w_fifo);    if (rq)        return dd_dispatch_request(dd, rq);    // 3. 顺序扫描调度读请求    rq = dd_pick_next_request(&dd->r_rb_root, dd->last_sector);    if (rq)        return dd_dispatch_request(dd, rq);    // 4. 顺序扫描调度写请求    rq = dd_pick_next_request(&dd->w_rb_root, dd->last_sector);    if (rq)        return dd_dispatch_request(dd, rq);    return NULL;}

调度逻辑：

• FIFO 队列用于过期检查

• Sort 队列用于顺序调度

• 读请求优先

这使得 Deadline 调度器在高负载情况下依然能保持 低延迟和高吞吐。

第 4 章：Deadline 调度器的读写分离优化

4.1 读请求的延迟优化

Deadline 调度器特别针对读请求设计了低延迟策略：

1. 短过期时间

• 默认 read_expire = 500ms，比写请求短得多。

• 读请求如果在此时间内未调度，则直接优先发出，确保数据库或应用响应时间可控。

2. 优先队列机制

• 读队列总是在写队列前调度。

• 在高 I/O 压力下，即使写请求积压，也不会显著影响读请求延迟。

3. 批量顺序扫描

• 当连续扇区存在多个读请求时，Deadline 会一次性调度，减少寻道次数。

• 对 HDD，提升吞吐；对 SSD，减少上下文切换开销。

4.2 写请求的滞后与合并策略

写请求设计上可容忍更长延迟，Deadline 调度器通过以下手段优化写吞吐：

1. 写请求滞后窗口（write_back_window）

• 写请求在短时间内不会立即调度，允许读请求优先。

• 避免“读饥饿”，提高响应性能。

2. 批量合并

• 连续扇区的写请求可以合并成单个请求，减少磁盘写操作次数。

• 内核函数 elv_merge() 或 blk_attempt_plug_merge() 实现合并逻辑。

3. 最大过期时间保证

• 即使写请求被延迟，它的最大等待时间 write_expire（默认 5s）不会超过。

• 超时后，写请求也会被强制调度，防止写饥饿。

这种设计保证了 读延迟低、写吞吐高，尤其适合数据库和虚拟化场景。

第 5 章：Deadline 调度器在多队列环境下的优化

5.1 blk-mq 多队列适配

Linux 4.x 及以上内核引入了 blk-mq（多队列块层），Deadline 调度器也适配了多队列机制：

1. 每个硬件队列独立调度

• 每个队列都有独立的 Deadline 数据结构。

• 避免单队列锁竞争，提高多核系统下吞吐。

2. 全局延迟保证

• 各队列独立计算过期时间。

• 队列之间通过 分布式调度 保证延迟边界，防止某个队列饥饿。

3. 高并发优化

• 使用原子操作和轻量锁保护队列，减少调度开销。

• 对 SSD 和 NVMe 队列特别有效，支持几万 QD（Queue Depth）的并发请求。

5.2 Deadline 与 CFQ / NOOP 比较

Deadline 调度器与其他调度器的区别：

Deadline 在高 I/O 压力下能保证读延迟，同时顺序扫描优化也保证了 HDD 顺序吞吐，是高性能存储的首选方案。

第 6 章：Deadline 调度器性能调优与应用实践

6.1 参数调优

Deadline 调度器核心参数可以通过 sysfs 调整：

1. read_expire / write_expire

• 控制请求过期时间。

• read_expire 缩短可以降低延迟，但可能降低吞吐。

• write_expire 增大可提高写吞吐，但会增加写延迟。

2. fifo_batch / front_merges

• 控制每次批量调度的请求数量。

• 增大 batch 可减少上下文切换，提高顺序访问效率。

3. 调优方法示例：

echo 200 > /sys/block/sda/queue/iosched/read_expireecho 1000 > /sys/block/sda/queue/iosched/write_expireecho 16 > /sys/block/sda/queue/iosched/fifo_batch

通过实际 I/O 测试调整参数，满足应用的低延迟和高吞吐需求。

6.2 实践应用场景

1. 数据库服务器

• 高随机读 I/O，延迟敏感。

• Deadline 调度器保证查询响应时间可控，同时顺序写吞吐合理。

2. 虚拟化环境

• 虚拟机磁盘 I/O 高并发。

• Deadline 在 blk-mq 模式下适配多队列，延迟可控。

3. 混合负载场景

• Web 服务日志写入 + 数据库查询。

• Deadline 优先读请求，写请求滞后，保证关键路径响应。

通过参数调优和合理队列设计，Deadline 调度器能够在不同硬件和工作负载下，提供稳定、可预测的 I/O 性能