Linux 存储与文件系统深度剖析（七）：IO 调度器深度剖析

Posted on Edited on In ,

IO 调度器（I/O Scheduler）是 Linux 块层中承上启下的核心组件：它介于文件系统/虚拟内存子系统发出的 bio 请求与底层硬件驱动之间，负责对请求进行排序、合并、仲裁，以求在吞吐量、延迟、公平性三个维度上达到系统预期的平衡点。本文基于 Linux 6.4-rc1 内核源码，深入剖析 mq-deadline、BFQ 和 Kyber 三个现代调度器的设计思想与核心实现。

1. 历史演进：从单队列到多队列

1.1 legacy 时代（单队列调度器）

早期 Linux 块层基于单一请求队列（single-queue）模型，所有 CPU 核心的 IO 请求汇聚到一把全局自旋锁保护的队列中。这一时代的调度器包括：

调度器 全称 特点
noop No Operation 几乎不做排序，适合 SSD/NVMe
deadline Deadline 读写分离 + FIFO 防饥饿
CFQ Completely Fair Queuing 进程级公平，为每个进程维护独立队列
AS Anticipatory Scheduler 预测式调度，已于 2.6.33 移除

单队列模型的瓶颈在于：随着 NVMe SSD IOPS 突破百万级，全局锁成为严重的性能瓶颈。在 16 核系统上，单队列调度器的锁争用开销甚至会抵消掉高速存储设备的优势。

1.2 blk-mq 时代（多队列调度器）

Linux 3.13 引入了 blk-mq（Multi-Queue Block IO Queueing Mechanism），彻底重构了块层架构：

  • Software Queues（per-CPU）：每个 CPU 有独立的软件队列，消除了热点锁争用。
  • Hardware Dispatch Queues：与硬件 queue pair 数量对应，NVMe 可以有多达数十个。
  • 调度器插件化：调度器通过 elevator_mq_ops 回调挂入 blk-mq 框架。

随之，传统调度器也被重写为 mq 版本：

legacy 调度器 blk-mq 对应版本 说明
noop none 无调度器，直接 passthrough
deadline mq-deadline 适配 blk-mq 的 deadline
CFQ BFQ 从 CFQ 演进而来的预算公平队列
- Kyber 全新设计，基于延迟目标的令牌桶

2. IO 调度器框架：elevator.c 与 blk-mq 的集成

2.1 核心数据结构

调度器框架定义在 block/elevator.h 中。每个调度器实现必须提供一个 elevator_type 结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// block/elevator.h
struct elevator_type
{
    /* managed by elevator core */
    struct kmem_cache *icq_cache;

    /* fields provided by elevator implementation */
    struct elevator_mq_ops ops;

    size_t icq_size;    /* see iocontext.h */
    size_t icq_align;   /* ditto */
    struct elv_fs_entry *elevator_attrs;
    const char *elevator_name;
    const char *elevator_alias;
    const unsigned int elevator_features;
    struct module *elevator_owner;
    /* ... */
    char icq_cache_name[ELV_NAME_MAX + 6]; /* elvname + "_io_cq" */
    struct list_head list;
};

elevator_mq_ops 是调度器与 blk-mq 框架之间的操作接口，定义了完整的生命周期回调：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// block/elevator.h
struct elevator_mq_ops {
    int (*init_sched)(struct request_queue *, struct elevator_type *);
    void (*exit_sched)(struct elevator_queue *);
    int (*init_hctx)(struct blk_mq_hw_ctx *, unsigned int);
    void (*exit_hctx)(struct blk_mq_hw_ctx *, unsigned int);
    void (*depth_updated)(struct blk_mq_hw_ctx *);

    bool (*allow_merge)(struct request_queue *, struct request *, struct bio *);
    bool (*bio_merge)(struct request_queue *, struct bio *, unsigned int);
    int (*request_merge)(struct request_queue *q, struct request **, struct bio *);
    void (*request_merged)(struct request_queue *, struct request *, enum elv_merge);
    void (*requests_merged)(struct request_queue *, struct request *, struct request *);
    void (*limit_depth)(blk_opf_t, struct blk_mq_alloc_data *);
    void (*prepare_request)(struct request *);
    void (*finish_request)(struct request *);
    void (*insert_requests)(struct blk_mq_hw_ctx *hctx, struct list_head *list,
            blk_insert_t flags);
    struct request *(*dispatch_request)(struct blk_mq_hw_ctx *);
    bool (*has_work)(struct blk_mq_hw_ctx *);
    void (*completed_request)(struct request *, u64);
    void (*requeue_request)(struct request *);
    struct request *(*former_request)(struct request_queue *, struct request *);
    struct request *(*next_request)(struct request_queue *, struct request *);
    void (*init_icq)(struct io_cq *);
    void (*exit_icq)(struct io_cq *);
};

elevator_queue 是每个请求队列（request_queue）对应的调度器实例：

1
2
3
4
5
6
7
8
9
10
// block/elevator.h
struct elevator_queue
{
    struct elevator_type *type;
    void *elevator_data;       /* 调度器私有数据，如 deadline_data / bfq_data */
    struct kobject kobj;
    struct mutex sysfs_lock;
    unsigned long flags;
    DECLARE_HASHTABLE(hash, ELV_HASH_BITS);  /* 用于加速 back-merge 查找 */
};

