Linux内核·调度】一个线程从就绪到拿到CPU要等多久——CFS调度器的 pick_next_task_fair

久爱不腻007

4人浏览 · 2026-07-31 14:22:56

久爱不腻007 · 2026-07-31 14:22:56 发布

你写了一个多线程服务，跑在 8 核的机器上。某天你用 perf sched latency 抓了一下调度延迟，发现有些线程从被唤醒到真正跑起来，中间等了 20 毫秒。

20 毫秒。对一个声称"完全公平"的调度器来说，这个数字合理吗？

要回答这个问题，光看文档不够。得钻进内核源码，从 __schedule() 开始，一路追到 pick_next_task_fair()，看清楚调度器到底是怎么从一堆等待的线程里挑出下一个幸运儿的。

这篇文章基于 Linux 6.1 内核源码（kernel/sched/fair.c），追踪一个线程从就绪队列到获得 CPU 执行权的完整路径。读完你会清楚三件事：

1.CFS 用什么数据结构管理就绪线程，为什么选红黑树不选堆

2.pick_next_task_fair 里的选择逻辑远不是"取最左节点"那么简单——skip、next、last 三个 buddy 指针各有用途

3.vruntime 的计算公式和权重表是怎么在源码里落地的，nice 值到底怎么影响你的线程被选中的概率

先看全景：__schedule() 到底在哪里调了 CFS

所有调度行为的起点都是 __schedule()。不管是时间片用完、线程主动让出 CPU、还是被更高优先级的任务抢占，最终都会走到这个函数。它在 kernel/sched/core.c 里，核心逻辑精简下来就是这几步：

// kernel/sched/core.c (简化)
static void __sched notrace __schedule(unsigned int sched_mode)
{
    struct task_struct *prev, *next;
    struct rq *rq;

    rq = cpu_rq(smp_processor_id());  // 拿到当前CPU的运行队列
    prev = rq->curr;                   // 当前正在跑的任务

    // ... 更新prev的状态，处理信号等 ...

    next = pick_next_task(rq, prev, &rf);  // 关键：选下一个任务

    if (likely(prev != next)) {
        context_switch(rq, prev, next, &rf);  // 上下文切换
    }
}

这段代码的核心就一个调用：pick_next_task()。这个函数会按优先级从高到低遍历所有调度类：stop_sched_class → dl_sched_class → rt_sched_class → fair_sched_class → idle_sched_class。CFS 对应的是 fair_sched_class，它的 .pick_next_task 回调指向的就是我们要追踪的 __pick_next_task_fair。

这里有一个值得注意的优化。内核在 pick_next_task 里做了一个快速判断：如果当前 CPU 上所有可运行的任务都属于 CFS 调度类（这是最常见的情况），它会走一条快速路径，直接调用 pick_next_task_fair()，跳过对 stop、deadline、rt 等调度类的遍历。在绝大多数服务器和桌面场景下，你的线程走的都是这条路，因为大部分用户态进程使用的都是 SCHED_NORMAL 策略（也就是 CFS），实时任务（SCHED_FIFO/SCHED_RR）和 deadline 任务在通用工作负载里很少见。

到这一步，问题就收窄了：CFS 调度器拿到整个 CPU 的运行队列后，是怎么选出下一个该跑的任务的？

要回答这个问题，得先理解 CFS 的核心设计理念，也就是 vruntime。不理解 vruntime 就去读 pick_next_task_fair 的代码，跟不看地图就闯迷宫没有区别。

CFS 的核心哲学：用 vruntime 模拟一颗"理想CPU"

CFS 的全称是 Completely Fair Scheduler，完全公平调度器。它由 Ingo Molnar 在 2007 年实现，在 Linux 2.6.23 中合入主线，替换了之前的 O(1) 调度器。CFS 的设计哲学可以用内核文档里的一句话概括：

CFS basically models an "ideal, precise multi-tasking CPU" on real hardware.

什么是"理想的多任务 CPU"？想象一个虚拟的处理器，它能真正地同时运行所有任务——不是像现实中那样快速轮换制造出并行的假象，而是物理上同时运行。每个任务按精确的比例分到算力。如果有 4 个任务在跑，每个分到 25% 的 CPU 能力；如果有 10 个，每个分到 10%。

现实中的 CPU 在任意时刻只能运行一个任务（先不考虑超线程）。所以 CFS 引入了 虚拟运行时间（vruntime） 来追踪每个任务在这个"理想 CPU"上的进度。思路很直接：如果在理想 CPU 上所有任务应该同步推进，那么在现实 CPU 上，vruntime 小的任务就是"落后"了，它获得的 CPU 时间比理想份额少，应该被优先调度；vruntime 大的任务说明它已经跑得"超前"了，应该让位给别人。

CFS 始终试图让所有可运行任务的 vruntime 趋于一致。谁落后了就让谁先跑，谁跑多了就让谁等一等。这个朴素的策略，构成了后面所有复杂代码的根基。

vruntime 的计算公式：update_curr 详解

vruntime 不是简单地等于物理运行时间。如果所有任务的权重（优先级）相同，vruntime 确实等于物理时间，但当任务有不同的 nice 值时，vruntime 要根据权重做归一化。这个计算逻辑在 update_curr() 函数中，它是 CFS 里被调用频率最高的函数之一。每次时钟中断、每次调度决策、每次任务入队出队，几乎都会触发它：

// kernel/sched/fair.c
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;

    curr->exec_start = now;    // 刷新时间戳

    // 累加物理运行时间（用于 /proc/[pid]/stat 等统计接口）
    curr->sum_exec_runtime += delta_exec;
    schedstat_add(cfs_rq->exec_clock, delta_exec);

    // 核心：把物理时间折算成虚拟时间，累加到 vruntime
    curr->vruntime += calc_delta_fair(delta_exec, curr);

    // 更新整个队列的 min_vruntime 基准线
    update_min_vruntime(cfs_rq);
}

这段代码做的事情本质上就是一个会计操作，给当前正在运行的任务"记账"。delta_exec 是这次记账周期内任务实际占用 CPU 的物理时间（纳秒精度），然后通过 calc_delta_fair 折算成 vruntime 增量。

calc_delta_fair：加权折算的数学

calc_delta_fair 内部调用了 __calc_delta，本质上在做一次定点数乘除运算：

vruntime增量 = delta_exec × (NICE_0_LOAD / se->load.weight)

其中 NICE_0_LOAD 是 nice 值为 0 的标准权重（1024）。如果一个任务的 nice 值就是 0（权重 1024），那么 NICE_0_LOAD / weight = 1，vruntime 增量就等于物理时间，像一面镜子一样精确反映真实运行时间。

但如果 nice 值不是 0 呢？

nice -5 的任务，权重 3121，vruntime 增量 = delta_exec × (1024/3121) ≈ delta_exec × 0.328。跑了 1 毫秒的物理时间，vruntime 只增长 0.328 毫秒。意味着它的 vruntime 增长得慢，在红黑树上更容易保持在左边，更容易被选中。

