做内核调度这块的代码阅读总有一种在拆精密机械表的感觉。CFS调度器里的pick_next_task_fair是每次发生进程切换几乎都要执行的热点路径而它内部的__pick_first_entity和__pick_next_entity两个函数加起来也就十几行却是整棵红黑树选择和遍历的入口。很多人看内核源码时会把这两个函数直接跳过觉得不过是rb_first和rb_next的封装但恰恰是这两个小函数决定了CFS在“最亏欠CPU的任务”之外还能怎么灵活补偿next、last、skip这些特殊情况。这篇笔记不聊宏观调度策略专门从源码、数据结构、调用场景到调试心得把这两个函数彻底过一遍。适合正在啃Linux内核进程管理、尤其是想弄明白CFS调度器怎么选下一个任务的人。1. CFS调度器和pick_next_task_fair在忙什么1.1 CFS用一个红黑树维护“最该跑”的任务CFS全称Completely Fair Scheduler中文叫完全公平调度器。它的核心思想不是给每个进程分一个固定时间片而是维护一个“虚拟运行时间”vruntime谁跑的CPU时间少、谁的vruntime小谁就更有资格被调度。你可以把这个机制想象成一个自助餐排队窗口每个人都记录自己已经取餐的时长CFS每次安排下一个窗口都会选那个等待最久、吃的最少的人。为了让“找最该跑的任务”这件事足够快内核把当前CPU上所有可运行的调度实体sched_entity按vruntime作为key放进一棵红黑树。红黑树是一种自平衡二叉搜索树插入和删除都是O(logN)而且最左边的节点天然就是vruntime最小的节点。如果有1000个任务在排队调度器不需要遍历所有任务直接拿树的最左节点就是答案。CFS能做到大规模任务下依然很低的调度开销这个树形结构是基础。1.2 pick_next_task_fair是fair调度类的选人入口调度器的核心切换函数是__schedule它会调用pick_next_task再根据当前CPU上运行队列的优先级依次询问各个调度类是否有可运行的任务。对于普通进程来说走的是fair调度类入口就是pick_next_task_fair。整个调用关系大概是__schedule() - pick_next_task(rq, prev, rf) - for_each_class(...) - fair_sched_class.pick_next_task pick_next_task_fair - pick_next_entity() - __pick_first_entity() - __pick_next_entity()pick_next_task_fair从rq-cfs这个就绪队列出发先选一个调度实体。如果选到的是普通任务就直接返回对应的task_struct如果开启了组调度CONFIG_FAIR_GROUP_SCHED选出的实体下面可能还挂着一个子CFS就绪队列那就要继续往下钻直到选中真正的任务。而每次从某个cfs_rq上“选一个实体”这件事核心就是pick_next_entity。pick_next_entity()里最先干活的函数就是__pick_first_entity在需要跳过或补偿时会用到__pick_next_entity。1.3 为什么单独抠这两个小函数很多读源码的人在这两个函数上一扫而过觉得底层API不复杂。但恰恰因为短反而掩盖了它们的设计地位__pick_first_entity提供了一个确定的最左起点__pick_next_entity提供了在起点不可用时往后探测的能力。CFS所有关于last、next、skip的调度优化最后都要靠这两个函数兜底。不理解它们就看不懂pick_next_entity里那些if分支为什么存在也不知道set_next_entity摘除节点的时候到底发生了什么。所以我建议所有想啃调度器的人先把这两个函数嚼碎。这也是本篇笔记最核心的价值。2. 动手之前先备好三块地基2.1 调度实体和CFS就绪队列的关键字段分析代码之前先搞清楚两个核心结构体。struct sched_entity也就是调度实体代表一个可以被调度的单位。它可能是某个进程也可能是某个任务组task group。我们最关心的字段是字段类型作用vruntimeu64虚拟运行时间红黑树的排序keyrun_nodestruct rb_node嵌入的红黑树节点用来挂到树上on_rqunsigned long是否已经入队挂到就绪队列上parent指针组调度时指向父实体另一个是struct cfs_rq也就是CFS就绪队列。它挂在每个CPU的rq上核心字段包括tasks_timeline、nr_running以及三个“调度伙伴”指针next、last、skip。tasks_timeline在较新内核里是struct rb_root_cached类型不是普通rb_root。普通rb_root只保存树根而rb_root_cached额外缓存了一个rb_leftmost指针这样取最左节点就可以做到O(1)。2.2 红黑树的“最左节点”为什么那么重要红黑树的排序规则是左子节点key小于父节点右子节点key大于父节点。因此树的最左节点就是当前vruntime最小、也就是最“亏欠”CPU的调度实体。CFS几乎总是优先运行它这保证了整体公平。但为什么不用普通的二叉搜索树因为普通二叉搜索树在极端插入顺序下会退化成链表查找就变成O(N)。红黑树通过颜色约束维持了树的平衡保证了最坏情况下插入、删除、查找都是O(logN)。而为了进一步降低调度开销内核引入rb_root_cached缓存leftmost使得取最左节点从O(logN)降到O(1)。插入和删除时rbtree通用代码会同步维护leftmost。这一点对调度路径很重要高频操作里少一次树遍历系统整体延迟都能改善。2.3 rb_entry和container_of从节点反推结构体红黑树的操作返回的是struct rb_node *指针但我们需要的是这个节点所在的结构体比如struct sched_entity。内核的通用做法是结构体里内嵌节点然后通过container_of宏根据成员偏移反推整个结构体地址。rb_entry就是专门为红黑树封装的container_of#define rb_entry(ptr, type, member) container_of(ptr, type, member)比如在__pick_first_entity里返回rb_entry(left, struct sched_entity, run_node)意思就是left指针指向的是某个sched_entity内部的run_node成员从这个指针位置减去run_node在sched_entity里的偏移量就得到这个sched_entity的起始地址。这是Linux内核里最常见的“侵入式容器”思想。很多人第一次看会觉得绕但只要理解了偏移量后面的源码就很容易读通。2.4 rb_root_cached的leftmost缓存如何维护rb_root_cached的结构是struct rb_root_cached { struct rb_root rb_root; struct rb_node *rb_leftmost; };当向树里插入节点时rbtree代码会和新leftmost比较如果新节点更小就更新rb_leftmost。删除节点时如果删除的正好是leftmost就重新在右子树里寻找最左节点或者从父节点路径上找后继。rb_first_cached本质上就是return root-rb_leftmost没有任何遍历。对于调度器这种对延迟极其敏感的地方这种微优化是有实际意义的。我们在分析源码时也必须知道__pick_first_entity的快速返回不是魔法而是维护好的缓存。3. __pick_first_entity一次拿到最左侧实体3.1 函数源码逐行读基于我最常用的Linux 5.10内核版本__pick_first_entity实现如下static 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 rb_entry(left, struct sched_entity, run_node); }逻辑非常直白一共三步从cfs_rq-tasks_timeline取出缓存的最左节点如果最左节点为空说明这棵红黑树目前是空的直接返回NULL否则通过rb_entry把红黑树节点指针转换成sched_entity指针。这段代码没有任何循环也没有复杂的判断。但不要因为简单就轻视它它几乎是每次find下一个任务时都要执行的“第一个动作”。3.2 为什么用rb_first_cached而不是rb_first如果你去翻老版本内核比如Linux 3.x会发现这里曾经用的是rb_first(cfs_rq-tasks_timeline)。rb_first会从根节点一路往左走直到没有左子节点复杂度是O(logN)。后来内核把cfs_rq-tasks_timeline改成rb_root_cached这里就变成返回rb_leftmost复杂度直接降到O(1)。为什么这个优化重要因为调度路径是全局热点每次进程切换都会经过。如果系统里跑着几百个任务O(logN)的树遍历可能只是几十次指针跳转听起来不多但乘上每秒成千上万次切换再叠加cache miss开销就不容忽视了。内核调度器的优化一向是“积少成多”越是这种不起眼的点越能体现工程师的功力。3.3 空树和返回NULL的连锁反应当CFS队列里没有可运行的调度实体时__pick_first_entity返回NULL。注意这个返回值不是摆设。调用方pick_next_entity第一行就把返回值赋值给se同时保存为left后续判断里如果直接解引用left会panic。不过在实际执行流程中pick_next_task_fair在调用pick_next_entity之前已经通过类似sched_fair_runnable(rq)的判断确认队列里至少有一个可运行任务。因此__pick_first_entity返回NULL的情况理论上不会在正常路径下发生。这里的NULL判断更多是防御性编程也是内核红黑树API的一贯风格。但如果你在做调度器实验改动了nr_running的维护逻辑就可能踩到这个坑。后面的调试章节我会再展开。3.4 一个容易看走眼的细节run_node不在结构体开头rb_entry(left, struct sched_entity, run_node)这个宏写起来很顺但如果你在gdb或crash里打印left和se地址会发现它们不相等中间差了个偏移量。这是container_of的标准行为run_node字段在sched_entity里并不是第一个成员。有一次我调试时想通过红黑树节点直接看vruntime顺手就把rb_node地址当成sched_entity地址去偏移结果拿到的数值完全不对。后来老实用了rb_entry才意识到结构体布局的问题。所以如果你也在追调度器代码记住红黑树节点指针和调度实体指针是两个地址中间隔着偏移务必用宏转换。4. __pick_next_entity沿着中序遍历往后走4.1 函数源码逐行读__pick_next_entity的实现同样很精简static struct sched_entity * __pick_next_entity(struct sched_entity *se) { struct rb_node *next rb_next(se-run_node); if (!next) return NULL; return rb_entry(next, struct sched_entity, run_node); }入参是一个sched_entity函数首先取它的run_node然后调用rb_next得到红黑树中序遍历的后继节点。如果没有后继说明这个实体已经是树里vruntime最大的那个返回NULL。否则继续用rb_entry把后继节点转成sched_entity。这里要注意rb_next返回的是给定节点在树上的“中序后继”。对CFS红黑树来说中序遍历就是vruntime从小到大的顺序所以后继节点就是刚才那个节点之后“第二小”的实体。4.2 rb_next在红黑树里怎么找后继理解rb_next的算法对判断这个函数的开销和边界很有帮助。内核rbtree通用实现里rb_next的逻辑是如果当前节点有右子树那么后继就是右子树中最左的节点如果当前节点没有右子树就沿着parent指针向上回溯直到找到一个祖先节点它作为其父节点的左孩子存在那么这个祖先节点的父节点就是当前节点的后继。这个过程最坏也是O(logN)但通常很快。在CFS的场景里__pick_next_entity不会频繁调用只有pick_next_entity需要跳过skip或者某些特殊分支时才会用。因此相比__pick_first_entity的O(1)这个函数稍微重一些但整体影响不大。4.3 为什么需要一个“次小”的实体你可能会疑惑CFS不是应该每次都选vruntime最小的实体吗为什么还需要“次小”的原因是内核为了交互性和低延迟在真正选任务之前会看几个特殊的调度实体指针cfs_rq-next通常是刚刚被唤醒、希望它能尽快运行的实体cfs_rq-last上一次运行的实体可能希望它继续运行cfs_rq-skip当前想跳过的实体比如某些场景下不希望它立刻执行。当最左实体正好是skip或者next/last有抢占优势时调度器会放弃最左实体选择另一个。那选谁不能随便选也不能往vruntime更大的方向乱跳。此时就需要一个符合红黑树顺序的备选实体。__pick_next_entity就是做这个用的它沿着中序顺序找到当前实体的下一个也就是“次小”的候选。这样即使绕过了最左实体挑选结果依然保持公平语义。4.4 与__pick_first_entity配合的边界条件这两个函数是“取起点”和“取备份起点”的关系不是每次都必须配对使用。在pick_next_entity里通常先用__pick_first_entity拿到最左实体left。如果cfs_rq-skip left就调用__pick_next_entity(left)拿次小实体作为新的候选。但如果left不是skip却因为next/last条件最终选中了另一个非最左实体此时不会调用__pick_next_entity去取后继。还有__pick_next_entity是在入参实体的基础上往后找如果你传入的是一个不在树上的实体比如通过cfs_rq-next拿到的、尚未入队的实体rb_next的行为是未定义的有可能访问到无效节点。所以这个函数只应该用于树上的实体这一点要特别注意。5. 放回pick_next_task_fair全景选人的完整流程5.1 pick_next_entity的分支逻辑CFS真正做选择的核心在pick_next_entity它的简化版本是这样的static struct sched_entity * pick_next_entity(struct cfs_rq *cfs_rq) { struct sched_entity *se __pick_first_entity(cfs_rq); struct sched_entity *left se; if (cfs_rq-skip se) { se __pick_next_entity(se); if (!se) return NULL; } if (cfs_rq-next wakeup_preempt_entity(cfs_rq-next, left) 1) { se cfs_rq-next; } else if (cfs_rq-last wakeup_preempt_entity(cfs_rq-last, left) 1) { se cfs_rq-last; } return se; }这段逻辑可以拆成三种情况最左实体没有任何特殊标签直接返回它最左实体是skip调用__pick_next_entity往后挪一个拿次小实体最左实体不是skip但cfs_rq-next或cfs_rq-last被设置并且通过wakeup_preempt_entity判断它们更适合抢占那就可以不选最左而选next或last。这里__pick_first_entity和__pick_next_entity的配合方式一目了然前者给定起点后者提供“起点不可用”时的备选。5.2 next、last、skip到底是什么意思这三个指针是CFS为了优化交互体验引入的“小灶”机制但也经常让人困惑。cfs_rq-next通常在check_preempt_wakeup里被设置指向刚被唤醒的进程对应的调度实体。它的意图是如果这个唤醒进程的vruntime已经够小有资格抢占当前任务那就尽量让它尽快运行减少唤醒延迟。cfs_rq-last通常指向正在退出运行的实体或者上一次运行的实体目的是在某些情况下让上一个任务继续跑减小切换开销。cfs_rq-skip则是一个主动跳过标记比如在负载均衡或某些不公平场景下不想让某个实体立刻被选中。有了这三个指针CFS就不再是死板地“每次只选最左”而是在公平优先的前提下给特殊情况开了一个可控的口子。wakeup_preempt_entity函数就是闸门它通过比较两个实体的vruntime和调度粒度gran决定是否允许这个口子生效。理解了这一点再看pick_next_entity的if分支就有逻辑了。5.3 set_next_entity选中之后不只是返回pick_next_entity只是“找”出了合适的调度实体真正把它从树上摘下来、更新状态的是set_next_entity。这个函数会做几件事把选中的sched_entity从cfs_rq的红黑树上删除通常通过__dequeue_entity更新on_rq状态维护cfs_rq-last等指针做一些统计和调度组相关的更新。所以__pick_first_entity和__pick_next_entity并不是完整的调度选择全过程它们只负责选择阶段的前端。你如果只看到这两个函数会以为CFS只是遍历树其实真正的删除和入队操作还在后面。这也是我读代码时的一个心得一些小函数承担的是“侦察兵”角色后续的“大部队”还要继续推进。5.4 组调度下会被多次调用现代内核打开CONFIG_FAIR_GROUP_SCHED后调度实体可能对应一个任务组组下面又有自己的cfs_rq。这时候pick_next_task_fair就不是选一次就完事而是从根cfs_rq开始不断循环pick_next_entity(root_cfs_rq) - 得到组实体 group_cfs_rq(se) - 如果非空下钻到子队列 pick_next_entity(child_cfs_rq) - 继续选 ...直到选到task_struct每次回到循环顶部都要调用一次pick_next_entity。这也就意味着__pick_first_entity和__pick_next_entity在一次schedule中可能被多次执行而且每次面对的是不同层级的cfs_rq。每个cfs_rq里维护着自己的红黑树和next/last/skip指针。理解了这一点才知道为什么这两个函数必须设计得如此精简、高效。5.5 一个完整的选择时间线例子假设某个CPU的cfs_rq上有三个任务A、B、Cvruntime的大小关系是A B C红黑树最左是A。现在B刚刚被唤醒并且被标记为cfs_rq-next。那么pick_next_entity执行的流程是__pick_first_entity拿最左实体AA不是skip判断cfs_rq-nextB和leftA的关系。如果wakeup_preempt_entity(B, A) 1说明B更适合抢占于是把候选实体换成B返回B。如果B的vruntime并没那么小没有通过抢占阈值检查则返回A。这里面还有个容易忽略的点cfs_rq-next指向的B不一定已经插入红黑树它可能只是一个唤醒路径上临时保存的指针。而A是树上的实体。因此__pick_first_entity和__pick_next_entity只保证对树上节点的操作是安全的next/last则更多是“外部候选”的角色。这两类来源要分开看待。6. 调试这两个函数时踩过的坑6.1 不要搞错调度实体类型第一次调试__pick_first_entity时我想用kprobe打印最左实体的vruntime直接写了rb_entry(rb_first_cached(cfs_rq-tasks_timeline), struct task_struct, se.run_node)结果数据完全对不上。原因很简单红黑树上的调度实体可能是task_group的group entity不是task_struct。只有经过task_of(se)转换才能拿到task_struct。group entity和task entity共用同一个sched_entity结构但task_of这个宏的前提是se确实嵌在task_struct里。因此在调试时一定要先判断实体类型或者干脆用内核提供的task_of和cfs_rq_of等辅助宏不要自己乱转。6.2 nr_running与红黑树数量不一致我曾经在把实体从树里摘除的逻辑上做了个实验结果系统跑了一会儿就panic。看调用栈最后落到__pick_first_entity返回NULL但外层以为队列里有任务继续解引用。根本原因是我改了dequeue_entity的逻辑导致实体已经从树里摘除了但cfs_rq-nr_running没有正确减一。两个计数器不一致调度器就以为自己还有任务可选。排查这类问题第一步在pick_next_task_fair入口打印cfs_rq-nr_running和红黑树的节点总数第二步检查所有enqueue/dequeue路径。尤其是那些在entity状态切换时忘记更新计数器的改动很容易导致这种“树空但计数器非零”的诡异现象。6.3 next/last指针的生命周期问题cfs_rq-next和cfs_rq-last这两个指针的生命周期很微妙。正常内核在set_next_entity、put_prev_entity、check_preempt_wakeup等位置会维护它们。但如果你的调度器补丁改动了这些路径就可能让next指针指向一个已经被dequeue、甚至已经释放的实体。wakeup_preempt_entity再去访问它轻则调度行为错乱重则内存访问异常。所以我做一个经验总结每次改动pick_next_entity或者相关队列操作前先确认next、last、skip的赋值和清空时机。__pick_first_entity和__pick_next_entity本身不负责清理这些指针不要指望它们兜底。6.4 用kprobe观察这两个函数是否被调用如果你想验证调用关系可以用内核的kprobe机制。假设内核符号可见可以这样echo p:pick_first __pick_first_entity cfs_rq%di /sys/kernel/debug/tracing/kprobe_events echo p:pick_next __pick_next_entity se%di /sys/kernel/debug/tracing/kprobe_events echo 1 /sys/kernel/debug/tracing/events/kprobes/pick_first/enable echo 1 /sys/kernel/debug/tracing/events/kprobes/pick_next/enable cat /sys/kernel/debug/tracing/trace_pipe这样能看到一次调度里__pick_first_entity被调用了多少次__pick_next_entity是否出现以及入参地址。注意kprobe本身在热路径上也会带来较大开销最好在虚拟机或者单CPU环境下测试别在生产环境开着跑。6.5 ftrace限定CPU范围防止soft lockup比kprobe更直观的方式是用function_graph看调用链echo function_graph /sys/kernel/debug/tracing/current_tracer echo __pick_first_entity __pick_next_entity pick_next_entity /sys/kernel/debug/tracing/set_ftrace_filter echo 1 /sys/kernel/debug/tracing/tracing_on cat /sys/kernel/debug/tracing/trace调度器路径是所有进程共享的超高频路径开启ftrace后系统会变得很卡。我自己的习惯是先写set_ftrace_pid把追踪限制到某个空闲进程或者用trace-cmd record -e sched_switch这类更高层的事件而不是直接全系统function_graph。否则很容易触发soft lockup最后连恢复trace都要费半天劲。从我个人的实际调试体会来说__pick_first_entity和__pick_next_entity虽然代码量极小但它俩是CFS在选择实体时最底层的两个抓手。把这两个函数连同周边的pick_next_entity、set_next_entity一起搞清楚再去看进程调度、组调度、唤醒抢占都会顺畅很多。以后你如果遇到调度器相关的性能问题也可以先在trace里看看到底是总是选最左还是经常走到__pick_next_entity的补偿路径这本身就是很好的排查起点。