Linux内核进程调度CFS算法与组调度配置案例 - 第4节

4.1 红黑树：CFS 调度器的核心数据结构

CFS（Completely Fair Scheduler）使用红黑树（Red-Black Tree）来组织就绪队列中的进程。红黑树是一种自平衡二叉搜索树，其插入、删除和查找操作的时间复杂度均为 O(log n)，能够高效地支持 CFS 对进程 vruntime 的排序与选择。

4.1.1 红黑树的 5 条基本性质

4.1.2 红黑树插入操作

红黑树的插入分为两个阶段：

1. BST 插入： 按照二叉搜索树规则，将新节点插入到合适位置，初始颜色设为红色。
2. 修复平衡： 通过旋转和颜色调整，恢复红黑树的 5 条性质。

插入修复的 3 种主要情况：

• 情况 1： 叔节点为红色 → 父节点和叔节点变黑，祖父节点变红，向上递归。
• 情况 2： 叔节点为黑色，且新节点是右子节点 → 左旋父节点，转为情况 3。
• 情况 3： 叔节点为黑色，且新节点是左子节点 → 右旋祖父节点，交换颜色。

4.2 __enqueue_entity 与 __dequeue_entity 实现

这两个函数是 CFS 操作红黑树的底层接口，负责将调度实体（sched_entity）插入或移除就绪队列的红黑树。

4.2.1 __enqueue_entity 实现

当进程变为可运行状态时，调用此函数将其加入红黑树：

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

    /* 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;
        }
    }

    /* 2. 插入节点并更新最左标记 */
    rb_link_node(&se->run_node, parent, link);
    rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);

    if (leftmost)
        cfs_rq->rb_leftmost = &se->run_node;
}

4.2.2 __dequeue_entity 实现

当进程被抢占或主动睡眠时，将其从红黑树中移除：

static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    /* 1. 如果移除的是最左节点，更新最左指针 */
    if (cfs_rq->rb_leftmost == &se->run_node) {
        struct rb_node *next = rb_next(&se->run_node);
        cfs_rq->rb_leftmost = next;
    }

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

4.3 最小 vruntime 节点获取

CFS 每次调度时，需要快速找到 vruntime 最小的进程。红黑树的最左侧节点即为目标。

4.3.1 获取方式

CFS 在 __pick_first_entity() 函数中优先使用 rb_leftmost 缓存：

struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
{
    struct rb_node *left = cfs_rq->rb_leftmost;

    if (!left)
        return NULL;

    return rb_entry(left, struct sched_entity, run_node);
}

4.4 红黑树操作与 CFS 调度流程整合

以下表格总结了红黑树操作在 CFS 调度周期中的位置：