Linux CFS调度器核心数据结构解析：sched_entity与cfs_rq设计意图

做内核调度器分析的人都知道，CFS（Completely Fair Scheduler）从2.6.23合入以来，一直是Linux默认调度器的绝对主力。即便后来有了EEVDF的演进，理解CFS的核心数据结构依然是一把钥匙——很多看起来玄乎的调度现象，比如某个进程老是抢不到CPU、负载均衡后runqueue分布不合理、延迟敏感任务被饿着，最后都能落到两个结构体的字段上：sched_entity和cfs_rq。

我最早啃这块源码的时候，其实是有点懵的。调度器这条路，从task_struct进去，先碰到se，然后是cfs_rq，再挖到红黑树，最后是一堆update函数和calc_delta_fair。绕一圈出来发现，真正要回答的问题只有一个：调度器凭什么决定下一个该跑谁？这个问题的答案，统统写在核心结构的"用意"里。这篇文章我不打算逐行翻译源码，而是从"结构为什么这么设计"的角度，把CFS的骨架拆开，顺带把虚拟时间、负载权重、调度延迟这些概念用实际数字过一遍，最后讲讲我在排查问题时的经验和踩过的坑。

1. CFS调度类在整个调度体系中的位置

1.1 调度类抽象：任务类型决定排队方式

先别急着钻进cfs_rq，得先看清CFS站在哪里。调度器在Linux里不是一套算法打天下，而是按"调度类"把任务分成几类，每一类有自己的排队和选择逻辑。核心抽象是struct sched_class，它本质上是一组函数指针，定义了"加入队列、离开队列、选下一个、抢占检查"这些标准动作。在内核源码里长这样：

struct sched_class { const struct sched_class *next; void (*enqueue_task)(struct rq *rq, struct task_struct *p, int flags); void (*dequeue_task)(struct rq *rq, struct task_struct *p, int flags); void (*yield_task)(struct rq *rq); bool (*yield_to_task)(struct rq *rq, struct task_struct *p); void (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags); struct task_struct *(*pick_next_task)(struct rq *rq); void (*put_prev_task)(struct rq *rq, struct task_struct *p); ... };

这个抽象非常像面向对象里的接口。内核里按优先级从高到低，有dl_sched_class（Deadline调度类）、rt_sched_class（实时调度类）、fair_sched_class（CFS）、idle_sched_class（空闲调度类）。每次调度发生时，调度核心从高到低遍历这些类，问一句"你这边有没有可跑的任务？"如果Deadline和RT类有任务，CFS基本就没机会被选中；只有前两个类的队列都空了，调度器才会走到fair_sched_class的pick_next_task。

1.2 CFS调度类的注册与核心回调

CFS调度类的实例就是全局的fair_sched_class，它把上面那些函数指针一一对应到自己的实现。比较重要的几个映射关系：

const struct sched_class fair_sched_class = { .next = &idle_sched_class, .enqueue_task = enqueue_task_fair, .dequeue_task = dequeue_task_fair, .yield_task = yield_task_fair, .check_preempt_curr = check_preempt_wakeup, .pick_next_task = pick_next_task_fair, .put_prev_task = put_prev_task_fair, };

这个映射的含义是：当普通任务被唤醒、创建或者时间片到期重排时，内核调用enqueue_task_fair把它塞进某个CPU的CFS就绪队列；调度器需要选下一个任务时，调用pick_next_task_fair从红黑树里取最左节点；当前任务要换出时，调用put_prev_task_fair把它放回队列。理解了这一层，后面看到enqueue_entity、dequeue_entity这些函数名时就不会乱了——它们是CFS调度类内部的具体实现，而sched_class是统一的壳。

1.3 从task_struct到调度实体

每次你fork()出一个新进程，内核在task_struct里会嵌入一个sched_entity字段，也就是我们说的se。这个se才是CFS真正排队和计算的对象，不是整个task_struct。所以当我说"一个任务在CFS红黑树里"，精确措辞应该是"这个任务的调度实体在红黑树里"。