2.2 请求合并机制

合并是提升吞吐量的重要手段。elevator.c 中的 elv_merge() 实现了三级合并策略：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// block/elevator.c
enum elv_merge elv_merge(struct request_queue *q, struct request **req,
        struct bio *bio)
{
    struct elevator_queue *e = q->elevator;
    struct request *__rq;

    /*
     * Levels of merges:
     *   nomerges:  No merges at all attempted
     *   noxmerges: Only simple one-hit cache try
     *   merges:    All merge tries attempted
     */
    if (blk_queue_nomerges(q) || !bio_mergeable(bio))
        return ELEVATOR_NO_MERGE;

    /*
     * First try one-hit cache.
     */
    if (q->last_merge && elv_bio_merge_ok(q->last_merge, bio)) {
        enum elv_merge ret = blk_try_merge(q->last_merge, bio);
        if (ret != ELEVATOR_NO_MERGE) {
            *req = q->last_merge;
            return ret;
        }
    }

    if (blk_queue_noxmerges(q))
        return ELEVATOR_NO_MERGE;

    /*
     * See if our hash lookup can find a potential backmerge.
     */
    __rq = elv_rqhash_find(q, bio->bi_iter.bi_sector);
    if (__rq && elv_bio_merge_ok(__rq, bio)) {
        *req = __rq;
        if (blk_discard_mergable(__rq))
            return ELEVATOR_DISCARD_MERGE;
        return ELEVATOR_BACK_MERGE;
    }

    if (e->type->ops.request_merge)
        return e->type->ops.request_merge(q, req, bio);

    return ELEVATOR_NO_MERGE;
}

合并分为三个级别：

  1. last_merge 缓存：O(1) 检查上一个被合并的请求，命中率极高。
  2. hash 表查找：以 rq_hash_key = pos + sectors 为键，快速定位可 back-merge 的请求。
  3. 调度器自定义：调用 ops.request_merge，如 mq-deadline 利用红黑树做 front-merge。

2.3 调度器注册与切换

所有已注册的调度器保存在全局链表 elv_list 中，通过 elv_register() / elv_unregister() 进行注册和注销。运行时切换调度器通过 sysfs 接口 /sys/block/<dev>/queue/scheduler 触发，内核执行 elevator_switch() 完成切换。

3. mq-deadline 调度器深度剖析

mq-deadline 是 legacy deadline 调度器针对 blk-mq 框架的重写版本，来自 block/mq-deadline.c。它在保留 deadline 防饥饿核心机制的基础上，引入了优先级感知和批量分发优化。

3.1 核心数据结构设计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// block/mq-deadline.c
enum dd_prio {
    DD_RT_PRIO   = 0,   /* 实时优先级 */
    DD_BE_PRIO   = 1,   /* 尽力而为（Best Effort，默认） */
    DD_IDLE_PRIO = 2,   /* 空闲优先级 */
    DD_PRIO_MAX  = 2,
};

/* 每个优先级维护独立的读写队列 */
struct dd_per_prio {
    struct list_head dispatch;
    struct rb_root sort_list[DD_DIR_COUNT];   /* 按扇区地址排序的红黑树 */
    struct list_head fifo_list[DD_DIR_COUNT]; /* 按到期时间排序的 FIFO 链表 */
    struct request *next_rq[DD_DIR_COUNT];   /* 红黑树中的"当前指针" */
    struct io_stats_per_prio stats;
};

struct deadline_data {
    struct dd_per_prio per_prio[DD_PRIO_COUNT]; /* RT/BE/IDLE 三套队列 */

    enum dd_data_dir last_dir;  /* 上一次调度的方向（读/写） */
    unsigned int batching;      /* 当前 batch 中已调度的请求数 */
    unsigned int starved;       /* 写请求被饥饿的次数 */

    int fifo_expire[DD_DIR_COUNT]; /* 读/写超时时间 */
    int fifo_batch;           /* 每批次最大请求数 */
    int writes_starved;       /* 写饥饿阈值 */
    int front_merges;
    u32 async_depth;
    int prio_aging_expire;

    spinlock_t lock;
    spinlock_t zone_lock;
};

关键参数默认值（在文件顶部定义）：

1
2
3
4
5
6
// block/mq-deadline.c
static const int read_expire  = HZ / 2;  /* 读请求最大等待时间：500ms */
static const int write_expire = 5 * HZ;  /* 写请求最大等待时间：5s（软限制） */
static const int prio_aging_expire = 10 * HZ; /* 低优先级老化时间：10s */
static const int writes_starved = 2;     /* 读调度连续 2 次后才调度写 */
static const int fifo_batch = 16;        /* 单次批量调度最多 16 个请求 */

ioprio 类别到 dd_prio 的映射：

1
2
3
4
5
6
7
// block/mq-deadline.c
static const enum dd_prio ioprio_class_to_prio[] = {
    [IOPRIO_CLASS_NONE] = DD_BE_PRIO,
    [IOPRIO_CLASS_RT]   = DD_RT_PRIO,
    [IOPRIO_CLASS_BE]   = DD_BE_PRIO,
    [IOPRIO_CLASS_IDLE] = DD_IDLE_PRIO,
};

