4. 红黑树与就绪队列：红黑树数据结构、cfs_rq 结构体、min_vruntime 的作用

CFS 调度器的核心数据结构是 红黑树（Red-Black Tree） 和 cfs_rq（CFS Run Queue）。红黑树用于按 vruntime 排序所有可运行的任务，而 cfs_rq 则管理该队列的全局状态。理解这两个结构以及 min_vruntime 的作用，是定位 vruntime 异常和任务饥饿问题的基础。

4.1 红黑树数据结构

CFS 使用红黑树来维护就绪队列中的任务。红黑树是一种自平衡的二叉搜索树，其关键特性保证了调度器的高效性：

• 键值（Key）：每个节点的键值是任务的 vruntime。
• 排序规则：左子节点的 vruntime 小于父节点，右子节点的 vruntime 大于父节点。
• 最左节点：树中最左侧的节点（即 vruntime 最小的节点）是下一个被调度执行的任务。
• 时间复杂度：插入、删除和查找操作的时间复杂度均为 O(log n)，其中 n 是就绪队列中的任务数。

4.2 cfs_rq 结构体

cfs_rq 是每个 CPU 上的 CFS 就绪队列，它封装了红黑树以及管理该队列所需的所有元数据。以下是 cfs_rq 结构体的核心字段：

4.3 min_vruntime 的作用

min_vruntime 是 CFS 调度器中一个至关重要的全局变量。它代表了当前就绪队列中所有任务的最小 vruntime 值。其核心作用包括：

• 新任务归一化：当新任务创建时，其初始 vruntime 被设置为 min_vruntime，确保新任务不会因为 vruntime 过小（获得过多 CPU 时间）或过大（被延迟调度）而破坏公平性。
• 唤醒任务归一化：当任务从睡眠状态被唤醒时，其 vruntime 会被调整为 min_vruntime（或略大于它），以防止睡眠较久的任务在唤醒后立即抢占 CPU。
• 防止 vruntime 溢出：通过定期更新 min_vruntime，可以避免所有任务的 vruntime 无限增长，从而防止 64 位整数溢出。
• 公平性基准：所有任务的 vruntime 都相对于 min_vruntime 进行比较，确保调度器始终选择“最需要 CPU”的任务。

4.4 关键代码路径

以下代码展示了 CFS 如何从红黑树中选取下一个任务，以及 min_vruntime 在任务入队时的更新逻辑：

// 选取下一个任务（核心调度路径）
static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
{
    // 从红黑树缓存中直接获取最左节点（vruntime 最小的任务）
    struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline);
    if (!left)
        return NULL;
    return rb_entry(left, struct sched_entity, run_node);
}

// 任务入队时更新 min_vruntime
static void update_min_vruntime(struct cfs_rq *cfs_rq)
{
    u64 vruntime = cfs_rq->min_vruntime;
    struct sched_entity *curr = cfs_rq->curr;

    // 如果当前任务存在，考虑其 vruntime
    if (curr)
        vruntime = curr->vruntime;

    // 如果红黑树非空，考虑最左节点的 vruntime
    if (cfs_rq->nr_running) {
        struct sched_entity *se = __pick_next_entity(cfs_rq);
        if (se)
            vruntime = min(vruntime, se->vruntime);
    }

    // 更新 min_vruntime，确保其单调递增
    cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
}

4.5 红黑树与 cfs_rq 的协作关系

下表总结了红黑树和 cfs_rq 在 CFS 调度中的协作关系：