2. CFS调度器基础：完全公平调度器（CFS）的设计思想，红黑树与虚拟运行时间（vruntime）原理

完全公平调度器（Completely Fair Scheduler, CFS）是 Linux 内核自 2.6.23 版本引入的默认调度器，其设计哲学颠覆了传统基于时间片轮转和优先级分级的调度模型。CFS 的核心目标是在真实硬件（有限 CPU 核心）上，为每个可运行进程模拟一个“理想、精确的多任务处理器”，确保每个进程都能获得公平的 CPU 时间份额。

核心思想： CFS 不直接分配时间片，而是通过维护一个按虚拟运行时间（vruntime）排序的红黑树，每次选择 vruntime 最小的进程来运行，从而在宏观上实现绝对的公平。

2.1 设计思想：从“时间片”到“权重比例”

传统 O(1) 调度器依赖固定的时间片和静态优先级，存在交互性差、时间片粒度粗糙等问题。CFS 引入了基于 权重（weight） 的调度模型，将调度决策转化为一个连续的比例公平问题。

  • 权重（Weight）： 每个进程（或调度组）都有一个权重值，由进程的 nice 值映射而来。权重越高，进程获得的 CPU 时间比例越大。
  • 调度延迟（sched_latency）： CFS 保证在一个调度周期内，所有可运行进程至少被调度一次。默认值为 6ms，可通过 /proc/sys/kernel/sched_latency_ns 调整。
  • 最小粒度（min_granularity）： 为了防止进程切换过于频繁，CFS 规定了进程运行的最小时间片，默认值为 0.75ms。

CFS 的调度周期并非固定，而是根据可运行进程数量动态调整：

// 调度周期计算逻辑（简化）
// nr_running: 当前可运行进程数量
// sched_latency: 调度延迟
// min_granularity: 最小粒度

if (nr_running * min_granularity <= sched_latency)
    period = sched_latency;
else
    period = nr_running * min_granularity;

每个进程在调度周期内获得的实际运行时间由其权重决定：

// 进程获得的实际运行时间
time_slice = period * (进程权重 / 所有可运行进程总权重)
关键对比： 传统调度器是“时间片分配器”，而 CFS 是“CPU 时间比例分配器”。CFS 不关心进程具体运行了多久，只关心它相对于其他进程是否获得了公平的份额。

2.2 虚拟运行时间（vruntime）原理

vruntime 是 CFS 实现公平调度的核心度量。它不是一个真实的时间，而是一个经过权重修正后的“虚拟时间”，用于衡量进程在理想多任务处理器上应该运行了多久。

vruntime 的计算公式：

// 进程每运行一次时钟 tick，vruntime 增加量
vruntime += delta_exec * (NICE_0_LOAD / 进程权重)

// 其中：
// delta_exec: 进程实际运行的物理时间
// NICE_0_LOAD: nice 值为 0 时的标准权重（1024）
// 进程权重: 由进程的 nice 值决定

vruntime 的核心特性：

特性 说明 调度意义
单调递增 进程运行时，vruntime 持续增加 运行越久的进程，vruntime 越大，被选中的概率越低
权重归一化 高权重进程的 vruntime 增长更慢 高权重进程可以运行更长的物理时间，但 vruntime 增长与低权重进程保持同步
睡眠补偿 进程睡眠时，vruntime 保持不变或减少 I/O 密集型进程（如交互式进程）醒来后 vruntime 较小，能快速获得 CPU
跨 CPU 归一化 不同 CPU 上的 vruntime 通过 min_vruntime 进行同步 保证进程迁移到其他 CPU 后，调度公平性不受影响
避坑指南： vruntime 不是物理时间，也不是 CPU 时间。它是一个用于排序的“虚拟标尺”。两个权重不同的进程，即使 vruntime 相同，它们实际运行的物理时间也可能相差很大。
不同权重进程的 vruntime 增长速率对比 不同权重进程的 vruntime 增长速率对比 物理时间 (delta_exec) vruntime 高权重进程 (nice=-20) 标准权重进程 (nice=0) 低权重进程 (nice=19) 斜率 = NICE_0_LOAD / 进程权重。权重越大，斜率越小，vruntime 增长越慢。

2.3 红黑树（Red-Black Tree）数据结构

CFS 使用红黑树来组织所有可运行进程（即处于 TASK_RUNNING 状态的进程）。红黑树是一种自平衡二叉查找树，其查找、插入、删除操作的时间复杂度均为 O(log n)，非常适合调度器这种需要频繁操作的数据结构。

红黑树在 CFS 中的角色：

  • 键值（Key）： 每个节点的键值是进程的 vruntime。
  • 排序规则： 左子树的 vruntime 小于父节点，右子树的 vruntime 大于父节点。
  • 最左节点： 整棵树中 vruntime 最小的节点，即下一个要被调度的进程。
  • 缓存指针： CFS 维护了一个 rb_leftmost 指针，直接指向最左节点，实现 O(1) 的“下一个进程”查找。
性能优势： 红黑树保证了调度器在数千个进程并发时，仍然能高效地找到下一个要运行的进程。相比 O(1) 调度器的优先级数组，红黑树在进程数量动态变化时表现更稳定。
CFS 红黑树结构示意图 CFS 红黑树结构示意图 vruntime=100 vruntime=50 vruntime=150 vruntime=20 vruntime=80 vruntime=120 vruntime=200 ← 下一个调度 红黑树按 vruntime 排序，最左节点（vruntime 最小）即为下一个要运行的进程。 CFS 通过 cached_leftmost 指针直接获取最左节点，实现 O(1) 的调度决策。 当进程运行时，其 vruntime 增加，可能会被重新插入到树中更靠右的位置。

