3. CFS就绪队列：struct cfs_rq 结构体深度分析

完全公平调度器（CFS）的核心数据结构是 struct cfs_rq，它代表一个 CFS 就绪队列。每个 CPU 核心都拥有一个独立的 cfs_rq，用于管理该 CPU 上所有处于可运行状态的普通进程（非实时进程）。本章将深入剖析该结构体的关键字段，并揭示其与红黑树之间的紧密协作关系。

3.1 struct cfs_rq 核心字段一览

struct cfs_rq 定义在 kernel/sched/sched.h 中，其字段设计围绕“虚拟运行时”和“负载均衡”两大核心目标。下表列出了最关键的结构体成员：

3.2 min_vruntime：公平性的基准线

min_vruntime 是 CFS 调度器中最关键的变量。它代表了红黑树中所有可运行进程的“最小虚拟运行时间”。CFS 通过维护这个值，实现了以下核心逻辑：

• 进程选择： 调度器总是选择红黑树中最左节点（即 vruntime 最小的进程）作为下一个运行的进程。这等价于选择“受 CPU 优待最少”的进程。
• 新进程插入： 当新进程被创建或唤醒时，其 vruntime 会被初始化为 min_vruntime，而不是 0。这防止了新进程“插队”并获得不公平的 CPU 时间。
• 时钟中断更新： 每次时钟中断，当前运行进程的 vruntime 会增加。如果当前进程的 vruntime 超过了 min_vruntime，调度器会检查是否需要重新调度。

3.3 load 与 nr_running：队列的“重量”与“规模”

load 字段（类型 struct load_weight）包含了 weight 和 inv_weight 两个成员。它代表了整个就绪队列的“计算压力”：

• 权重累加： 每当一个进程进入就绪队列，其进程权重（由 nice 值决定）就会被累加到 load.weight 中。
• 调度周期计算： CFS 的调度延迟（sysctl_sched_latency）会根据 load.weight 和 nr_running 动态调整。进程越多，每个进程获得的时间片越短。
• 负载均衡： 在多 CPU 系统中，load 是判断 CPU 是否过载的核心指标，用于触发进程迁移。

3.4 curr 与 next：调度决策的“现在”与“未来”

curr 和 next 是两个指向 sched_entity 的指针，它们直接关联到调度器的决策路径：

• curr： 指向当前正在 CPU 上执行的进程的调度实体。在调度循环中，curr 用于更新其 vruntime 并检查是否需要被抢占。
• next： 指向红黑树中最左节点（即 __pick_first_entity() 的返回值）。在 pick_next_task_fair() 函数中，调度器直接返回 next 指向的进程。如果 next 与 curr 不同，则发生上下文切换。

3.5 红黑树与就绪队列的协作关系

红黑树（tasks_timeline）是 CFS 就绪队列的“骨架”。所有可运行进程的调度实体（struct sched_entity）都通过 run_node 节点挂载在这棵树上。树的关键字是 vruntime。

下图展示了 struct cfs_rq 与红黑树之间的核心关系：

3.6 关键操作：红黑树插入与 min_vruntime 更新

当一个进程被唤醒并加入就绪队列时，内核会执行以下关键步骤：

1. 初始化 vruntime： 新进程的 vruntime 被设置为 cfs_rq->min_vruntime，确保其不会落后于当前队列中的其他进程。
2. 红黑树插入： 调用 rb_add_augmented_cached() 函数，以 vruntime 为键值将调度实体插入红黑树。
3. 更新 min_vruntime： 如果新插入的节点成为新的最左节点，则 min_vruntime 会被更新为该节点的 vruntime。
4. 更新 next 指针： 如果新插入的节点 vruntime 小于当前 next 指向的节点，则 next 指针会指向新节点。

// 简化后的 enqueue_entity 核心逻辑
static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
    // 1. 更新调度统计信息
    update_curr(cfs_rq);

    // 2. 如果进程之前被 dequeue，恢复其 vruntime
    if (se->vruntime == 0)
        se->vruntime = cfs_rq->min_vruntime;

    // 3. 将调度实体插入红黑树
    __enqueue_entity(cfs_rq, se);

    // 4. 更新 cfs_rq 的统计字段
    cfs_rq->nr_running++;
    // ... 更新 load 权重 ...
}

3.7 总结：cfs_rq 的设计哲学

struct cfs_rq 的设计体现了 CFS 调度器的核心思想：

• 去中心化： 每个 CPU 拥有独立的 cfs_rq，避免了全局锁竞争，提高了多核扩展性。
• O(log N) 复杂度： 红黑树保证了进程的插入、删除和选择操作的时间复杂度为 O(log N)，其中 N 为就绪队列中的进程数。
• 公平性量化： min_vruntime 将抽象的“公平”概念量化为一个具体的数值，使得调度决策变得简单而高效。
• 缓存友好： next 指针和 curr 指针的设计减少了不必要的红黑树遍历，提升了调度器的性能。