nice 5 的任务，权重 335，vruntime 增量 = delta_exec × (1024/335) ≈ delta_exec × 3.06。跑了 1 毫秒，vruntime 涨 3.06 毫秒。它的 vruntime 增长快，在树上很快就会往右移动，被选中的机会变少。

这个设计的巧妙之处在于：通过扭曲时间的流速来实现权重的差异化。 高权重任务的时间"变慢"，低权重任务的时间"变快"。在红黑树上，大家用同一把尺子（vruntime）排队，但尺子对不同人的刻度不一样。结果就是高权重任务天然排在前面，低权重任务天然靠后，不需要任何额外的优先级判断逻辑，这全部被编码在 vruntime 的计算规则里了。

为什么用乘除而不是加减？因为乘除保持了比例关系的稳定性。不管任务运行了多长时间，高权重和低权重之间的 vruntime 比率始终是它们权重比率的倒数。这种数学上的优雅性，是 CFS 能做到"完全公平"的核心保障。

在实现层面，__calc_delta 没有直接做浮点除法（内核里不允许用浮点），而是用了定点数的移位和乘法来模拟。它先把除数取倒数再乘，通过 32 位定点数表示保证了纳秒级精度下的数值稳定性。这个实现细节虽然对理解调度逻辑不重要，但如果你去读 __calc_delta 的源码，能看到大量的 >>32、<<32 操作，那就是定点数运算的痕迹。

nice 值与权重的对应关系

nice 值范围是 -20 到 +19，总共 40 个级别。内核用一张预先计算好的查找表把 nice 值映射到权重：

// kernel/sched/core.c
const int sched_prio_to_weight[40] = {
 /* -20 */ 88761, 71755, 56483, 46273, 36291,
 /* -15 */ 29154, 23254, 18705, 14949, 11916,
 /* -10 */  9548,  7620,  6100,  4904,  3906,
 /*  -5 */  3121,  2501,  1991,  1586,  1277,
 /*   0 */  1024,   820,   655,   526,   423,
 /*   5 */   335,   272,   215,   172,   137,
 /*  10 */   110,    87,    70,    56,    45,
 /*  15 */    36,    29,    23,    18,    15,
};

这张表的设计遵循一个原则：相邻两个 nice 值之间的权重比大约是 1.25:1。也就是说每调整一档 nice 值，CPU 时间份额的变化大约是 10%。这不是拍脑袋的数字。1.25 的选择来自 Ingo Molnar 的工程经验：变化太小（比如 1.1:1），用户感知不到差异，调 nice 值没意义；变化太大（比如 2:1），低优先级任务很容易被饿死，系统稳定性受影响。1.25:1 是一个经过反复测试的平衡点。

拿具体数字说话。nice 0 权重 1024，nice -1 权重 1277。如果只有这两个任务同时运行，它们分到的 CPU 时间比约为 1277:1024 ≈ 55.5%:44.5%。nice -1 的任务多获得大约 11% 的 CPU 时间。再看极端情况：nice -20 权重 88761，nice 19 权重 15。比值约 5917:1。nice -20 的任务几乎独占 CPU，nice 19 的任务每 5917 份时间才能分到 1 份。但注意，它仍然分到了。CFS 的"完全公平"不是绝对平均，而是"按比例分配"，哪怕比例极小也不会完全饿死。

min_vruntime：防止"时间穿越"的基准线

update_curr 的最后一行调用了 update_min_vruntime(cfs_rq)。这个函数维护了一个非常重要的值：cfs_rq->min_vruntime。它是一个单调递增的基准线，大致等于当前运行队列中所有实体里最小的 vruntime。

为什么需要这个基准线？考虑两个场景：

场景一：新任务入队。 一个刚 fork 出来的任务，vruntime 应该设为多少？如果设为 0，它的 vruntime 远小于所有正在运行的任务，会霸占 CPU 很久直到 vruntime 追上来（恶意用户可以不断 fork 新进程来独占 CPU）。如果设为一个很大的值，新任务又要等很久才有机会跑。CFS 的做法是设为 cfs_rq->min_vruntime（加上半个调度周期作为惩罚），这样新任务既不会抢占太多，也不会等太久。

场景二：睡眠任务被唤醒。 一个任务睡了 10 分钟，其他任务的 vruntime 已经增长了很多，而它的 vruntime 还停留在 10 分钟前的值。如果直接用这个旧值放回红黑树，它会排在最左边，抢占所有任务很长时间。CFS 的做法是在唤醒时把它的 vruntime 补偿到 min_vruntime - sched_latency/2，让它有一定的优先调度优势（毕竟它刚醒，对延迟敏感），但不至于抢太多。

min_vruntime 还有一个作用：当任务在不同 CPU 之间迁移时，两个 CPU 的 vruntime 标尺可能不同（因为各自的负载不同，vruntime 增长速率不一样）。迁移时需要先从源 CPU 的 min_vruntime 中减去旧基准，再加上目标 CPU 的 min_vruntime，完成坐标系的转换。这个操作在 migrate_task_rq_fair 里实现。

数据结构：红黑树 + cfs_rq + sched_entity

理解了 vruntime 的含义和计算方式，接下来看 CFS 用什么数据结构来管理这些带着 vruntime 的任务。

struct sched_entity：调度实体

每个任务（task_struct）内嵌了一个 sched_entity 结构体，这是 CFS 调度的基本单元：

// include/linux/sched.h (简化)
struct sched_entity {
    struct load_weight  load;       // 权重（由nice值决定）
    struct rb_node      run_node;   // 红黑树节点
    u64                 vruntime;   // 虚拟运行时间
    u64                 exec_start; // 上次开始执行（或上次记账）的时间戳
    u64                 sum_exec_runtime;  // 累计物理运行时间
    unsigned int        on_rq;      // 是否在运行队列上
    int                 depth;      // 在cgroup层级中的深度
    struct sched_entity *parent;    // 父调度实体（cgroup场景）
    struct cfs_rq       *my_q;      // 拥有的子运行队列（组调度）
};

为什么不直接用 task_struct 做调度单元？因为 CFS 支持组调度（cgroup 的 CONFIG_FAIR_GROUP_SCHED）。一个 sched_entity 可以代表一个具体的任务，也可以代表一个任务组。在 CFS 的视角里，不管你是一个真实的线程还是一个包含 50 个线程的 Docker 容器，在某一层级的红黑树上，你都只是一个 sched_entity 节点。组调度场景下，调度器先在组之间按各组的 cpu.shares 权重做公平调度，然后递归进入被选中的组内部，在组内任务之间再做一次公平调度。这种层级化的设计让 CFS 能在容器化环境（Docker、Kubernetes）中对不同 cgroup 实施精确的 CPU 配额控制，而不需要在调度器核心逻辑里为容器写任何特殊代码。

sched_entity 里的 load 字段（struct load_weight 类型）包含两个成员：weight（权重）和 inv_weight（权重的倒数，预计算好用于加速除法）。这个 inv_weight 就是前面提到的 __calc_delta 中定点数除法的关键，它避免了每次计算 vruntime 时都做一次真正的除法运算。

