Linux CFQ 调度器源码解析

第一章：CFQ 调度器设计背景与核心思想

1.1 从单队列到公平调度：CFQ 诞生的动机

    在 Linux 块层的发展过程中，I/O 调度器的演进本质上是在解决三个核心矛盾：吞吐量（throughput）、延迟（latency）以及公平性（fairness）。早期的 Linux 使用简单的 elevator（如 noop 和 deadline）来进行请求排序，这类调度器更多关注磁盘寻道优化（如电梯算法减少 seek），而对“谁的 I/O 应该优先执行”缺乏精细控制。在多进程环境中，尤其是数据库、桌面系统以及多用户服务器中，不同进程的 I/O 行为差异极大，例如同步读（interactive）与批量写（batch）之间存在显著冲突，如果仅依赖 FIFO 或简单排序机制，就会导致某些进程长期得不到调度，从而产生 starvation。

    CFQ 的设计目标正是为了解决这一问题，其核心理念是“将磁盘 I/O 资源视为可分配的时间片资源”，类似于 CPU 调度中的 Completely Fair Scheduler（CFS）。CFQ 并不是简单地按请求排序，而是将请求归属到进程（或进程组）级别，通过为每个进程维护独立的队列（cfq_queue），再基于时间片（time slice）来轮转调度，从而实现“按进程公平分配磁盘带宽”。这种设计使得 CFQ 能够区分同步 I/O 与异步 I/O，给予交互式任务更高优先级，同时避免批量任务完全压制其他任务。

    从源码结构来看，CFQ 主要实现在 block/cfq-iosched.c 中，其核心数据结构包括 cfq_data（调度器全局状态）、cfq_queue（每个进程或上下文的请求队列）、cfq_group（cgroup 支持）等。CFQ 将 block layer 中的 request_queue 抽象为多个逻辑队列，并在调度层维护红黑树（rb_tree）来管理这些队列的调度顺序。这里的关键在于：CFQ 并不直接对 request 排序，而是对“队列”排序，再从队列中取 request，这是一种两级调度模型。

    这种设计在机械硬盘时代尤为有效，因为 seek 成本高且 I/O 请求差异明显，但随着 SSD 的普及，其意义逐渐减弱，这也是后来 CFQ 被 blk-mq + mq-deadline/BFQ 替代的重要原因之一。不过从架构角度看，CFQ 是 Linux I/O 调度器中最复杂、最具“操作系统调度思想”的实现之一，其源码极具研究价值。

1.2 CFQ 的核心机制：时间片、公平性与队列分层

    CFQ 的核心机制可以归纳为三个关键词：时间片（time slice）、服务树（service tree）以及优先级权重（weight）。每一个 cfq_queue 在被调度时都会分配一个时间片，在这个时间片内，该队列可以连续发起 I/O 请求，从而减少磁盘 head 的频繁切换，这一点与 CPU 调度中的时间片轮转类似。但与 CPU 调度不同的是，CFQ 的时间片并非固定，而是根据队列类型（同步/异步）、历史行为以及系统负载动态调整。在源码中，时间片管理主要通过 cfq_slice_alloc() 和 cfq_slice_expired() 等函数实现。每当一个队列被选中调度时，CFQ 会调用 cfq_set_active_queue() 将其设为 active queue，并记录其 slice 起始时间。随着请求不断 dispatch，如果时间片耗尽或队列空闲，就会触发 slice 过期逻辑，从而切换到下一个队列。值得注意的是，CFQ 引入了“idle slice”机制，即在同步读场景下，调度器会在队列暂时无请求时短暂等待（idle），以便该进程快速提交后续请求，从而减少上下文切换带来的性能损耗。

    服务树（service tree）是 CFQ 实现公平性的核心数据结构，其本质是一个基于虚拟时间（vtime）的红黑树。在 cfq_group 内部，所有 cfq_queue 会按照其虚拟运行时间（类似 CFS 的 vruntime）排序，调度器总是选择“最少服务”的队列优先执行。相关实现可见 cfq_service_tree_add() 和 cfq_rb_first() 等函数。每个队列在执行 I/O 时，其服务时间会累加到 vtime，从而影响其在树中的位置，这种机制确保了长期公平性。

    CFQ 还支持 I/O 优先级（ionice）和 cgroup 权重控制。每个队列都有一个权重值（weight），权重越高，其分配到的时间片越多。在源码中，权重转换为时间片长度通常通过比例计算实现，例如 slice = base_slice * weight / total_weight。这种机制使得系统管理员可以对关键服务（如数据库）分配更多 I/O 资源。

    总结来看，CFQ 的设计本质是“将 I/O 调度问题转化为时间分配问题”，并通过分层队列 + 红黑树调度 + 动态时间片，实现接近理想公平的资源分配模型。这种设计虽然复杂，但为后续 blk-mq 调度器提供了重要的理论基础。