3.2 双数据结构：红黑树 + FIFO 链表

每个方向（读/写）的请求同时存在于两个数据结构中：

  • 红黑树（sort_list）：按扇区地址（LBA）排序，用于顺序扫描，最大化吞吐量（类似电梯算法中的磁头移动方向）。
  • FIFO 链表（fifo_list）：按请求到期时间排序，用于防止饥饿，确保老请求不会无限等待。

这种双结构设计是 deadline 调度器的精髓：正常情况下按红黑树顺序调度以获得高吞吐，一旦有请求即将超时，立即切换到 FIFO 顺序调度。

3.3 FIFO 超时检测

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// block/mq-deadline.c
static inline int deadline_check_fifo(struct dd_per_prio *per_prio,
                                      enum dd_data_dir data_dir)
{
    struct request *rq = rq_entry_fifo(per_prio->fifo_list[data_dir].next);

    /*
     * rq is expired!
     */
    if (time_after_eq(jiffies, (unsigned long)rq->fifo_time))
        return 1;

    return 0;
}

rq->fifo_time 在请求插入时设置为 jiffies + fifo_expire[data_dir]。

3.4 核心调度决策：__dd_dispatch_request()

这是 mq-deadline 最关键的函数，完整呈现其调度逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// block/mq-deadline.c（精简版）
static struct request *__dd_dispatch_request(struct deadline_data *dd,
                                             struct dd_per_prio *per_prio,
                                             unsigned long latest_start)
{
    struct request *rq, *next_rq;
    enum dd_data_dir data_dir;

    /* 1. 优先从 dispatch 队列取（已准备好分发的请求） */
    if (!list_empty(&per_prio->dispatch)) {
        rq = list_first_entry(&per_prio->dispatch, struct request, queuelist);
        if (started_after(dd, rq, latest_start))
            return NULL;
        list_del_init(&rq->queuelist);
        goto done;
    }

    /* 2. 如果当前方向还有请求且 batch 未满，继续同方向调度 */
    rq = deadline_next_request(dd, per_prio, dd->last_dir);
    if (rq && dd->batching < dd->fifo_batch)
        goto dispatch_request;

    /* 3. batch 已满或当前方向无请求，重新选择方向 */
    if (!list_empty(&per_prio->fifo_list[DD_READ])) {
        /* 读队列非空：检查写队列是否需要防饥饿 */
        if (deadline_fifo_request(dd, per_prio, DD_WRITE) &&
            (dd->starved++ >= dd->writes_starved))
            goto dispatch_writes;  /* 写请求已饥饿，强制调度写 */

        data_dir = DD_READ;
        goto dispatch_find_request;
    }

    if (!list_empty(&per_prio->fifo_list[DD_WRITE])) {
dispatch_writes:
        dd->starved = 0;
        data_dir = DD_WRITE;
        goto dispatch_find_request;
    }
    return NULL;

dispatch_find_request:
    next_rq = deadline_next_request(dd, per_prio, data_dir);
    if (deadline_check_fifo(per_prio, data_dir) || !next_rq) {
        /* FIFO 中有超时请求，或者红黑树已到末尾：从 FIFO 头部重新开始 */
        rq = deadline_fifo_request(dd, per_prio, data_dir);
    } else {
        /* 无超时，继续红黑树顺序调度 */
        rq = next_rq;
    }

    if (!rq)
        return NULL;

    dd->last_dir = data_dir;
    dd->batching = 0;   /* 重置批次计数 */

dispatch_request:
    if (started_after(dd, rq, latest_start))
        return NULL;
    dd->batching++;
    deadline_move_request(dd, per_prio, rq);
done:
    dd->per_prio[prio].stats.dispatched++;
    blk_req_zone_write_lock(rq);
    rq->rq_flags |= RQF_STARTED;
    return rq;
}

3.5 优先级感知调度：dd_dispatch_request()

顶层 dispatch 函数在三个优先级之间进行仲裁：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// block/mq-deadline.c
static struct request *dd_dispatch_request(struct blk_mq_hw_ctx *hctx)
{
    struct deadline_data *dd = hctx->queue->elevator->elevator_data;
    const unsigned long now = jiffies;
    struct request *rq;
    enum dd_prio prio;

    spin_lock(&dd->lock);

    /* 首先检查低优先级请求是否已老化（等待超过 prio_aging_expire） */
    rq = dd_dispatch_prio_aged_requests(dd, now);
    if (rq)
        goto unlock;

    /* 按优先级顺序调度：RT > BE > IDLE */
    for (prio = 0; prio <= DD_PRIO_MAX; prio++) {
        rq = __dd_dispatch_request(dd, &dd->per_prio[prio], now);
        if (rq || dd_queued(dd, prio))
            break;
    }

unlock:
    spin_unlock(&dd->lock);
    return rq;
}

这里有一个重要的防饥饿机制：dd_dispatch_prio_aged_requests() 会在低优先级请求等待超过 prio_aging_expire（默认 10 秒）后，强制将其提升调度，避免低优先级请求永久饥饿。

3.6 异步 IO 深度限制

为防止异步写请求耗尽所有 tag，mq-deadline 通过 dd_limit_depth() 限制异步请求的 tag 使用量：