在task_struct中相关字段是：

struct task_struct { ... const struct sched_class *sched_class; struct sched_entity se; struct sched_rt_entity rt; struct sched_dl_entity dl; ... };

这里有个很关键的设计意图：一个任务同时会有多个调度实体，但同一时刻它只属于一个调度类。比如普通进程只有se有意义，实时进程主要用rt，Deadline任务用dl。CFS只操作se和fair_sched_class这一对。很多做容器、做云平台优化的人会去动task_struct->se的权重和vruntime，就是因为CFS的一切决策都建立在se之上。

2. sched_entity：调度实体的设计意图

2.1 为什么单独抽象出调度实体

刚开始学内核的时候我有个疑问：为什么直接在task_struct里放vruntime、run_node这些字段不行吗？非得再包一层sched_entity？

答案在组调度（group scheduling）。支持CONFIG_FAIR_GROUP_SCHED之后，CFS不仅要调度任务，还要调度任务组。一个用户、一个容器、一个cgroup，都可以作为一个调度实体参与CPU分配。这种情况下，一个"调度实体"可能仍然是个进程，也可能是嵌套的一整棵子调度树。如果把调度字段直接摊在task_struct里，组调度压根没法做。抽出sched_entity之后，任务、任务组都能统一用同一套字段排进红黑树，调度器根本不需要关心你到底是进程还是个组。

2.2 核心字段逐个拆解

sched_entity在5.x内核里的定义大致是：

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; u64 nr_migrations; struct sched_statistics statistics; int depth; struct sched_entity *parent; struct cfs_rq *cfs_rq; struct cfs_rq *my_q; };

我逐个说一下每个字段到底是干嘛的，这才是"结构用意"的重点。

load，类型是struct load_weight，里面核心是weight和inv_weight。这个weight不是任务的物理占用，而是调度权重，它和nice值一一对应。CFS分配CPU时间时，权重越大，分到的slice越长。inv_weight是weight的乘数倒数，为了做除法优化用的——内核里计算vruntime增量要用"反比"关系，提前存好倒数能避免每次做昂贵的除法。

run_node，这就是红黑树节点。CFS把同一CPU上的可运行实体组织成一颗红黑树，run_node就是挂在树上的钩子。这里要特别注意：这个节点是嵌入在结构体内部的，不是指针指向外部内存。这样设计的好处是，每次入队出队不用动态分配节点，省掉了malloc的延迟和不稳定性。

on_rq，标志位，表示这个实体当前是否在就绪队列里。值为1说明在cfs_rq上，值为0说明不在。我在排查"任务明明在运行怎么找不到"这类问题时，第一眼就会看这个标志。

exec_start、sum_exec_runtime、prev_sum_exec_runtime、vruntime这组字段是核心中的核心。exec_start记录本次调度开始的时间戳；sum_exec_runtime是该实体累计的真实运行时间；prev_sum_exec_runtime是上一次被换出时的累计运行时间，用来计算本次运行了多久；vruntime是虚拟运行时间，也就是该实体在CFS里的"排位分"。后面我会专门用一节讲它怎么算。

2.3 一个任务从唤醒到运行的字段流转

我习惯用一条完整链路把上面这些字段串起来，这样比背结构体定义效率高得多。

假设一个任务在睡眠后被唤醒。调度核心调用enqueue_task_fair，进入enqueue_entity。此时on_rq从0变成1，load被累加到cfs_rq上。然后调用place_entity设置vruntime：如果这是一个新任务，vruntime会被更新为cfs_rq->min_vruntime再加上一个初始虚拟时间片，防止新任务一上来就把老任务挤掉。之后调用__enqueue_entity，通过红黑树插入算法把run_node挂到合适位置。

接下来调度器调用pick_next_task_fair，pick_next_entity从红黑树取最左节点——也就是vruntime最小的实体。如果选中的就是当前这个任务，set_next_entity会被调用，此时把exec_start更新为当前时钟，vruntime从prev_sum_exec_runtime继续累加。