struct cfs_rq：CFS 运行队列

每个 CPU 维护一个 cfs_rq，它是 CFS 调度的核心数据结构：

// kernel/sched/sched.h (简化)
struct cfs_rq {
    struct load_weight  load;            // 队列中所有实体的总权重
    unsigned int        nr_running;      // 可运行实体数量
    u64                 exec_clock;      // 队列的总执行时间（统计用）
    u64                 min_vruntime;    // 基准线（单调递增）

    struct rb_root_cached tasks_timeline; // 红黑树（带缓存的最左节点）

    struct sched_entity *curr;  // 当前正在运行的实体（不在树里）
    struct sched_entity *next;  // "next buddy"——唤醒抢占时的优先候选
    struct sched_entity *last;  // "last buddy"——被抢占者，缓存友好
    struct sched_entity *skip;  // "skip buddy"——主动yield的实体
};

这里面有四个指针特别值得关注：curr、next、last、skip。它们就是后面 pick_next_entity 里那些"不只取最左节点"的复杂逻辑的来源。

curr 指向当前正在这个 CPU 上运行的 CFS 实体。关键点：curr 不在红黑树里。 当一个实体被 set_next_entity 选中开始运行时，它会从红黑树中摘除。只有当它用完时间片或被抢占时，put_prev_entity 才会把它重新插回树中。这意味着 __pick_first_entity 取到的最左节点永远不包含当前正在运行的实体。pick_next_entity 需要单独把 curr 拿出来跟最左节点做比较。

next、last、skip 三个 buddy 指针在 pick_next_entity 里的作用，等追到那里的时候再详细讲。先记住它们的存在。

为什么用红黑树，不用最小堆

你可能会想：既然每次都要取 vruntime 最小的任务，用最小堆不是 O(1) 取最小值吗？为什么要用 O(log N) 的红黑树？

原因有三个，而且每一个都跟 CFS 的实际需求紧密相关：

第一，CFS 需要频繁删除任意位置的节点。 当一个正在运行队列里等待的任务收到信号、被迁移到其他 CPU、或者所属的 cgroup 被限流时，都需要把它从树中移除。红黑树的任意节点删除是 O(log N)，而且因为每个节点自带 rb_node（嵌入在 sched_entity 里），删除时不需要先搜索，直接从 rb_node 就能操作。堆的任意节点删除也是 O(log N)，但你得先知道这个节点在堆数组里的位置，这需要额外的索引维护。

第二，红黑树提供了有序遍历的能力。 CFS 的 skip 机制需要找到"次左节点"——vruntime 第二小的实体。红黑树用 rb_next() 就能 O(1) 拿到中序遍历的下一个节点，代码直接调用 __pick_next_entity 就行了，非常自然。堆结构做不到 O(1) 找次小值——最小堆只保证根是最小的，第二小的可能在根的两个子节点中的任一个，但在有数千节点的堆里，定位次小值仍然需要额外工作。

第三，rb_root_cached 让取最小值也变成了 O(1)。 Linux 内核的红黑树实现提供了一个叫 rb_root_cached 的变体。它在普通 rb_root 的基础上多维护了一个 rb_leftmost 指针，指向树中最左节点。每次插入或删除操作时顺便更新这个指针，额外成本几乎为零。这样 rb_first_cached 就是一次指针解引用，O(1)，跟堆取最小值一样快。

综合下来，CFS 用红黑树拿到了堆的 O(1) 取最小值优势，同时还保留了有序遍历和高效的任意删除能力。这是一个工程上"以简驭繁"的典型选择——用一个数据结构统一解决多个需求，避免引入额外的复杂度。

红黑树的插入与删除：enqueue 和 dequeue

理解红黑树在 CFS 中的角色，还需要知道节点是怎么进出树的。

任务变为可运行状态（被唤醒或新创建）时，enqueue_task_fair 被调用，它最终通过 __enqueue_entity 把 sched_entity 的 run_node 插入红黑树：

static void __enqueue_entity(struct cfs_rq *cfs_rq,
                             struct sched_entity *se)
{
    rb_add_cached(&se->run_node, &cfs_rq->tasks_timeline,
                  __entity_less);
}

__entity_less 是比较函数，按 vruntime 排序。rb_add_cached 在插入后会自动维护 rb_leftmost 缓存——如果新插入的节点 vruntime 比当前最左节点还小，它就成为新的最左节点。

任务变为不可运行状态（进入睡眠或退出）时，dequeue_task_fair 通过 __dequeue_entity 从树中移除：

static void __dequeue_entity(struct cfs_rq *cfs_rq,
                             struct sched_entity *se)
{
    rb_erase_cached(&se->run_node, &cfs_rq->tasks_timeline);
}

rb_erase_cached 在删除时也会维护 rb_leftmost——如果删除的恰好是最左节点，它会更新指针指向新的最左节点。

整个过程中，红黑树的自平衡操作（旋转和变色）确保树的高度始终保持在 O(log N)。对于一个有 1000 个可运行任务的系统，树的高度大约只有 20 层。每次插入或删除最多需要 3 次旋转，这个代价在调度器的整体开销中几乎可以忽略。

第一层：pick_next_task_fair 的整体结构

准备工作做完了。现在正式追踪 pick_next_task_fair——CFS 调度类的核心选择函数，定义在 kernel/sched/fair.c 的第 7493 行附近（Linux 6.1）。这个函数大约有 150 行代码，但结构清晰，可以分成四个阶段来理解：

// kernel/sched/fair.c (Linux 6.1, 简化标注)
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;
    int new_tasks;

again:
    // 阶段1：检查是否有CFS任务可运行
    if (!sched_fair_runnable(rq))
        goto idle;

#ifdef CONFIG_FAIR_GROUP_SCHED
    // 阶段2（组调度优化路径）：如果 prev 也是CFS任务，
    // 尝试最小化cgroup层级的切换开销
    if (!prev || prev->sched_class != &fair_sched_class)
        goto simple;

    do {
        struct sched_entity *curr = cfs_rq->curr;
        if (curr) {
            if (curr->on_rq) update_curr(cfs_rq);
            else curr = NULL;
        }
        se = pick_next_entity(cfs_rq, curr);
        cfs_rq = group_cfs_rq(se);
    } while (cfs_rq);

    // ... 最小化切换的优化代码 ...
    goto done;

simple:
#endif
    // 阶段3（简单路径）：逐层选择 + 设置
    if (prev)
        put_prev_task(rq, prev);

    do {
        se = pick_next_entity(cfs_rq, NULL);
        set_next_entity(cfs_rq, se);
        cfs_rq = group_cfs_rq(se);
    } while (cfs_rq);

    p = task_of(se);

done:
    return p;

idle:
    // 阶段4：当前CPU没有CFS任务，尝试从其他CPU偷任务
    new_tasks = newidle_balance(rq, rf);
    if (new_tasks < 0)
        return RETRY_TASK;  // 有更高优先级任务出现，需要重试
    if (new_tasks > 0)
        goto again;  // 偷到了，重新选择

    return NULL;  // 真的没活干了，进入 idle
}