1
2
3
4
5
6
7
8
9
10
11
12
// block/mq-deadline.c
static void dd_limit_depth(blk_opf_t opf, struct blk_mq_alloc_data *data)
{
    struct deadline_data *dd = data->q->elevator->elevator_data;

    /* 同步读不限制 */
    if (op_is_sync(opf) && !op_is_write(opf))
        return;

    /* 异步请求和写请求限制为 async_depth（默认为 3/4 × nr_requests） */
    data->shallow_depth = dd->async_depth;
}

4. BFQ 调度器深度剖析

BFQ（Budget Fair Queueing）是目前 Linux 中最复杂的 IO 调度器，来自 block/bfq-iosched.c，其核心算法实现在 block/bfq-wf2q.c。它的设计目标是：在保证高吞吐量的同时，为交互式应用和软实时应用提供极低延迟。

4.1 设计哲学：从时间切片到预算切片

CFQ 为每个进程分配时间切片（time slice），设备在切片内归该进程使用。BFQ 的关键改进是将分配单位从时间切片改为扇区预算（budget）：

  • CFQ 时间切片：进程在固定时间内尽可能多发 IO → 吞吐率波动大，依赖设备内部队列深度。
  • BFQ 扇区预算：进程发完固定扇区数后才轮换 → 调度粒度直接与设备吞吐量挂钩，不受设备延迟影响。

以扇区为单位的好处在于：慢速 HDD 和快速 NVMe 使用相同调度参数，都能获得理论上正确的带宽比例保证。

4.2 核心数据结构

bfq_queue：进程 IO 队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// block/bfq-iosched.h
struct bfq_queue {
    int ref;
    struct bfq_data *bfqd;

    unsigned short ioprio, ioprio_class;

    /* 协作队列合并支持 */
    struct bfq_queue *new_bfqq;
    struct rb_node pos_node;
    struct rb_root *pos_root;

    /* 按扇区地址排序的请求红黑树 */
    struct rb_root sort_list;
    struct request *next_rq;
    int queued[2];      /* sync/async 请求数 */
    struct list_head fifo;  /* FIFO 过期链表 */

    /* B-WF2Q+ 调度实体 */
    struct bfq_entity entity;
    struct bfq_weight_counter *weight_counter;

    int max_budget;           /* 最大预算（扇区数） */
    unsigned long budget_timeout;

    int dispatched;           /* 已发往驱动的请求数 */
    unsigned long flags;

    /* thinktime 统计（用于检测交互式应用） */
    struct bfq_ttime ttime;
    u32 seek_history;         /* 寻道历史位图，用于随机/顺序检测 */
    /* ... */
};

bfq_entity：B-WF2Q+ 的调度实体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// block/bfq-iosched.h
struct bfq_entity {
    struct rb_node rb_node;   /* 在服务树（active/idle）中的节点 */
    bool on_st_or_in_serv;

    /* B-WF2Q+ 虚拟时间戳 [扇区/权重] */
    u64 start, finish;

    struct rb_root *tree;
    u64 min_start;            /* 子树最小 start，支持 O(log N) 查找 */

    int service;  /* 本次服务槽中已消耗的扇区数 */
    int budget;   /* 预算：F_i = S_i + budget / weight */
    int allocated;

    int weight;       /* 当前权重 */
    int new_weight;
    int orig_weight;  /* 原始权重（weight boosting 前） */

    /* 层次化调度支持 */
    struct bfq_entity *parent;
    struct bfq_sched_data *my_sched_data; /* 非叶节点：自身的调度数据 */
    struct bfq_sched_data *sched_data;    /* 所属的调度数据 */

    int prio_changed;
};

bfq_service_tree：B-WF2Q+ 服务树

1
2
3
4
5
6
7
8
9
10
11
// block/bfq-iosched.h
struct bfq_service_tree {
    struct rb_root active;   /* 活跃实体（有请求待调度） */
    struct rb_root idle;     /* 空闲实体（预算耗尽但虚拟时间未达到） */

    struct bfq_entity *first_idle;  /* idle 树中 F_i 最小的实体 */
    struct bfq_entity *last_idle;   /* idle 树中 F_i 最大的实体 */

    u64 vtime;         /* 调度器虚拟时间 */
    unsigned long wsum; /* 活跃+空闲实体的权重之和 */
};

每个 ioprio_class（RT/BE/IDLE）对应一棵独立的服务树，由 bfq_sched_data 管理：

1
2
3
4
5
6
7
// block/bfq-iosched.h
struct bfq_sched_data {
    struct bfq_entity *in_service_entity;   /* 当前服务中的实体 */
    struct bfq_entity *next_in_service;     /* 下一个候选实体（预选优化） */
    struct bfq_service_tree service_tree[BFQ_IOPRIO_CLASSES];
    unsigned long bfq_class_idle_last_service;
};

4.3 B-WF2Q+ 算法

B-WF2Q+（Budgeted Worst-case Fair Weighted Fair Queueing plus）是 BFQ 的核心调度算法，定义在 block/bfq-wf2q.c。

虚拟时间戳的计算

每个实体的虚拟完成时间（virtual finish time）计算为：

1
F_i = S_i + budget_i / weight_i

其中 S_i 是该实体开始服务时调度器的虚拟时间，budget_i 是分配的扇区预算，weight_i 是该实体的权重。