第二章：CFQ 核心数据结构与内存布局

2.1 cfq_data 与全局调度状态管理

    CFQ 调度器的核心入口是 cfq_data 结构体，它对应于每一个 block device 的调度实例，可以理解为 CFQ 的“全局上下文”。在 request_queue 初始化时，如果选择 CFQ 调度器，会调用 cfq_init_queue() 分配并初始化一个 cfq_data 实例，并挂载到 

q->elevator->elevator_data

上。这个结构体内部包含多个关键字段，例如 service_tree（服务树）、active_queue（当前调度队列）、busy_queues（活跃队列数量）以及时间相关的统计信息。

cfq_data 中最重要的成员之一是 struct cfq_rb_root service_tree;，它本质上是一个红黑树，用于维护所有活跃 cfq_queue 的调度顺序。除此之外，CFQ 还维护多个服务树，例如针对不同优先级（RT、BE、IDLE）的分类树，这在源码中通过 cfq_data->service_trees[CFQ_PRIO_NR] 实现。这种多树结构允许 CFQ 先按优先级选择队列，再在同一优先级内实现公平调度。

另一个关键字段是 active_queue，表示当前正在消耗时间片的 cfq_queue。当该队列时间片用尽或不再有请求时，调度器会调用 cfq_schedule_dispatch() 从服务树中选择下一个队列。这一过程涉及多个函数调用链：

cfq_dispatch_requests() → cfq_select_queue() → cfq_rb_first()

体现了 CFQ 的核心调度路径。

    在并发控制方面，CFQ 依赖 request_queue 的队列锁（queue_lock）以及自身的 spinlock 来保证数据结构一致性。由于 CFQ 是为单队列 block layer 设计的，其锁竞争问题在多核环境下较为严重，这也是 blk-mq 替代它的重要原因之一。从源码角度看，大量函数都以 _locked 形式存在，例如 cfq_add_rq_rb()，要求调用者持有锁。

    cfq_data 是 CFQ 的“大脑”，负责全局调度决策、队列管理以及时间片分配，是理解 CFQ 的入口。

2.2 cfq_queue 与进程级 I/O 抽象

    与 cfq_data 相对应，cfq_queue 是 CFQ 中最核心的“执行单元”，它代表一个进程（或 I/O 上下文）的请求队列。每个进程在发起 I/O 时，会通过 cfq_get_queue() 获取或创建一个 cfq_queue，该队列内部维护该进程的所有 pending request。这样，CFQ 可以实现“按进程隔离”的调度策略，而不是简单的全局 request 队列。

    cfq_queue 内部包含多个关键字段，例如 rb_root sort_list（用于按 sector 排序的请求树）、fifo 队列（用于 FIFO fallback）、slice_start（时间片起始时间）以及 slice_end（结束时间）。其中 sort_list 是一个按扇区号排序的红黑树，用于减少磁盘寻道，而 FIFO 队列用于处理 deadline 相关逻辑，避免请求长期得不到处理。

    cfq_queue 还包含状态标志，例如是否为同步队列（sync queue）、是否处于 idle 状态等。这些状态直接影响调度策略。例如，同步读队列通常会获得更长的 idle 时间，以提高交互性能，而异步写队列则更倾向于批量处理。在源码中，这些逻辑分布在 cfq_should_idle()、cfq_slice_idle() 等函数中。

    CFQ 支持 cgroup（blkio controller），通过 cfq_group 将多个 cfq_queue 组织成层次结构。在这种情况下，调度不再是简单的“进程公平”，而是“组内公平 + 组间权重分配”。这在云计算环境中尤为重要，可以实现不同容器之间的 I/O 隔离。

    从生命周期角度看，cfq_queue 的创建与销毁与 I/O 上下文（io_context）紧密相关。当进程退出或长时间无 I/O 时，其 cfq_queue 会被回收。源码中通过引用计数（refcount）来管理这一过程，避免悬挂指针。

    cfq_queue 是 CFQ 实现公平调度的核心抽象，它将复杂的 I/O 请求流转化为“按队列调度”的模型，并通过多种数据结构（红黑树 + FIFO）实现高效管理。

