4. CFS调度算法核心

完全公平调度器（CFS）的核心逻辑集中在两个关键函数：pick_next_task_fair 和 put_prev_task_fair。前者负责从红黑树中选出下一个最值得运行的进程，后者负责将当前被抢占或主动让出CPU的进程放回红黑树。这两个函数共同维护了CFS“红黑树+虚拟运行时间”的调度模型。

4.1 核心数据结构：CFS就绪队列与红黑树

每个CPU都有一个独立的CFS就绪队列 struct cfs_rq，其中包含红黑树的根节点、最小虚拟运行时间缓存等关键字段。

4.2 pick_next_task_fair：从红黑树选择下一个进程

当调度器决定进行进程切换时，会调用 pick_next_task_fair。该函数的核心逻辑是：从CFS就绪队列的红黑树中取出最左节点（vruntime最小的进程），并更新调度器状态。

// 简化后的核心逻辑（kernel/sched/fair.c）
static struct task_struct *
pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct sched_entity *se;
    struct task_struct *p;

    if (!cfs_rq->nr_running)
        goto idle;  // 队列为空，返回idle

    // 1. 从红黑树缓存中获取最左节点
    se = pick_next_entity(cfs_rq, NULL);

    // 2. 设置当前运行的调度实体
    set_next_entity(cfs_rq, se);

    // 3. 从调度实体获取task_struct
    p = task_of(se);
    return p;

idle:
    // 返回idle进程
    return idle_sched_class.pick_next_task(rq, prev, rf);
}

// pick_next_entity 内部实现
static struct sched_entity *
pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    // 直接从缓存获取最左节点
    struct rb_node *left = cfs_rq->tasks_timeline.rb_leftmost;
    if (!left)
        return NULL;

    // 返回最左节点对应的调度实体
    return rb_entry(left, struct sched_entity, run_node);
}

4.3 put_prev_task_fair：将当前进程放回红黑树

当当前进程被抢占或主动让出CPU时，调度器调用 put_prev_task_fair 将其放回CFS就绪队列。该函数的核心任务是：更新进程的虚拟运行时间，并将其重新插入红黑树。

// 简化后的核心逻辑（kernel/sched/fair.c）
static void put_prev_task_fair(struct rq *rq, struct task_struct *prev)
{
    struct sched_entity *se = &prev->se;
    struct cfs_rq *cfs_rq = cfs_rq_of(se);

    // 1. 更新当前进程的虚拟运行时间
    update_curr(cfs_rq);

    // 2. 如果进程仍然可运行，重新插入红黑树
    if (se->on_rq) {
        // 更新红黑树中的位置（可能删除再插入）
        __enqueue_entity(cfs_rq, se);
        // 更新cfs_rq的min_vruntime
        update_min_vruntime(cfs_rq);
    }

    // 3. 清除当前运行实体指针
    cfs_rq->curr = NULL;
}

// update_curr 核心：计算delta_exec并更新vruntime
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;

    // 更新exec_start为当前时间
    curr->exec_start = now;

    // 根据权重计算虚拟运行时间增量
    curr->vruntime += calc_delta_fair(delta_exec, curr);
    // 更新cfs_rq的min_vruntime
    update_min_vruntime(cfs_rq);
}

4.4 虚拟运行时间计算与红黑树插入

CFS的核心创新在于使用虚拟运行时间（vruntime）来衡量进程的“公平性”。calc_delta_fair 函数将实际运行时间按进程权重进行归一化，权重越高的进程，其vruntime增长越慢，从而获得更多的CPU时间。

// 虚拟运行时间计算（简化）
static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
    // NICE_0_LOAD = 1024（nice=0的权重）
    if (unlikely(se->load.weight != NICE_0_LOAD))
        // 按权重比例缩放：delta * NICE_0_LOAD / weight
        delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
    return delta;
}

// 红黑树插入操作
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;

    // 查找插入位置（按vruntime排序）
    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_cached(&se->run_node,
                           &cfs_rq->tasks_timeline, leftmost);
}

4.5 调度实体与红黑树节点的关系

每个进程的调度实体 struct sched_entity 内嵌了一个 struct rb_node，用于将进程链接到CFS就绪队列的红黑树中。通过 container_of 宏，内核可以在调度实体和进程描述符之间自由转换。

// 调度实体结构（简化）
struct sched_entity {
    struct load_weight      load;           // 调度权重
    struct rb_node          run_node;       // 红黑树节点
    struct list_head        group_node;     // 用于组调度
    unsigned int            on_rq;          // 是否在就绪队列中
    u64                     exec_start;     // 当前运行开始时间
    u64                     sum_exec_runtime;// 总运行时间
    u64                     vruntime;       // 虚拟运行时间
    u64                     prev_sum_exec_runtime; // 上次切换时的总运行时间
    struct sched_entity     *parent;        // 父调度实体（组调度）
    struct cfs_rq           *cfs_rq;        // 所属CFS就绪队列
};

// 从调度实体获取进程描述符
static inline struct task_struct *task_of(struct sched_entity *se)
{
    return container_of(se, struct task_struct, se);
}

4.6 总结：CFS选择机制的核心优势

• O(1)选择时间：通过缓存最左节点，pick_next_task_fair 可以在常数时间内找到下一个进程。
• 公平性保证：红黑树按vruntime排序，确保vruntime最小的进程总是被优先选择，实现完全公平。
• 权重感知：通过 calc_delta_fair 将实际运行时间按权重缩放，高权重进程获得更多CPU时间。
• 低开销维护：红黑树的插入和删除操作虽然为O(log n)，但实际系统中进程数量有限，开销可忽略。