内核里如果有一样东西可以被称为心脏那一定是任务与调度。内存管理、文件系统、设备驱动这些子系统再复杂最后都会汇到同一个问题CPU 这一个时刻到底该让谁跑下一个时刻又该换谁来。你写的进程为什么会卡顿为什么一个死循环可以把整个系统拖垮为什么后台任务和前台任务能同时感觉在运行这些现象背后的所有答案都藏在任务与调度这套机制里。这一篇是内核系列里最关键的部分也是劝退率最高的部分。我尽量用大白话拆开讲适合正在啃内核源码、或者从应用开发转向系统软件的人。这一讲先把单核视角下的任务模型、状态切换和经典调度算法聊透多核调度和实时调度这类高级话题后面再说。1. 先把概念理清任务、进程、线程到底在说什么1.1 内核调度的是什么很多人一开始都会有一个错误印象进程是调度的单位。这个说法在早期的单进程系统里勉强成立但在现代操作系统里它已经不够准确了。更严谨的划分是这样的进程是一个资源容器它持有地址空间、打开的文件描述符、信号处理函数、环境变量这些资源而真正被调度器选中、放到 CPU 上运行的是线程。一个进程里可以有多个线程这些线程共享进程的地址空间和资源但各自拥有独立的栈和寄存器上下文。当进程只创建了主线程时进程和线程看起来是同一个东西所以很多教材就含糊地把进程调度四个字写到底。但在多线程进程普及之后这个偷懒的讲法会让后面的很多问题都解释不通。内核视角里其实没有进程和线程这种泾渭分明的概念统一称呼就是任务。内核线程也是任务某些用户态线程库里的执行实体最终也要映射成内核任务。调度器眼里它们都长一个样挂在某个队列里的节点身上挂着一堆描述自身状态的数据。所以你看调度相关的代码时发现操作对象一直是一个统一的结构体而不是区分这是进程这是线程就是这个原因。1.2 CPU 凭什么同时干多件事单核 CPU 同一时刻只能执行一条指令流这是硬件决定的。那我们平时为什么感觉电脑在同时运行浏览器、聊天软件、后台编译任务答案是并发不是并行。并发和并行是两个容易被混淆的概念。并行是多个 CPU 核心同一时刻各跑各的指令流并发则是单个核心上多个任务快速轮流执行因为切换速度足够快宏观上看起来像同时在跑。拿咖啡机类比一个咖啡机同一时间只能做一杯咖啡但排队的人轮流用每个人用一小会儿从外面看好像大家都在同时喝咖啡。这个类比里咖啡机就是 CPU排队的人就是任务每个人使用咖啡机的时间就是时间片。时间片这个概念后面会反复用到它指的是调度器允许某个任务一次连续占用 CPU 的上限。单核系统上的多任务本质是个时间分割游戏。1.3 任务的五种状态内核给任务建的状态机任务不是一出生就在 CPU 上跑到死的。它要经过一个完整的生命周期内核为此定义了五种基础状态这是理解调度机制绕不开的地基。内核的任务状态机可以用一个表格先看全貌状态含义任务在哪里能否被调度新建刚创建资源还没完全就绪创建流程中否就绪万事俱备只差 CPU就绪队列是运行正在 CPU 上执行CPU 上是阻塞等待 IO、锁或某个条件等待队列否终止执行完毕等待回收退出列表否核心的转换关系要捋清楚就绪和运行之间是双向的运行中任务被抢占或时间片耗尽回到就绪调度器选中就绪任务它转为运行。运行态任务发起 IO 操作或者等待某个锁主动进入阻塞阻塞条件满足后IO 完成、锁释放任务回到就绪重新等待调度。有一个细节容易被忽略任务只能从运行态主动进入阻塞态这是通过系统调用完成的而任务从运行态被赶回就绪态不需要任务配合时钟中断就能把它切下来。这意味着调度器拥有一票否决权——任务说我还要继续跑,内核说时间到了你该让位前者没有任何商量余地。这个设计保证了单个任务即使写了个死循环也无法独占 CPU 不放。阻塞态和就绪态的区别值得多说两句。有人会问阻塞的任务不也是在等吗和就绪有什么不同区别在于等的东西不同。就绪任务等的是 CPUCPU 一空出来它就可以上阻塞任务等的是外部事件比如磁盘数据返回、网络包到达、锁被释放这类事件可能几微秒也可能几十毫秒后才来。把等待事件不同的任务放到不同的队列里调度器就不用每次遍历所有任务一遍遍问你醒了吗这是效率上的关键设计。2. 任务控制块内核给每个任务发的一张身份证2.1 这张身份证上到底写了什么调度器要管理任务就得有地方记录每个任务的全部信息。这个数据结构就是任务控制块PCB也叫 TCB可以理解为内核给每个任务发的一张动态更新的身份证。PCB 里大致有这几类信息标识信息任务 ID、父任务 ID、任务组关系用户态常用 pid/tid内核里则是各种 ID 的组合。状态信息当前任务处于上面讲的五种状态中的哪一种以及相关的阻塞原因。CPU 上下文通用寄存器值、程序计数器、栈指针。这是切换时最重要的一块后面专门讲。调度信息优先级、当前时间片剩余量、调度类、已运行累计时长。内存信息地址空间描述、页表指针。两个进程切换时要换页表线程切换则不需要。文件与 IO 信息打开的文件表、当前等待的 IO 请求。统计信息累计 CPU 时间、切换次数、睡眠时间。同步信息等待的锁、条件变量、信号量等。这每一类字段为什么都要存在举个简单例子假设没有栈指针字段任务被切下去后再切回来时连自己该从哪条指令继续执行都不知道。PCB 就是在扮演断点存档的角色游戏里存档需要记录的角色位置、血量、道具PCB 里记录的则是一个任务重新上 CPU 所需的全部硬件状态。2.2 成千上万的任务是怎么被管理的一个系统同时存在的任务数量从嵌入式环境里的十几个到服务器上的上千个都有可能。内核不可能每次想找一个任务就全盘扫描所以任务管理必须靠数据结构来支撑。最常见的组织方式就是队列和树。就绪队列存放所有处于就绪态的任务等待队列按事件类型拆分终止任务挂在退出列表等待回收。就绪队列本身也分层次早期简单的系统用 FIFO 链表后来的系统用多级队列、红黑树、位图这些更复杂的形式目的都一样——让选中下一个任务这个操作的效率可控。有一个很多人没意识到的点真正的复杂度不在任务总数而在查找最快可运行任务这个动作。如果就绪队列只是普通链表每次挑选都要遍历任务数量上千后遍历一次的开销累积起来就很可观。所以现代内核里的调度器数据结构越来越复杂本质是在用空间换时间。这也是为什么你去看内核源码时光一个就绪队列的组织方式就能研究很久。2.3 切换的那一刻保存现场与恢复现场任务切换也叫上下文切换是整个调度的具体动作。它的完整过程可以拆成几个固定步骤触发点到来时钟中断、系统调用、任务主动阻塞。保存现场把当前 CPU 所有寄存器状态保存到当前任务的 PCB 里。进入内核调度逻辑调度器从就绪队列选下一个任务。切换地址空间如果两个任务属于不同进程页表要换同进程内线程切换这一步可省略。恢复现场从新任务 PCB 中取出寄存器值加载回 CPU。更新统计信息切换次数、运行时长等。用伪代码写出来是这样def context_switch(prev, next): # 保存上个任务的现场 prev.cpu_state.registers save_registers() prev.cpu_state.stack_pointer current_sp() prev.status TASK_READY enqueue(prev, ready_queue) # 选择下一个任务通常由调度算法决定 next pick_next_task() # 恢复下个任务的现场 if prev.mm ! next.mm: switch_address_space(next.mm) load_registers(next.cpu_state.registers) load_stack_pointer(next.cpu_state.stack_pointer) next.status TASK_RUNNING run()这个流程看起来平淡但有两个关键细节值得留意。第一切换操作本身是在内核态、且通常是关中断状态下完成的。想象一下寄存器保存到一半又来一个中断把当前寄存器的值冲掉现场就全乱了。所以整个切换动作必须有关中断保护防止中间状态被破坏。第二所谓安全点的概念。任务不能在任何一条指令处被强行切换尤其是正在修改内核数据结构临界区的时候。这也是为什么系统里除了时钟中断触发抢占还需要各种同步机制配合。这一块在后面的锁与同步章节会展开这里先埋个引子。3. 调度器在权衡什么四个指标和三组矛盾3.1 四个经典指标调度器不是拍脑袋选任务的它要面对一堆可能互相打架的指标。教科书里最常用的有这几个每个都代表一种决策视角。周转时间任务从到达系统到完成全部执行的总耗时。公式是完成时间减到达时间。用户关心的是我提交的任务什么时刻能出结果。等待时间任务在就绪队列里等待的总时间。公式是周转时间减执行时间。注意这里只算等待 CPU 的时间不包括阻塞时间。响应时间从任务到达系统到它第一次获得 CPU 的时间。交互式应用的体验主要靠这个指标保证。CPU 利用率CPU 用于执行任务指令的时间占比。切换本身不干活却要消耗时间会直接拉低利用率。举个例子三个任务同时到达执行时间分别是 10ms、5ms、2ms如果按 FCFS 顺序执行平均周转时间是 (101517)/314ms平均等待时间是 (01015)/38.33ms。这些数字后面会反复用来对比不同算法。3.2 三组矛盾理想很丰满希望周转时间短、响应也快、CPU 利用率还高。现实是这些目标很难同时满足。第一组矛盾是吞吐与响应。如果只追求整体吞吐量让长任务一口气跑完最高效因为切换次数少、浪费少。但这样后到的短任务就要在队列里等很久响应时间变得很难看。反过来如果频繁切换让每个人都能快速响应切换开销又摊薄了吞吐量。第二组矛盾是公平与效率。完全公平的做法是时间片轮转人人均等。但均等意味着长任务和短任务享受相同待遇这对短任务来说并不划算——明明你 10ms 就能做完非要被打断两次。反而照顾短任务优先执行这种看似不公平的策略能让平均周转时间更好看。第三组矛盾是 CPU 密集与 IO 密集。有的任务一直在做计算有的任务频繁发起 IO 后睡眠。IO 密集任务真正需要的 CPU 时间并不多但很在意醒来后能快速被调度到。如果调度器对它们一视同仁IO 任务可能在等 CPU 的过程中让设备空转整体效率受影响。调度器需要识别任务的行为特征而不是把它当均匀负载处理。3.3 切换开销占比一个新手最容易忽略的指标上下文切换不是一个零成本操作。保存寄存器、刷新流水线、可能还要换页表、让 TLB 失效这些时间都是纯开销不产生任何实际计算价值。这里有一个简单的估算公式假设切换成本为 C时间片长度为 Q那么切换开销占总 CPU 时间的比例约为 C/(QC)。举个例子若切换成本 0.1ms时间片 10ms开销占比约为 0.99%时间片压缩到 1ms占比直接跳到约 9%时间片放大到 100ms占比只剩约 0.1%。时间片 Q切换成本 C开销占比1ms0.1ms约 9%10ms0.1ms约 1%100ms0.1ms约 0.1%所以时间片不能无限度减小。你看着任务切换得飞快其实是把大量 CPU 时间烧在了切换动作本身。经验上时间片至少要是切换成本的 100 倍以上才不至于让系统空转在换人上。4. 从排队到抢地盘五种经典调度算法逐个过4.1 先来先服务排队排得明明白白但不一定对FCFS 是最直观的算法谁先来谁先执行直到运行完或主动阻塞才轮到下一个。它的优点是没有抢占、实现简单、也没有饿死问题——每个人早晚会轮到自己。但它有著名的护航效应convoy effect假设一个耗时 50ms 的长任务先到后面跟着一堆 2ms 的短任务那这些短任务都要眼巴巴等那 50ms 过去。像一辆慢吞吞的货车堵在窄路上后面所有小车都被带崩。前面那个例子P150P220P310按 FCFS 执行的平均等待时间是 (05070)/340ms平均周转 66.67ms响应时间同样是 40ms。这个数字带来的体验就是你提交了一个 10ms 的小任务系统却让你等了 70ms 才轮到。4.2 短作业优先效率高但要先把未来算准SJF 算法的思路是就绪队列里谁执行时间短谁先跑。还拿 P150P220P310 举例按短到长排序就是 P3、P2、P1平均等待时间变成 (01030)/313.33ms平均周转降到 40ms。这个提升非常显著短任务不用再被长任务堵死了。问题在哪在于调度器怎么知道每个任务要执行多久。任务自己不报告内核也不能提前预知未来所以纯粹的 SJF 在现实里没法精确实现只能靠历史运行时间做预测。另一个问题是长任务可能一直轮不上——如果系统里持续不断地冒出短任务那个 500ms 的长任务可能永远被排在后面这叫饿死。SJF 还有抢占版本叫最短剩余时间优先SRTF。它允许一个剩余时间更短的新任务到达时打断当前正在运行的任务。考虑一个场景任务 A 需要 10ms在 t0 到达并开始执行执行到 t2 时一个只需要 2ms 的短任务 B 到达。非抢占式 SJF 会让 A 一直跑完B 等到 t10而 SRTF 会在 t2 时把 A 切下来先让 B 跑 2ms 完成再接着跑 A。两个任务的平均等待时间从 4ms 降到 1ms短任务的响应体验天差地别。但 SRTF 同样依赖对执行时长的预测而且切换更频繁开销也更大。4.3 时间片轮转人人有份但切换是有代价的轮转调度RR是最直观的公平方案每个就绪任务轮流拿一个时间片时间片用完就排到队尾。还在那个例子P150P220P310时间片设为 15ms可以看到 P1 先跑 15ms然后 P2 跑 15msP3 跑 10ms 刚好完成之后 P2 补 5msP1 再补 35ms。算下来平均响应时间只有 15ms比 FCFS 的 40ms 友好太多。但轮转的代价是平均周转时间可能变差。同一个例子RR 的平均周转约 65ms比 SJF 的 40ms 差一截。原因是它强制打断了长任务让它拖得更久。如果把时间片调到 5ms响应时间进一步降到 5ms但切换次数大增CPU 的空转时间变多。所以时间片大小就是一个旋钮调大接近 FCFS吞吐好但响应差调小响应好但开销爆炸。这个权衡没有绝对正确取决于系统的应用场景。批处理系统偏向大时间片交互式系统偏向小时间片。现代桌面系统则采取更混合的策略——先给你一个很短的响应再考虑整体效率。4.4 优先级调度与老化允许特权但不能饿死人现实需求里有些任务就是比另一些重要。系统管理员想杀掉一个失控进程这比后台备份任务紧急得多前台动画渲染比后台日志同步重要。所以优先级调度出现了就绪队列按优先级分成多层调度器总是先挑高优先级层里的任务。但显式优先级会带来一个新问题低优先级任务可能饿死。假设高优先级任务一直源源不断低优先级任务永远轮不上。解决方案之一叫老化aging每过一个固定周期把等待时间超标的低优先级任务优先级往上提一级时间足够长后任何任务都能升到足够高的优先级被调度到。这个机制保证了你有权优先但不代表别人永远没有机会。还有一个相关的高级话题是优先级反转——高优先级任务等待低优先级任务持有的锁时反而被中优先级任务截胡。这个与信号量相关的问题在讲同步机制时单独细说这一讲先知道有这回事即可。4.5 多级反馈队列把各种策略揉在一起的综合方案如果有一种算法不用预先知道执行时间对短任务响应很快又不会让长任务饿死那就是多级反馈队列MLFQ。MLFQ 的神奇之处在于它不需要任务自报时长而是让任务的行为自己说话。它设置了多个就绪队列每个队列有各自优先级和时间片长度。高优先级队列时间片短低优先级队列时间片长。新任务的规则通常是进入最高优先级队列如果在当前队列的时间片内没有跑完就降一级任务主动放弃 CPU比如等 IO则优先级不变。短任务在高层队列里跑一两轮就完成了长任务慢慢被降到底层虽然响应变慢但至少每次能拿很长的连续运行时间不会饿死。队列级别优先级时间片长度典型处理对象队列 0最高5ms新任务、短任务队列 1中等20ms被降级的较长任务队列 2较低80ms长任务、后台吃 CPU 型任务队列 3最低320msCPU 密集型长任务这个结构就是我猜你是短任务先按短任务的待遇你你要是真长我再调整。很多现代内核的调度器设计灵感都有 MLFQ 的影子不同之处在于具体的数据结构、抢占规则和负载均衡策略。5. 一个看得见摸得着的实验三种算法在模拟任务集上的表现5.1 构造一个有意思的任务集理论聊太多容易飘我建议每个学调度的人都自己动手算一遍。这里给一个可复现的实验任务集三个任务同一时刻到达执行时间分别为 P150ms、P220ms、P310ms。别小看这个简单的设定三个数字足以把不同算法的性格差异暴露出来。为了让结论有对比价值我分别用 FCFS、SJF非抢占、RR时间片先 15ms再 5ms跑一遍手工推演整个时间轴统计平均等待、平均周转和平均响应。5.2 三种算法的结果比对先给出手推的原始数据。FCFS 顺序是 P1、P2、P3SJF 顺序是 P3、P2、P1RR q15 的轮转顺序依次是 P1(15ms)、P2(15ms)、P3(10ms)、P1 续跑、P2 补跑RR q5 的轮转更细碎但每个任务同样能推进到完成。汇总表格如下调度算法平均等待 (ms)平均周转 (ms)平均响应 (ms)FCFS4066.6740SJF非抢占13.334013.33RRq1536.676515RRq53056.675这组数字信息量很大。SJF 在平均等待和平均周转两个指标上全面碾压因为它一次性按短到长排好队切换最少。但它依赖预言能力现实中做不到。RR 的响应时间随着时间片减小而大幅改善q5 时平均响应只有 5ms但付出的代价是切换次数增加、平均周转反而比 q15 时好一点这里注意q5 时平均周转 56.67ms 小于 q15 的 65ms是因为任务本身短更小的时间片让短任务能更快插队完成。但如果任务的执行时长变大切换开销的负面影响就会盖过这个优势。也就是说时间片大小没有最优解只有针对负载的合适解。这也是为什么要强调指标组合单看某个指标会给误导。你只优化响应时间CPU 吞吐可能崩只优化周转交互体验可能烂。实际系统要做的是在多个目标间取平衡点。5.3 动手写一个最小调度模拟器纯粹手推时间轴能训练直觉但想测试更多任务、更复杂的到达时间还是写程序方便。我以前给初学者推荐过一个极简思路用 Python 的队列模拟就绪队列用字典保存剩余运行时间每次循环结算一个时间片。核心逻辑长这样from collections import deque def rr_simulate(tasks, quantum): # tasks: [(name, arrival, burst)] time 0 remaining {name: burst for name, _, burst in tasks} ready deque(sorted(tasks, keylambda t: t[1])) record {} while ready: name, arrival, burst ready.popleft() run min(quantum, remaining[name]) time run remaining[name] - run if remaining[name] 0: ready.append((name, arrival, burst)) else: record[name] time return record这个玩具模拟器能帮助你理解调度流程但必须清楚它和真实内核的差距它没算上下文切换成本没处理任务中途阻塞也没考虑多核并行。所以它的输出是一种理想化数据真实系统的数字会差不少。我建议你在推完基础算法后自己往模拟器里加切换开销参数亲眼看看时间片从 10ms 改成 1ms 时总耗时怎么变化——这个上手操作比看任何讲解都更能建立直觉。6. 给入门者的大实话学这块时我踩过的三个坑6.1 把并发当并行后面读代码会很别扭我对很多入门者说过最容易绊倒人的不是数据结构而是没厘清并发和并行。写应用层代码时并发和并行的区别常常不影响结果你 new 个线程就完事了。但一接触调度器单核并发模型和多核并行模型完全是两套逻辑单核上讨论的是时间分配多核还要讨论任务往哪个核放核之间如何负载均衡。如果一开始就用任务同时在各核跑的假设去理解单核调度器的代码很多设计会显得莫名其妙。我自己的经验是先把单核场景彻底搞透再去看多核调度两者之间的鸿沟要用真实代码去跨越。6.2 切换成本不是纸面上的零初学的时候时间片这个概念看起来只是个数字。直到有一次我在某个目标板上把时间片从 12ms 调到 2ms 想改善响应结果系统整体吞吐大跌连串口打印都变得不稳定。翻出调度统计一看发现大量 CPU 时间花在了切换和调度逻辑上实际任务执行比例变小了。从那以后我养成一个习惯优化调度参数之前先看调度器统计里的切换次数和平均切换成本。你连成本基线都没有调参数就是蒙着眼睛拧旋钮。6.3 只背算法不画时间轴等于没学FCFS、SJF、RR、MLFQ 这些名词背起来很轻松但一到面试或者实际调优就露馅。我强烈建议做一件事拿一张纸把每个算法的执行时间轴画出来。画 FCFS 时你会直观看到护航效应画 SJF 时你会体会到短作业优先到底换了什么画 RR 时你会看见时间片大小如何决定切换节奏。这个过程很枯燥但非常值得。我见过太多人能把算法定义倒背如流却算不对三个任务的平均等待时间——原因就是从来没自己推演过时间轴。从简单任务集开始画再逐步加入到达时间错开、任务中途阻塞等复杂情况调度的直觉就是这样练出来的。这一讲的内容是任务与调度的地基任务模型长什么样PCB 里装了什么上下文切换做了什么经典调度算法在权衡什么以及为什么没有银弹。后面所有与谁该跑有关的高级话题——多核负载均衡、实时调度、调度与锁的纠缠——都会在这个地基上展开。我的建议是先把手推时间轴这个基本功练熟再看代码。你会发现代码里那些曾经让你头疼的字段和队列突然都有了明确的意义。