第三章：请求插入路径与排序机制

3.1 请求进入 CFQ：从 submit_bio 到 cfq_insert_request

    当用户态发起一次 I/O 操作（例如 read/write），最终会通过 submit_bio() 进入 block layer，并在经过 request 合并（merge）后生成一个 struct request。如果当前调度器是 CFQ，则该 request 会进入 CFQ 的插入路径，即 cfq_insert_request()。这一函数是 CFQ 接收新请求的核心入口，其主要任务是将 request 插入到对应的 cfq_queue 中，并维护排序结构。

在调用链上，路径大致为：

submit_bio() → generic_make_request() → blk_mq_submit_bio()（旧内核为 __make_request()）→ elv_add_request() → cfq_insert_request()。

    在这个过程中，CFQ 会首先通过 cfq_get_queue() 找到当前进程对应的 cfq_queue，如果不存在则创建新的队列。这个过程依赖于 io_context，即每个进程的 I/O 上下文，用于关联进程与队列。

    进入 cfq_insert_request 后，CFQ 会尝试将 request 插入到队列的 sort_list 红黑树中，该树按扇区号排序，从而实现类似 elevator 的寻道优化。如果 request 可以与已有请求合并（例如相邻扇区），则会触发 merge 逻辑，这在 cfq_merge() 和 elv_merge() 中实现。否则，请求将作为一个新的节点插入红黑树。

    CFQ 还会将 request 插入 FIFO 队列（通常是双向链表），用于保证请求不会长期饿死。FIFO 队列与 sort_list 是并行存在的，两者分别服务于不同目标：前者保证公平性，后者优化性能。在 dispatch 阶段，CFQ 会根据策略在两者之间进行选择。

    CFQ 在插入请求时会更新队列状态，例如如果队列此前为空，则可能将其加入 service tree，并标记为 busy queue。这一步通过 cfq_add_cfqq_busy() 完成，它会将 cfq_queue 插入到 cfq_data 的服务树中，从而参与调度。

    请求插入路径不仅仅是“放入队列”，而是涉及队列创建、排序结构维护、合并优化以及调度状态更新，是 CFQ 整体工作流的起点。

3.2 排序与合并：红黑树与 FIFO 的协同设计

    CFQ 的排序机制是其性能优化的重要组成部分，其核心在于“在公平调度的前提下尽可能减少磁盘 seek”。为此，CFQ 在每个 cfq_queue 内部维护一个按扇区号排序的红黑树（sort_list），以及一个 FIFO 队列。这种双结构设计使得 CFQ 能够在性能与公平之间取得平衡。

    红黑树排序的核心函数是 cfq_add_rq_rb()，它会根据 request 的起始扇区（sector）将其插入到合适的位置。在 dispatch 阶段，CFQ 会优先选择“最接近当前磁头位置”的请求，从而减少寻道时间。这种策略类似于传统 elevator，但局限于单个队列内部，而不是全局。

    FIFO 队列用于实现类似 deadline 的机制，即如果某个请求在队列中等待时间过长，则必须优先处理。在源码中，每个 request 都带有一个时间戳（例如 rq->fifo_time），CFQ 会在 dispatch 时检查是否有请求超时，如果有，则优先从 FIFO 队列中取出。这一逻辑在 cfq_dispatch_requests() 中体现。

    CFQ 还支持 request merge，即在插入新请求时尝试与已有请求合并，从而减少 I/O 次数。merge 分为 front merge 和 back merge，分别对应前向和后向合并。CFQ 通过 elv_rb_find() 在红黑树中查找相邻请求，如果满足条件则合并。这一机制对顺序 I/O 性能提升显著。

    需要注意的是，CFQ 的排序是“局部排序”，即每个队列内部有序，但队列之间不直接排序，而是通过服务树调度。这种两级排序机制使得 CFQ 在多进程环境下既能保持公平性，又能兼顾单进程性能。

    CFQ 的排序与合并机制体现了其设计哲学：在复杂的调度模型中，通过局部优化（红黑树排序）和全局策略（服务树调度）协同，实现整体性能最大化。