阶段 1 最简单：检查这个 CPU 上有没有 CFS 可运行任务。sched_fair_runnable 就是检查 rq->cfs.nr_running 是否大于 0。如果没有 CFS 任务了，直接跳到 idle 路径做负载均衡。

阶段 2 是组调度场景下的优化路径，需要 CONFIG_FAIR_GROUP_SCHED 编译选项。它的特别之处在于：如果前一个任务（prev）和新选出的任务（p）在同一个 cgroup 树的不同位置，它不做完整的 put_prev + set_next，而是只操作它们公共祖先以下的部分。这个优化对深嵌套的 cgroup 场景很重要，后面单独展开。

阶段 3 是简单路径，也是理解核心逻辑的入口。那个 do-while 循环做两件事：

1.
用 pick_next_entity 从当前层的红黑树中选出最佳实体

2.
如果选出的实体是一个任务组（group_cfs_rq(se) 返回非 NULL），就进入那个组的子 cfs_rq，继续在下一层选

这就是 CFS 组调度的递归下降过程。在没有 cgroup 的场景下（大多数桌面系统和简单的服务器部署），group_cfs_rq(se) 返回 NULL，循环只执行一次。

阶段 4 是 idle 路径。这部分涉及多核负载均衡里的 newidle_balance，它会释放然后重新获取 rq->lock，所以可能需要重试整个选择过程。

接下来重点追阶段 3 里的 pick_next_entity——这才是调度决策的真正核心。

第二层：pick_next_entity——选择的真正逻辑

pick_next_entity 是整个调度选择的决策核心。很多教程会告诉你"CFS 就是取红黑树最左节点"，这话对了一半。如果你去看 Linux 2.6.24 最初版本的 CFS，确实几乎就是取最左。但在 16 年的演化中，这个函数越来越复杂，加入了 skip、next、last 三种 buddy 机制来做性能优化。现在的 pick_next_entity 实际上要在四个候选人之间做权衡：

/*
 * Pick the next process, keeping these things in mind, in this order:
 * 1) keep things fair between processes/task groups
 * 2) pick the "next" process, since someone really wants that to run
 * 3) pick the "last" process, for cache locality
 * 4) do not run the "skip" process, if something else is available
 */
static struct sched_entity *
pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    // 取红黑树最左节点
    struct sched_entity *left = __pick_first_entity(cfs_rq);
    struct sched_entity *se;

    // Step 1: 确定"理想候选人"——vruntime 最小的实体
    // curr不在树里，需要单独比较
    if (!left || (curr && entity_before(curr, left)))
        left = curr;

    se = left;  // 默认选最左的（或curr）

    // Step 2: skip 处理——如果"理想候选人"恰好是 skip，换一个
    if (cfs_rq->skip && cfs_rq->skip == se) {
        struct sched_entity *second;
        if (se == curr) {
            second = __pick_first_entity(cfs_rq);
        } else {
            second = __pick_next_entity(se);  // 取中序遍历的下一个
            if (!second || (curr && entity_before(curr, second)))
                second = curr;
        }
        // 只有当换人不太不公平时才真的跳过 skip
        if (second && wakeup_preempt_entity(second, left) < 1)
            se = second;
    }

    // Step 3: next buddy——刚唤醒的"想跑"的任务优先
    if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
        se = cfs_rq->next;

    // Step 4: last buddy——上一个被抢占的任务，缓存友好
    else if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
        se = cfs_rq->last;

    return se;
}

代码只有 30 多行，但每一步背后都有精心设计的理由。逐个拆解。

Step 1：确定最左节点——__pick_first_entity

struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
{
    struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline);
    if (!left)
        return NULL;
    return __node_2_se(left);
}

rb_first_cached 直接返回 rb_root_cached 里缓存的最左节点指针，时间复杂度 O(1)。__node_2_se 是一个 container_of 宏展开，从 rb_node 的地址反推出包含它的 sched_entity 地址——这是 Linux 内核里经典的嵌入式数据结构技巧。

注意 Step 1 里的一个关键细节：因为 curr（当前正在运行的实体）不在红黑树里，__pick_first_entity 拿到的最左节点不包含 curr。所以代码用 entity_before(curr, left) 来比较 curr 和最左节点的 vruntime。entity_before 就是比较两者的 vruntime 大小，如果 curr 的 vruntime 更小，说明当前任务还没用完它的"份额"，它仍然是最佳候选人。

Step 2：skip 机制——调用了 sched_yield 的任务

当一个任务调用 sched_yield() 时，内核会把它标记为 skip（通过 set_skip_buddy）。这个标记的意思是："我主动让出 CPU，这轮调度别选我了"。

但 CFS 不会无条件跳过它。如果跳过 skip 后选出的第二候选人跟 skip 的 vruntime 差太多（超过 wakeup_granularity），那说明跳过 skip 会导致严重的不公平——这时候 CFS 宁可违背 yield 的意愿也要保持公平性。公平性是 CFS 的底线。

__pick_next_entity(se) 在这里的作用是找中序遍历的下一个节点——也就是 vruntime 第二小的实体。这正是前面分析红黑树优势时提到的"有序遍历能力"的实际应用。

Step 3：next buddy——刚唤醒的任务优先

next 指针指向的是刚被唤醒的、触发了唤醒抢占的任务。它在 check_preempt_wakeup() 里被设置：

// check_preempt_wakeup() 中的关键片段
if (wakeup_preempt_entity(se, pse) == 1) {
    if (!next_buddy_marked)
        set_next_buddy(pse);
    goto preempt;
}

当一个睡眠的任务被唤醒（比如 I/O 完成、收到信号、等到了锁），check_preempt_wakeup 会被调用来决定它是否应该抢占当前任务。如果被唤醒任务的 vruntime 比当前任务小超过 wakeup_granularity，内核判定应该抢占，被唤醒任务就会被标记为 next buddy。这样在接下来的 pick_next_entity 里，它会被优先选中——即使红黑树最左节点可能是另一个任务。

为什么要给刚唤醒的任务这种优待？原因是实用主义的。刚唤醒的任务通常意味着某个 I/O 事件已经完成，用户正在等待响应。典型场景：

你按了键盘上的一个键，处理键盘中断的内核线程把事件传递给你的 GUI 进程，GUI 进程被唤醒。如果它要在红黑树上慢慢排队等着自然升到最左，你会感觉到明显的输入延迟。

一个网络服务器的 worker 线程在 epoll_wait 上睡着了，新的请求到来触发唤醒。如果唤醒后不能迅速获得 CPU，请求的「首字节」延迟就会上升。

next buddy 机制能让这些延迟敏感的任务"合法插队"，大幅改善交互响应和 I/O 延迟。前提是插队不能太离谱——wakeup_preempt_entity 的公平性检查确保了这一点。

Step 4：last buddy——缓存局部性优化

