引言
Linux 内核的进程调度器是操作系统最核心的组件之一，它决定了哪个进程获得 CPU 时间、何时获得、获得多久。自 2.6.23 内核起，CFS（Completely Fair Scheduler，完全公平调度器）取代了之前的 O(1) 调度器，成为 Linux 默认的进程调度器。CFS 的设计理念优雅而深刻：它不直接分配时间片，而是让每个进程追求一个共同的虚拟时间——vruntime，并通过红黑树高效地选出 vruntime 最小的进程运行。本文将从数学原理出发，深入剖析 CFS 的每一个核心机制。
1. 从理想多处理器说起
CFS 的设计灵感来自于一个理想化的模型：假设你有 N 个相同优先级的进程运行在单核 CPU 上，那么在理想情况下，每个进程应该获得 1/N 的 CPU 时间。这就是"完全公平"的含义。在真实硬件中，这种理想状态无法精确达到——CPU 处理的是离散的时钟中断，进程切换有其固有开销。CFS 的目标是无限逼近这个理想状态。
这个理想模型有一个精妙的推论：我们不需要给每个进程分配固定的时间片，只需要追踪每个进程已经消耗了多少 CPU 时间，优先调度消耗最少的那个。这就是 vruntime 的出发点。
2. vruntime：虚拟运行时间的数学模型
vruntime（virtual runtime）是 CFS 的核心数据结构，记录在 sched_entity 结构体的 vruntime 字段中。它的更新公式是：
实际运行时间(vruntime) += 实际运行时间 × (NICE_0_LOAD / 进程权重)其中 NICE_0_LOAD 是 nice 值 0 对应的标准权重（值为 1024）。
2.1 Nice 值与权重的映射关系
Linux 内核定义了一个权重映射表 sched_prio_to_weight[40]，覆盖 nice 值 -20 到 +19 的范围。相邻两个 nice 级的权重比约为 1.25 倍，这意味着：
- nice 0 的权重为 1024
- nice +1 的权重约为 820（进程 vruntime 增长更快，相当于获得更少 CPU）
- nice -1 的权重约为 1275（进程 vruntime 增长更慢，相当于获得更多 CPU）
数学上，这种设计保证了在一个调度周期内，不同 nice 值的进程实际运行时间之比等于它们的权重之比：time_A / time_B = weight_A / weight_B。
2.2 为什么用除法而不用乘法
vruntime 的计算可以等价为 vruntime += 实际运行时间 × 1024 / 权重。对于高权重（低 nice 值）的进程，它们实际运行同样时间后 vruntime 增长得更慢，因此在红黑树中位置更靠左，会被更频繁地调度——这正是高优先级应该获得更多 CPU 时间的体现。
3. 红黑树：高效维护调度队列
CFS 使用红黑树（Red-Black Tree）来维护所有可运行进程的调度队列，以 vruntime 作为排序键。红黑树是一种自平衡二叉搜索树，CFS 选择它的关键原因是：
- 插入/删除操作 O(log N) 复杂度
- 可以快速找到最小 vruntime 的节点（最左节点）
- 相比堆（优先队列），支持高效的节点删除与重新插入
3.1 调度队列结构
每个 CPU 运行队列（cfs_rq）维护一个红黑树：
struct cfs_rq {
struct rb_root_cached tasks_timeline; // 红黑树根节点（带缓存的最左节点）
struct sched_entity *curr; // 当前正在运行的调度实体
struct sched_entity *next; // 抢占时快速切换的下一个
struct sched_entity *last; // 上次执行的实体（用于唤醒抢占）
unsigned int nr_running; // 可运行进程数
...
};红黑树带了一个 rb_leftmost 缓存指针，指向最左节点，这样选取下一个要运行的进程时无需遍历树——直接 O(1) 获取。
3.2 pick_next_entity：选择下一个进程
当调度器需要选择下一个运行的实体时，内核调用 pick_next_entity()：
struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq) {
struct sched_entity *left = __pick_first_entity(cfs_rq);
struct sched_entity *se = left;
// 如果 left 是 group 调度实体，可能跳过而选第二个
if (cfs_rq->skip == left)
se = __pick_next_entity(left);
// 不选 kernel thread（如果有的话被跳过）
// 返回选中的实体
return se;
}4. 调度延迟与最小粒度
CFS 有两个关键参数控制调度的"粒度"，它们在 kernel/sched/fair.c 中定义：
sysctl_sched_latency（默认 6ms）：目标调度周期，即所有可运行进程轮流运行一遍的目标时间。sysctl_sched_min_granularity（默认 0.75ms）：最小调度粒度，一个进程至少运行这么长时间才能被抢占。
调度周期的实际计算公式为：
sched_period = max(sysctl_sched_latency,
nr_running × sysctl_sched_min_granularity)当可运行进程较少时（比如 2-3 个），周期等于 sysctl_sched_latency（6ms），每个进程分到 3ms 或 2ms；当进程很多时（比如 10 个），周期被拉长为 10 × 0.75ms = 7.5ms。
这种设计在公平性和切换开销之间取得了平衡：进程少时保证低延迟，进程多时避免频繁切换带来的缓存污染。
5. 进程的生命周期：创建与就绪
5.1 新进程的 vruntime 初始化
当一个新进程通过 fork() 创建时，task_fork_fair() 负责初始化其 vruntime。关键点在于"补偿策略"：新进程的 vruntime 被设置为当前 cfs_rq 的 min_vruntime，而不是 0。这防止了新创建进程因 vruntime 为 0 而长时间霸占 CPU——也防止了 fork 炸弹式的攻击。
// 新进程的 vruntime 初始化为 min_vruntime
se->vruntime = cfs_rq->min_vruntime;5.2 入队操作：enqueue_entity
当进程变为可运行状态时，enqueue_entity() 将其插入红黑树：
void enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) {
bool renorm = !(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATED);
bool curr = cfs_rq->curr == se;
// 规范化 vruntime（确保新入队的进程不会过旧或过新）
if (renorm)
se->vruntime += cfs_rq->min_vruntime;
update_curr(cfs_rq);
// 将实体插入红黑树
enqueue_entity_load_avg(cfs_rq, se);
account_entity_enqueue(cfs_rq, se);
if (flags & ENQUEUE_WAKEUP)
place_entity(cfs_rq, se, 0); // 唤醒补偿
// 插入到红黑树中
__enqueue_entity(cfs_rq, se);
}5.3 place_entity：唤醒补偿
一个阻塞等待 I/O 的进程被唤醒时，它的 vruntime 可能远小于活跃进程，因为它在阻塞期间没有累加 vruntime。如果不加处理，它会"骗过" CFS 获得不成比例的 CPU 时间。place_entity() 解决了这个问题：vruntime = max(vruntime, min_vruntime - sysctl_sched_latency)。同时，为了照顾交互式进程，新唤醒的进程获得一定的"初始信用"：
// 首次唤醒时给予起点补偿，促进交互式进程响应
if (initial && sched_feat(START_DEBIT))
vslice = sched_vslice(cfs_rq, se);
se->vruntime = max_vruntime(se->vruntime, cfs_rq->min_vruntime - vslice);6. 负载均衡：多核调度
在多核系统中，CFS 还需要解决 CPU 间负载不均的问题。调度域（sched_domain）构成一个拓扑结构，从 SMT 线程级 → 物理核心级 → NUMA 节点级逐级向上。负载均衡在空闲平衡（idle balance）、周期性平衡（periodic balance）和新 idle 平衡三种模式下触发。
6.1 调度域层次
// x86_64 典型的调度域拓扑：
MC 域（Multi-Core）：包含同一物理 CPU 的 SMT 线程
DIE 域：包含同一 Die 上的所有物理核心
NUMA 域：包含同一 NUMA 节点上的所有核心
从最底层开始，逐层向上进行负载均衡。这样既利用了共享缓存（SMT 间迁移代价低），又控制了跨 NUMA 迁移的开销。
6.2 can_migrate_task：迁移可行性检查
不是所有进程都可以迁移到任意 CPU。CFS 进行以下检查：进程最近是否访问过目标 CPU 的数据（缓存亲和性）、cpuset 限制、缓存热度等。频繁迁移会导致缓存失效，反而降低性能。
6.3 不均衡检测
周期性负载均衡通过 update_sd_lb_stats() 收集调度组的统计数据，然后判断本地组与最忙组的负载差是否超过阈值（sd->imbalance_pct，默认为 125）。这意味着只有当负载差超过 ~25% 时才会触发迁移，避免不必要的进程移动。
7. 组调度（Group Scheduling）
CFS 支持基于 cgroup 的组调度，使得资源的"公平"不仅体现在进程粒度，还可以体现为用户/组粒度。sched_entity 可以表示一个进程或一个调度组，调度组的 entity 在更高层的 cfs_rq 中与其他用户竞争，在其内部再以同样的 CFS 算法分配给组内进程。
struct sched_entity {
struct load_weight load; // 权重
struct run_node run_node; // 红黑树节点
struct cfs_rq *cfs_rq; // 所属于的 cfs_rq
struct cfs_rq *my_q; // 组调度实体才有自己的 cfs_rq
...
};当 se->my_q 不为 NULL 时，表示它是一个组调度实体。CFS 先在高层次上决定哪个组获得 CPU，再在组内选择一个进程运行——完美递归。
8. CFS 与实时调度器的交互
Linux 的调度类（sched_class）按优先级排列：SCHED_FIFO/SCHED_RR > SCHED_NORMAL (CFS) > SCHED_IDLE。这意味着：
- 实时进程总是在普通进程之前被调度
- 高优先级的实时进程先于低优先级的实时进程
- CFS 完全不会运行，直到所有实时进程都不处于可运行状态
当实时进程耗尽其时间片或被更高优先级进程抢占时，CFS 才获得执行机会。这种严格的优先级层次保证了实时系统的确定性延迟。
9. 关键调优参数
| 参数 | 默认值 | 说明 |
|---|---|---|
| sched_latency_ns | 6,000,000 ns | 目标调度周期 |
| sched_min_granularity_ns | 750,000 ns | 最小时间片 |
| sched_wakeup_granularity_ns | 1,000,000 ns | 唤醒抢占粒度 |
| sched_migration_cost_ns | 500,000 ns | 进程迁移的最小"热度"时间 |
| sched_nr_migrate | 32 | 负载均衡时的最大迁移进程数 |
调优建议：桌面/交互式场景可以适当降低 sched_latency_ns 以提高响应速度；服务器/HPC场景可以提高该值以降低调度开销。
10. 观测与调试
如何观察 CFS 的实际行为？
cat /proc/<pid>/sched：查看进程的 vruntime、vruntime 起始值、最小 vruntime、权重等信息perf sched record / perf sched latency：录制并分析调度延迟trace-cmd record -e sched_switch：追踪具体的上下文切换事件/proc/sys/kernel/sched_*：运行时调整调度参数bpftrace -e "tracepoint:sched:sched_switch { @[comm] = count(); }"：用 eBPF 实时统计调度切换频次
总结
CFS 的设计之美在于它的简洁：一个数学模型（vruntime）、一种数据结构（红黑树）、一组调优参数，就解决了通用操作系统的进程调度问题。它没有显式的优先级队列，没有传统意义上的"时间片"，却通过 vruntime 的平滑推进和公平补偿机制，实现了对 CPU 时间精确的按比例分配。理解 CFS，不仅是理解 Linux 内核的一个核心子系统，更是理解如何在工程实践中用优雅的设计解决复杂问题的一个经典范例。
发表评论 取消回复