Linux进程切换与O(1)调度器：内核如何高效管理进程

想先聊一个挺有画面感的场景好几年前我在一台压力机上跑一个模拟程序开了几千个线程本意是榨干CPU结果top一看用户态CPU占比不高反而是si和系统态居高不下。一开始怀疑是锁竞争后来用perf一看发现大量的时间花在了schedule和try_to_wake_up上——问题不在业务代码而在于内核调度本身。那时候Linux内核还在2.6.x用的正是O(1)调度器。也就是从那次排查开始我才正经去啃了“进程怎么组织、进程怎么切换、调度器怎么选下一个进程”这三件事也才真正理解了这个系列前面聊的进程描述符、生命周期之后内核到底还有哪些家底。这篇就把这三块掰开揉碎讲清楚既写给准备面试的人也写给想搞明白自己机器上“那一瞬间到底发生了什么”的人。1. 先看进程怎么被“组织”起来不是简单存起来就完事很多资料一说进程管理上来就贴task_struct结构体列几十个字段看得人头大。但真正要理解内核的进程组织核心问题只有一个内核手里可能有几万个task_struct它得能在不同场景下快速找到“我想要的那一批”。这个需求决定了它不能只靠一套数据结构打天下。1.1 双向链表与哈希表两个最基础的组织第一套是全局双向循环链表。每个task_struct里有一个list_head tasks成员内核把所有进程串成一个大链表头是init_task也就是0号进程。这个链表最大的价值是“遍历全进程”你敲ps -e、用for_each_process宏或者内核在fork时检查进程数上限都是靠它。它的特点是简单可靠但只适合“挨个看”的场景不适合“精确找”。第二套是按PID查找用的哈希表。早期内核维护一个pid_hash数组通过pid_hashfn把PID散列到某个桶里冲突的进程用pid_chain串成小链表。为什么要哈希而不是直接拿PID当数组下标因为PID空间太大又是稀疏的直接建数组浪费得离谱。哈希表能做到平均O(1)定位而kill、wait这类频繁调用的路径最依赖它。到了3.x内核PID查找又换成了基数树idr那是后话但设计意图没变快速按PID定位task_struct。1.2 runqueue就绪进程的专属空间链表和哈希表解决的是“全量”和“按身份找”的问题但调度器关心的是另一类集合当前CPU上哪些进程是“就绪且可以跑”的。这个集合被单独组织成运行队列也就是runqueue。2.4时代的runqueue就是一条全局单链表所有就绪进程排在上面调度时从头到尾遍历。2.6开始改成了每CPU一个runqueue里面最关键的是两个prio_array_t数组分别叫active和expired。每个prio_array_t内部按优先级分成了140条链表同一优先级的进程排在一条链上。这样调度器选进程时不用遍历所有进程只要找到优先级最高的那条非空链表取队首就行。这个“每CPU独立”的设计也很讲究每个CPU只管自己的就绪队列锁竞争小而且进程在同一个CPU上反复调度cache命中率也高。1.3 等待队列睡眠与唤醒的桥进程因为等某个事件睡过去之后就不再占着runqueue了而是挂到对应的等待队列上。等待队列的结构是wait_queue_head_t加一串wait_queue_entry_t每个等待项里保存着进程描述符指针和一个回调函数。典型的用法是进程要等一个条件就初始化一个等待项把自己挂进队列然后把状态改成TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE最后调用schedule让出CPU。等条件满足时别的进程调用wake_up逐个把等待队列里的进程状态改回TASK_RUNNING并从队列摘除、重新塞进runqueue。这里有个经典的坑叫“睡眠竞态”如果在检查条件和真正睡眠之间唤醒事件提前发生了而进程又没进队列那这次唤醒就丢了进程可能永远睡下去。这也是为什么现代内核推荐用wait_event系列宏它在循环里帮你把“检查条件、挂队列、睡眠”包成一个原子操作。我自己排查过不少“进程突然D状态挂死”的问题最后几乎都能追到类似场景要么漏了唤醒要么唤醒和睡眠之间缺了锁保护。2. 进程切换内核里最敏感的一跳进程组织好了调度器也选出了下一个要跑的进程接下来就是“换人”。这个过程在教科书里叫上下文切换在内核代码里是context_switch。很多初学者以为切换就是把寄存器保存一下、恢复一下实际远没那么简单光看代码会绕晕。2.1 切换入口谁在调用schedule所有进程切换最终都汇聚到一个函数schedule。它的调用场景可以粗暴分成两类。第一类是主动让出进程自己调用sleep、wait、yield等明确表达“我现在不想跑了”。第二类是被动让出最常见的是时钟中断处理完后发现当前进程的TIF_NEED_RESCHED标志被置位了于是在中断返回路径上调用schedule。谁设置的标志可能是唤醒更高优先级进程时设置的也可能是时间片耗尽的tick中断里设置的。这里有一个初学者容易忽略的点schedule不一定只在“进程主动调用”时发生它经常是在中断上下文的尾巴上被调用的。这意味着切换前后我们可能身处非常微妙的执行环境。所以schedule函数开头一大段工作都是在处理“当前进程状态收尾”比如把prev从运行状态改成睡眠状态、把占用的内核锁释放掉这些事情不是洁癖而是保证下一次回到这个进程时世界是完整的。2.2 从用户态陷入内核TSS与新内核栈先补一个前置知识每个进程在内核态使用的是自己的内核栈。问题来了进程在用户态跑着跑着突然来了一次系统调用或中断CPU这时候怎么知道该用哪个内核栈答案是查TSS里的esp0字段。早期的Linux是每个进程一个TSS切进程就切TSS成本高。2.6之后改成每CPU一个TSS切换进程时不再整体换TSS只更新tss-esp0 next-thread.esp0把内核栈指针换成新进程的。这一步发生在上下文切换中保证了新进程下次从用户态陷入内核时能正确找到属于自己的内核栈。很多讲切换的文章不提这一手导致读者看代码看到load_sp0之类操作一头雾水。说白了就是换内核栈的时机不只是“切走的时候”还包括“告诉CPU以后怎么定位新进程的栈”。2.3 switch_mm换掉整个地址空间接下来是地址空间切换。每个进程有独立的地址空间严格说是独立的mm_struct和页表切换进程必须把CPU的页表基址寄存器CR3换成新进程的页表地址。这个动作由switch_mm完成。但换CR3的代价不低因为旧页表的TLB缓存全部失效了接下来一段时间CPU会频繁陷入页表遍历出现大量TLB miss。内核做了不少优化比如“懒TLB”模式如果切换后的进程和切换前的进程共享mm典型的就是同进程内的线程切换那压根不需要换CR3线程切换因此比进程切换便宜得多。这也解释了为什么高并发服务宁可多开线程也不愿多开进程——除了共享内存方便连切换开销都省了一截。2.4 switch_to寄存器和内核栈的交接switch_mm换的是“地址空间”switch_to换的才是真正的“执行现场”。这个宏做的事可以浓缩成一句话把当前进程的esp内核栈指针和eip下一条指令地址保存到prev的thread结构里再从next的thread结构里恢复出esp和eip跳过去继续跑。难点在于这个宏调用时看起来像一个普通函数调用但它其实在执行中途就切换了栈返回时已经不是原来的进程了。所以Linux的实现里switch_to宏接受了三个参数prev、next、last。last是给调度器用的一个技巧——切换后重新调度回来时通过last参数能知道“上一个进程是谁”。不理解这个的人去看schedule后半段的代码很容易迷路。我建议想深入的人直接去反汇编看一下__switch_to和switch_to宏展开后的汇编比自己对着源码猜要直观得多。真正要记的就一句切换的本质是换栈栈一换整个执行流就换了。3. O(1)调度器为什么诞生2.4时代的一次“调度事故”有了进程组织有了切换机制接下来是这台机器的“大脑”调度器。2.6内核引入的O(1)调度器是Linux调度史上的一块里程碑但要说清楚它牛在哪得先看看它之前是什么样。3.1 2.4的O(n)调度器是怎么工作的2.4内核的调度器用一个全局链表管理所有就绪进程。每次schedule它都要遍历这条链表上的每一个进程用一个叫goodness的函数给每个进程打分。打分综合考虑进程的静态优先级、剩余时间片、是否是交互式进程等因素最后选出得分最高的那个来运行。这个逻辑听起来挺合理问题在于它每次选进程都要“全部过一遍”。如果系统里就十个进程那无所谓但如果是一千个、一万个呢遍历链表本身就成了开销。更尴尬的是系统负载越高、进程越多调度器花在“选进程”上的时间就越长而选出来的进程可能才跑了没几毫秒又该切了。当调度开销逼近甚至超过进程实际运行时间时整个系统就像陷入了一场“调度风暴”CPU看起来一直在忙但业务吞吐量上不去。我前面说压测时看到系统态飙高本质就是这个问题的余波。3.2 进程多了以后问题会恶化到什么程度这里可以做一个粗糙的估算假设goodness对每个进程的开销是几十个CPU周期几千个进程遍历一次就是几万周期如果再算上链表遍历时的cache miss实际开销还得翻几倍。而一次schedule在很多负载高的场景下每秒要触发几百上千次。把这些乘起来调度器吃掉的可就不是几个百分点的问题了负载高的机器上甚至能看到30%以上的CPU时间耗在调度上。Ingo Molnár后来提交O(1)调度器补丁时核心口号就是让调度开销与进程数量彻底解耦不管系统里有多少进程选下一个进程的开销都应该是常数。3.3 O(1)的设计思路用空间换时间O(1)这个名字本身就是目标调度算法的执行时间跟进程总数无关恒为常数。怎么做到答案是拿空间换时间。内核预先为140个优先级各准备一条就绪链表所有进程按优先级挂到对应的链表上。再用一张140 bit的位图记录哪些优先级队列里有进程。选进程的时候只需要在位图上找到第一个置位的bit就能定位到那条非空的最高优先级链表然后取链表头一个节点就完事了。整个过程不走循环不遍历进程只有位图查找和链表取头两个常数时间操作。这套设计放到今天看依然非常漂亮它把“在大量进程里挑一个”变成了“查一个140 bit的位图”思路极简收益极大。4. O(1)调度器核心机制拆解位图、双数组与时间片标题既然点名了O(1)调度算法这部分就值得展开讲透。我会按它的数据结构、选进程路径、时间片轮转、交互式识别、实时插队这几条线来拆。4.1 prio_array_t140个队列加上一张位图O(1)调度器的核心数据结构是prio_array_t代码大概是这个样子#define MAX_PRIO 140 #define BITMAP_SIZE ((MAX_PRIO 31) / 32) struct prio_array { int nr_active; unsigned long bitmap[BITMAP_SIZE]; struct list_head queue[MAX_PRIO]; };queue是140条双向链表分别对应140个优先级。bitmap的每一位对应一条链表如果某个优先级的链表里有进程对应bit就是1。140个优先级在32位系统下正好用5个unsigned long5乘32等于160超出部分不用。nr_active表示这个数组里当前挂了多少个进程。140个优先级是怎么分配的0到99留给实时进程100到139是普通进程。普通进程的优先级由nice值映射而来nice范围是-20到19映射公式是static_prio 100 nice 20。所以nice 0对应优先级120nice -20对应100nice 19对应139。数值越小优先级越高。4.2 从位图到进程O(1)的关键一步schedule选择下一个进程的主路径核心代码极其短idx sched_find_first_bit(array-bitmap); queue array-queue idx; next list_entry(queue-next, task_t, run_list);第一步用sched_find_first_bit找到位图里第一个置位的bit得到最高优先级队列的下标。第二步定位到那条链表。第三步取链表头部第一个节点作为下一个要运行的进程。三步全部是常数时间没有循环没有遍历。sched_find_first_bit之所以快是因为它通常会被编译器优化成一条硬件位扫描指令比如x86上的BSF。内核在汇编层面做了封装一条指令就能扫完一个unsigned long里的所有bit。这也是O(1)调度器能在常数时间里完成任务的重要硬件基础。补充一个细节sched_find_first_bit扫描的是整个bitmap数组这里是5个unsigned long扫描次数固定不随进程数增长所以它依然满足O(1)。4.3 active与expired双数组时间片的轮转在哪发生光有优先级队列还没有解决“时间片用完怎么办”的问题。O(1)调度器的重要设计是每个CPU的runqueue里有两个prio_array_tactive和expired。所有还有剩余时间片的就绪进程挂在active里调度时只从active选。当一个进程的时间片被时钟中断扣完它并不会立刻被丢回active队尾而是被挪到expired里对应的优先级队列上。只有当active数组里一个进程都不剩了内核才做一个动作交换active和expired指针把整个expired数组变成新的active。这比逐个链表合并要快得多就是一次指针交换。这个双数组设计还有个隐藏的好处它保证了同一优先级内部的进程能够相对公平地轮转。新进程从expired一侧重新排入不会插到还在运行的旧进程前面避免了一个进程疯狂插队导致同优先级进程饿死的问题。所以当你看到“O(1)调度器”字样时第一反应不应该是“优先级位图”而应该是“active/expired两个数组加一张位图”三者是一体的。4.4 时间片是怎么算出来的nice值如何转成毫秒时间片的计算是O(1)调度器另一个很有意思的点。普通进程的时间片不是固定值而是根据static_prio算出来的。内核里有一个task_timeslice函数不同小版本的公式略有出入但等价口径可以表达成time_slice (140 - static_prio) * 20 / 4;单位是毫秒。套几个典型值你会看得更清楚nicestatic_prio时间片-20100200ms-10110150ms0120100ms1013050ms191395ms所以nice 0的进程每次拿到100毫秒nice -20的进程能跑200毫秒nice 19的只能跑5毫秒。这个差距就是nice值的意义所在它通过调整时间片长度直接影响进程能连续占用CPU多久。可惜的是很多人在用户态调nice只是照猫画虎不知道背后对应的是这么一套毫秒级的计算表。4.5 sleep_avg怎么识别“交互式进程”时间片解决了“每个进程跑多久”但Linux还有一个执念让交互式进程比如vi、ssh、终端响应足够快。O(1)调度器引入了一个叫sleep_avg的字段进程睡眠越久sleep_avg越大进程运行时间越长它越小。当一个就绪进程的sleep_avg超过某个阈值时内核把它判定为“交互式进程”并动态降低它的优先级数值通常是减5。这意味着它在调度时会被排到比同nice进程更靠前的位置。这个启发式思路在多数场景下是有效的但也有明显的副作用这点我在下一章展开。这里先记住一条主线交互式判断本质上是拿“最近睡得够不够多”来猜“你是不是一个需要低延迟响应的进程”它不是对进程行为的精确测量只是一条启发式规则。4.6 实时进程是怎么插队的最后补一下实时进程的调度。优先级0到99的进程走SCHED_FIFO或SCHED_RR策略它们也有自己的队列和位图。只要实时优先级队列里有进程普通进程100到139就几乎没有机会被选中。你可以用chrt命令亲手试chrt -f -p 99 1234把1234进程的调度策略设为SCHED_FIFO优先级设为99它就会变成系统里优先级最高的进程之一普通进程在它面前只能等着。这也是很多实时音视频处理程序会调高自己优先级的原因。但需要注意实时优先级设置不当会导致普通系统服务饿死生产环境里动手前务必确认自己在做什么。5. 从O(1)到CFS那些年O(1)处理不了的问题O(1)调度器从2.6.0开始服役一直到2.6.23被CFS取代期间经历了许多修补。它确实解决了“调度开销随进程数增长”的问题但在“公平性”和“交互式识别准确性”上先天就有缺陷。5.1 sleep_avg启发式识别的漏洞sleep_avg的办法太粗暴了。一个进程睡眠时间越长唤醒后就越容易被当成交互式进程获得动态优先级加成。这导致一个很尴尬的场景某个后台程序虽然每次睡眠很久但它被唤醒后其实是要做大量CPU密集计算的系统却把它当成交互式进程给了一堆优先级加成反而挤压了真正的前台交互进程。反过来一个频繁唤醒但每次都只做少量工作的进程也会因为sleep_avg波动而被误判。Linux内核社区在2.6.x时代为修这些误判打了不少补丁比如限制sleep_avg的增长上限、调整交互式阈值等但根本问题在于用一个简单的“睡眠时间”统计量去预测“交互性”本身就是不可靠的。这也是为什么CFS出现时社区会有一种“终于不用再打补丁了”的解脱感。5.2 公平性缺口与低优先级饥饿O(1)的active/expired机制保证了同一优先级内部不会乱插队但跨优先级场景并不完美。极端nice值造成的5毫秒对200毫秒的时间片差距会让低优先级进程在重负载下长时间得不到CPU。虽然调度器有一些补偿机制但补偿也是启发式的不能保证真正的公平。更明显的问题在于普通进程和实时进程之间的界线上一个高优先级实时进程如果一直不放弃CPU低优先级的普通进程会完全饿死连系统响应都变差。这类问题在生产环境里触发过不少“宿主机卡死”事件。CFS后来用完全公平模型从根上消除了“时间片优先级队列”的公平性缺陷。5.3 CFS做了什么根本改变CFS的思路和O(1)完全不同。它不再维护140个优先级队列而是维护一棵按vruntime排序的红黑树。每个进程有一个虚拟运行时间vruntime它随着进程实际运行而增长但增长速度受进程权重由nice值决定影响。权重高的进程vruntime增长慢权重低的增长快。调度器每次运行时直接选红黑树最左边那个vruntime最小的进程。这个模型最妙的地方在于睡眠进程的vruntime不会增长醒来后自然排在红黑树靠前位置自动获得补偿不需要sleep_avg这种启发式判断。它把“识别交互式进程”这件事从规则变成了数学结果。所以CFS能同时做到公平、响应快、实现简单它能取代O(1)并不意外。当然O(1)也没有完全退出历史舞台实时调度类SCHED_FIFO和SCHED_RR在现代内核里依然沿用基于固定优先级队列的组织方式只是实现细节变了。6. 在当前系统上验证你的理解命令、面试与常见误区原理看得再多不落到命令行上验证一遍总觉得隔了一层。这里分享几个我常用的验证手段以及一些面试沟通的技巧。6.1 观察调度行为的实用命令如果你想看进程当前的优先级和调度策略ps和chrt就够了ps -eo pid,comm,pri,ni,stat,psr chrt -p 1234pri列显示动态优先级ni是nice值。chrt -p直接打印进程当前使用的调度策略和实时优先级能让你直观感受到普通进程和实时进程的区别。想观察系统的切换频率vmstat 1里的cs列就是每秒上下文切换次数高并发下动辄几万是正常的但如果超过几十万且系统态CPU占比很高就该检查是不是调度配置或任务模型出了问题。想看更细的调度统计可以用perf sched它能记录一段时间内每个进程的调度延迟、运行时间和切换关系perf sched record -- sleep 5 perf sched latencyperf sched latency会输出每个进程的平均调度延迟、最大延迟等信息。这类工具非常适合验证“我改了一个优先级之后延迟到底降了没有”比靠感觉靠谱得多。6.2 面试高频问题怎么答关于进程组织和调度的面试题我整理几个高频的附上相对完整的回答思路为什么O(1)调度器是O(1)的因为选进程的路径是固定次数的位图扫描加链表取头位图长度固定140 bit不随进程数增长而变化。核心数据结构是prio_array_t由140条队列和一张位图组成。active和expired为什么用两个数组为了让时间片耗尽的进程不会插队到同优先级正在运行进程的前面保证同优先级内的公平轮转也方便在active清空时通过指针交换快速开启下一轮而不是逐条合并链表。时间片是固定值吗不是。普通进程的时间片由static_prio换算范围大约在5毫秒到200毫秒之间nice值越小时间片越长。sleep_avg是干什么的它是O(1)调度器识别交互式进程的启发式指标睡眠时间长会让动态优先级提升但误判率不低这也是它后来被CFS的vruntime模型取代的原因之一。CFS为什么不需要sleep_avg了因为CFS按vruntime选择进程睡眠进程的vruntime不增长醒来后自动靠前补偿是模型天然具备的不需要额外猜测“谁更交互”。面试时如果能顺带提到active/expired指针交换和sched_find_first_bit背后的BSF指令往往能让人感觉你是真读过源码的而不仅仅是背了结论。6.3 几个容易理解错的点最后说几个我见过很多人搞混的误区。误区一O(1)意味着调度器完全不遍历进程。准确说是“选择下一个进程”这个主路径完全不需要遍历进程链表。但调度器在时钟中断、唤醒、fork等路径上仍然有O(1)之外的开销只是这些开销不随就绪进程数线性增长。误区二优先级数值越大越优先。在Linux普通进程的优先级体系里数值越小越优先。100到139这个区间里100最高、139最低。很多从Windows思维过来的人习惯“数字大高优先级”在这套体系里正好相反。误区三CFS没有优先级的概念。CFS有但它的优先级通过权重影响vruntime的增长速度而不是直接决定队列位置。nice -20的进程vruntime增长更慢所以在红黑树里更容易保持靠前。数据模型变了nice的意图没变。误区四切换进程和切换线程开销差不多。同一进程内的线程切换不涉及CR3切换和TLB失效通常比进程切换便宜得多。高并发服务选多线程模型不只是为了共享内存方便调度开销也是实打实的收益。最后分享一点排查和学习的体会把进程组织、进程切换和O(1)调度放在一起读其实能看到一个统一的主题内核做任何设计都在权衡“查找效率”和“公平/实时性”。task_struct用链表和哈希表从不同维度索引runqueue用双数组加位图让选进程变成常数时间sleep_avg则是为了交互性付出的代价。我当年在那台压测机上查调度瓶颈时如果早一点懂位图和双数组的设计可能就不会绕那么多弯路。后来带团队排查线上CPU毛刺看到vmstat的cs列飙高、perf的调度延迟异常第一反应也变成了“先看调度模型再看业务代码”。建议想深入的人直接下载2.6.11左右的内核源码只看kernel/sched.c和include/linux/sched.h两个文件跟着schedule函数走一遍会比刷十篇博客都管用。