last 指针指向的是上一个被抢占的任务。逻辑是：如果这个被抢占者的 vruntime 跟最左节点差不多，优先让它继续跑。理由是缓存局部性——这个任务刚刚在这个 CPU 上执行过，它的代码段和数据段大概率还在 L1/L2 缓存里。如果选一个完全不相关的任务来跑，TLB 会被刷掉，缓存会被冲掉，导致大量 cache miss，新任务的头几毫秒会非常慢。

CPU 缓存的冷启动惩罚有多大？在现代处理器上，一次 L3 cache miss 的延迟大约 30-50 纳秒（约 100 个时钟周期），而一次内存访问的延迟约 80-200 纳秒。一个被冲掉缓存的任务在刚恢复执行时，可能有数千次 cache miss，累积起来就是数百微秒的额外开销。对于调度器来说，这不是微不足道的——调度器本身就在微秒级别做决策，如果每次调度决策导致几百微秒的缓存冷启动，那调度器再怎么优化选择逻辑都是白搭。

这就是为什么内核注释里写着 for cache locality。last buddy 机制花费了一点点公平性（在 wakeup_granularity 的容忍范围内）来换取显著的缓存性能收益。在工程实践中，这种权衡几乎总是划算的。

四个候选人的优先级决策逻辑

把 Step 1 到 Step 4 串起来，pick_next_entity 的决策优先级是：

1.先定基准：找到 vruntime 最小的实体（最左节点或 curr）

2.处理 skip：如果基准恰好是 skip，尝试换到第二候选人（需通过公平性检查）

3.next buddy 覆盖：如果有 next 且公平性检查通过，选 next

4.last buddy 兜底：如果没有 next 但有 last 且公平性检查通过，选 last

5.兜底：以上都不满足，选 vruntime 最小的

注意每一步的 buddy 生效都有 wakeup_preempt_entity(...) < 1 的公平性检查作为前置条件。CFS 不会为了性能优化完全牺牲公平性——所有的 buddy 优化都有一个底线：你可以插队，但不能插太狠。

第三层：wakeup_preempt_entity——公平性的守门人

pick_next_entity 里反复出现的 wakeup_preempt_entity 是公平性检查的核心函数。它的实现简洁到了极点：

static int
wakeup_preempt_entity(struct sched_entity *curr,
                      struct sched_entity *se)
{
    s64 gran, vdiff = curr->vruntime - se->vruntime;

    if (vdiff <= 0)
        return -1;  // curr的vruntime ≤ se，不应抢占

    gran = wakeup_gran(se);
    if (vdiff > gran)
        return 1;   // 差距超过粒度阈值，应该抢占

    return 0;        // 差距在粒度范围内，不抢占
}

三个返回值的含义映射到 pick_next_entity 里的用法：

返回 < 1（即 -1 或 0）：curr 和 se 的公平性差距可接受，buddy 机制可以生效

返回 1：差距太大，超过了公平性容忍度，buddy 不应该生效

wakeup_gran 函数进一步细化了"粒度"的定义。它把通过 /proc/sys/kernel/sched_wakeup_granularity_ns 配置的粒度值（默认 1ms = 1000000 纳秒）根据任务的权重做了一次归一化——用了跟计算 vruntime 同样的 calc_delta_fair 函数。效果是：权重越高的任务，换算后的粒度值越小，触发抢占的门槛越低，更容易被唤醒抢占到。这是 CFS 对高优先级任务的又一个隐性优待——它不只通过 vruntime 的增长速率来体现优先级差异，连抢占的灵敏度都跟权重挂钩了。

理解了这个函数，pick_next_entity 里所有的 buddy 逻辑就通透了：buddy 机制本质上是在公平性允许的范围内做缓存和延迟优化。如果优化和公平冲突，永远是公平赢。

第四层：set_next_entity——被选中之后的准备工作

从 pick_next_entity 选出来的实体，还要经过 set_next_entity 的处理才能真正开始执行。这一步是任务从"等待者"变成"执行者"的状态转换：

static void
set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    clear_buddies(cfs_rq, se);  // 清除所有 buddy 标记

    if (se->on_rq) {
        update_stats_wait_end_fair(cfs_rq, se);  // 结束等待统计
        __dequeue_entity(cfs_rq, se);   // 从红黑树中移除
        update_load_avg(cfs_rq, se, UPDATE_TG);
    }

    update_stats_curr_start(cfs_rq, se);  // 开始运行统计
    cfs_rq->curr = se;  // 标记为当前运行实体

    se->exec_start = rq_clock_task(rq_of(cfs_rq));  // 设置计时起点
    se->prev_sum_exec_runtime = se->sum_exec_runtime;
}

几个值得注意的设计决策：

第一，正在运行的任务会从红黑树中移除（__dequeue_entity）。 这是 CFS 的一个重要设计选择。运行中的任务没有"等待"的概念，它不需要参与排序竞争。把它从树中摘除后，红黑树里只剩下真正在等待 CPU 的任务，__pick_first_entity 的语义更清晰。同时也避免了 update_curr 更新 curr 的 vruntime 后需要重新调整它在树中位置的额外开销。

第二，clear_buddies 清除所有 buddy 标记。 如果被选中的实体是某个 buddy（比如它既是 next 又是最左节点），那这些 buddy 指针在它开始运行后就没意义了——它已经在跑了，下次调度决策时不需要通过 buddy 来优待它。这个清理确保 buddy 指针不会残留过时的引用。

第三，exec_start 的设置。 这个时间戳是下一次 update_curr 计算 delta_exec（物理运行时间增量）的起点。从这一刻开始，这个任务每占用 CPU 一个纳秒，都会被 update_curr 记录并折算成 vruntime 增量。当它的 vruntime 增长到超过其他等待者时，下一次调度决策就会选择别的任务来跑。

put_prev_entity：任务让出 CPU 时的对称操作

跟 set_next_entity 对称的是 put_prev_entity，它在任务被切换下去时调用：

static void put_prev_entity(struct cfs_rq *cfs_rq,
                            struct sched_entity *prev)
{
    if (prev->on_rq) {
        update_curr(cfs_rq);  // 做最后一次记账
        update_stats_wait_start_fair(cfs_rq, prev);
        __enqueue_entity(cfs_rq, prev);  // 放回红黑树
    }
    cfs_rq->curr = NULL;  // 清除当前运行实体
}

关键操作就是 __enqueue_entity——把被切换下去的任务重新插回红黑树。注意在插回之前先调用了 update_curr，确保这个任务在运行期间积累的物理时间被完整地折算成 vruntime。这样当它被放入红黑树排序时，用的是最新的、准确的 vruntime 值。

set_next_entity 和 put_prev_entity 构成了一对对称操作。被选中时从树中摘除并开始计时，被切换下去时停止计时并放回树中。红黑树里始终只包含"正在等待的"实体，而不包含"正在运行的"——这个不变式贯穿 CFS 的所有代码路径。

组调度的递归下降：cgroup 场景下的特殊路径

