一、CFS的设计哲学：从“时间片”到“虚拟时间”
Linux 2.6.23 引入的完全公平调度器（Completely Fair Scheduler, CFS）是操作系统调度器设计的一个里程碑。在 CFS 之前，Linux 使用的是 O(1) 调度器，后者基于运行队列和优先级数组，通过静态时间片轮转实现调度。O(1) 调度器的局限在于：时间片固定、交互式进程识别 heuristic 复杂、公平性难以量化。
CFS 的核心思想很简单：不分配时间片，而是跟踪每个进程的虚拟运行时间（virtual runtime, vruntime），优先调度 vruntime 最小的进程。这个模型将“什么是公平”这个哲学问题转化为一个数学问题：如果有 N 个可运行进程，每个进程在理想多任务 CPU 上应该获得 1/N 的时间。vruntime 增长速率与进程权重（nice 值）成反比——高权重进程的 vruntime 增长更慢，从而获得更多实际 CPU 时间。
二、Virtual Runtime 的数学本质
vruntime 的计算公式看似简单，却蕴含精妙的设计：
delta_vruntime = (delta_exec * NICE_0_LOAD) / se.load.weight其中：
delta_exec：实际墙上时钟运行时间NICE_0_LOAD：nice 0 对应的权重值（1024）se.load.weight：该进程 sched_entity 的权重
这意味着：nice 0 进程的 vruntime 增长速率与实际时间相同；nice -5（更高优先级）进程的 vruntime 增长更慢，因此在红黑树中位置更靠左，被优先调度。
CFS 使用一个关键常数 sysctl_sched_min_granularity（默认 0.75ms）和 sysctl_sched_latency（默认 6ms）来确定：当可运行进程数 N 增大时，每个进程的最小时间片 = latency/N，但不低于 min_granularity。这保证了上下文切换开销不会随进程数增长而失控。
三、红黑树：为什么不是最小堆？
CFS 使用红黑树（Red-Black Tree）而非最小堆来组织可运行进程，原因在于调度操作的多样性需求：
| 操作 | 红黑树 O(log N) | 最小堆 O(log N) / O(N) |
|---|---|---|
| pick next（取最小） | O(1) 缓存 leftmost | O(1) 取堆顶 |
| enqueue（入队） | O(log N) | O(log N) |
| dequeue（出队） | O(log N) | O(log N) |
| delete（删除） | O(log N) 需查节点 | O(N) 需先查找 |
| update key（更新vruntime） | O(log N) 先删后插 | O(N) 需先定位 |
虽然最小堆的取最小值是 O(1)（配合 leftmost 缓存），但在进程唤醒、迁移、优先级变化等需要“定位特定节点”的场景下，红黑树的有序性使其能高效完成这些操作。此外，红黑树天然支持范围查询——在 select_task_rq 等路径中，可以快速找到满足条件的进程。
内核中红黑树的实现位于 kernel/sched/rbtree.c，每个 CPU 的运行队列（cfs_rq）维护一棵独立的红黑树，节点键值为 se.vruntime
四、pick_next_entity 与调度入口
当 CPU 需要选择下一个运行的进程时，调用链为：
schedule() → pick_next_task() → pick_next_task_fair() → pick_next_entity()pick_next_entity 直接取 cfs_rq.leftmost（红黑树最左节点），这是 O(1) 操作。leftmost 指针在每次 enqueue/dequeue 时维护，保证快速访问。
值得注意的是，CFS 并非总是调度同一进程。每次时钟中断（tick）更新当前进程的 vruntime 后，会检查 vruntime - cfs_rq.min_vruntime 是否超过当前进程的时间片。如果超过，设置 TIF_NEED_RESCHED 标志，在下一个调度点触发上下文切换。
五、组调度（CGroup）与层级公平
CFS 支持层级调度：用户组（task group）内部先按 CFS 公平分配，组间再按权重分配。每个 sched_entity 可以嵌套——顶层是 CPU 级别的 cfs_rq，下挂用户组级别的 se，再下挂进程级别的 se。
关键的计算发生在 account_entity_enqueue：当一个进程入队时，它贡献的负载会向上传播到所有父级 sched_entity。这使得 shares（组权重）机制可以在多级间精确分配 CPU 时间。
CPU 控制组（cpu cgroup）通过 cpu.cfs_quota_us 和 cpu.cfs_period_us 实现硬上限——当组内所有进程在一个周期内累计运行时间超过配额时，该组被节流（throttled），直到下一个周期。
六、NUMA 感知与负载均衡
在 NUMA 架构下，CFS 的负载均衡策略直接影响性能。sched_numa_balancing 通过以下机制优化内存局部性：
- 周期性内核扫描：扫描进程地址空间，标记未映射的页面（错位页面）
- 迁移决策：当错位页面比例超过阈值时，将进程迁移到离内存更近的节点
- Idle balance：当某个 CPU 进入 idle 时，主动从其他 CPU 拉取任务
在 kernel/sched/fair.c 中，task_numa_faults 和 numa_group.total_faults 跟踪页面错位率，决定了何时触发迁移。这种“先错后纠”的策略保证 NUMA 迁移不会过于激进。
七、CFS 的边界：不是纯“完全公平”
CFS 在实践中对纯模型做了几处调整：
- min_vruntime 偏移：新创建进程的 vruntime 初始化为
cfs_rq.min_vruntime（而非 0），避免新进程因 vruntime 过小而长时间占用 CPU，饿死老进程 - 唤醒抢占（wakeup_preempt）：被唤醒的进程如果 vruntime 远小于当前进程，会立即抢占。CFS 通过
sysctl_sched_wakeup_granularity控制抢占粒度，避免频繁切换 - cfs_bandwidth：组调度使用 HTB-like 的带宽控制器，
runtime、period、quota三个字段精确控制每个组的可用 CPU 时间
八、工程实践：如何观测 CFS 行为
理解和调优 CFS 需要正确的观测工具：
- perf sched：记录调度事件延迟，生成甘特图可视化调度序列
- /proc/[pid]/sched：显示 vruntime、sum_exec_runtime、nr_migrations 等 CFS 内部指标
- /sys/fs/cgroup/cpu/：cgroup CPU 控制参数实时可调
- sched_debug：debugfs 接口，显示每个 CPU runqueue 的详细状态
当发现系统响应缓慢时，可以调小 sched_min_granularity_ns 增加调度频率，或调大 sched_migration_cost_ns 减少不必要迁移。
九、总结
CFS 的成功在于将“公平”这一抽象概念具象化：vruntime 将时间度量归一化，红黑树提供高效的有序操作，层级组和 NUMA 感知扩展了公平性的维度。从 O(1) 调度器到 CFS 的演进，体现了操作系统设计从经验 heuristics 到可量化模型的范式转变。理解 CFS 不仅是理解一个算法，更是理解现代操作系统如何通过数据结构选择和数学抽象来解决复杂的资源分配问题。
发表评论 取消回复