3. CFS调度器设计哲学：完全公平概念、红黑树数据结构、虚拟运行时间(vruntime)核心机制
完全公平调度器（Completely Fair Scheduler, CFS）是Linux内核2.6.23版本引入的默认调度器，其设计哲学彻底颠覆了传统基于时间片和优先级的调度模型。CFS的核心目标是在真实硬件上模拟“理想、精确的多任务CPU”，确保每个可运行进程都能获得公平的CPU时间份额。
3.1 完全公平概念：从“时间片”到“CPU份额”
传统调度器为每个进程分配固定时间片，时间片耗尽则切换。CFS摒弃了这种“时间片”思维，转而采用CPU使用比例模型：
- 理想公平模型：假设存在一个完美的多任务CPU，能够同时运行所有进程，每个进程以1/N的速率（N为可运行进程数）推进其执行进度。
- 实际逼近：CFS通过记录每个进程的虚拟运行时间（vruntime），并始终选择vruntime最小的进程运行，从而在宏观上逼近理想公平。
- 权重（Weight）：通过
nice值映射的权重，允许某些进程获得不成比例的CPU份额。高权重进程的vruntime增长更慢，因此获得更多运行机会。
核心思想：CFS不关心“每个进程运行了多久”，而是关心“每个进程相对于其他进程，运行了多少”。vruntime是衡量这一相对进度的关键指标。
3.2 红黑树数据结构：高效的可运行队列
CFS使用红黑树（Red-Black Tree）来组织所有可运行进程（即处于TASK_RUNNING状态的进程）。红黑树是一种自平衡的二叉查找树，其特性完美契合CFS的调度需求：
- 键值：每个节点的键值为该进程的
vruntime。 - 最左节点：树中最左侧的节点（即vruntime最小的节点）就是下一个要被调度的进程。
- 插入与删除：进程状态变化（如被唤醒、被抢占）时，需要快速插入或删除节点。红黑树的插入、删除、查找操作的时间复杂度均为
O(log N)，其中N为可运行进程数。
为什么选择红黑树？
- 平衡性：保证最坏情况下的查找效率，避免退化为链表。
- 有序性：天然支持按vruntime排序，便于快速找到最小值。
- 非递归遍历：内核中常使用
rb_first()、rb_next()等宏进行非递归遍历，性能优异。
下图展示了CFS红黑树的结构与调度选择逻辑：
3.3 虚拟运行时间（vruntime）核心机制
vruntime是CFS调度器的灵魂，它不是一个简单的时钟计时器，而是一个经过权重归一化和调度周期补偿的虚拟时间度量。
3.3.1 vruntime的计算公式
vruntime += delta_exec * (NICE_0_LOAD / se->load.weight)其中：
delta_exec：进程实际运行的物理时间（纳秒级）。NICE_0_LOAD：nice值为0时的基准权重（内核中定义为1024）。se->load.weight：当前进程的调度实体权重，由nice值映射而来。
关键理解：权重越大的进程（nice值越小），其
se->load.weight越大，因此NICE_0_LOAD / weight比值越小，vruntime增长越慢。这意味着高权重进程在相同物理时间内，其vruntime增长更少，从而在红黑树中“落后”于其他进程，获得更多运行机会。
3.3.2 nice值与权重的映射关系
| nice值 | 权重（weight） | vruntime增长速率（相对nice=0） | CPU份额比例 |
|---|---|---|---|
| -20 | 88761 | 0.0115x | 约86.7x |
| -10 | 11051 | 0.0927x | 约10.8x |
| 0 | 1024 | 1.0x | 1.0x（基准） |
| 10 | 304 | 3.37x | 约0.3x |
| 19 | 15 | 68.27x | 约0.015x |
3.3.3 vruntime的修正与补偿
CFS在以下场景会对vruntime进行特殊处理，以保证公平性和响应性：
- 新进程唤醒：新创建的进程或从睡眠中唤醒的进程，其vruntime会被设置为当前红黑树中最左节点的vruntime（或略小），避免新进程因vruntime过小（初始为0）而长时间抢占CPU。
- 跨CPU迁移：进程被迁移到另一个CPU时，其vruntime会根据两个CPU的负载差异进行修正，防止迁移导致不公平。
- 睡眠补偿：长时间睡眠的进程被唤醒时，其vruntime会被“回拨”（设置得更小），使其能快速获得CPU，提升交互响应性。
- 调度周期限制：CFS通过
sysctl_sched_latency和sysctl_sched_min_granularity参数控制调度延迟，确保每个进程在合理时间内都能获得运行机会。
vruntime的物理意义：可以将其理解为“进程在理想公平CPU上应该消耗的时间”。实际运行时间通过权重缩放后，与理想时间进行比较，差值决定了进程在红黑树中的位置。
下图展示了vruntime在调度周期中的变化与调度决策流程：
3.4 关键数据结构与内核代码映射
CFS调度器在内核中的核心数据结构是struct sched_entity（调度实体），每个进程的task_struct中都包含一个该结构体实例：
// 调度实体（简化版）
struct sched_entity {
struct load_weight load; // 权重信息
struct rb_node run_node; // 红黑树节点
unsigned int on_rq; // 是否在可运行队列中
u64 vruntime; // 虚拟运行时间
u64 prev_sum_exec_runtime; // 上次统计的累计运行时间
// ... 其他字段
};
// 可运行队列（CFS就绪队列）
struct cfs_rq {
struct load_weight load; // 队列总负载
unsigned int nr_running; // 可运行进程数
u64 min_vruntime; // 队列中最小的vruntime
struct rb_root_cached tasks_timeline; // 红黑树根节点（含缓存）
// ... 其他字段
};
min_vruntime的作用：
cfs_rq->min_vruntime缓存了红黑树中最左节点的vruntime值，用于新进程唤醒时的vruntime初始化，以及跨CPU迁移时的修正计算，避免频繁遍历红黑树。
3.5 设计哲学总结
| 设计要素 | 传统调度器 | CFS调度器 |
|---|---|---|
| 时间模型 | 固定时间片 | CPU使用比例（权重归一化） |
| 数据结构 | 多级反馈队列、优先级数组 | 红黑树（按vruntime排序） |
| 公平度量 | 时间片耗尽次数 | 虚拟运行时间（vruntime） |
| 优先级实现 | 静态优先级、动态优先级调整 | nice值映射权重，影响vruntime增长速率 |
| 调度复杂度 | O(1)（查找优先级位图） | O(log N)（红黑树查找） |
| 交互响应 | 通过动态优先级提升 | 通过睡眠补偿和vruntime回拨 |
CFS的设计哲学可以概括为：用数学上的“公平”替代工程上的“时间片”，用树形结构替代队列结构，用虚拟时间替代物理时间。这种设计使得CFS在大多数负载下都能提供平滑、公平且响应迅速的调度体验，成为Linux内核调度器发展史上的里程碑。