如果你的系统用了 Docker 或 Kubernetes，几乎一定涉及 cgroup 和组调度（CONFIG_FAIR_GROUP_SCHED）。在这种配置下，pick_next_task_fair 的行为会变得更复杂——不是选一次就够了，而是要逐层递归向下选。

回顾阶段 3 的循环：

do {
    se = pick_next_entity(cfs_rq, NULL);
    set_next_entity(cfs_rq, se);
    cfs_rq = group_cfs_rq(se);
} while (cfs_rq);

group_cfs_rq(se) 的逻辑：如果 se 代表一个任务组（se->my_q 非 NULL），返回这个组自己的 cfs_rq；如果 se 代表一个具体任务（se->my_q == NULL），返回 NULL，循环终止。

举个实际的例子。假设一台机器上跑了两个 Docker 容器，对应两个 cgroup，各自配了不同的 cpu.shares：

root_cfs_rq                            (CPU 0 的顶层运行队列)
  ├── container_A_se  [weight=2048]    (容器A的调度实体)
  │     └── container_A_cfs_rq         (容器A内部的运行队列)
  │           ├── nginx_se             (nginx worker)
  │           └── php_se               (php-fpm worker)
  └── container_B_se  [weight=1024]    (容器B的调度实体)
        └── container_B_cfs_rq         (容器B内部的运行队列)
              ├── redis_se             (redis server)
              └── cron_se              (定时任务)

调度发生时：

1.
在 root_cfs_rq 的红黑树中做 pick_next_entity。因为 container_A 的权重是 container_B 的两倍，在 vruntime 维度上 container_A 的 vruntime 增长更慢，更容易被选中。假设选中了 container_A_se。

2.
group_cfs_rq(container_A_se) 返回 container_A_cfs_rq，循环继续。

3.
在 container_A_cfs_rq 中再做一次 pick_next_entity，这次的候选人是 nginx_se 和 php_se。假设 nginx_se 的 vruntime 更小，选中它。

4.
group_cfs_rq(nginx_se) 返回 NULL（它是一个具体任务不是组），循环结束。最终选出的任务是 nginx worker。

组调度的公平性是层级化的。容器层面：container_A 获得约 2/3 CPU 时间，container_B 获得约 1/3。容器内部：nginx 和 php-fpm 按各自的 nice 值权重再次分配——两层公平性互不干涉，由 vruntime 的层级计算自然保证。

组调度优化路径——最小化 cgroup 层级切换开销

pick_next_task_fair 里有一段被 #ifdef CONFIG_FAIR_GROUP_SCHED 包裹的优化逻辑。当 prev（前一个任务）和新选出的任务 p 都属于 CFS 调度类时，它会尝试只在两个任务的最近公共祖先（LCA）以下做切换操作，避免从 root 开始完整遍历整个 cgroup 层级。

if (prev != p) {
    struct sched_entity *pse = &prev->se;

    // 沿着 cgroup 层级向上爬，找到最近公共祖先
    while (!(cfs_rq = is_same_group(se, pse))) {
        int se_depth = se->depth;
        int pse_depth = pse->depth;

        if (se_depth <= pse_depth) {
            put_prev_entity(cfs_rq_of(pse), pse);
            pse = parent_entity(pse);  // prev 向上走一层
        }
        if (se_depth >= pse_depth) {
            set_next_entity(cfs_rq_of(se), se);
            se = parent_entity(se);    // next 向上走一层
        }
    }

    put_prev_entity(cfs_rq, pse);
    set_next_entity(cfs_rq, se);
}

这段代码非常像两棵树之间求 LCA 的经典算法——先把深度大的那个向上爬到同一层，然后两个一起爬，直到碰到同一个节点。在 CFS 这里，每走一步都伴随着 put_prev_entity（把旧路径上的节点放回红黑树）或 set_next_entity（把新路径上的节点从红黑树摘除）。

对于深嵌套的 cgroup 结构（Kubernetes 环境里 cgroup v2 可以套好几层），这个优化避免了从 root 开始的完整 put/set 遍历，显著减少了红黑树操作和负载统计更新的次数。在极端情况下（比如 cgroup 嵌套 5-6 层，而前后两个任务在同一个子 cgroup 里），这个优化可以把切换开销从 O(depth) 降到 O(1)。

负载均衡的入口：idle 路径与 newidle_balance

如果当前 CPU 的 CFS 运行队列是空的，pick_next_task_fair 会走到 idle 标签处：

idle:
    if (!rf)
        return NULL;

    new_tasks = newidle_balance(rq, rf);

    if (new_tasks < 0)
        return RETRY_TASK;  // 更高优先级任务出现，需要重试
    if (new_tasks > 0)
        goto again;         // 偷到了任务，回去重新选

    update_idle_rq_clock_pelt(rq);
    return NULL;  // 真的没活了，进 idle

newidle_balance 是 CFS 多核负载均衡机制的一个重要入口。它的工作是：当一个 CPU 发现自己没有 CFS 任务可运行时，主动去其他忙碌的 CPU 上"偷"一些任务过来，避免出现"有的核忙死、有的核闲着"的局面。

这个函数的实现涉及调度域（sched_domain）的层级遍历——先在同一个物理核的超线程兄弟之间找，再在同一个 die 内的核之间找，然后是跨 NUMA 节点找。层级越远，迁移的代价越高（因为 NUMA 跨节点的内存访问延迟显著增加），所以内核会优先在拓扑距离近的核之间做平衡。

需要注意 newidle_balance 的一个副作用：它会释放并重新获取运行队列锁（rq->lock）。在锁被释放的窗口期，可能有更高优先级的任务（实时任务或 deadline 任务）被唤醒并放到了这个 CPU 上。所以函数返回 RETRY_TASK 表示"可能有更紧急的任务了，别急着选 CFS 任务，先回去让调度器核心重新检查所有调度类"。

这也解释了 pick_next_task_fair 开头的 again: 标签——整个选择过程可能需要重复执行，因为负载均衡操作可以改变运行队列的状态。

调度时机：什么时候触发 pick_next_task_fair

理解了选择逻辑后，还差一个关键拼图：内核什么时候会调用 __schedule()，进而触发 pick_next_task_fair？

主要有四个时机。

1. 时钟中断——周期性检查（`task_tick_fair`）

每次时钟中断都会调用 task_tick_fair → entity_tick，更新 vruntime 并检查是否该让位：

static void
entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr,
            int queued)
{
    update_curr(cfs_rq);  // 更新vruntime

    if (cfs_rq->nr_running > 1)
        check_preempt_tick(cfs_rq, curr);  // 检查是否该让位
}

check_preempt_tick 的判断逻辑涉及两个关键参数：

sched_latency（默认 6ms）：定义一个"调度周期"。在一个周期内，所有可运行任务都应该至少获得一次执行机会。每个任务理论上分到的时间片是 sched_latency / nr_running。

sched_min_granularity（默认 0.75ms）：最小时间片。如果 sched_latency / nr_running 小于这个值，就用 sched_min_granularity 作为时间片下限。