2.4 CFS 调度流程：从 enqueue 到 pick_next

CFS 的调度流程可以概括为三个核心操作：入队（enqueue）、选择（pick_next） 和 出队（dequeue）。

  1. enqueue_task_fair（入队）：
    • 当进程变为可运行状态（如被唤醒、fork 新进程）时，调用此函数。
    • 计算进程的初始 vruntime（通常基于当前 CPU 的 min_vruntime）。
    • 将进程节点插入到红黑树中，并更新 rb_leftmost 指针。
  2. pick_next_task_fair（选择下一个）：
    • 从红黑树中获取 rb_leftmost 指向的节点。
    • 如果当前进程与选中的进程不同，则执行上下文切换。
    • 如果红黑树为空，则选择 idle 进程。
  3. dequeue_task_fair（出队）：
    • 当进程变为不可运行状态（如睡眠、退出）时，调用此函数。
    • 将进程节点从红黑树中移除。
    • 更新 rb_leftmost 指针，指向新的最左节点。
关键数据结构： 每个 CPU 都有一个独立的 CFS 运行队列 struct cfs_rq，其中包含红黑树的根节点 tasks_timeline、rb_leftmost 指针、min_vruntime 等关键字段。
CFS 调度核心流程 CFS 调度核心流程 进程变为可运行 enqueue_task_fair() pick_next_task_fair() 进程运行 (vruntime 增长) 时钟中断触发 scheduler_tick()，检查是否需要抢占当前进程。

2.5 调度实体与组调度（Scheduling Entity & Group Scheduling）

CFS 的调度单位是 调度实体（struct sched_entity），它可以是单个进程，也可以是一个 任务组（task group）。组调度（Group Scheduling）是 CFS 的重要扩展，允许对一组进程进行整体资源控制。

调度实体类型 对应结构 说明
进程实体 struct task_struct 中的 se 字段 代表一个独立的线程或进程
组实体 struct task_group 中的 se 字段 代表一组进程，组内进程共享组分配的 CPU 时间

组调度的层级结构：

  • 每个任务组有自己的 CFS 运行队列（struct cfs_rq）和红黑树。
  • 组实体作为父级 CFS 运行队列中的一个节点参与调度。
  • 当组实体被选中运行时，调度器会进入该组的 CFS 运行队列，选择组内 vruntime 最小的进程运行。
  • 这种层级结构支持嵌套，可以实现精细化的 CPU 资源隔离（如 Docker 容器的 CPU 份额控制）。
实际应用： 通过 cpu.shares（CFS 配额）和 cpu.cfs_quota_us（CFS 带宽控制），可以精确限制容器或 cgroup 的 CPU 使用上限和下限。
CFS 组调度层级结构 CFS 组调度层级结构 根 CFS 运行队列 组实体 A (shares=1024) 组实体 B (shares=2048) 进程 A1 进程 A2 进程 B1 进程 B2 组调度层级：根队列包含组实体，组实体内部包含自己的 CFS 运行队列和红黑树。 组 A 的 shares=1024，组 B 的 shares=2048，因此组 B 获得的 CPU 时间是组 A 的 2 倍。 组内进程再按各自的权重公平分配组获得的 CPU 时间。

2.6 关键数据结构与内核代码映射

理解 CFS 需要熟悉以下几个核心内核数据结构：

数据结构 文件位置 关键字段 作用
struct cfs_rq kernel/sched/sched.h load, nr_running, min_vruntime, tasks_timeline, rb_leftmost 每个 CPU 的 CFS 运行队列
struct sched_entity include/linux/sched.h load, run_node, vruntime, on_rq, parent 调度实体，嵌入在 task_struct 或 task_group 中
struct task_group kernel/sched/sched.h se, cfs_rq, shares 任务组，用于组调度和 cgroup 控制
struct sched_class kernel/sched/sched.h enqueue_task, dequeue_task, pick_next_task, check_preempt_curr 调度类接口，CFS 对应 fair_sched_class

核心函数调用链（以时钟中断触发调度为例）：

scheduler_tick()
  └─ task_tick_fair()          // CFS 的时钟 tick 处理
       ├─ update_curr()        // 更新当前进程的 vruntime 和负载
       ├─ check_preempt_tick() // 检查是否需要抢占
       │    └─ resched_curr()  // 设置 TIF_NEED_RESCHED 标志
       └─ entity_tick()        // 处理调度实体的 tick
            └─ update_cfs_rq_h_load() // 更新运行队列的负载
学习建议： 阅读内核源码时，建议从 kernel/sched/fair.c 中的 task_tick_fair() 和 pick_next_task_fair() 入手，这两个函数是理解 CFS 运行时行为的最佳入口。

2.7 本章小结

CFS 调度器通过 权重比例分配 替代了传统的时间片模型，利用 vruntime 作为公平性的统一度量，借助 红黑树 实现高效的进程排序和选择。其核心设计思想可以概括为：

  • 公平性： 所有进程在 vruntime 维度上平等，权重只影响物理时间的分配比例。
  • 高效性： 红黑树 + cached_leftmost 指针保证了 O(log n) 的插入/删除和 O(1) 的调度决策。
  • 可扩展性： 组调度机制支持层级化的资源控制，为容器化和虚拟化场景提供了基础。
  • 交互性： 睡眠补偿机制天然支持 I/O 密集型进程，无需单独的交互式进程检测逻辑。

理解 CFS 的这些基础原理，是后续深入分析 PELT 负载跟踪算法、负载均衡、调度延迟优化等高级主题的必备前提。

← 上一章 📖 返回目录 下一章 →