第四章：CFQ 调度与 dispatch 路径深度解析

4.1 调度入口：cfq_dispatch_requests 调用链与执行框架

    CFQ 的调度核心发生在 request 被“派发（dispatch）”到设备驱动之前，这一过程的主入口函数是 cfq_dispatch_requests()。从调用路径来看，block layer 在需要从调度器获取 request 时，会调用 __blk_run_queue()，进而进入 q->elevator->ops->elevator_dispatch_fn，在 CFQ 中对应的就是 cfq_dispatch_requests()。这一函数承担了从 CFQ 内部结构中选取合适 request 并提交到底层驱动的职责，是 CFQ 最关键的执行路径之一。

    在实现上，cfq_dispatch_requests 并不是简单地从某个队列取出 request，而是经历了一个完整的调度决策过程。首先，它会检查当前是否存在 active queue（即正在消耗时间片的 cfq_queue），如果没有，则通过 cfq_select_queue() 从 service tree 中选择一个新的队列。这个选择过程基于红黑树最左节点（最小 vtime），即“最应该被服务”的队列。选中之后，通过 cfq_set_active_queue() 将其设置为当前活动队列，并初始化其时间片。

    一旦 active queue 确定，调度器就会尝试从该队列中取 request。具体过程由 cfq_dispatch_insert() 或类似函数完成，它会优先从队列的 sort_list（红黑树）中选择合适的 request，同时检查 FIFO 队列是否有超时请求需要优先处理。如果当前队列没有 request（可能是刚好用完或暂时无新请求），则进入 idle 判断逻辑，这一点在下一章会详细分析。

    CFQ 在 dispatch 时还会考虑设备队列深度（queue depth）以及 request 合并状态。如果底层设备队列已满（例如 NCQ 深度达到上限），则调度器不会继续 dispatch，而是等待完成中断（completion）后再触发调度。这一行为通过 blk_queue_full() 等接口体现。

    从并发角度看，cfq_dispatch_requests 通常在持有 queue_lock 的情况下执行，因此其执行路径必须尽量高效，否则会影响整个 block layer 的并发性能。这也是 CFQ 在多核环境下扩展性较差的原因之一：所有调度决策都在单锁保护下完成。

    cfq_dispatch_requests 并非简单的“取请求”，而是包含了队列选择、时间片管理、排序策略以及设备状态判断的一整套调度逻辑，是 CFQ 调度器的执行核心。

