2、CFS设计哲学：完全公平调度的数学原理、红黑树与虚拟运行时间的关系

完全公平调度器（CFS）的核心思想并非追求绝对的“同时运行”，而是确保每个进程在无限小的时间尺度上获得相等的CPU时间份额。这一哲学通过“虚拟运行时间”（vruntime）与红黑树的数据结构得以精确实现。

2.1 完全公平的数学原理：理想模型与加权逼近

CFS的数学基础建立在“理想多任务处理器”模型之上。假设系统中有N个可运行进程，在任意无限小的时间间隔内，每个进程都应获得1/N的CPU时间。然而，物理CPU只能串行执行指令，因此CFS通过虚拟运行时间来逼近这一理想状态。

核心公式：

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

其中，NICE_0_LOAD 是nice值为0时的基准权重（1024），进程权重由nice值映射表决定。该公式的数学意义在于：将不同优先级的进程“归一化”到同一时间尺度。权重越高的进程，其实际运行时间在vruntime中的“折扣”越大，从而在红黑树中保持靠左的位置，获得更多CPU时间。

2.2 红黑树：vruntime的排序与查找结构

CFS使用红黑树（Red-Black Tree）来组织所有可运行进程，其排序键值就是进程的vruntime。红黑树是一种自平衡二叉查找树，保证插入、删除和查找操作的时间复杂度为O(log N)。

红黑树在CFS中的角色：

• 左节点： vruntime 较小的进程（更饥饿，应优先调度）。
• 右节点： vruntime 较大的进程（已获得较多CPU时间）。
• 根节点： 始终是vruntime最小的进程（__pick_first_entity 直接返回最左节点）。

红黑树与vruntime的关系表：

2.3 虚拟运行时间与红黑树的动态交互

vruntime并非静态值，它在进程运行、睡眠、被唤醒等事件中持续更新。红黑树也随之动态调整，以维护“完全公平”的秩序。

交互流程：

1. 时钟中断触发： 更新当前进程的vruntime（增加实际运行时间折算后的值）。
2. 检查是否需要抢占： 如果当前进程的vruntime超过了红黑树最左节点的vruntime，则设置抢占标志。
3. 进程出队： 当前进程被换出时，从红黑树中删除其节点。
4. 进程入队： 被唤醒或新创建的进程，根据其vruntime插入红黑树适当位置。
5. 调度选择： 调度器直接选取红黑树最左节点作为下一个运行进程。

2.4 CFS调度核心架构图

下图展示了CFS调度器的核心组件及其与vruntime、红黑树的关系：

2.5 完全公平的数学证明与权重映射

CFS的公平性可以通过数学归纳法理解：假设在时间T内，进程i和进程j分别获得了实际运行时间t_i和t_j。根据vruntime公式，它们的虚拟运行时间分别为：

vruntime_i = t_i × (1024 / weight_i)
vruntime_j = t_j × (1024 / weight_j)

当系统达到完全公平状态时，所有进程的vruntime应相等：

vruntime_i = vruntime_j
⇒ t_i / weight_i = t_j / weight_j
⇒ t_i : t_j = weight_i : weight_j

这意味着，进程获得的CPU时间比例严格等于其权重比例。这正是CFS“完全公平”的数学本质。

nice值与权重映射表（部分）：