这个公式保证了：权重为 w 的实体，相比权重为 1 的实体，能获得 w 倍的带宽分配。

时间戳比较

1
2
3
4
5
// block/bfq-wf2q.c
static int bfq_gt(u64 a, u64 b)
{
    return (s64)(a - b) > 0;
}

使用有符号比较处理 64 位虚拟时间的回绕问题。

next_in_service 的更新

bfq_update_next_in_service() 在实体激活、重入队列或位置调整时被调用，维护 sd->next_in_service 指针，实现 O(1) 的下一调度实体预测：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// block/bfq-wf2q.c
static bool bfq_update_next_in_service(struct bfq_sched_data *sd,
                                       struct bfq_entity *new_entity,
                                       bool expiration)
{
    struct bfq_entity *next_in_service = sd->next_in_service;
    bool parent_sched_may_change = false;
    bool change_without_lookup = false;

    if (new_entity && new_entity != sd->next_in_service) {
        change_without_lookup = true;

        if (next_in_service) {
            unsigned int new_entity_class_idx = bfq_class_idx(new_entity);
            struct bfq_service_tree *st =
                sd->service_tree + new_entity_class_idx;

            /* 如果优先级相同、新实体已eligible且 finish 更小，则替换 */
            change_without_lookup =
                (new_entity_class_idx == bfq_class_idx(next_in_service)
                 && !bfq_gt(new_entity->start, st->vtime)
                 && bfq_gt(next_in_service->finish, new_entity->finish));
        }
    }
    /* ... */
}

4.4 Idle 机制与预期式调度

BFQ 的 idle 机制是其实现低延迟的关键。当一个进程的队列变空时，BFQ 不会立即切换到其他进程，而是短暂等待（默认 bfq_slice_idle = NSEC_PER_SEC / 125 = 8ms），预期该进程会继续发出 IO。

1
2
3
// block/bfq-iosched.c
/* Idling period duration, in ns. */
static u64 bfq_slice_idle = NSEC_PER_SEC / 125;

Idle 的触发条件（idling_needed_for_service_guarantees() 中判断）：

  1. 调度是非对称的（不同进程有不同权重，或存在 weight-raising 进程）
  2. 设备不支持深度队列（!bfqd->hw_tag），防止进程切换导致 NCQ 效率下降
  3. 进程是交互式或软实时应用（BFQ 通过 thinktime 统计识别）

Weight Raising 机制：BFQ 会识别交互式应用（频繁短暂活跃）和软实时应用（有周期性 IO pattern），通过临时提升权重（最高 BFQ_SOFTRT_WEIGHT_FACTOR = 100 倍）来保证其低延迟响应。

4.5 关键常量与 thinktime

1
2
3
4
5
6
7
8
9
10
11
12
// block/bfq-iosched.c
/* 低于此阈值（2ms）的 thinktime 视为"即时"，不触发 idle */
#define BFQ_MIN_TT     (2 * NSEC_PER_MSEC)

/* 异步请求的带宽权重惩罚因子（异步写消耗 3 倍预算） */
static const int bfq_async_charge_factor = 3;

/* 超时时间：约 125ms，对应 CFQ 默认值 */
const int bfq_timeout = HZ / 8;

/* 默认最大预算：16 * 1024 扇区 = 8 MB */
static const int bfq_default_max_budget = 16 * 1024;

异步写的 3 倍预算惩罚（bfq_async_charge_factor = 3）是防止异步写饥饿同步读的关键设计：同样权重的进程，其同步 IO 消耗的预算是异步 IO 的 1/3，因此同步 IO 能得到 3 倍的调度机会。

4.6 层次化 cgroup 调度

BFQ 支持完整的 cgroup IO 控制，通过 bfq_group 将 cgroup 层次映射为调度树层次。每个 bfq_group 包含一个 bfq_sched_data，形成树状调度结构。B-WF2Q+ 的层次化扩展（H-WF2Q+）保证了跨 cgroup 的带宽分配能够反映 cgroup 权重。

5. Kyber 调度器深度剖析

Kyber 由 Facebook（现 Meta）于 Linux 4.12 引入，来自 block/kyber-iosched.c。它专为高速 NVMe SSD 设计，核心思路是通过令牌桶限制并发深度来控制设备延迟，而不是对请求排序。

5.1 设计理念：延迟目标驱动的令牌桶

Kyber 的核心观察是：对于高性能 SSD，吞吐量通常不是瓶颈，延迟控制才是关键。Kyber 将设备分为四个调度域：

1
2
3
4
5
6
7
8
// block/kyber-iosched.c
enum {
    KYBER_READ,
    KYBER_WRITE,
    KYBER_DISCARD,
    KYBER_OTHER,
    KYBER_NUM_DOMAINS,
};

每个域有独立的最大并发深度和默认延迟目标：

1
2
3
4
5
6
7
8
9
10
11
12
13
// block/kyber-iosched.c
static const unsigned int kyber_depth[] = {
    [KYBER_READ]    = 256,
    [KYBER_WRITE]   = 128,
    [KYBER_DISCARD] = 64,
    [KYBER_OTHER]   = 16,
};

