4. CFS 运行队列结构：cfs_rq 数据结构详解

CFS 调度器的核心数据结构是 cfs_rq（CFS Run Queue），它代表一个 CPU 上所有可运行的 CFS 调度类进程的集合。理解 cfs_rq 的内部结构，是掌握 CFS 调度行为的基础。

4.1 cfs_rq 核心字段解析

cfs_rq 结构体定义在 kernel/sched/sched.h 中，其关键字段如下表所示：

4.2 红黑树与 min_vruntime 维护

CFS 使用红黑树（Red-Black Tree）来组织调度实体，以 vruntime 作为键值。红黑树保证了插入、删除和查找操作的时间复杂度为 O(log N)。

min_vruntime 的更新机制：

• 时钟 tick 更新： 每次时钟中断时，如果当前进程是 CFS 调度类，会调用 update_curr() 更新当前进程的 vruntime，并尝试更新 cfs_rq->min_vruntime。
• 入队/出队更新： 当进程入队或出队时，会检查红黑树最左节点（即 vruntime 最小的节点）的 vruntime，并更新 min_vruntime。
• 防止回退： min_vruntime 是单调递增的，即使所有进程都出队，它也不会回退，而是会基于当前时间向前推进。

下图展示了红黑树与 min_vruntime 的关系：

4.3 调度实体入队操作：enqueue_task_fair

当一个进程变为可运行状态（如被唤醒、fork 后首次运行）时，会触发入队操作。核心流程如下：

1. 更新负载： 调用 update_load_add() 将进程的权重加到 cfs_rq->load 上。
2. 更新统计： 调用 update_curr() 更新当前进程的 vruntime，并维护 cfs_rq->min_vruntime。
3. 设置 vruntime： 对于新进程，其 vruntime 会被设置为 max(min_vruntime, se->vruntime)，防止“插队”行为。
4. 插入红黑树： 调用 __enqueue_entity() 将调度实体插入红黑树，键值为 se->vruntime。
5. 更新 min_vruntime： 如果新插入的实体位于红黑树最左端，则更新 min_vruntime。
6. 检查抢占： 如果新入队的实体 vruntime 小于当前运行实体的 vruntime，则设置 TIF_NEED_RESCHED 标志，触发调度。

4.4 调度实体出队操作：dequeue_task_fair

当一个进程不再可运行（如主动睡眠、被杀死）时，会触发以下出队流程：

1. 更新负载： 调用 update_load_sub() 从 cfs_rq->load 中减去进程权重。
2. 更新统计： 调用 update_curr() 记录进程的最后一次运行时间。
3. 从红黑树移除： 调用 __dequeue_entity() 从红黑树中删除该调度实体。
4. 更新 min_vruntime： 如果被移除的实体是红黑树最左节点，则需要重新查找新的最左节点并更新 min_vruntime。
5. 处理 cgroup 层级： 如果该实体是一个 task group，还需要递归地从父 cfs_rq 中出队。

下表总结了入队与出队操作的关键差异：

4.5 入队/出队操作流程图

下图展示了 CFS 调度实体入队和出队的完整流程：

4.6 关键代码片段

以下是 __enqueue_entity() 和 __dequeue_entity() 的核心逻辑：

// 内核源码: kernel/sched/fair.c

static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node;
    struct rb_node *parent = NULL;
    struct sched_entity *entry;
    int leftmost = 1;

    // 红黑树查找插入位置
    while (*link) {
        parent = *link;
        entry = rb_entry(parent, struct sched_entity, run_node);
        if (entity_before(se, entry)) {
            link = &parent->rb_left;
        } else {
            link = &parent->rb_right;
            leftmost = 0;
        }
    }

    // 插入节点
    rb_link_node(&se->run_node, parent, link);
    rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline.rb_root);

    // 更新最左节点缓存
    if (leftmost)
        cfs_rq->tasks_timeline.rb_leftmost = &se->run_node;
}

static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    // 如果删除的是最左节点，需要更新缓存
    if (cfs_rq->tasks_timeline.rb_leftmost == &se->run_node) {
        struct rb_node *next_node;

        next_node = rb_next(&se->run_node);
        cfs_rq->tasks_timeline.rb_leftmost = next_node;
    }

    // 从红黑树中删除
    rb_erase(&se->run_node, &cfs_rq->tasks_timeline.rb_root);
}