Linux 调度子系统介绍：从 rq、cfs_rq 到调度实体流转

前言自己在看调度子系统时候不太理解rq怎么变化怎么入队出队红黑树怎么变化所以和ai共同完成了这篇文章了解了大概的一些流程。阅读本文的时候可能需要先了解一些cfs调度的基础。Linux 调度子系统的核心职责是决定每个 CPU 下一刻应该运行哪个任务。它并不是一个单一算法而是一套由调度类、运行队列、调度实体、负载统计、抢占机制和多核负载均衡共同组成的系统。在现代 Linux 内核中普通任务主要由 fair 调度类负责。历史上这部分被称为 CFSCompletely Fair Scheduler在较新的内核中fair 调度器已经演进为 EEVDFEarliest Eligible Virtual Deadline First。不过很多核心结构仍然沿用 CFS 时代的命名例如cfs_rq、sched_entity等。调度类Linux 通过不同的 scheduler class 管理不同类型的任务。整体优先级大致如下stop class deadline class realtime class fair / ext class idle class常见调度策略对应关系如下SCHED_DEADLINE - deadline class SCHED_FIFO - realtime class SCHED_RR - realtime class SCHED_NORMAL - fair class SCHED_BATCH - fair class SCHED_IDLE - fair classstop class是内核内部使用的最高优先级调度类例如 CPU hotplug、任务迁移 stop 场景。idle class是兜底逻辑只有没有其他任务可运行时才会运行 idle task。普通应用线程大多属于SCHED_NORMAL因此主要走 fair 调度类。核心结构理解 Linux fair 调度需要先理解几个关键结构task_struct sched_entity rq cfs_rq sched_classtask_struct是 Linux 中进程或线程的核心结构里面包含任务状态、优先级、调度策略、CPU 亲和性等信息。sched_entity是 fair 调度器真正调度的实体。它可以代表一个普通任务也可以代表一个 task group。fair 调度器不会只看task_struct而是通过sched_entity管理运行时间、权重、虚拟运行时间、deadline、统计信息等。rq是 runqueue每个 CPU 一个表示该 CPU 的调度总队列。cfs_rq是 fair 调度类的运行队列是rq中的一部分。二者关系可以概括为rq 每个 CPU 的调度总账本 cfs_rq rq 中 fair 调度类的子账本一个 CPU 的rq大致可以理解为rq ├── dl_rq // deadline 任务 ├── rt_rq // realtime 任务 ├── cfs_rq // 普通 fair 任务 └── idle // idle task因此rq管理该 CPU 上所有调度类的状态cfs_rq只管理 fair 调度类里的普通任务。rq 与 cfs_rq 的区别rq是 per-CPU 唯一的。每个 CPU 都有一个自己的struct rq调度器在这个 CPU 上做选择时会从这个rq出发。rq中包含当前正在运行的 task CPU clock nr_running 调度锁 load/util 统计 deadline/rt/fair 子队列 CPU capacity 负载均衡状态cfs_rq则只服务于 fair 调度类。它负责管理普通任务或 task group 对应的sched_entity。需要注意的是如果开启 group scheduling一个 CPU 上可能不止一个cfs_rq。因为 cgroup/task group 本身也可以作为一个调度实体参与调度。结构上可能类似root cfs_rq ├── task A 的 sched_entity ├── group X 的 sched_entity │ └── group X 的 cfs_rq │ ├── task B │ └── task C └── task D所以rq 是 per-CPU 的 cfs_rq 是 per-CPU、per-task-group 的。CFS 到 EEVDF传统 CFS 的核心思想是公平。每个调度实体都有一个vruntime即虚拟运行时间。普通理解如下任务实际运行越久vruntime 越大 vruntime 越小说明越“欠 CPU” 调度器优先选择 vruntime 最小的任务。nice值会影响权重。高优先级任务权重大运行同样的真实时间时vruntime增长更慢因此能获得更多 CPU 时间。传统 CFS 中红黑树主要按vruntime排序左侧节点 vruntime 更小 更应该被调度但在较新的内核中fair 调度已经切换到 EEVDF。EEVDF 的选择逻辑可以概括为先找 eligible 的实体 再从 eligible 实体中选择 virtual deadline 最早的实体。eligible 可以粗略理解为该实体还“欠 CPU 时间”也就是 lag 0。virtual deadline 则用于表达该实体在公平性和延迟目标下应该被服务的紧迫程度。因此新内核中不能再简单说 fair 调度就是“取红黑树最左边 vruntime 最小的任务”。更准确的说法是fair/EEVDF 在 eligible 实体中选择 virtual deadline 最早的实体。不过cfs_rq中仍然使用红黑树组织调度实体。cfs_rq 中的红黑树和 curr在cfs_rq中有两个非常关键的成员tasks_timeline curr可以理解为cfs_rq ├── tasks_timeline红黑树保存 runnable 但当前没有在 CPU 上运行的实体 └── curr当前正在 CPU 上运行的实体这是理解调度实体流转的关键。很多人容易误以为se-on_rq 1 就表示 se 一定在红黑树里这是不准确的。更准确的关系是se-on_rq 1 表示该实体属于 runnable 队列体系 但它可能在红黑树中也可能正在 cfs_rq-curr 上运行。当前正在 CPU 上运行的实体通常不保留在红黑树中而是放在cfs_rq-curr。所以 fair 调度类中的 runnable 实体可以分成两部分runnable entities 红黑树中的等待实体 cfs_rq-curr任务唤醒进入 cfs_rq 和红黑树当一个任务从睡眠状态被唤醒例如 IO 完成、futex 被唤醒、timer 到期会进入唤醒路径try_to_wake_up() - select_task_rq_fair() - enqueue_task_fair() - enqueue_entity() - __enqueue_entity()此时调度实体会被加入目标 CPU 的cfs_rq。入队时会更新se-on_rq 1 cfs_rq-nr_running / nr_queued load/util 统计 PELT 统计 vruntime / deadline 相关状态如果该实体不是当前运行实体就会插入cfs_rq-tasks_timeline红黑树。在传统 CFS 中插入位置主要由vruntime决定。在 EEVDF 中红黑树主要按 virtual deadline 排序同时通过 augmented rb-tree 维护子树中的min_vruntime等信息以便快速判断某个子树中是否有 eligible 实体。可以简单表示为任务睡眠 - wakeup - se-on_rq 1 - se 插入 cfs_rq 红黑树调度选择从 cfs_rq 中 pick 下一个实体当调度器需要选择下一个任务时会进入类似流程schedule() - pick_next_task() - pick_next_task_fair() - pick_next_entity()传统 CFS 的直觉是选择 vruntime 最小的实体也就是红黑树最左节点。EEVDF 中则是选择 eligible 且 virtual deadline 最早的实体为了做到这一点红黑树不仅按 deadline 排序还维护子树的min_vruntime。这样调度器可以判断左子树中是否存在 eligible 实体如果没有就剪枝跳过。也就是说红黑树在 EEVDF 中承担两个角色按 virtual deadline 提供顺序 通过 augmented 信息辅助 eligibility 搜索。被选中运行从红黑树移动到 curr假设任务 A 被选中运行会进入set_next_entity(cfs_rq, A)如果 A 当前在红黑树中调度器会先把它从红黑树中摘掉然后设置为当前运行实体A 从 tasks_timeline 删除 cfs_rq-curr A A-on_rq 仍然是 1此时 A 的状态是A 正在 CPU 上运行 A 不在红黑树中 A 在 cfs_rq-curr 中 A-on_rq 1。这就是on_rq和“是否在红黑树中”的区别。图示如下运行前 cfs_rq-curr B tasks_timeline: A / \ C D A 被选中后 cfs_rq-curr A tasks_timeline: C \ D红黑树实际形状会因为旋转和平衡发生变化图只是表达语义。任务运行中更新 runtime、vruntime 和 deadline任务 A 在 CPU 上运行时tick 或调度事件会调用update_curr(cfs_rq)它会更新当前实体的运行统计delta_exec now - exec_start sum_exec_runtime delta_exec vruntime 加权后的 delta_exec 更新 virtual deadline / lag 更新 PELT util/load 更新 cfs_rq 统计此时 A 不在红黑树中因此红黑树不会因为 A 每运行一个 tick 就不断旋转。A 的vruntime、deadline 等字段会持续变化等它之后需要重新回到红黑树时再根据新的 key 插入合适位置。普通抢占curr 重新插回红黑树如果 A 时间到了或者另一个更合适的任务 B 被唤醒A 会被切走。但只要 A 仍然 runnable它不会彻底出队而是从curr重新回到红黑树。流程大致是put_prev_entity(cfs_rq, A)如果 A 仍然on_rqupdate_curr(cfs_rq) __enqueue_entity(cfs_rq, A) cfs_rq-curr NULL变化如下A 从 curr 回到 tasks_timeline 红黑树 A-on_rq 仍然是 1 A 仍然 runnable只是暂时不运行。然后下一个实体 B 会被选中B 从红黑树摘出 cfs_rq-curr B因此一次普通的 fair 上下文切换可以理解为prev 仍 runnable: curr - 插回红黑树 next 被选中: 红黑树 - 摘出成为 curr这不是完整的 dequeue/enqueue 语义而是curr和红黑树之间的移动。任务阻塞不再 runnable真正出队如果任务 A 不是被抢占而是主动睡眠例如等待 IO、等待 futex、调用 sleep或者任务退出那么它就不再 runnable需要从 fair 调度队列中移除。流程类似dequeue_task_fair() - dequeue_entity()这里要区分两种情况。如果 A 正在 CPU 上运行也就是cfs_rq-curr A那么 A 本来就不在红黑树中所以不需要从红黑树删除。此时只需要A-on_rq 0 更新 load/util/PELT 更新 cfs_rq 统计 清理 curr如果 A 不在运行而是在红黑树里等待 CPU那么出队时要从红黑树中删除__dequeue_entity() - 从 tasks_timeline 删除 A - A-on_rq 0所以阻塞路径可以总结为如果任务是 curr 不插回红黑树直接离开 runnable 体系 如果任务在红黑树中 从红黑树删除再离开 runnable 体系任务迁核旧 cfs_rq 出队新 cfs_rq 入队在 SMP 系统中任务可能因为负载均衡、唤醒选核、CPU affinity 变化而迁移 CPU。如果任务 A 从 CPU0 迁移到 CPU1逻辑上是CPU0.rq.cfs_rq: dequeue A set_task_cpu(A, CPU1) CPU1.rq.cfs_rq: enqueue A这时它会从旧 CPU 的cfs_rq和红黑树中移除再插入新 CPU 的cfs_rq。如果开启 cgroup 调度迁移还会涉及 task group 层级中对应的cfs_rq和sched_entity。group scheduling 下的层级入队和出队在开启 group scheduling 的系统中调度实体不一定只是 task也可能是 task group。例如root cfs_rq ├── task A ├── group G 的 sched_entity │ └── group G 的 cfs_rq │ ├── task B │ └── task C └── task D当 task B 被唤醒时流程不是只把 B 加到一个平面队列中而是B 的 sched_entity 进入 group G 的 cfs_rq group G 的 sched_entity 进入父级 cfs_rq 必要时继续向上直到 root cfs_rq。出队时也会沿层级更新。这也是为什么 fair 调度中很多 enqueue/dequeue 逻辑会沿for_each_sched_entity()向上遍历。enqueue/dequeue 和上下文切换的区别这是理解调度器时很重要的一点。enqueue/dequeue主要对应任务 runnable 状态变化 任务 CPU 归属变化 任务 cgroup 层级状态变化 任务被 throttle/unthrottle。而普通上下文切换不一定意味着任务完整 dequeue 再 enqueue。例如 A 被 B 抢占A 仍 runnable那么 A 只是从 curr 插回红黑树不是离开cfs_rq。B 被选中时从红黑树摘出成为 curr也不是新唤醒入队。真正的入队通常发生在任务从 sleeping 变成 runnable真正的出队通常发生在任务从 runnable 变成 sleeping / stopped / exited一个完整生命周期示例假设任务 A 从睡眠到运行再到被抢占最后阻塞1. A 睡眠 A 不在红黑树 A-on_rq 0 2. A 被唤醒 enqueue_entity() A 插入 cfs_rq-tasks_timeline A-on_rq 1 3. 调度器选择 A pick_next_entity() set_next_entity() A 从红黑树摘出 cfs_rq-curr A A-on_rq 1 4. A 在 CPU 上运行 update_curr() 更新 A 的 runtime、vruntime、deadline、util A 仍不在红黑树 5. A 被 B 抢占但仍 runnable put_prev_entity() A 插回红黑树 A-on_rq 1 6. B 被选中运行 B 从红黑树摘出 cfs_rq-curr B 7. A 再次被选中 A 从红黑树摘出 cfs_rq-curr A 8. A 等待 IO进入睡眠 dequeue_entity() A 不再插回红黑树 A-on_rq 0图示总结sleeping - wakeup/enqueue - red-black tree - pick/set_next - curr - preempt/put_prev - red-black tree - pick again - curr - block/dequeue - sleeping总结Linux 调度子系统可以从三个层次理解。第一层是调度类deadline / realtime / fair / idle它们决定不同类型任务之间的优先级关系。第二层是运行队列rq 是每个 CPU 的调度总队列 cfs_rq 是 fair 调度类的运行队列。第三层是 fair 调度内部的实体流转红黑树保存等待 CPU 的 runnable entity curr 保存当前正在 CPU 上运行的 entity on_rq 表示 entity 仍属于 runnable 体系但不表示它一定在红黑树中。最终可以用一张简图概括CPU rq ├── dl_rq ├── rt_rq ├── cfs_rq │ ├── tasks_timeline 红黑树 │ │ ├── 等待 CPU 的 sched_entity │ │ └── 等待 CPU 的 sched_entity │ └── curr │ └── 当前正在运行的 sched_entity └── idle普通 fair 调度任务的状态变化可以概括为wakeup: sleeping - 红黑树 pick: 红黑树 - curr preempt: curr - 红黑树 block/exit: curr 或 红黑树 - 离开 cfs_rq migrate: old cfs_rq - new cfs_rq理解这条主线后再去看enqueue_task_fair()、dequeue_task_fair()、pick_next_entity()、set_next_entity()、put_prev_entity()、update_curr()这些函数就能把 fair 调度中的任务流转和红黑树变化串起来。