做内核调度器分析的人都知道CFSCompletely 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_classDeadline调度类、rt_sched_class实时调度类、fair_sched_classCFS、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有意义实时进程主要用rtDeadline任务用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变成1load被累加到cfs_rq上。然后调用place_entity设置vruntime如果这是一个新任务vruntime会被更新为cfs_rq-min_vruntime再加上一个初始虚拟时间片防止新任务一上来就把老任务挤掉。之后调用__enqueue_entity通过红黑树插入算法把run_node挂到合适位置。接下来调度器调用pick_next_task_fairpick_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_vruntimestatic 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结构维护PELTPer-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也就是nice0的权重。这个公式的意思很直白权重越大同样物理运行时间折算出的虚拟时间越小在红黑树里就越靠左下次更可能被选中。举个例子两个任务A和BA权重1024nice0B权重335nice约等于5。两者都运行10ms。A的vruntime增加10 * 1024 / 1024 10msB的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%。两个nice0的任务竞争一个CPU时间是1:1一个nice0和一个nice-5的任务竞争权重比是1024:3121CPU时间比例大约1:3。这个表在设计上是有讲究的——它保证nice值对调度优先级的影响大致均匀不会出现nice0和nice-1差距微小、而nice-19到-20差距巨大的情况。4.3 调度周期和任务时间片知道了实体权重和队列总权重就可以算时间片了。CFS的调度周期由sched_slice决定底层是__sched_periodstatic 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默认6mssysctl_sched_min_granularity默认0.75mssched_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。如果其中一个nice0任务权重变成1549相当于nice-6总权重4621则它的时间片是约2ms其他三个任务各约1.33ms。4.4 新任务、睡眠任务的vruntime修正CFS里有个经典问题新任务创建出来如果不做任何处理它的vruntime为0肯定比老任务的vruntime小会被红黑树排到最左边直接抢占CPU老任务可能被饿着。内核的处理方式是place_entitystatic 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或者用kprobeecho 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 常见问题和避坑清单做调度相关开发这几年我整理过一份高频问题清单很多都能从核心结构入手现象可能的结构原因排查方向某个任务CPU占用极低se.vruntime被抬得过高红黑树位置太靠右检查是否有任务反复睡眠唤醒触发GENTLE_FAIR_SLEEPERS补偿过大多核间负载不均某个cfs_rq的avg和load异常看PELT半衰期统计排除瞬时负载干扰频繁上下文切换sysctl_sched_min_granularity过小任务时间片被切碎检查调度周期和nr_running是否超过nr_latency新进程抢占太猛START_DEBIT特性被关闭新进程vruntime没加补偿查看/sys/kernel/debug/sched/features确认特性开关实时任务卡死普通任务fair_sched_class被RT调度类压制这是调度类优先级设计使然看RT任务的CPU占用还有一个容易踩的坑修改/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这些结构单个拎出来都不复杂但组合起来就成了一个能支撑几千进程稳定运行的系统。所谓核心结构的用意说到底就是每个字段都承载了一个明确的调度目标当你带着问题去看这些字段时调度器的行为就不再是黑盒了。
Linux CFS调度器核心数据结构解析：sched_entity与cfs_rq设计意图
做内核调度器分析的人都知道CFSCompletely 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_classDeadline调度类、rt_sched_class实时调度类、fair_sched_classCFS、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有意义实时进程主要用rtDeadline任务用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变成1load被累加到cfs_rq上。然后调用place_entity设置vruntime如果这是一个新任务vruntime会被更新为cfs_rq-min_vruntime再加上一个初始虚拟时间片防止新任务一上来就把老任务挤掉。之后调用__enqueue_entity通过红黑树插入算法把run_node挂到合适位置。接下来调度器调用pick_next_task_fairpick_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_vruntimestatic 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结构维护PELTPer-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也就是nice0的权重。这个公式的意思很直白权重越大同样物理运行时间折算出的虚拟时间越小在红黑树里就越靠左下次更可能被选中。举个例子两个任务A和BA权重1024nice0B权重335nice约等于5。两者都运行10ms。A的vruntime增加10 * 1024 / 1024 10msB的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%。两个nice0的任务竞争一个CPU时间是1:1一个nice0和一个nice-5的任务竞争权重比是1024:3121CPU时间比例大约1:3。这个表在设计上是有讲究的——它保证nice值对调度优先级的影响大致均匀不会出现nice0和nice-1差距微小、而nice-19到-20差距巨大的情况。4.3 调度周期和任务时间片知道了实体权重和队列总权重就可以算时间片了。CFS的调度周期由sched_slice决定底层是__sched_periodstatic 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默认6mssysctl_sched_min_granularity默认0.75mssched_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。如果其中一个nice0任务权重变成1549相当于nice-6总权重4621则它的时间片是约2ms其他三个任务各约1.33ms。4.4 新任务、睡眠任务的vruntime修正CFS里有个经典问题新任务创建出来如果不做任何处理它的vruntime为0肯定比老任务的vruntime小会被红黑树排到最左边直接抢占CPU老任务可能被饿着。内核的处理方式是place_entitystatic 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或者用kprobeecho 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 常见问题和避坑清单做调度相关开发这几年我整理过一份高频问题清单很多都能从核心结构入手现象可能的结构原因排查方向某个任务CPU占用极低se.vruntime被抬得过高红黑树位置太靠右检查是否有任务反复睡眠唤醒触发GENTLE_FAIR_SLEEPERS补偿过大多核间负载不均某个cfs_rq的avg和load异常看PELT半衰期统计排除瞬时负载干扰频繁上下文切换sysctl_sched_min_granularity过小任务时间片被切碎检查调度周期和nr_running是否超过nr_latency新进程抢占太猛START_DEBIT特性被关闭新进程vruntime没加补偿查看/sys/kernel/debug/sched/features确认特性开关实时任务卡死普通任务fair_sched_class被RT调度类压制这是调度类优先级设计使然看RT任务的CPU占用还有一个容易踩的坑修改/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这些结构单个拎出来都不复杂但组合起来就成了一个能支撑几千进程稳定运行的系统。所谓核心结构的用意说到底就是每个字段都承载了一个明确的调度目标当你带着问题去看这些字段时调度器的行为就不再是黑盒了。
