Linux内核调度器性能调优：CFS与实时调度策略 - 第4节

4.1 完全公平调度器的设计哲学

CFS（Completely Fair Scheduler）是 Linux 内核默认的调度器，其核心设计哲学是：在理想的多任务处理器上，每个进程应获得完全相等的 CPU 时间片。CFS 摒弃了传统固定时间片和优先级队列的设计，转而采用基于虚拟运行时间（vruntime）的公平分配模型。

4.1.1 从“时间片”到“权重比例”

传统调度器为每个进程分配固定时间片，优先级高的进程获得更长的时间片。CFS 则引入权重（weight）概念：每个进程的优先级（nice 值）对应一个权重，权重越高，进程在单位时间内获得的 CPU 时间比例越大。CFS 的目标是让所有进程的 vruntime 尽可能相等。

4.2 虚拟运行时间（vruntime）

vruntime 是 CFS 的核心度量指标，它表示一个进程在理想 CPU 上运行的时间。实际运行时间会根据进程权重进行加权换算，公式如下：

vruntime += 实际运行时间 * (NICE_0_LOAD / 进程权重)

其中 NICE_0_LOAD 是 nice 值为 0 时的标准权重（1024）。权重越高的进程，其 vruntime 增长越慢，从而获得更多 CPU 时间。

4.2.1 vruntime 的关键特性

• 单调递增：vruntime 只增不减，确保调度器始终选择“最饥饿”的进程。
• 权重感知：高优先级（低 nice 值）进程的 vruntime 增长慢，低优先级进程增长快。
• 睡眠补偿：进程睡眠时 vruntime 保持不变，唤醒后因其 vruntime 较小，会优先获得 CPU。

4.3 红黑树（Red-Black Tree）数据结构

CFS 使用红黑树来组织所有可运行的进程，以 vruntime 作为键值。红黑树是一种自平衡二叉查找树，具有以下特性：

• 节点颜色：每个节点为红色或黑色。
• 根节点为黑色。
• 红色节点的子节点必须为黑色（不能有连续红色节点）。
• 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些特性保证了红黑树的最坏情况查找、插入、删除操作时间复杂度均为 O(log n)，其中 n 为可运行进程数。

4.3.1 红黑树在 CFS 中的角色

4.4 CFS 调度流程

CFS 的调度周期由 schedule() 函数触发，核心流程如下：

1. 选择下一个进程：从红黑树中查找 vruntime 最小的节点（最左节点）。
2. 上下文切换：保存当前进程状态，恢复目标进程状态。
3. 运行进程：进程在 CPU 上执行，同时更新其 vruntime。
4. 时钟中断处理：每次时钟中断检查当前进程是否应该被抢占。
5. 重新入队：如果进程被抢占或主动让出 CPU，将其重新插入红黑树。

4.4.1 抢占决策

CFS 通过比较当前进程的 vruntime 与红黑树中最左节点的 vruntime 来决定是否抢占：

if (当前进程的 vruntime > 最左节点的 vruntime + 调度粒度)
    触发抢占，调度最左节点运行

调度粒度（sysctl_sched_min_granularity）默认为 0.75ms，防止过于频繁的上下文切换。

4.5 权重与优先级映射

Linux 的 nice 值范围是 -20 到 19，对应 40 个优先级级别。CFS 将 nice 值映射为权重，权重决定了进程的 CPU 时间分配比例。

权重表定义在 kernel/sched/core.c 中的 sched_prio_to_weight 数组，每个 nice 值对应一个权重值，相邻 nice 值之间的权重比例约为 1.25。

4.6 CFS 与实时调度策略的对比

CFS 是普通进程的默认调度器，而实时进程使用 SCHED_FIFO 或 SCHED_RR 策略。两者在调度行为上有本质区别：

4.7 总结