2. CFS调度器基础
完全公平调度器（Completely Fair Scheduler, CFS）是 Linux 内核自 2.6.23 版本起引入的默认调度类，用于普通进程（SCHED_NORMAL / SCHED_OTHER）的 CPU 时间分配。CFS 摒弃了传统基于固定时间片和优先级计算权重的 O(1) 调度器模型，转而采用一种基于“虚拟运行时间”的加权公平队列模型，其核心数据结构为红黑树。
2.1 CFS的设计哲学：模拟理想多任务处理器
CFS 的设计目标非常直观：让每个可运行的进程都能获得 CPU 时间的“公平”份额。其理想模型是假设存在一个“完美多任务处理器”，能够以无限小的粒度同时运行所有进程。在实际物理 CPU 上，CFS 通过以下原则逼近这一理想：
- 公平性（Fairness）： 在时间窗口内，所有进程获得的实际 CPU 时间与其权重（nice 值）成正比。
- 低延迟（Low Latency）： 交互式进程（如编辑器、终端）应能快速获得响应，避免长时间饥饿。
- 高吞吐（High Throughput）： 计算密集型进程在长时间运行中仍能获得应有的 CPU 份额。
- 复杂度 O(log N)： 调度决策（选择下一个运行进程）的时间复杂度与系统中可运行进程数量 N 呈对数关系，保证大规模服务器场景下的可扩展性。
2.2 虚拟运行时间（vruntime）
vruntime 是 CFS 调度器的核心度量指标。它不是一个真实的墙上时钟时间，而是经过进程权重（优先级）加权后的“虚拟消耗时间”。
2.2.1 vruntime 的计算公式
每次时钟 tick 或进程状态切换时，内核会更新当前运行进程的 vruntime。其核心公式如下：
vruntime += delta_exec * (NICE_0_LOAD / se->load.weight)其中：
- delta_exec： 当前进程实际运行的物理时间（单位：ns）。
- NICE_0_LOAD： nice 值为 0 时的默认权重（内核定义为 1024）。
- se->load.weight： 当前进程的调度实体权重，由 nice 值映射而来。
从公式可以看出：
- 权重越高（nice 值越低，优先级越高），
load.weight越大，vruntime 增长越慢。 - 权重越低（nice 值越高，优先级越低），
load.weight越小，vruntime 增长越快。 - nice 值为 0 的进程，其 vruntime 增长速率等于物理时间速率。
2.2.2 nice 值与权重的映射关系
内核维护一个全局数组 sched_prio_to_weight[40]，将 -20 到 19 的 nice 值映射为权重。下表展示了部分映射关系：
| nice 值 | 权重（load.weight） | 相对 nice=0 的 CPU 占比 | vruntime 增长速率（相对物理时间） |
|---|---|---|---|
| -20 | 88761 | 约 86.7 倍 | 极慢（1/86.7） |
| -10 | 29216 | 约 28.5 倍 | 慢（1/28.5） |
| 0 | 1024 | 1 倍（基准） | 1:1 同步 |
| 10 | 36 | 约 0.035 倍 | 快（约 28.5 倍） |
| 19 | 15 | 约 0.015 倍 | 极快（约 68.3 倍） |
2.3 红黑树：CFS 的就绪队列数据结构
CFS 使用红黑树（Red-Black Tree）来组织每个 CPU 上所有可运行的调度实体（se）。红黑树是一种自平衡二叉查找树，其核心特性保证了 CFS 的高效性：
- 有序性： 所有节点按照 vruntime 排序，最左侧节点（最小值）即为当前最需要 CPU 的进程。
- 平衡性： 插入、删除、查找操作的时间复杂度均为 O(log N)，其中 N 为可运行进程数。
- 缓存友好： 红黑树的内存布局相对紧凑，有利于 CPU 缓存命中。
2.3.1 CFS 调度周期与红黑树操作流程
下图展示了 CFS 在一个调度周期内的核心操作流程：
2.3.2 红黑树在 CFS 中的具体实现
在 Linux 内核源码中，CFS 的红黑树实现位于 kernel/sched/fair.c 文件中。每个 CPU 有一个 struct cfs_rq 结构体，其中包含红黑树的根节点：
// 内核源码片段：struct cfs_rq 中的红黑树相关字段
struct cfs_rq {
struct load_weight load; // 该队列的总权重
unsigned int nr_running; // 可运行进程数
u64 min_vruntime; // 队列中最小的 vruntime（用于新进程初始化）
struct rb_root_cached tasks_timeline; // 红黑树根节点（带缓存最左节点）
struct sched_entity *curr; // 当前正在运行的调度实体
struct sched_entity *next; // 下一个将要运行的调度实体（抢占优化）
// ... 其他字段
};rb_root_cached 是内核提供的一种红黑树变体，它在标准红黑树基础上额外缓存了最左侧节点（即 vruntime 最小的节点）。这使得“选择下一个运行进程”的操作从 O(log N) 降为 O(1)，因为调度器只需读取缓存的最左节点即可，无需遍历整棵树。
2.4 CFS 调度实体的核心数据结构
每个进程或线程在内核中对应一个 struct sched_entity（调度实体），它是 CFS 管理的基本单元。以下是其关键字段：
| 字段名 | 类型 | 说明 |
|---|---|---|
load.weight |
unsigned long |
调度实体的权重，由 nice 值映射而来，决定 CPU 时间分配比例。 |
vruntime |
u64 |
虚拟运行时间，CFS 调度的核心排序依据。 |
run_node |
struct rb_node |
红黑树节点，用于将调度实体插入到 cfs_rq 的红黑树中。 |
on_rq |
int |
标记该实体是否在就绪队列上（1=在队列，0=不在）。 |
exec_start |
u64 |
当前运行片段的起始时间戳，用于计算 delta_exec。 |
sum_exec_runtime |
u64 |
该实体累计的总物理运行时间。 |
prev_sum_exec_runtime |
u64 |
上次切换出 CPU 时的累计运行时间，用于计算本次运行片段。 |
2.5 CFS 调度决策的完整过程
当调度器需要选择下一个运行进程时（例如在时钟中断、进程睡眠、yield 等场景），CFS 执行以下步骤：
- 更新当前进程的 vruntime： 根据公式
vruntime += delta_exec * (NICE_0_LOAD / load.weight)更新当前运行实体的 vruntime。 - 检查是否触发抢占： 比较当前进程的 vruntime 与红黑树最左节点的 vruntime。如果当前进程的 vruntime 大于最左节点，说明有更“饥饿”的进程等待运行，设置
TIF_NEED_RESCHED标志。 - 选择下一个进程： 在
pick_next_task_fair()函数中，从cfs_rq的红黑树中取出最左节点（vruntime 最小）作为下一个运行实体。 - 上下文切换： 执行
context_switch()，保存当前进程的寄存器状态，恢复新进程的寄存器状态，完成切换。 - 新进程开始运行： 新进程的
exec_start被设置为当前时间，开始累积其 vruntime。
struct task_group），拥有自己的 vruntime 和红黑树。这使得 CPU 带宽可以在 cgroup 之间按权重分配，而 cgroup 内部的进程再按 CFS 规则竞争。这是后续章节的核心基础。
2.6 CFS 与 O(1) 调度器的关键差异
| 对比维度 | O(1) 调度器（2.6.0-2.6.22） | CFS 调度器（2.6.23+） |
|---|---|---|
| 核心数据结构 | 140 个优先级链表（active/expired 数组） | 红黑树（按 vruntime 排序） |
| 时间片分配 | 固定时间片，基于优先级静态计算 | 动态时间片，基于 vruntime 和权重动态调整 |
| 交互式进程识别 | 启发式算法（睡眠时间、平均运行时间等） | 天然支持：交互式进程睡眠时间长，vruntime 小，唤醒后立即获得 CPU |
| 公平性 | 优先级高的进程可能长时间霸占 CPU | 严格按权重比例分配，vruntime 保证长期公平 |
| 复杂度 | O(1) 选择进程，但负载均衡复杂 | O(log N) 选择进程，但实际最左节点缓存为 O(1) |
| 组调度支持 | 需要额外补丁，不原生支持 | 原生支持，通过 struct task_group 实现层级调度 |