📚 课程目录第3章 CFS核心数据结构

3. CFS核心数据结构：红黑树与vruntime

完全公平调度器（CFS）的核心思想是“让每个进程都能公平地获得CPU时间”。为了实现这一目标，CFS摒弃了传统的时间片轮转和优先级队列，转而采用了一种基于虚拟运行时间（vruntime）的调度模型，并使用红黑树（rbtree）作为就绪队列的核心数据结构。

3.1 红黑树在CFS中的角色

红黑树是一种自平衡的二叉查找树，其插入、删除和查找的时间复杂度均为 O(log n)。在CFS中，红黑树被用作就绪队列（runqueue）的索引结构，用于快速选择下一个要运行的进程。

键值（Key）：每个调度实体（sched_entity）的 vruntime 作为红黑树的键值。
排序规则：树中所有节点的 vruntime 按照从小到大的顺序排列。最左侧的叶子节点（即 vruntime 最小的节点）就是下一个被调度执行的进程。
核心操作：当进程被唤醒或创建时，将其插入红黑树；当进程运行完毕或被抢占时，将其从树中删除；调度器通过查找最左节点来选取下一个进程。

设计思想：CFS 不直接分配时间片，而是通过 vruntime 来度量进程的运行进度。vruntime 越小的进程，表示它“欠”的CPU时间越多，因此越应该被优先调度。

    关键数据结构：struct sched_entity 是CFS调度的基本单位，它内嵌在 task_struct 中。其中 vruntime 字段是红黑树的排序依据，run_node 字段是红黑树的节点。

3.2 vruntime 虚拟运行时间概念

vruntime 是CFS调度器的核心度量指标，它表示一个进程在理想、公平的CPU上运行了多长时间。vruntime 不是真实的墙上时钟时间，而是经过权重（weight）加权后的虚拟时间。

vruntime 的设计哲学是：“让每个进程的 vruntime 尽可能相等”。当调度器选择下一个进程时，总是选择 vruntime 最小的进程，从而保证所有进程的虚拟运行时间趋于一致，实现“完全公平”。

3.3 vruntime 计算原理

vruntime 的计算涉及两个核心因素：实际运行时间和进程权重。其基本计算公式如下：

vruntime += delta_exec * (NICE_0_LOAD / se->load.weight)

其中：

delta_exec：进程本次实际运行的物理时间（单位：ns）。
NICE_0_LOAD：nice值为0时的标准权重（内核中定义为1024）。
se->load.weight：当前进程的权重，由进程的nice值决定。

重要理解：权重越大的进程（即优先级越高），其 se->load.weight 值越大，因此 NICE_0_LOAD / se->load.weight 比值越小，导致 vruntime 增长越慢。这意味着高优先级进程在相同物理时间内，其 vruntime 增长更慢，从而获得更多的CPU时间。

3.4 权重与nice值的映射关系

Linux内核维护了一个全局的权重表 sched_prio_to_weight[]，将nice值（-20 ~ 19）映射为对应的权重值。nice值每增加1，CPU时间减少约10%。

nice 值	权重 (weight)	vruntime 增长速率（相对nice=0）
-20	88761	极慢（约1.1%）
-10	2929	慢（约35%）
0	1024	基准（100%）
10	335	快（约306%）
19	15	极快（约6827%）

    示例计算：假设一个nice=0的进程运行了10ms，其vruntime增加10ms。而一个nice=-10的进程运行同样的10ms，其vruntime增加 10ms * (1024 / 2929) ≈ 3.5ms。因此，高优先级进程的vruntime增长更慢，在红黑树中更容易保持在左侧，从而获得更多调度机会。

3.5 核心代码实现

在CFS调度类中，update_curr() 函数负责更新当前进程的 vruntime。以下是关键代码片段：

// kernel/sched/fair.c
static void update_curr(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->curr;
    u64 now = rq_clock_task(rq_of(cfs_rq));
    u64 delta_exec;

    if (unlikely(!curr))
        return;

    // 计算本次实际运行时间
    delta_exec = now - curr->exec_start;
    if (unlikely((s64)delta_exec <= 0))
        return;

    curr->exec_start = now;

    // 核心：根据权重更新 vruntime
    curr->vruntime += calc_delta_fair(delta_exec, curr);
}

// 计算加权后的 vruntime 增量
static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
    if (unlikely(se->load.weight != NICE_0_LOAD))
        delta = __calc_delta(delta, NICE_0_LOAD, &se->load);

    return delta;
}

代码解读：calc_delta_fair() 函数实现了 vruntime 的加权计算。如果进程权重等于标准权重（nice=0），则直接返回 delta；否则调用 __calc_delta() 进行比例缩放，确保高权重进程的 vruntime 增长更慢。

3.6 红黑树操作与调度点

CFS调度器在以下关键点操作红黑树：

进程入队（enqueue_task_fair）：当进程变为可运行状态时，将其 sched_entity 插入红黑树。
进程出队（dequeue_task_fair）：当进程阻塞或退出时，将其从红黑树中移除。
调度选择（pick_next_task_fair）：从红黑树中查找最左节点，即 vruntime 最小的进程。
时钟中断（entity_tick）：周期性检查当前进程是否运行了足够长时间，是否需要被抢占。

    调度点总结：CFS 的调度决策完全基于红黑树和 vruntime。每次调度时，调度器只需找到树中最左侧的节点，即可确定下一个运行的进程。这种设计保证了 O(log n) 的调度效率，同时实现了公平性。

3.7 总结

CFS通过红黑树和vruntime实现了高效、公平的进程调度。红黑树提供了O(log n)的查找性能，而vruntime的加权计算机制确保了不同优先级的进程能够获得与其权重成比例的CPU时间。理解这两个核心概念，是掌握CFS调度器工作原理的关键。