static const u64 kyber_latency_targets[] = {
    [KYBER_READ]    = 2ULL * NSEC_PER_MSEC,  /* 2ms */
    [KYBER_WRITE]   = 10ULL * NSEC_PER_MSEC, /* 10ms */
    [KYBER_DISCARD] = 5ULL * NSEC_PER_SEC,   /* 5s */
};

批次调度大小：

1
2
3
4
5
6
7
// block/kyber-iosched.c
static const unsigned int kyber_batch_size[] = {
    [KYBER_READ]    = 16,
    [KYBER_WRITE]   = 8,
    [KYBER_DISCARD] = 1,
    [KYBER_OTHER]   = 1,
};

5.2 令牌桶实现：sbitmap_queue

Kyber 使用 sbitmap_queue（可扩展位图队列）实现令牌桶，每个调度域的令牌数（depth）即为该域允许的最大飞行中请求数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// block/kyber-iosched.c
struct kyber_queue_data {
    struct request_queue *q;
    dev_t dev;

    /* 每个域的令牌桶 */
    struct sbitmap_queue domain_tokens[KYBER_NUM_DOMAINS];

    /* 异步请求比例限制（KYBER_ASYNC_PERCENT = 75%） */
    unsigned int async_depth;

    struct kyber_cpu_latency __percpu *cpu_latency;

    /* 定时器：聚合延迟统计并调整令牌深度 */
    struct timer_list timer;

    unsigned int latency_buckets[KYBER_OTHER][2][KYBER_LATENCY_BUCKETS];
    unsigned long latency_timeout[KYBER_OTHER];
    int domain_p99[KYBER_OTHER];

    u64 latency_targets[KYBER_OTHER]; /* 目标延迟（可通过 sysfs 调整） */
};

每个 hw queue 对应一个 kyber_hctx_data：

1
2
3
4
5
6
7
8
9
10
11
12
// block/kyber-iosched.c
struct kyber_hctx_data {
    spinlock_t lock;
    struct list_head rqs[KYBER_NUM_DOMAINS]; /* 各域的请求链表 */
    unsigned int cur_domain;   /* 当前正在调度的域 */
    unsigned int batching;     /* 当前批次已调度数 */
    struct kyber_ctx_queue *kcqs;
    struct sbitmap kcq_map[KYBER_NUM_DOMAINS];
    struct sbq_wait domain_wait[KYBER_NUM_DOMAINS];
    struct sbq_wait_state *domain_ws[KYBER_NUM_DOMAINS];
    atomic_t wait_index[KYBER_NUM_DOMAINS];
};

5.3 异步请求隔离

为防止异步请求洪水阻塞同步请求，Kyber 预留 25% 的令牌给同步操作：

1
2
3
4
5
6
7
8
9
// block/kyber-iosched.c
enum {
    /*
     * In order to prevent starvation of synchronous requests by a flood of
     * asynchronous requests, we reserve 25% of requests for synchronous
     * operations.
     */
    KYBER_ASYNC_PERCENT = 75,
};

5.4 延迟直方图与自适应调节

Kyber 在 per-CPU 上记录延迟直方图，延迟桶相对于目标延迟按比例划分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// block/kyber-iosched.c
/*
 * Requests latencies are recorded in a histogram with buckets defined
 * relative to the target latency:
 *
 * <= 1/4 * target latency
 * <= 1/2 * target latency
 * <= 3/4 * target latency
 * <= target latency
 * <= 1 1/4 * target latency
 * <= 1 1/2 * target latency
 * <= 1 3/4 * target latency
 * > 1 3/4 * target latency
 */
enum {
    KYBER_LATENCY_SHIFT = 2,
    KYBER_GOOD_BUCKETS = 1 << KYBER_LATENCY_SHIFT,       /* 4 个"好"桶 */
    KYBER_LATENCY_BUCKETS = 2 << KYBER_LATENCY_SHIFT,    /* 共 8 个桶 */
};

每完成一个请求，调用 kyber_completed_request() 记录延迟样本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// block/kyber-iosched.c
static void kyber_completed_request(struct request *rq, u64 now)
{
    struct kyber_queue_data *kqd = rq->q->elevator->elevator_data;
    struct kyber_cpu_latency *cpu_latency;
    unsigned int sched_domain;
    u64 target;

    sched_domain = kyber_sched_domain(rq->cmd_flags);
    if (sched_domain == KYBER_OTHER)
        return;

    cpu_latency = get_cpu_ptr(kqd->cpu_latency);
    target = kqd->latency_targets[sched_domain];
    add_latency_sample(cpu_latency, sched_domain, KYBER_TOTAL_LATENCY,
                       target, now - rq->start_time_ns);
    add_latency_sample(cpu_latency, sched_domain, KYBER_IO_LATENCY, target,
                       now - rq->io_start_time_ns);
    put_cpu_ptr(kqd->cpu_latency);

    timer_reduce(&kqd->timer, jiffies + HZ / 10); /* 100ms 后聚合统计 */
}

kyber_timer_fn() 每 100ms 运行一次，聚合 per-CPU 延迟数据，计算 p90/p99，并动态调整各域的令牌深度：

  • 如果设备 IO 延迟的 p90 超过目标（bad = true）：压缩延迟满足（p99 < KYBER_GOOD_BUCKETS）的域的令牌深度。
  • 无论是否 bad，都会基于 p99 线性缩放令牌深度：