当 nr_running > sched_latency / sched_min_granularity = 8 时（在默认参数下），调度周期会自动拉长为 nr_running × sched_min_granularity，避免过于频繁的上下文切换吃掉 CPU 时间。这意味着当一个 CPU 上有 20 个可运行任务时，允许一个调度周期达到 20 × 0.75ms = 15ms，让每个任务至少跑 0.75ms 才被切换。

如果检查发现当前任务已经跑超了它的份额，check_preempt_tick 会调用 resched_curr(rq) 设置 TIF_NEED_RESCHED 标志。这个标志不会立刻导致调度，而是在当前任务返回用户态或者到达内核中的可抢占点时才真正触发 __schedule()。

2. 任务唤醒——check_preempt_wakeup

当一个睡眠的任务被唤醒时，check_preempt_wakeup 判断它是否应该抢占当前任务：

static void check_preempt_wakeup(struct rq *rq,
                                  struct task_struct *p,
                                  int wake_flags)
{
    struct sched_entity *se = &rq->curr->se, *pse = &p->se;

    // SCHED_IDLE 策略的任务始终被普通任务抢占
    if (unlikely(task_has_idle_policy(rq->curr)) &&
        likely(!task_has_idle_policy(p)))
        goto preempt;

    // SCHED_BATCH 任务不主动抢占（靠 tick 驱动）
    if (unlikely(p->policy != SCHED_NORMAL) ||
        !sched_feat(WAKEUP_PREEMPTION))
        return;

    update_curr(cfs_rq_of(se));
    if (wakeup_preempt_entity(se, pse) == 1) {
        set_next_buddy(pse);    // 标记为 next buddy
        goto preempt;
    }
    return;

preempt:
    resched_curr(rq);           // 设置 TIF_NEED_RESCHED
    if (sched_feat(LAST_BUDDY) && entity_is_task(se))
        set_last_buddy(se);     // 被抢占者设为 last buddy
}

注意最后两行：当抢占发生时，被抢占的任务（se）会被标记为 last buddy，而抢占者（pse）被标记为 next buddy。这两个 buddy 标记会在下一次 pick_next_entity 时发挥作用——next buddy 让唤醒者优先获得 CPU，last buddy 让被抢占者在不太不公平的情况下尽快恢复执行（缓存还热着）。

3. 任务主动让出——yield 和阻塞

当任务调用 sched_yield() 时，yield_task_fair 会先清除所有 buddy 标记再把当前任务设为 skip buddy：

static void yield_task_fair(struct rq *rq)
{
    struct sched_entity *se = &rq->curr->se;

    if (unlikely(rq->nr_running == 1))
        return;  // 就自己一个，yield 没意义

    clear_buddies(cfs_rq, se);
    update_curr(cfs_rq);   // 先做一次记账
    set_skip_buddy(se);    // 标记为 skip
}

这里有一个细节：yield 之前先调用了 update_curr，确保这个任务在 yield 之前的运行时间被正确记账到 vruntime 里。否则 vruntime 可能偏低，即使被标记为 skip，第二候选人的公平性检查也可能判定"跳过 skip 不公平"而继续选它。

当任务因为等锁、等 I/O 等原因阻塞时，会调用 dequeue_task_fair 把它从红黑树中移除，然后触发调度。被阻塞的任务不参与后续的调度决策，直到它被唤醒并重新 enqueue。

4. 任务创建——fork 后的 vruntime 初始化

新创建的任务通过 task_fork_fair 初始化 vruntime。CFS 的策略是把新任务的 vruntime 设为 cfs_rq->min_vruntime，并根据 sched_child_runs_first 参数决定是否让子进程先运行。

默认配置下 sched_child_runs_first = 0，也就是 fork 后父进程继续运行。但某些工作负载（比如 Apache 的 prefork 模式）会设为 1，让 fork 出来的子进程立即获得 CPU。不管哪种策略，新任务的 vruntime 都不会是 0——它被设为当前队列的 min_vruntime，确保新任务不会因为 vruntime 极小而霸占 CPU 过长时间。

实战调优：用参数控制 pick_next_task_fair 的行为

理解了源码逻辑后，下面这些参数就不再是黑盒了——你知道它们在代码的哪个位置、什么条件下生效：

关键参数一览

参数	默认值	sysctl 路径	在源码中的作用位置
`sched_latency_ns`	6000000 (6ms)	`/proc/sys/kernel/sched_latency_ns`	`check_preempt_tick` 计算时间片
`sched_min_granularity_ns`	750000 (0.75ms)	`/proc/sys/kernel/sched_min_granularity_ns`	`check_preempt_tick` 时间片下限
`sched_wakeup_granularity_ns`	1000000 (1ms)	`/proc/sys/kernel/sched_wakeup_granularity_ns`	`wakeup_preempt_entity` 公平性阈值

低延迟场景（音视频、游戏服务器、交互式应用）

# 目标：让唤醒的任务尽快获得CPU
echo 3000000 > /proc/sys/kernel/sched_latency_ns       # 调度周期→3ms
echo 500000  > /proc/sys/kernel/sched_min_granularity_ns # 最小粒度→0.5ms
echo 500000  > /proc/sys/kernel/sched_wakeup_granularity_ns # 唤醒粒度→0.5ms

缩短 sched_wakeup_granularity 意味着 wakeup_preempt_entity 里的 gran 变小，更容易返回 1 触发抢占。也意味着 pick_next_entity 里的 buddy 公平性容忍度变低——只有 vruntime 差距非常小的 buddy 才能生效。

代价是更频繁的上下文切换。一次上下文切换的直接成本大约 2-5 微秒（保存/恢复寄存器），但间接成本（缓存失效、TLB 刷新）可能高达 10-50 微秒。如果你的调度周期太短导致每秒切换超过几千次，这些开销会显著压缩留给业务逻辑的 CPU 时间。

高吞吐场景（批量计算、机器学习训练、大数据处理）

# 目标：减少切换次数，最大化缓存利用
echo 24000000 > /proc/sys/kernel/sched_latency_ns       # 调度周期→24ms
echo 3000000  > /proc/sys/kernel/sched_min_granularity_ns # 最小粒度→3ms
echo 4000000  > /proc/sys/kernel/sched_wakeup_granularity_ns # 唤醒粒度→4ms

拉高 sched_wakeup_granularity 让 wakeup_preempt_entity 更难返回 1，减少了唤醒抢占的频率。每个任务在获得 CPU 后能跑更久，充分利用缓存预热，但交互响应会明显变慢。

用 ftrace 和 perf 观察调度行为

光看源码不够直观。实际系统上的调度行为可以用以下工具观察。

ftrace：追踪调度事件

# 启用调度器事件追踪
echo 1 > /sys/kernel/debug/tracing/events/sched/sched_switch/enable
echo 1 > /sys/kernel/debug/tracing/events/sched/sched_wakeup/enable

# 实时查看
cat /sys/kernel/debug/tracing/trace_pipe | head -30

输出示例：