4.2 队列选择算法：cfq_select_queue 与服务树调度

    CFQ 的公平性核心体现在队列选择算法中，而这一逻辑集中在 cfq_select_queue() 函数中。该函数的任务是：从所有活跃的 cfq_queue 中选出“最应该被调度”的一个。其实现基础是 service tree（服务树），即一个按虚拟时间（vtime）排序的红黑树。

    在 CFQ 中，每个 cfq_queue 都维护一个类似 CFS 的虚拟运行时间（vtime），表示该队列已经消耗的服务量。队列每执行一次 I/O，其 vtime 会增加，从而在服务树中的位置向右移动。调度器总是选择 vtime 最小的队列（即红黑树最左节点），保证长期来看每个队列获得的服务时间近似相等。这一机制本质上是“最小服务优先”，与 CFS 的 vruntime 模型高度一致。

    在源码实现中，cfq_select_queue 会遍历不同优先级（RT、BE、IDLE）的服务树，优先选择高优先级树中的队列。如果高优先级树为空，则降级选择下一层。这种多级服务树结构使得 CFQ 能够同时实现“优先级调度 + 公平调度”。例如，实时任务（RT）可以始终优先于普通任务（BE），但在同一优先级内部仍然保持公平。

    当选中一个队列后，CFQ 会调用 cfq_slice_alloc() 为其分配时间片。时间片长度与队列权重（weight）相关，权重越高，时间片越长。此外，CFQ 还会根据队列类型（同步/异步）调整 slice，例如同步读通常获得更长的 slice，以提升交互性能。

    一个重要细节是：CFQ 的公平性是“基于时间”的，而不是“基于请求数”。也就是说，一个大 request（例如 1MB 顺序写）与多个小 request（例如 4KB 随机读）在调度上是按时间消耗来计量的，而不是数量。这种设计更接近实际设备负载，但也带来了复杂性，例如需要精确估计每个 request 的服务时间。

    CFQ 在队列切换时还会更新统计信息，例如 cfqg->vdisktime（虚拟磁盘时间），并将队列重新插入服务树。这一过程通过 cfq_service_tree_add() 和 cfq_service_tree_del() 完成，确保红黑树始终保持有序。

    cfq_select_queue 是 CFQ 公平调度的核心算法，其通过红黑树 + 虚拟时间机制，实现了类似 CPU 调度器的公平性模型，同时结合优先级体系，满足复杂系统需求。

第五章：时间片分配与 Idle 策略

