1. CFS 调度器概述
完全公平调度器（Completely Fair Scheduler, CFS）是 Linux 内核自 2.6.23 版本引入的默认进程调度器。它摒弃了传统基于固定时间片和优先级计算的设计，转而采用基于虚拟运行时间（vruntime）的模型，为所有进程提供近似理想的 CPU 时间分配。
核心思想：CFS 不直接分配时间片，而是通过维护一个按 vruntime 排序的红黑树，每次选择 vruntime 最小的进程运行，从而在宏观上实现“完全公平”。
1.1 CFS 设计哲学
CFS 的设计哲学可以概括为“模拟理想多任务处理器”。在理想的多任务处理器中，所有可运行进程能够同时获得等比例的 CPU 时间。CFS 通过以下原则逼近这一理想状态：
- 公平性优先：确保每个进程在无限小的时间粒度上都能获得公平的 CPU 份额。
- 权重差异化：通过 nice 值调整进程权重，高权重进程获得更多 CPU 时间，但公平性模型依然成立。
- 低延迟交互：对 I/O 密集型或交互式进程进行补偿，减少调度延迟。
- 无固定时间片：不预设时间片长度，而是根据系统负载动态调整运行周期。
设计对比：传统 O(1) 调度器使用固定时间片和优先级数组，而 CFS 使用红黑树和 vruntime，时间复杂度从 O(1) 退化为 O(log n)，但换来了更好的公平性和交互体验。
1.2 虚拟运行时间（vruntime）概念
vruntime 是 CFS 调度器的核心度量指标。它表示一个进程在 CPU 上执行的“虚拟时间”，而非真实物理时间。vruntime 的计算公式如下：
vruntime += 实际运行时间 * (NICE_0_LOAD / 进程权重)其中 NICE_0_LOAD 是 nice 值为 0 时的基准权重（1024）。进程权重越高，vruntime 增长越慢，从而获得更多 CPU 时间。
| nice 值 | 权重 | vruntime 增长速率（相对 nice=0） | 典型场景 |
|---|---|---|---|
| -20 | 88761 | 极慢（约 1.15%） | 实时音频处理 |
| -10 | 11051 | 慢（约 9.27%） | 后台编译任务 |
| 0 | 1024 | 基准（100%） | 普通用户进程 |
| 10 | 335 | 快（约 305%） | 低优先级批处理 |
| 19 | 15 | 极快（约 6827%） | 空闲任务 |
注意：vruntime 不是单调递增的。当进程被唤醒、fork 或进行负载均衡时，内核可能会对 vruntime 进行修正（如减去最小 vruntime 或进行归一化），以防止新进程或唤醒进程被过度惩罚。
CFS 通过以下机制确保 vruntime 的公平性：
- 时钟中断：每次 tick 更新当前进程的 vruntime。
- 调度点：进程主动让出 CPU、睡眠、唤醒或创建新进程时检查是否需要重新调度。
- 最小 vruntime 跟踪：红黑树最左节点即为最小 vruntime 进程。
1.3 红黑树数据结构
CFS 使用红黑树（Red-Black Tree）来组织所有可运行进程。红黑树是一种自平衡二叉查找树，具有以下特性：
- 每个节点是红色或黑色。
- 根节点是黑色。
- 所有叶子节点（NIL）是黑色。
- 红色节点的子节点必须是黑色（不能有两个连续红色节点）。
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
在 CFS 中，红黑树的键值（key）是进程的 vruntime。调度器每次选择树中最左侧节点（即 vruntime 最小的进程）来运行。
红黑树在 CFS 中的操作流程如下：
- 插入：当进程变为可运行状态时，根据其 vruntime 插入红黑树。
- 选择：调度器从树中取出最左侧节点（最小 vruntime）作为下一个运行进程。
- 更新：进程运行后，vruntime 增加，可能被重新插入到树中更靠右的位置。
- 删除：进程退出或变为不可运行状态时，从树中移除。
性能优势：红黑树的所有操作（插入、删除、查找）时间复杂度均为 O(log n)，其中 n 为可运行进程数量。对于数千个进程的系统，这仍然非常高效。
CFS 红黑树在内核中的核心数据结构定义如下：
// 内核源码：kernel/sched/sched.h
struct cfs_rq {
struct load_weight load; // 当前队列的总负载
unsigned long nr_running; // 可运行进程数量
u64 min_vruntime; // 队列中的最小 vruntime
struct rb_root tasks_timeline; // 红黑树根节点
struct rb_node *rb_leftmost; // 最左侧节点（最小 vruntime）
struct sched_entity *curr; // 当前正在运行的调度实体
// ... 其他字段
};
struct sched_entity {
struct load_weight load; // 该实体的权重
struct rb_node run_node; // 红黑树节点
unsigned int on_rq; // 是否在运行队列中
u64 vruntime; // 虚拟运行时间
u64 exec_start; // 当前运行开始时间
// ... 其他字段
};通过 cfs_rq 结构体中的 tasks_timeline 红黑树和 rb_leftmost 指针，CFS 能够以 O(1) 的时间复杂度获取最小 vruntime 进程，并以 O(log n) 的时间复杂度完成插入和删除操作。