当任务运行到调度点被换出时，put_prev_entity先算本次运行时间：sum_exec_runtime += current_time - exec_start，然后prev_sum_exec_runtime = sum_exec_runtime，同时把vruntime增加对应增量，再调__enqueue_entity塞回红黑树。整个过程下来，sum_exec_runtime是物理时间总账，vruntime是虚拟时间总账，红黑树里谁靠左，谁的下一次运行机会就更大。

3. cfs_rq：就绪队列的设计意图

3.1 每个CPU一个cfs_rq，不是全局一个

CFS不是全局一个队列，而是每个CPU一个cfs_rq，配合调度域做负载均衡。这一点设计意图很明确：避免全局锁竞争。如果把所有CPU的任务塞进同一个队列，每次入队出队都要拿一把大锁，多核扩展性会非常差。所以内核为每个CPU的rq内嵌了一个cfs_rq，这个CPU上所有CFS实体的运行信息都记录在里头。

struct cfs_rq在5.x里长这样，我删减了组调度相关的嵌套细节，保留主路径：

struct cfs_rq { struct load_weight load; unsigned int nr_running; unsigned int h_nr_running; u64 exec_clock; u64 min_vruntime; struct rb_root_cached tasks_timeline; struct sched_entity *curr; struct sched_entity *next; struct sched_entity *last; unsigned int idle_nr_running; unsigned int idle_h_nr_running; struct sched_avg avg; };

3.2 tasks_timeline：红黑树根与最左缓存

tasks_timeline类型是struct rb_root_cached，它不是普通的红黑树根，而是额外缓存了最左节点指针。CFS每次选任务都要取最左节点，如果每次都从根节点往下爬到最左，那是O(logN)的路径；有了缓存，直接取rb_leftmost就是O(1)。这个优化在进程数几百上千时收益非常明显。

这里插一句为什么选红黑树而不是最小堆。最小堆取最小值也是O(1)，但内核最终选了红黑树，主要原因是红黑树节点可以内嵌在struct sched_entity里，不需要单独分配；而且红黑树在平衡维护上比堆更灵活，对查找、插入、删除混合场景更友好。其实对调度器来说，任务数量一般不会特别大，红黑树的开销完全可接受，而它带来的内存内嵌设计让整个入队出队过程没有一次动态内存分配。

tasks_timeline里的红黑树排序规则很直接：按vruntime从小到大，键值就是se->vruntime。插入时用entity_before比较两个实体的vruntime，谁小谁靠左。

3.3 min_vruntime：全部排位赛的基准线

min_vruntime是CFS里最容易被忽略却最关键的字段。它的引入是为了解决一个根本问题：虚拟运行时间一直累加会越来越大，不同实体之间比较vruntime时，是拿绝对数值比，而不是相对值比。min_vruntime就像一个基准线，新任务、睡眠唤醒任务、CPU空闲后的任务，都会用它来校准自己的vruntime。

它的更新逻辑在update_min_vruntime：

static void update_min_vruntime(struct cfs_rq *cfs_rq) { u64 vruntime = cfs_rq->min_vruntime; if (cfs_rq->curr) vruntime = cfs_rq->curr->vruntime; if (cfs_rq->rb_leftmost) vruntime = min_vruntime(vruntime, cfs_rq->rb_leftmost->vruntime); cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime); }

这段代码看着绕，其实意图是：min_vruntime取"当前运行实体vruntime"和"红黑树最左节点vruntime"中较小的那个，同时保证min_vruntime自身单调不减（用max_vruntime防止回退）。为什么单调不减？因为所有实体的vruntime都在增长，如果基准线回退，新唤醒的任务会被错误地放得很靠前，造成调度不公平。

我举个实际例子。假设某CPU上所有任务都在睡眠，红黑树空了，min_vruntime已经涨到1000ms。此时一个任务醒来，如果没有min_vruntime校准，它的vruntime还是上次离开队列时的500ms，那它一醒就会排在队伍最前，连续抢占CPU。内核的做法是在唤醒路径的place_entity里把该实体的vruntime抬升到不早于min_vruntime - sysctl_sched_latency的位置，避免睡眠任务凭借"老资格"饿死其他任务。

