写这篇东西之前我先说一下自己写这篇文章的出发点。很多人在学Linux内核的时候一看到“进程调度”“O(1)调度器”就开始头大觉得这玩意儿离自己太远——我又不写内核懂这个干嘛但实际上你排查线上CPU飙高、进程卡死、容器频繁抖动的时候最终都会绕回调度器。O(1)调度队列虽然是2.6内核时代的老古董但它把“调度决策必须在常数时间内完成”这个思想玩到了极致后来的CFS完全公平调度器很多设计都是站在它的肩膀上。所以我想用一篇文章把进程切换和O(1)调度队列这两件事掰开揉碎讲清楚重点说它为什么能O(1)、双队列结构到底解决了什么问题以及我们在实际运维和开发中能拿这些知识做什么。这篇文章适合刚接触内核调度的人也适合被线上调度问题折磨过的同行希望看完你也能像我一样遇到调度问题的时候心里不慌。Linux系统进程切换与O(1)调度队列一个老内核调度器的拆解笔记1. 先搞懂进程切换上下文切换到底在切什么1.1 用户态与内核态的分界线讲调度之前必须先讲进程切换。很多人把进程切换想象成“CPU换个进程跑”这个说法没错但太粗糙了。进程切换的核心是上下文切换context switch它要保存的是一整套CPU的运行现场通用寄存器、程序计数器、栈指针、段寄存器、EFLAGS标志位还有浮点寄存器现在叫FPU/AVX状态。为什么要保存这么多因为CPU是共享的一个进程让出CPU之后下一个进程拿到的必须是干干净净的现场不能残留上一个进程的寄存器内容否则程序逻辑立刻乱掉。这里先建立一个关键概念进程切换发生在内核态。用户程序跑着跑着一旦发生系统调用、中断或者异常CPU就会从用户态切到内核态。内核态和用户态的分界线靠CS段寄存器的CPLCurrent Privilege Level位维持CPL0是内核态CPL3是用户态。一旦进入内核态执行的代码就不再是应用程序的代码了而是内核的代码——比如schedule()调度函数。也就是说所有调度行为都发生在“进程让出CPU、进入内核态”这个前提之下没有内核态入口就没有调度这回事。很多初学者会把“用户态→内核态”和“进程A→进程B”这两件事搞混。前者是同一进程从用户栈切到内核栈后者是不同进程之间的切换。用户态→内核态只需要切换栈指针和加载内核代码段进程A→进程B则要把整个CPU现场都换掉。O(1)调度器优化的正是后者这种“进程间切换”的决策和批量切换过程。1.2 从syscall到schedule()的关键路径一个进程主动让出CPU最典型的路径是这样的进程A在用户态调用sched_yield()或阻塞在wait_event这个系统调用进入内核最终触发schedule()。schedule()做的事可以简化成三步挑选下一个进程、切换地址空间如果需要、切换硬件上下文。O(1)调度器对应“挑选下一个进程”这一步做了常数时间优化而“切换硬件上下文”则一直依赖体系结构相关的汇编代码。x86平台上的进程切换关键代码在arch/x86/kernel/process_32.c或process_64.c里核心是__switch_to这个函数。它做的事情包括保存当前进程的内核栈指针到task_struct-thread.sp加载下一个进程的内核栈指针交换TSS任务状态段中的esp0字段以及切换FS/GS等段寄存器。esp0这个东西值得多说一句——它是CPU从用户态陷入内核态时自动加载的内核栈顶。每个进程都有自己的内核栈所以每次切换进程都必须把TSS里的esp0改成新进程的内核栈顶否则中断一来CPU会把栈指针指向错误的栈内核直接崩掉。我当年第一次读这段代码时就是卡在esp0这个点搞明白之后整个上下文切换的链路就顺了。除了主动让出还有被动切换。最常见的是时钟中断每个tick通常1ms或10ms触发一次硬件中断中断处理完会检查当前进程的时间片是否耗尽如果耗尽就设置need_resched标志在中断返回路径上跳进schedule()。这条路径叫“中断返回时调度”好处是调度决不会被硬生生插入到用户态指令流中间而是等到一个安全的边界才切换。这也是为什么Linux的调度延迟不是纳秒级而是毫秒级的一个原因——它不追求极致抢占而是追求安全与稳定。1.3 实测观察怎么知道系统在做上下文切换你不一定需要读汇编才能感知进程切换。Linux提供了一堆现成的观测手段vmstat 1输出里的cs列就是每秒上下文切换次数。/proc/stat里面有ctxt字段记录系统启动以来的总切换次数。pidstat -w 1按进程查看自愿切换cswch和非自愿切换nvcswch。perf stat -e context-switches ./app统计程序运行期间的切换次数。我自己的经验是如果cs列长时间飙到几万甚至几十万系统通常处于“线程风暴”状态——大量线程在互相争抢锁频繁睡眠唤醒调度器忙得团团转。O(1)调度器在这种场景下虽然能快速决策但庞大的切换开销本身也会拖垮性能。这提醒我们调度优化的尽头往往是应用层设计问题而不是内核参数问题。2. O(1)调度队列凭什么“O(1)”2.1 140个优先级链表把排队从“线性扫描”变成“直接索引”O(1)调度器最核心的数据结构就是runqueue运行队列。每个CPU都有一个自己的runqueue比如双核CPU就有两个。每个runqueue里维护了两组优先级链表数组一组叫active一组叫expired各自有140个链表头对应140个优先级。这140个优先级从0到1390到99是实时优先级RT100到139是普通优先级。普通进程默认优先级是120对应nice值0。nice值每增减1优先级就增减1。注意这里有个反直觉的点数值越小优先级越高。所以nice-20的进程优先级是100是普通进程里最高的一档nice19的进程优先级是139是最低的一档。为什么要用140个链表而不是用一个队列因为调度器每次选下一个进程时如果从队头扫到队尾去找优先级最高的进程那复杂度就是O(n)。进程越多选进程越慢。而用140个链表再加上一个优先级位图bitmap就可以做到“一眼定位”看看位图里从第0位到第139位哪一位是1就知道非空链表中优先级最高的是哪一档然后直接摘链表头节点就行。这个bitmap的设计非常漂亮。140位对应20个32位字或者5个64位字。在内核里查找第一个非空链表时可以先按字为单位扫描找到非零字之后再用一条bsfl指令bit scan forward直接算出是第几位。整个过程没有任何循环遍历进程列表的操作时间复杂度严格O(1)。2.2 active/expired双队列为什么不能让进程原地复用时间片O(1)调度器的第二个灵魂设计是双队列轮转。简单说每个runqueue都有两个队列active队列里装的是“还有剩余时间片”的进程expired队列里装的是“时间片耗尽”的进程。调度器永远只从active队列选进程当active队列里某个进程的时间片用完就把它移到expired队列并按照一定的规则重新计算它的新时间片。当active队列整个空了调度器做一个常数时间的指针交换——把active和expired两个指针互换原来的expired队列变成新的active队列新一轮调度周期开始。你可能会问为什么时间片用完了不直接给他续上还非要先挪到expired队列里去这里有个关键设计动机保证调度公平性的批量处理。如果进程A用完时间片立刻续期它就能一直占着CPU低优先级进程永远轮不到。双队列强制“先来后到”——所有时间片耗尽的进程都排到expired队列尾部只有当前active队列里所有进程都走完一轮它们才会被重新放行。这跟银行排队叫号是一个道理所有人都得排队不能因为你是VIP就反复插队。有人可能觉得那这不就是原始的round-robin吗不完全是。因为它不是纯轮转而是“优先级轮转”的混合体高优先级进程可以被选中多次低优先级进程在active队列里饿不死一个调度周期内至少能跑一次但也不会抢占高优先级进程的配额。2.3 常数时间的调度决策O(1)到底省了什么O(1)的“1”不是一个字面意义上的操作数说的是无论系统里有多少个进程、多少个CPU调度器挑选下一个进程的时间都一样。我们要对比一下在旧版的Linux 2.4调度器里每次调度都要遍历整个任务列表挨个计算“好细胞”权重goodness选出一个分数最高的进程。进程数几百个的时候还好上千个线程的时候就明显感觉调度开销上来了。这个算法本质是O(n)的进程数量直接决定选进程的时间。多核时代到来之后这种O(n)调度的扩展性问题会非常致命。O(1)调度器用三个手段彻底解决了这个问题bitmap索引找最高优先级非空链表O(1)双向链表节点从链表头摘进程、往链表尾挂进程O(1)指针交换active队列耗尽后切换双队列O(1)。这三个“O(1)”拼起来调度决策的耗时就跟进程数无关了。这正是“O(1)调度队列”名字的由来。我们现在回头看CFS调度器Linux 2.6.23开始又把调度器的数据结构换成了红黑树选最左节点是O(log n)看着好像比O(1)退步了但实际上CFS追求的是完全公平的虚拟运行时间模型红黑树换来的公平性收益远大于那点查找开销。不过O(1)调度器锁定的“常数时间内做决策”这个目标始终是调度器设计的黄金准则。3. 时间片、交互性与负载均衡是怎么配合的3.1 时间片计算的来龙去脉其实没有人均一份O(1)调度器里每个进程的时间片不是固定不变的。内核里有一套动态计算规则进程优先级越高时间片越长优先级越低时间片越短。这不是拍脑袋定的它的逻辑是高优先级进程通常承担关键任务给它更长的时间片能减少切换次数让它一口气干完低优先级进程给短时间片保证它们频繁让位不至于拖慢高优先级进程。具体公式可以简化为时间片以tick为单位约等于(140 - 优先级) * 某个系数。优先级100的进程时间片最长优先级139的进程时间片最短。这个规则保证了调度器在“优先级高的多跑”和“低优先级的不饿死”之间做了折中。这里有一个值得注意的细节时间片大小和交互性识别是联动计算的。交互性强的进程比如文本编辑器、Shell往往频繁等待用户输入实际占用CPU的时间很少。内核会给这类进程一个“交互性奖励”动态调高它们的优先级、延长时间片让它们能在用户敲键盘的时候迅速响应。相反CPU密集型进程会被逐渐调低优先级把资源让给交互进程。这个设计在单核时代很聪明但到了多核时代就露怯了——它依赖“睡眠时间/运行时间”的统计而统计是全局的不看CPU。于是CFS后来果断抛弃了这套“预测进程行为”的思路改成了完全按权重分配CPU时间的模型你权重高你就分得多我不管你交互不交互。3.2 tick处理与进程抢占调度器是怎么“动起来”的O(1)调度器不是等进程主动让出CPU才工作它还有一套周期性的驱动机制叫tick调度。每个CPU上的时钟中断触发时内核会调用scheduler_tick()这个函数做几件事找到当前正在运行的进程把它的时间片计数减1如果时间片耗尽把进程移到expired队列如果当前进程的优先级比active队列里最高优先级进程低就设置need_resched标志返回中断路径检查到need_resched后调用schedule()。这个过程说明了几件事。第一O(1)调度器是“按tick驱动”的抢占式调度器它允许高优先级进程抢占低优先级进程但抢占粒度受限于tick周期——不会在进程运行到一半的任意指令处打断而是在下一个时钟中断边界上检查。第二时间片的减少是离散的每次tick减1而不是用高精度定时器纳秒级扣减这决定了它的调度延迟上限大约是几个tick。我经常跟人讲理解tick调度是理解整个Linux调度行为的钥匙。很多线上问题表现为“进程明明优先级很高却响应很慢”排查到最后往往发现是tick周期太大比如HZ10010ms才检查一次或者CPU被其他中断长期抢占导致need_resched标志虽然置上了但调度路径迟迟走不到。3.3 多核负载均衡O(1)调度器怎么把进程分配到CPU上O(1)调度器每个CPU一个runqueue就带来了新的问题CPU0忙死、CPU1闲死怎么办于是内核里有一个**负载均衡load_balance**机制。它不是每时每刻都在搬进程而是定时触发——每个CPU在空闲的时候或者周期性tick里会去看看其他CPU的runqueue如果自己的队列空了或者明显比别的CPU空闲就从别的CPU的runqueue里“偷”一些进程过来。具体的偷法很有意思。它不是随便从对方的队列头拿一个而是尽量拿对方队列尾部、优先级最低的进程。为什么是尾部因为头部进程优先级高被拿走后对源CPU的响应延迟影响大尾部进程优先级低影响相对小。而且一次不会拿太多只拿必要的数量避免“刚搬过来又被搬回去”的乒乓效应。实际线上调优时有两个跟负载均衡相关的点经常被问到CPU affinity亲和性通过sched_setaffinity把进程绑到指定CPU可以有效避免它被load balance搬来搬去。对于缓存敏感型的应用比如大量使用本地内存数据的程序绑核收益非常明显。irqbalance中断亲和性分配不当会导致某个CPU被硬中断淹没间接造成调度延迟。这是负载均衡容易忽略的盲区。还有一个必须提的坑O(1)调度器的负载均衡只考虑“进程数量”不太考虑“CPU时间占用率”。A和B两个CPUA上有两个CPU密集进程B上有10个睡眠进程从进程数看B负载更高实际A才最忙。这个缺陷在CFS时代通过load权重统计修正了但O(1)调度器时期确实存在一些场景下负载不平衡的案例。理解这个历史局限对读老代码或者排查老系统很有帮助。4. 实操排查调度器视角下的性能问题4.1 查看调度器状态从/proc和命令行快速判断面对一个卡顿或挂死的系统怎么快速判断调度器有没有出问题我自己有一套固定的排查路径分享给读者参考。第一板斧是看平均负载和上下文切换。uptime看1/5/15分钟负载vmstat 1看r运行队列长度和cs上下文切换次数。如果r远大于CPU核数说明进程在排队如果cs非常高说明系统在频繁切换可能是有锁竞争或者线程风暴。此时用pidstat -w 1进一步看哪些进程的非自愿切换nvcswch多这些进程多半是被抢占了。第二板斧是查优先级和调度策略。ps -eo pid,pri,ni,cls,comm可以看每个进程的优先级、nice值和调度类。cls列里TS表示普通分时调度O(1)的普通进程FF表示SCHED_FIFORR表示SCHED_RR。如果你发现某个实时进程长期占着CPU不松手那普通进程会被饿死系统表现为“假死”——ping不通、命令敲不动但内核还活着。第三板斧是针对单进程精确计时。strace -c -p pid附加到进程上看系统调用耗时分布或者perf sched record记录调度事件perf sched latency看调度延迟。这套组合拳在分析“为什么我的服务延迟突然飙到几百毫秒”这类问题时非常有效。我之前排查过一个中间件抖动问题花了一晚上最终定位到是它某个线程被rt进程长期抢占perf sched延迟数据里那个巨大的wait time一锤定音。4.2 优先级反转与SCHED_FIFO一个老生常谈却常踩的坑讲调度必然绕不开优先级反转priority inversion。经典场景是低优先级进程持有锁高优先级进程需要同一把锁于是高优先级进程被阻塞此时中优先级进程不需要锁抢占CPU导致低优先级进程没机会释放锁高优先级进程只能干等。在O(1)调度器时代内核提供了一些机制来缓解比如rt_mutex的优先级继承priority inheritance——当低优先级进程持有锁时临时把它提升到等待该锁的最高优先级进程的优先级等它释放锁后再降回来。但用户态的pthread_mutex默认是不做优先级继承的除非用PTHREAD_PRIO_INHERIT属性创建互斥锁。所以你做实时应用时对锁的语义要格外留心否则表面看着优先级调度策略没问题实际上优先级反转一直在发生。另一个容易踩的坑是SCHED_FIFO的滥用。它和SCHED_RR都属于实时调度类优先级范围0到99。SCHED_FIFO进程一旦运行除非自己阻塞或让出CPU否则同优先级的其他进程甚至更高优先级的普通进程都抢不走它。这意味着万一你的FIFO进程里有个死循环整个CPU就废了。生产环境里要用SCHED_FIFO一定要先评估它的最长运行时间并设置好看门狗。不然一次代码bug就能让全业务雪崩这我见过不止一次。提示chrt命令可以快速设置进程的调度策略。比如chrt -f -p 50 pid把进程设为SCHED_FIFO优先级50。但改实时优先级不是闹着玩的改之前先确认内核里RT throttling开启默认开启否则实时进程可以无限期霸占CPU系统直接瘫痪。4.3 CPU负载不均与affinity绑核还是放任多核系统上调度器负责让CPU负载均衡但均衡并不总是最优解。有两种典型场景需要人为干预一种是NUMA架构下的内存访问延迟。进程的内存可能只存在于某个NUMA节点如果调度器把进程搬到另一个节点的CPU上它访问本地内存就变成了跨节点访问延迟可能高出一倍。这时候用numactl绑定节点比让调度器自由均衡更划算。我见过一个数据库实例绑核前后吞吐相差将近30%因为跨节点访问的代价在内存密集型负载下特别明显。另一种是CPU密集型与IO密集型的混部场景。你希望CPU密集任务稳定跑在某几个核上IO密集型任务随便飘这时候用sched_setaffinity隔离CPU池。比如把8核分成两组0-3跑计算任务4-7跑IO任务各自绑定互不干扰。对比一下不做隔离的默认调度往往能看到显著的性能提升。不过要注意绑核不能太死板CPU数少而进程多的时候绑核反而会加剧排队这个要根据实际负载调配。对于跑在虚拟机里的业务也有一个额外心得如果宿主机开启了CPU overcommitguest里的调度器感知不到物理CPU的竞争容易自己把自己弄得忙乱。此时合理设置guest的vCPU数量和affinity映射效果往往比调guest内核参数更好。5. 从O(1)到CFS这套知识今天还有用吗写到这里肯定有人要问Linux 2.6.23之后都换成CFS调度器了O(1)调度队列已经进历史博物馆了学它还有意义吗我的答案是意义非常大尤其是这几个层面。第一O(1)调度器的双队列模型和bitmap优先级索引是理解内核数据结构设计的经典范例。你可以把它当成“如何用空间换时间、用索引换速度”的教学案例。很多后续的内核组件比如epoll、网络收包路径都用到了类似的思想用散列/位图快速定位活动对象而不是线性扫描。理解了O(1)调度队列就理解了一类内核优化范式。第二实时调度部分继承了下来。到今天为止Linux的实时任务依然用优先级0-99的链表管理这部分设计几乎没有变化。你生产环境里配SCHED_FIFO、配chrt、调/proc/sys/kernel/sched_rt_period_us本质上操作的就是O(1)调度器留下来的rt队列框架。所以排查实时任务相关问题时O(1)的知识依然是基础。第三从O(1)到CFS的演进史给了我们一个特别好的“为什么”视角。CFS为什么要抛弃优先级数组因为O(1)为了常数时间牺牲了公平性低优先级进程可能要等一轮active队列全部跑完才能再次运行而一轮的时间取决于active里所有进程的时间片总和。当系统里进程数目巨大时这个轮转周期会变得不可控交互体验和实时性都会恶化。CFS用红黑树虚拟运行时间解决了“怎么让所有进程按照权重精确分配CPU时间”的问题。知道这段历史的人看CFS代码和参数时就不会一头雾水——很多sysctl参数比如sched_latency_ns、sched_min_granularity_ns都跟这个设计权衡有直接关系。我自己的习惯是遇到调度相关的问题先问一句“这个特性继承自哪个时代”。如果是O(1)时代的遗产比如实时任务、affinity、优先级反转我就按老套路排查如果是CFS时代的机制比如cfs带宽控制、组调度我再切换到新框架。这种时间维度的知识视野能帮你在茫茫内核源码里快速找到方向。6. 几个排查工具和内核参数的速查笔记这一节作为实操补充把前面提到的知识点浓缩成可以直接照做的排查清单。说实话这些命令和参数单拎出来都不难但组合在一起能覆盖大部分调度类问题的排查场景。排查命令清单uptime看负载均值负载长期大于CPU核数说明有排队。top -H按线程维度看CPU占用定位烧CPU的线程。vmstat 1看r和cs判断调度器吞吐压力。pidstat -w 1按进程看自愿/非自愿切换次数。perf sched record/latency记录和分析调度延迟适合深度排查抖动。chrt -p pid查进程实时调度参数。cat /proc/pid/sched查进程具体的调度统计信息。cat /proc/sched_debug内核开启CONFIG_SCHED_DEBUG后这个文件会输出每个CPU的运行队列详细信息。常用内核参数适用于较新的CFS但排查思路同样适用于O(1)时期/proc/sys/kernel/sched_min_granularity_ns调度器保证每个进程最短运行时间。/proc/sys/kernel/sched_latency_ns调度器目标调度延迟。/proc/sys/kernel/sched_rt_period_us和sched_rt_runtime_us实时进程带宽上限设置。/proc/sys/kernel/sched_autogroup_enabled自动分组调度开关容器场景常会用到。调参的基本原则是改一个参数观察一段时间再改下一个切忌一把梭。我见过有人把sched_min_granularity_ns调得极低想“提高响应速度”结果调度切换频率暴涨系统整体吞吐反而下降。调度器本质上在跟延迟、公平性、吞吐量三方博弈没有银弹。7. 一点私货我排查调度问题时的几条经验最后聊点工具之外的感受。我踩过很多调度相关的坑有三条经验想单独强调一下。第一条慎用实时优先级。SCHED_FIFO不是银弹它是一把没有保险的快刀。我接手过一个数据库中间件的性能优化开发同学为了降低延迟把核心工作线程设成了SCHED_FIFO优先级80结果一个版本上线后整个宿主机的CPU被这个线程占满其他VM和容器全部卡死。排查到最后的结论就是实时优先级只适合明确知道执行时长上限的短小任务而且必须配合RT throttling使用。普通业务线程老老实实用SCHED_OTHER或者SCHED_BATCH就好。第二条切换次数是你最好的朋友。无论多大的应用性能问题只要把上下文切换次数拉出来跟正常基线一比很快就能找到方向。如果切换次数暴涨了几十倍优先怀疑锁竞争、线程频繁唤醒、或者CPU overcommit如果切换次数不高但延迟高优先怀疑中断处理、cpu affinity 或睡眠等待。这套二分法在无数次线上排查里都管用。第三条调度问题多半不是调度器的问题。这话有点绕但确实是我最深的体会。大多数被骂“调度器有bug”的现象最后都指向了应用层的不合理设计线程创建太多、锁粒度太大、忙等待、频繁轮询、SPINLOCK误用。调度器只是在忠实执行你给它安排的竞争规则。所以遇到调度引发的性能问题别急着改内核参数先把应用层的线程模型和锁设计捋一遍。省下来的调参时间拿去优化业务代码性价比高得多。我个人现在看内核调度相关的东西其实已经不怎么看O(1)那套代码了但当年被它训练出来的排查思路——先看队列结构再看时间片分配最后看负载迁移——一直延伸到了今天。如果你也想把内核调度这块吃透我建议找一台还在用2.6内核的老机器或者干脆用QEMU模拟把O(1)调度器的代码一行一行读一遍那种收获是看任何总结文章都替代不了的。