<idle>-0   [002] 12345.678901: sched_wakeup:   comm=myapp pid=1234 prio=120 target_cpu=002
<idle>-0   [002] 12345.678910: sched_switch:   prev=swapper/2:0 ==> next=myapp:1234
myapp-1234 [002] 12345.679900: sched_switch:   prev=myapp:1234 ==> next=worker:5678

从 sched_wakeup（时间戳 678901）到对应的 sched_switch（时间戳 678910）之间的差值就是调度延迟——这个例子里是 9 微秒。这是 CPU idle 时的理想情况：CPU 没有其他任务在跑，唤醒后几乎立即被调度。在高负载下，同样的延迟可能达到几毫秒。

perf sched：系统化的延迟分析

perf sched record -- sleep 10       # 记录 10 秒的调度事件
perf sched latency --sort max       # 按最大延迟排序输出

输出会列出每个 task 在记录期间的最大/平均调度延迟。如果某些任务的最大延迟异常偏高，你就知道需要检查它所在 CPU 的运行队列长度、cgroup 配额限制、或者是否被实时任务霸占了 CPU。

/proc/sched_debug：运行队列的实时快照

cat /proc/sched_debug | head -60

这个文件会打印每个 CPU 的运行队列状态，包括 nr_running、min_vruntime、当前 curr 实体的 vruntime、以及红黑树中各实体的 vruntime。你可以直接看到红黑树里谁排在最左——这在排查调度异常时非常有价值。

CFS 的局限与 EEVDF 的接替

CFS 从 Linux 2.6.23（2007 年）一直用到 Linux 6.5（2023 年），陪伴内核走过了 16 年。但它有几个天然的设计局限：

延迟不确定性。 CFS 保证的是长时间窗口内的公平性——给定足够长的时间段内，所有任务获得的 CPU 时间占比趋近于它们的权重比。但它不保证单次调度延迟的上界。100 个 vruntime 相近的任务同时竞争，某个刚唤醒的任务排到第几个跑，取决于红黑树的当前状态和 buddy 指针的碰巧方向。这对实时性要求高的工作负载是个问题。

sleeper fairness 的粗糙补偿。 睡了很久的任务醒来后 vruntime 远小于其他任务。CFS 通过 min_vruntime 补偿来防止它霸占 CPU，但补偿策略是固定的（补偿到 min_vruntime 附近），不能针对不同类型的唤醒做差异化处理。一个刚醒的交互进程和一个刚醒的批处理进程获得同样的补偿，但它们对延迟的敏感度完全不同。

buddy 机制的启发式本质。 next、last、skip 三个 buddy 都是启发式优化——它们在大多数情况下有效，但没有理论保证。特别是在高并发场景下，buddy 指针可能频繁被覆盖（每次唤醒都可能设置新的 next），导致优化效果不稳定。

从 Linux 6.6 开始（2023 年 10 月合入），内核的默认公平调度器已经从 CFS 切换到了 EEVDF（Earliest Eligible Virtual Deadline First）。EEVDF 也由 Peter Zijlstra 在 CFS 的基础上演化而来，保留了 vruntime 的核心概念，但引入了"虚拟截止时间（virtual deadline）"。每个任务不仅有 vruntime 表示它"已经用了多少"，还有一个 deadline 表示它"最迟应该在什么时候被调度到"。

EEVDF 的调度决策从"取 vruntime 最小且通过 buddy 启发检查的实体"变成了"取所有 eligible（有资格的）实体中 deadline 最早的"。这个机制天然地为每个任务提供了延迟上界的保证——不需要依赖 buddy 指针的碰运气。CFS 里那三个 buddy 指针和 wakeup_preempt_entity 的公平性检查，在 EEVDF 里被更系统化的 eligibility + deadline 机制完全取代。

不过，EEVDF 的底层仍然是红黑树，vruntime 的计算方式没有根本改变，权重表也是同一张。你在本文中学到的关于 vruntime 设计、calc_delta_fair 加权折算、红黑树组织方式、组调度递归下降、min_vruntime 基准线的知识，在理解 EEVDF 时完全适用。

回到开头的问题

现在回到最开始的场景：你的线程从被唤醒到跑起来等了 20 毫秒。追完 pick_next_task_fair 的源码后，你知道这 20 毫秒可能被消耗在以下环节：

1. 运行队列排队。 如果那个 CPU 上有大量可运行任务——比如 cgroup 配额不合理导致太多线程堆在同一个核上，或者绑核策略有问题——你的线程要等到所有 vruntime 更小的任务先跑一轮才能排到。在默认的 6ms 调度周期下，如果有 20 个可运行任务，每个至少跑 0.75ms 的最小粒度，一个调度周期就是 15ms，你的线程被选中之前的平均等待时间约为 7-8ms，最大可达 15ms。如果你的 vruntime 恰好还偏大（比如你是个计算密集型任务），等待时间会更长。

2. 唤醒抢占没有生效。 如果你的线程是 SCHED_BATCH 策略，check_preempt_wakeup 里有一条硬规则直接 return 不做抢占检查。即使是 SCHED_NORMAL，如果你的 vruntime 跟当前任务的差距没超过 wakeup_granularity（默认 1ms），抢占也不会触发。你的线程只能等到下一次时钟 tick 触发 check_preempt_tick 时才有机会被调度。

3. CPU 被更高优先级的调度类占据。 pick_next_task 的遍历顺序是 stop → deadline → rt → fair → idle。如果那个 CPU 上有 SCHED_FIFO 或 SCHED_RR 的实时任务在跑，CFS 的任务必须等实时调度类里所有任务都处理完才轮得到。实时任务可以轻松地把 CFS 任务的延迟推到几百毫秒级别。

4. 负载均衡延迟。 如果你的线程被唤醒后，select_task_rq_fair 决定把它放到另一个 CPU 上（因为原来的 CPU 太忙了），迁移过程本身加上目标 CPU 上的排队等待引入了额外的延迟。跨 NUMA 节点的迁移尤其慢，因为任务的数据可能在远端节点的内存上，访问延迟翻倍。

排查思路也就清楚了：先用 perf sched latency 确认延迟集中在哪些任务上，再用 cat /proc/sched_debug 看对应 CPU 的运行队列状态（nr_running 是否过高，是否有实时任务），然后根据上面的分析对症下药——调整调度参数、优化 cgroup 配额、调整绑核策略分散负载，或者把延迟敏感的任务提升 nice 值（降低 nice 数字 = 提高优先级）。

pick_next_task_fair 只是 CFS 调度器的选择逻辑——fair.c 里 12000 多行代码中的 150 行。但追踪这一个函数，就能串起 vruntime 设计、权重表工程、calc_delta_fair 的定点运算、红黑树 rb_root_cached 的原因选择、buddy 三指针的缓存和延迟优化、组调度的递归下降、min_vruntime 基准线的多重用途、负载均衡的入口点——这些散落在万行代码里的精密机制，构成了一条完整的调度决策链路。

下次再看到调度延迟的数字，你知道它不是一个黑盒里蹦出来的随机数。每一微秒的等待，都是这些代码路径执行的确定性结果。