3.4 负载与PELT调度平均

cfs_rq里还有load和avg字段。load是就绪队列上所有实体权重的总和，决定每个任务在该CPU上能分到的CPU时间比例。avg是sched_avg结构，维护PELT（Per-Entity Load Tracking）的统计数据，包括load_sum、util_sum、runnable_sum等。这个字段是负载均衡和CPU频率调度的数据来源。做过CPU调频或者看/proc/schedstat的人应该对util_avg不陌生，它就是由avg里的util_sum按半衰期衰减算出来的。

这里有一个容易混的概念：load是瞬时权重总和，avg是历史加权均值。瞬时负载可以用来做单次时间片计算，但做迁移决策时必须看历史均值，不然一个瞬时突刺就会导致负载均衡抖动。

4. 虚拟时间、权重和调度切片的计算

4.1 vruntime的计算逻辑

CFS的核心公平观是：每个任务获得的CPU时间应该与其权重成正比。为了实现这一点，内核把物理运行时间折算成虚拟运行时间vruntime，公式是：

vruntime增量 = 实际运行时间 * NICE_0_LOAD / se.load.weight

其中NICE_0_LOAD是固定值1024，也就是nice=0的权重。这个公式的意思很直白：权重越大，同样物理运行时间折算出的虚拟时间越小；在红黑树里就越靠左，下次更可能被选中。

举个例子，两个任务A和B，A权重1024（nice=0），B权重335（nice约等于5）。两者都运行10ms。A的vruntime增加10 * 1024 / 1024 = 10ms，B的vruntime增加10 * 1024 / 335 ≈ 30.5ms。因为A的vruntime涨得慢，被选中的频率远高于B，自然拿到的CPU时间更多。这就是CFS"完全公平"在数学上的落地——不是让每个人运行一样长，而是让每个人跑完自己的权重比例。

4.2 nice值与权重的映射表

nice值每个程序员都见过，但很多人不知道它是怎么映射到权重的。内核里有一张静态表sched_prio_to_weight，覆盖nice从-20到19共40个等级：

static 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倍缩放。也就是说nice每降低1，优先级提升约25%。两个nice=0的任务竞争一个CPU，时间是1:1；一个nice=0和一个nice=-5的任务竞争，权重比是1024:3121，CPU时间比例大约1:3。这个表在设计上是有讲究的——它保证nice值对调度优先级的影响大致均匀，不会出现nice=0和nice=-1差距微小、而nice=-19到-20差距巨大的情况。

4.3 调度周期和任务时间片

知道了实体权重和队列总权重，就可以算时间片了。CFS的调度周期由sched_slice决定，底层是__sched_period：

static u64 __sched_period(unsigned long nr_running) { if (unlikely(nr_running > sched_nr_latency)) return nr_running * sysctl_sched_min_granularity; else return sysctl_sched_latency; }

sysctl_sched_latency默认6ms，sysctl_sched_min_granularity默认0.75ms，sched_nr_latency = 6 / 0.75 = 8。所以当运行任务数不超过8个时，调度周期固定6ms；超过8个后，调度周期随任务数线性增长，每个任务保证至少0.75ms的运行机会。

单个任务在一个调度周期内获得的时间片为：

time_slice = period * se.load.weight / cfs_rq.load

假设4个任务，nice都为0，总权重4096，周期6ms，每个任务时间片就是6ms * 1024 / 4096 = 1.5ms。4个任务轮流，每人1.5ms，一圈6ms。如果其中一个nice=0任务权重变成1549（相当于nice=-6），总权重4621，则它的时间片是约2ms，其他三个任务各约1.33ms。

4.4 新任务、睡眠任务的vruntime修正

CFS里有个经典问题：新任务创建出来，如果不做任何处理，它的vruntime为0，肯定比老任务的vruntime小，会被红黑树排到最左边，直接抢占CPU，老任务可能被饿着。内核的处理方式是place_entity：