5.1 时间片机制：slice 分配与过期控制

    CFQ 的时间片（slice）机制是其区别于其他 I/O 调度器的核心特征之一，它将磁盘 I/O 抽象为“时间资源”，并按时间片分配给不同队列。时间片的分配由 cfq_slice_alloc() 完成，而过期控制则由 cfq_slice_expired() 和相关逻辑处理。

    在实现上，每个 cfq_queue 在被选中为 active queue 时，会分配一个 slice，记录在 cfqq->slice_start 和 cfqq->slice_end 中。slice 的长度通常基于一个基础值（如 cfq_slice_sync 或 cfq_slice_async），再根据队列权重进行调整。例如，高权重队列会获得更长的 slice，从而在单位时间内发起更多 I/O。

    时间片的消耗并不是简单的“时间流逝”，而是与 request dispatch 紧密相关。每当一个 request 被 dispatch，CFQ 会更新当前时间，并检查是否超过 slice_end。如果超出，则触发 slice 过期，当前队列被移出 active 状态，并重新插入服务树等待下一轮调度。

    CFQ 还引入了多种 slice 类型，例如同步 slice、异步 slice、idle slice 等。同步 slice 通常较长，以保证交互式任务（如 shell、GUI）的响应性，而异步 slice 较短，以防止后台写任务占用过多资源。这些参数可以通过 /sys/block/*/queue/iosched/ 进行调优。

    CFQ 还实现了“slice 延长”机制，即如果一个队列在 slice 内持续有请求且表现为顺序 I/O，调度器可能会延长其 slice，以减少队列切换带来的开销。这一优化在 cfq_should_preempt() 等函数中体现。

    slice 机制虽然提高了公平性，但也引入了额外延迟。例如，当一个新队列到达时，必须等待当前队列 slice 用完才能被调度，这在某些低延迟场景下是不利的。

    时间片机制是 CFQ 的核心资源分配手段，通过动态 slice 分配与过期控制，实现了精细化的 I/O 调度。

5.2 Idle 策略：提升同步 I/O 性能的关键优化

    CFQ 的 idle 策略是其最具特色、也是最具争议的设计之一，其核心思想是在同步 I/O 场景下“主动等待”一小段时间，以便同一进程提交后续请求，从而减少队列切换和磁盘寻道。

    当 active queue 的 request 被耗尽时，CFQ 并不会立即切换到下一个队列，而是调用 cfq_should_idle() 判断是否需要进入 idle 状态。如果该队列是同步队列（例如读操作），且系统负载较低，则 CFQ 会等待一段时间（由 cfq_slice_idle 控制），期间如果有新请求到达，则继续使用当前队列，否则才切换。

    这一机制对交互式应用非常重要。例如，一个进程执行 read() 系统调用，读取一块数据后需要进行用户态处理，然后再发起下一次 read。如果调度器立即切换队列，就会导致磁盘 head 在不同队列之间来回跳动，增加延迟。而 idle 策略可以保持“上下文局部性”，显著降低平均响应时间。

    在源码中，idle 机制通过定时器或延迟检查实现，CFQ 会记录 idle 起始时间，并在 dispatch 循环中不断检查是否超时或有新请求到达。如果超时，则触发 slice 过期；如果有新请求，则继续 dispatch。

    idle 策略在 SSD 时代逐渐成为负担。由于 SSD 没有寻道成本，等待（idle）反而会浪费时间，降低吞吐量。因此，在现代系统中，通常会关闭或缩短 idle 时间。

    CFQ 还支持“非 idle 队列”，例如异步写队列通常不会启用 idle，以避免影响整体吞吐。

    idle 策略体现了 CFQ 对机械硬盘特性的深度优化，但在新型存储设备上，其收益逐渐下降，这也是 CFQ 被淘汰的重要原因之一。

第六章：CFQ 的局限性与被替代的根本原因

6.1 单队列架构瓶颈与多核扩展问题

    CFQ 设计于单队列 block layer 时代，其所有调度决策都围绕一个全局 request_queue 展开，这在多核系统中带来了严重的扩展性问题。由于所有 I/O 请求都需要经过同一个调度器实例，并受同一把 queue_lock 保护，当 CPU 核数增加、I/O 并发度提升时，这把锁会成为性能瓶颈。

    具体表现为：在高并发场景下，大量线程同时提交 I/O，请求在进入 CFQ 时需要争抢 queue_lock，而调度路径（如 cfq_insert_request、cfq_dispatch_requests）本身又较为复杂，持锁时间较长，从而导致严重的锁竞争（lock contention）。这不仅增加了 CPU 开销，还会限制 I/O 吞吐。

    CFQ 的调度模型是“串行”的，即同一时刻只有一个 active queue 在 dispatch request，这在机械硬盘时代是合理的（因为设备本身是串行的），但在支持并行 I/O 的设备（如 SSD、NVMe）上就显得过于保守。现代存储设备可以同时处理多个 request，而 CFQ 的模型无法充分利用这一能力。

    这些问题直接促使了 blk-mq（multi-queue block layer）的诞生。blk-mq 将单一 request_queue 拆分为多个硬件队列（hardware queue）和软件队列（software queue），每个 CPU 可以独立提交 I/O，从而显著减少锁竞争。而 CFQ 由于设计上依赖单队列，难以适配这一架构。

    因此，从架构层面看，CFQ 的最大局限在于其“中心化调度模型”，无法适应多核与高并发 I/O 的发展趋势。

6.2 SSD 时代的失效与调度器演进

    CFQ 的另一个根本问题在于其优化目标是机械硬盘（HDD），而非现代 SSD。在 HDD 上，寻道时间（seek time）是主要开销，因此 CFQ 通过排序（sort_list）和 idle 策略来减少 seek，效果显著。但在 SSD 上，访问延迟几乎与位置无关，这些优化反而成为负担。

    例如，CFQ 的排序机制在 SSD 上意义不大，因为随机访问与顺序访问成本差异很小；而 idle 策略则会直接浪费时间，因为没有必要等待“局部性”。此外，CFQ 的时间片模型可能导致设备队列利用率不足，无法充分发挥 SSD 的并行能力。

随着 blk-mq 的引入，Linux 社区逐步用新的调度器替代 CFQ，例如：

• mq-deadline：在多队列环境下实现类似 deadline 的简单调度，强调低延迟与高吞吐

• BFQ（Budget Fair Queueing）：继承 CFQ 思想，但在 blk-mq 上重新设计，提供更好的公平性

• none：完全不调度，直接将 request 提交给设备（适用于高性能 SSD）

CFQ 最终在 Linux 5.x 之后被逐步移除，成为历史。这一演进过程反映了一个重要趋势：I/O 调度器必须紧密结合硬件特性，不能脱离设备模型单独设计。

    从架构角度总结，CFQ 是“面向 HDD 的公平调度器”，而现代调度器则是“面向并行设备的轻量调度器”。CFQ 的思想（如公平性、权重控制）仍然在 BFQ 中延续，但其具体实现已经完全重构。