1
2
3
4
5
6
// block/kyber-iosched.c（kyber_timer_fn 内）
if (bad || p99 >= KYBER_GOOD_BUCKETS) {
    orig_depth = kqd->domain_tokens[sched_domain].sb.depth;
    depth = (orig_depth * (p99 + 1)) >> KYBER_LATENCY_SHIFT;
    kyber_resize_domain(kqd, sched_domain, depth);
}

6. 如何选择 IO 调度器

6.1 设备类型与调度器的匹配关系

设备类型 推荐调度器 理由
HDD（机械硬盘） mq-deadline 或 BFQ HDD 随机寻道代价极高，需要 elevator 排序来最小化磁头移动；BFQ 能给交互式应用保证延迟
SATA SSD mq-deadline 或 BFQ SSD 无寻道开销，但对于混合读写工作负载，deadline 的防饥饿机制仍有价值
NVMe SSD none 或 Kyber NVMe 具备原生多队列和极低延迟，调度器开销可能得不偿失；Kyber 在需要延迟保证时适用
数据库服务器（顺序 IO 为主） none 或 mq-deadline 数据库通常自己管理 IO 顺序，调度器介入收益有限
桌面/多媒体工作站 BFQ BFQ 的 weight-raising 机制能保证桌面交互和音视频的低延迟响应
虚拟机磁盘（virtio） none 虚拟机的 IO 已在宿主机层面调度，客户机无需再做调度

6.2 调度器选择的核心指标

使用 mq-deadline 的场景：

  • 需要严格的读写公平性防止饥饿
  • 混合随机/顺序工作负载
  • 需要 ioprio 优先级支持（RT/BE/IDLE 三档）
  • Zoned Block Device（SMR 硬盘）

使用 BFQ 的场景：

  • 桌面系统，需要保证前台应用响应
  • 多租户服务器，需要 cgroup 级别的 IO 带宽隔离
  • 同时运行交互式任务和批处理任务的混合负载
  • 关注绝对公平性（每个进程按权重获得带宽）

使用 Kyber 的场景：

  • 高性能 NVMe 设备，IOPS > 100K
  • 延迟敏感型服务（要求 P99 读延迟 < 2ms）
  • 负载已知，需要可调的延迟目标

使用 none 的场景：

  • NVMe SSD，追求最大吞吐量
  • 应用层已做 IO 合并和调度（如数据库 WAL）
  • 虚拟化环境

7. 实际调优示例

7.1 查看和修改调度器

1
2
3
4
5
6
7
8
9
10
11
12
13
# 查看当前调度器（方括号内为当前激活的）
cat /sys/block/nvme0n1/queue/scheduler
# 输出示例：[none] mq-deadline kyber bfq

# 切换到 bfq
echo bfq > /sys/block/sda/queue/scheduler

# 持久化（通过 udev 规则）
# /etc/udev/rules.d/60-iosched.rules
ACTION=="add|change", KERNEL=="sd[a-z]*", \
    ATTR{queue/scheduler}="bfq"
ACTION=="add|change", KERNEL=="nvme*", \
    ATTR{queue/scheduler}="none"

7.2 mq-deadline 调优参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 读请求超时时间（ms），默认 500ms
echo 200 > /sys/block/sda/queue/iosched/read_expire

# 写请求超时时间（ms），默认 5000ms
echo 2000 > /sys/block/sda/queue/iosched/write_expire

# 写饥饿阈值（读调度多少次后必须调度写），默认 2
echo 4 > /sys/block/sda/queue/iosched/writes_starved

# 批次大小，默认 16
echo 32 > /sys/block/sda/queue/iosched/fifo_batch

# 是否允许前向合并（1=允许）
echo 1 > /sys/block/sda/queue/iosched/front_merges

7.3 BFQ 调优参数

1
2
3
4
5
6
7
8
9
10
11
# 低延迟模式（对交互式/软实时应用进行 weight-raising），默认开启
echo 1 > /sys/block/sda/queue/iosched/low_latency

# idle 等待时间（us），默认 8000us = 8ms
echo 4000 > /sys/block/sda/queue/iosched/slice_idle_us

# 严格的 IO 带宽隔离（牺牲部分吞吐，保证精确的带宽比例）
echo 1 > /sys/block/sda/queue/iosched/strict_guarantees

# 查看 BFQ 统计（debugfs）
cat /sys/kernel/debug/block/sda/bfq/stats

7.4 Kyber 调优参数

1
2
3
4
5
# 调整读延迟目标（ns），默认 2ms
echo 1000000 > /sys/block/nvme0n1/queue/iosched/read_lat_nsec

# 调整写延迟目标（ns），默认 10ms
echo 5000000 > /sys/block/nvme0n1/queue/iosched/write_lat_nsec

7.5 通用队列参数

1
2
3
4
5
6
7
8
9
10
11
# 队列深度（影响并发请求数）
echo 64 > /sys/block/nvme0n1/queue/nr_requests

# 合并策略：0=禁止，1=仅相邻合并，2=完全合并
echo 2 > /sys/block/sda/queue/nomerges

# 读前/写后的预读大小（KB）
echo 2048 > /sys/block/sda/queue/read_ahead_kb