static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial) { u64 vruntime = cfs_rq->min_vruntime; if (initial && sched_feat(START_DEBIT)) vruntime += sched_vslice(cfs_rq, se); if (sched_feat(GENTLE_FAIR_SLEEPERS) && !initial) { unsigned long thresh = sysctl_sched_latency; vruntime -= thresh; } se->vruntime = max_vruntime(se->vruntime, vruntime); }

initial表示新进程。新进程的vruntime被设置为min_vruntime + sched_vslice，也就是在基准线上再加一个自己的虚拟时间片，避免新任务秒杀老任务。非初始唤醒且开启了GENTLE_FAIR_SLEEPERS时，vruntime会被允许比min_vruntime略低一点，但不超过一个调度延迟的阈值，这给了睡眠任务一点补偿，又防止它攒太多"时间债"导致CPU饥饿。

5. 从核心结构反推调度问题的排查经验

5.1 用sched_debug观察cfs_rq实时状态

排查调度问题，我第一个动作就是打开/proc/sched_debug。它会把每个CPU的cfs_rq信息打出来，包括nr_running、min_vruntime、curr->pid、红黑树左右子树数量等。我经常用一个命令快速抓取关键行：

grep -E "cfs_rq\[[0-9]+\]|min_vruntime|curr->pid|nr_running" /proc/sched_debug

这里有几个看数据的经验。如果某个CPU的cfs_rq里nr_running长期为0但系统负载很高，说明任务可能都被分到其他CPU上了，要用schedstat看是不是负载均衡失效。如果两个CPU的min_vruntime差得非常大，比如一个在1000ms一个在50000ms，说明两个队列上的任务虚拟时间基准严重不一致，通常是因为迁移太频繁或者休眠任务太多，这时候要结合PELT的util_avg判断是负载不均还是虚拟时间漂移。

5.2 用ftrace和perf验证字段变化

光看静态快照不够，还得跟踪动态变化。我用ftrace的sched_switch事件抓过调度上下文切换，再用perf sched做过延时分析。但如果你想验证的是vruntime在具体路径上怎么更新，我建议在关键函数上挂trace_printk或者用kprobe：

echo 'p:enqueue_entity __enqueue_entity se=%di cfs_rq=%si' >> /sys/kernel/debug/tracing/kprobe_events echo 1 > /sys/kernel/debug/tracing/events/kprobes/enable

在实际生产环境我不会随便挂kprobe，但在实验室环境验证"负载权重对时间片的影响"很管用。比如我写一个绑核的高CPU任务，另一个任务nice从0调到-10，观察sched_switch里的运行时间片变化，基本能对应上4.3节算出的理论值。内核调度器的数学公式不是摆设，实测偏差通常很小。

5.3 常见问题和避坑清单

做调度相关开发这几年，我整理过一份高频问题清单，很多都能从核心结构入手：

还有一个容易踩的坑：修改/proc/sys/kernel/sched_child_runs_first会影响fork出来的子进程是否先于父进程运行。这个参数本质上是让子进程的se.vruntime设置得比父进程更靠左。很多人改完发现行为不像预期，主要是因为现在内核里这个参数受sysctl_sched_child_runs_first和START_DEBIT共同影响，新进程既要加min_vruntime又要加延迟补偿，叠加后的效果和直觉会有偏差。

另外，做CPU绑核优化时务必注意：taskset绑核不改变任务的调度实体属性，vruntime和load仍然是按全局调度类维护的。如果你看到一个绑核任务在某CPU上红黑树里长期靠右，先别怀疑绑核没生效，要去看该CPU上其他任务的权重是不是设得更高。

在我实际调试里，最值得反复咀嚼的一个点就是：CFS的一切设计都是在"公平"和"效率"之间找平衡。红黑树、min_vruntime、PELT这些结构，单个拎出来都不复杂，但组合起来就成了一个能支撑几千进程稳定运行的系统。所谓"核心结构的用意"，说到底就是每个字段都承载了一个明确的调度目标，当你带着问题去看这些字段时，调度器的行为就不再是黑盒了。