# 禁用写回缓存（适用于需要强持久化的场景）
echo write through > /sys/block/sda/queue/write_cache

8. 性能测试方法（fio 测试方案）

8.1 基础吞吐量测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 顺序读吞吐量
fio --name=seq-read --ioengine=libaio --iodepth=32 \
    --rw=read --bs=128k --direct=1 --size=4g \
    --filename=/dev/sda --group_reporting

# 顺序写吞吐量
fio --name=seq-write --ioengine=libaio --iodepth=32 \
    --rw=write --bs=128k --direct=1 --size=4g \
    --filename=/dev/sda --group_reporting

# 随机 4K 读 IOPS（典型数据库随机读）
fio --name=rand-read --ioengine=libaio --iodepth=64 \
    --rw=randread --bs=4k --direct=1 --size=4g \
    --filename=/dev/nvme0n1 --group_reporting

8.2 混合读写公平性测试

1
2
3
4
5
# 模拟混合负载：75% 读 + 25% 写，测试调度器公平性
fio --name=mixed --ioengine=libaio --iodepth=32 \
    --rw=randrw --rwmixread=75 --bs=4k --direct=1 \
    --size=4g --filename=/dev/sda --group_reporting \
    --runtime=60 --time_based

8.3 延迟尾部测试（latency percentiles）

1
2
3
4
5
6
7
# 测试不同调度器的 P99 延迟
fio --name=lat-test --ioengine=libaio --iodepth=8 \
    --rw=randread --bs=4k --direct=1 --size=4g \
    --filename=/dev/nvme0n1 --group_reporting \
    --runtime=60 --time_based \
    --percentile_list=50,90,95,99,99.9 \
    --lat_percentiles=1

8.4 多进程公平性测试（验证 BFQ）

1
2
3
4
5
6
7
8
9
10
11
12
13
# 两个进程同时运行：一个大块顺序写，一个小块随机读
# 测试调度器能否保证随机读不被顺序写饿死

# 进程 1：后台顺序写
fio --name=bg-write --ioengine=libaio --iodepth=32 \
    --rw=write --bs=1m --direct=1 --size=4g \
    --filename=/dev/sda --ioscheduler=bfq &

# 进程 2：前台随机读，观察延迟
fio --name=fg-read --ioengine=libaio --iodepth=4 \
    --rw=randread --bs=4k --direct=1 --size=4g \
    --filename=/dev/sda --ioscheduler=bfq \
    --runtime=30 --time_based --lat_percentiles=1

8.5 不同调度器的对比测试脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#!/bin/bash
# 对比 none / mq-deadline / bfq / kyber 的随机读延迟

DEVICE=/dev/nvme0n1
SCHEDULERS="none mq-deadline bfq kyber"

for sched in $SCHEDULERS; do
    echo "Testing scheduler: $sched"
    echo $sched > /sys/block/$(basename $DEVICE)/queue/scheduler
    sleep 1

    fio --name=${sched}-test \
        --ioengine=libaio --iodepth=16 \
        --rw=randread --bs=4k --direct=1 \
        --filename=$DEVICE --size=4g \
        --runtime=30 --time_based \
        --output-format=json \
        --output=${sched}-result.json \
        --group_reporting

    echo "Scheduler $sched: done"
done

# 提取 P99 延迟
for sched in $SCHEDULERS; do
    echo -n "$sched P99: "
    python3 -c "
import json
with open('${sched}-result.json') as f:
    d = json.load(f)
lat = d['jobs'][0]['read']['lat_ns']
print(f\"{lat.get('percentile', {}).get('99.000000', 'N/A')} ns\")
"
done

8.6 blktrace 追踪调度行为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 采集 IO 事件追踪
blktrace -d /dev/sda -o sda_trace &
BTRACE_PID=$!

# 运行工作负载
fio --name=test --ioengine=libaio --iodepth=16 \
    --rw=randrw --bs=4k --direct=1 --size=1g \
    --filename=/dev/sda --runtime=10 --time_based

kill $BTRACE_PID
blkparse sda_trace > sda_trace.txt

# 查看队列、合并、调度延迟统计
btt -i sda_trace.blktrace.0 | head -50

9. 总结

维度 mq-deadline BFQ Kyber
设计目标 防饥饿 + 顺序调度 公平带宽 + 低延迟 延迟目标控制
核心机制 红黑树 + FIFO 双结构 B-WF2Q+ 虚拟时间戳 令牌桶 + 延迟直方图
适用设备 HDD / SATA SSD HDD / SATA SSD NVMe SSD
cgroup 支持 通过 ioprio 类别 完整层次化 cgroup 基础支持
代码复杂度 中等（~1500 行） 极高（~8000 行） 较低（~1000 行）
延迟保证 软 deadline 权重比例保证 目标延迟保证
吞吐量 高（批量顺序调度） 中等（idle 有开销） 高（令牌桶无排序开销）

从架构层面看，Linux IO 调度器体现了策略与机制分离的设计哲学：blk-mq 框架提供了统一的请求分配、标签管理、硬件队列路由机制，调度器插件只需实现特定的策略（如何排序、何时分发、如何公平分配）。三个现代调度器各自针对不同的硬件特性和应用场景做了精细的优化，理解其源码级实现，是进行系统性 IO 调优和内核存储子系统开发的必备基础。