操作系统硬核拆解：处理机调度定义、三级调度、调度方式、调度五大准则、五大主流调度算法完整介绍

操作系统硬核拆解处理机调度定义、三级调度、调度方式、调度五大准则、五大主流调度算法完整介绍这篇文章我前前后后改了三四遍。起因是去年帮学弟复习 408 的时候发现他对着教材背了一周调度算法结果一道稍微变形的题就不会做了。问他SJF 为什么平均等待时间最短答不上来问他多级反馈队列里 I/O 完成的进程回哪个队列也答不上来。说白了就是只记住了结论没理解设计背后的逻辑。所以我决定自己重新梳理一遍把为什么讲透。全文大概一万五千字内容偏多建议收藏了慢慢看。一、处理机调度到底在干嘛先别急着看定义我们想一个场景。你开了家小饭馆后厨就一个厨师。中午高峰期门口排了十几桌客人。你得决定先做哪桌的菜每桌做多久来了个老顾客要不要插个队厨房实在站不下了要不要让几桌先去外面等会儿这就是处理机调度。CPU 就是那个厨师进程就是排队的客人调度算法就是你定的规矩。回到课本上的说法处理机调度就是从就绪队列中按照一定算法选一个进程把 CPU 分配给它去跑。注意只有就绪态的进程才参与竞争——正在阻塞等 I/O 的进程不在候选范围内这个细节后面做题会用到。那为什么非得有调度单处理机同一时刻只能跑一个进程如果没有调度机制要么 CPU 空转所有进程都在等 I/O要么某个进程把 CPU 霸占到天荒地老后面的进程全饿死。调度本质上就是在公平和效率之间找平衡。多说一句多核 CPU 的调度比单核复杂得多——不光要决定谁跑还得决定在哪个核上跑。但底层思路是一样的这篇文章先把单核讲清楚。二、三级调度一个漏斗操作系统把调度拆成了三层我习惯叫它漏斗模型——作业从最上面进来经过层层筛选最终只有一个进程能上 CPU。外存上的所有作业 ↓ 高级调度作业调度 ← 决定谁能进内存 ↓ 中级调度内存置换 ← 决定谁暂时出去透透气 ↓ 低级调度进程调度 ← 决定谁上 CPU ↓ CPU 执行高级调度作业调度干的事情很直白从磁盘上的后备队列里挑几个作业给它们分配内存、建 PCB、塞进就绪队列。频率很低分钟级别。因为每调一次都要读磁盘开销大。有个容易忽略的点高级调度只在批处理系统里存在。你用 Linux 开个终端跑个程序那程序直接就进内存了没有什么后备队列等着你。分时系统、实时系统一般没有这一层。中级调度内存置换这层是为了解决一个尴尬局面内存里 5 个进程全在等磁盘 I/OCPU 闲得发慌但内存又满了新作业进不来。怎么办把几个等 I/O 的进程先踢到外存去挂起腾出地方。等 I/O 做完了再换回来。Linux 里的 swap 分区干的就是这个事。你电脑内存不够用的时候系统会把一些进程的页面换到 swap 里这就是中级调度在工作。你可以在终端跑一下vmstat 1看看siswap in和soswap out列有数值的时候说明中级调度正在忙活。低级调度进程调度这是唯一不可缺少的调度。不管你是什么系统总得有个机制决定下一个该谁跑。频率最高毫秒级。Linux 默认调度周期大概 6ms 左右CFS 下是动态的也就是说每秒可能切换一两百次。什么时候会触发调度两种情况进程自己不要 CPU 了跑完了exit()要读文件、等网络进入阻塞态主动调了sleep()、wait()进程被强制剥夺 CPU时间片到了时钟中断来了个更紧急的进程中断处理完发现高优先级任务就绪调度发生时系统要做一次上下文切换把当前进程的寄存器现场存到 PCB 里再把下一个进程的现场恢复出来。这个过程在 x86-64 上大概 1~3 微秒。听着不多但如果时间片设得太小比如 1ms切换开销就能占到 10% 以上白白浪费 CPU。想看实际的上下文切换数据Linux 下跑这个# 查看系统全局上下文切换次数每秒vmstat15# 查看某个进程的自愿/非自愿切换次数cat/proc/pid/status|grepctxt# voluntary_ctxt_switches: 12345 ← 主动让出如等I/O# nonvoluntary_ctxt_switches: 678 ← 被抢占如时间片到了nonvoluntary_ctxt_switches这个数如果特别大说明你的进程频繁被抢占可能是优先级设低了或者时间片太短。三级对比高级调度中级调度低级调度调度谁作业进程挂起/激活就绪进程频率分钟级秒级毫秒级方向外存→内存内存↔外存就绪→CPU是否必须批处理才需要可选必须记住一句话就行低级调度是所有系统的底线没有它系统跑不起来。三、剥夺式和非剥夺式这两个概念其实特别好理解就是能不能插队的区别。非剥夺式非抢占你拿到了 CPU就安安稳稳跑到结束或者自己主动让出来。中间不管来了多急的任务都得等你跑完。剥夺式抢占你正在跑突然来了个优先级更高的进程或者你的时间片到了系统直接把你暂停CPU 给别人。现在几乎所有通用操作系统都是抢占式的。你想想如果你正在用浏览器后台一个编译任务把 CPU 占了 30 秒不撒手你的鼠标都动不了——这就是非抢占的体验完全不能接受。但抢占也不是没有代价。每次抢占都要做一次上下文切换切换本身消耗 CPU 时间。而且实现起来复杂得多——你得处理各种竞态条件、锁、死锁问题。所以在一些资源极度受限的嵌入式系统里比如单片机跑个简单控制逻辑还是会用非抢占式图的就是简单可靠。还有一个细节即便是 Linux 这种抢占式系统在内核态执行某些关键路径时也会临时关闭抢占。比如正在修改一个内核链表这时候要是被抢占了另一个进程也来改这个链表数据就乱了。Linux 里用preempt_disable()和preempt_enable()来控制这个。你在内核源码里搜这俩函数出现频率高得吓人。四、调度五大准则评价一个调度算法好不好不能只看一个指标。教材上列了五个我按重要程度和使用频率排一下。周转时间周转时间 完成时间 − 提交时间 周转时间 完成时间 - 提交时间周转时间完成时间−提交时间就是用户把作业丢给系统到拿到结果中间过了多久。这是批处理系统最关心的指标。还有一个带权周转时间带权周转时间 周转时间 实际运行时间 带权周转时间 \frac{周转时间}{实际运行时间}带权周转时间实际运行时间周转时间​为什么要搞这么个东西因为一个跑了 100 秒的作业等 10 秒和一个跑了 1 秒的作业等 10 秒体验完全不同。带权周转时间消除了这种不公平。它的最小值是 1提交后立刻执行零等待。等待时间等待时间 周转时间 − 运行时间 等待时间 周转时间 - 运行时间等待时间周转时间−运行时间就是进程在就绪队列里干等的时间。注意不包括 I/O 等待——等磁盘读写那是必要的不算浪费。响应时间响应时间 第一次有反应的时刻 − 提交请求的时刻 响应时间 第一次有反应的时刻 - 提交请求的时刻响应时间第一次有反应的时刻−提交请求的时刻这个指标是给分时系统和交互式系统用的。你敲了个命令多久能看到第一个字符输出这就是响应时间。它跟周转时间是两码事。一个命令可能 0.3 秒就开始输出了响应时间 0.3s但完整跑完要 20 秒周转时间 20s。用户关心的是我敲完回车多久有反应不是多久全部跑完。CPU 利用率CPU 忙碌时间占总时间的比例。理论上越高越好但实际中 40%~90% 都算正常取决于 I/O 密集程度。吞吐量单位时间完成多少作业。批处理系统很看重这个。这五个指标之间的关系说句实话这五个指标互相矛盾不可能同时最优。你想让响应时间短就得频繁切换进程吞吐量就下来了。你想让吞吐量高就让长作业多跑一会儿别切换响应时间就上去了。你想对短作业公平SJF长作业就可能饿死。所以面试要是问你哪个调度算法最好别说某个具体算法说看场景。批处理看吞吐量和周转时间分时系统看响应时间和公平性实时系统看能不能在 deadline 前完成。五、五大调度算法这部分是重头戏我尽量把每个算法的设计动机讲清楚而不是干巴巴地列步骤。5.1 先来先服务FCFS最朴素的策略谁先来谁先跑不管你是跑 1 秒还是跑 1 小时。实现极其简单一个 FIFO 队列就搞定了。也不会饿死任何人——毕竟严格按顺序来。但它有个要命的问题叫护航效应Convoy Effect。举个例子进程到达时间运行时间P108P214P322P431FCFS 的执行顺序就是 P1→P2→P3→P40 8 12 14 15 |─────────|──────|────|──| P1 P2 P3 P4算一下进程完成时间周转时间等待时间带权周转时间P18801.00P2121172.75P31412106.00P415121112.00平均等待时间 7.00平均带权周转时间 5.44。你看 P4只需要跑 1 个时间单位结果等了 11 个单位。带权周转时间高达 12——它 92% 的时间都在干等。这就是护航效应一个长作业像高速公路上的慢车把后面所有快车全堵住了。FCFS 什么时候能用作业长度差不多的批处理系统。大家跑的时间都差不多先后顺序影响不大。5.2 短作业优先SJF既然 FCFS 的问题是长作业堵路那最直接的改进就是让短的先走。SJF 每次从就绪队列里挑运行时间最短的进程执行。理论上可以证明在所有非抢占式算法里SJF 的平均等待时间是最短的。直觉上也好理解短作业先跑完后面所有作业的等待时间都少了一截。长作业后跑虽然自己等得久但只影响它一个。还是上面那组进程非抢占 SJFt0只有 P1P1 跑t8P1 跑完就绪队列里 P2(4)、P3(2)、P4(1)选 P4t9P4 跑完选 P3(2)t11P3 跑完选 P2(4)t15全部完成0 8 9 11 15 |─────────|--|────|────────| P1 P4 P3 P2进程完成时间周转时间等待时间带权周转时间P18801.00P21514103.50P311974.50P49656.00平均等待时间 5.50比 FCFS 的 7.00 好了不少。抢占式变体SRTF最短剩余时间优先如果新来的进程比当前正在跑的进程剩余时间还短直接抢占。同样的例子t0P1 开始跑剩余 8t1P2 来了运行时间 4 P1 剩余 7抢占t2P3 来了运行时间 2 P2 剩余 3抢占t3P4 来了运行时间 1P3 剩余也是 1相等不抢P3 继续t4P3 完成P4(1) 最短P4 跑t5P4 完成P2(剩余3) 跑t8P2 完成P1(剩余7) 跑t15P1 完成0 1 2 3 4 5 8 15 |--|--|--|--|--|-----|─────────| P1 P2 P3 P3 P4 P2 P1进程完成时间周转时间等待时间P115157P2873P3420P4521平均等待时间 2.75。比非抢占 SJF 的 5.50 又好了一大截。但 SJF 有两个硬伤第一饥饿。如果系统里不断有短作业进来长作业可能永远排不上。这不是理论上的可能是实际会发生的。第二运行时间怎么知道进程还没跑呢你怎么知道它要跑多久实际中只能用估算。常用的方法是指数加权移动平均EWMAτ n 1 α ⋅ t n ( 1 − α ) ⋅ τ n \tau_{n1} \alpha \cdot t_n (1-\alpha) \cdot \tau_nτn1​α⋅tn​(1−α)⋅τn​拿上一次的实际运行时间t n t_ntn​和上一次的预测值τ n \tau_nτn​做加权平均得到下一次的预测。α \alphaα一般取 0.5。说白了就是根据历史表现猜未来。这个思路在 Linux CFS 里也有体现——CFS 追踪每个进程的累计运行时间来估算它的 CPU 需求只不过实现方式更精细。5.3 优先级调度给每个进程一个优先级数字每次选优先级最高的跑。思路很简单但优先级怎么定是个学问。静态优先级创建进程时就定好后面不变。比如系统进程优先级高于用户进程付费用户高于免费用户。简单但死板。动态优先级跑的过程中会变。比如等得越久优先级越高防饥饿跑得越久优先级越低保公平。灵活但实现复杂。还是那组进程假设优先级数字越小越优先进程到达时间运行时间优先级P1083P2141P3224P4312非抢占式P1 先跑t0 时只有它跑完后 P2 优先级最高然后 P4最后 P3。0 8 12 13 15 |─────────|──────|--|──| P1 P2 P4 P3平均等待时间 (07119)/4 6.75。优先级调度最大的问题还是饥饿。解决办法是老化Aging每等一段时间优先级自动提升一级。等得够久优先级总会升到最高不可能永远轮不到。实际系统里到处都是优先级调度的影子系统优先级机制怎么查看/修改Linuxnice 值-20 ~ 19nice -n 10 ./my_program或reniceWindows7 个优先级类任务管理器 → 设置优先级FreeRTOS可配置通常 0~31xTaskCreate()的参数VxWorks256 级0 最高taskSpawn()的 priority 参数Linux 下你可以用top命令看每个进程的NInice 值和PR优先级列。nice 值越低优先级越高分到的 CPU 时间越多。5.4 高响应比优先HRN这个算法的设计动机特别明确SJF 对短作业好但会饿死长作业FCFS 不饿死任何人但对短作业不友好能不能取个折中HRN 定义了一个响应比R p 1 等待时间 要求服务时间 R_p 1 \frac{等待时间}{要求服务时间}Rp​1要求服务时间等待时间​每次调度时算一下所有就绪进程的响应比选最高的。这个公式妙在哪里你拆开看大家等待时间一样的时候运行时间越短响应比越高——照顾了短作业像 SJF大家运行时间一样的时候等待时间越长响应比越高——照顾了老进程像 FCFS长作业虽然分母大、初始响应比低但分子里的等待时间一直在涨总有一天会超过短作业——不会饿死还是那组进程t0 时只有 P1P1 跑。t8P1 跑完算响应比P2等了 7R p 1 7 / 4 2.75 R_p 1 7/4 2.75Rp​17/42.75P3等了 6R p 1 6 / 2 4.00 R_p 1 6/2 4.00Rp​16/24.00P4等了 5R p 1 5 / 1 6.00 R_p 1 5/1 6.00Rp​15/16.00← 最高选 P4。t9P4 跑完P2等了 8R p 1 8 / 4 3.00 R_p 1 8/4 3.00Rp​18/43.00P3等了 7R p 1 7 / 2 4.50 R_p 1 7/2 4.50Rp​17/24.50← 最高选 P3。t11只剩 P2P2 跑。0 8 9 11 15 |─────────|--|────|────────| P1 P4 P3 P2平均等待时间 5.50跟 SJF 一样。但 HRN 不会饿死长作业这是它比 SJF 强的地方。代价是每次调度都要重新算一遍所有进程的响应比开销比 FCFS 和 SJF 大一些。不过在实际系统中这点计算量不算什么。5.5 多级反馈队列MLFQ终于说到这个了。我个人觉得这是调度算法里设计得最漂亮的一个也是现代操作系统实际在用的东西。前面四个算法各有各的问题FCFS 太傻SJF 会饿死人优先级调度需要人为定优先级HRN 是非抢占的响应慢。MLFQ 的思路是我全都要。它的规则不复杂但组合起来效果很好搞 n 个就绪队列Q 1 Q_1Q1​优先级最高Q n Q_nQn​最低新进程进Q 1 Q_1Q1​按时间片轮转时间片用完了还没跑完降到Q 2 Q_2Q2​去再用完再降一直降到Q n Q_nQn​优先级越低的队列时间片越长一般翻倍只有高优先级队列全空了才轮到低优先级队列画出来大概是这样新进程 → [Q1 时间片1] → 没跑完 → [Q2 时间片2] → 没跑完 → [Q3 时间片4] → ... ↑ I/O完成的进程也回这里为什么这么设计你想想不同进程的行为交互式进程比如你的浏览器频繁等 I/O等用户输入、等网络每次 I/O 完成就回到 Q1。所以它始终在高优先级队列里响应很快。CPU 密集型进程比如视频编码一直占着 CPU 不放时间片到了就降级。降到后面时间片变长反而减少了上下文切换的次数。短进程在 Q1 里一两个时间片就跑完了根本不用降级。你看不需要人为指定优先级进程根据自己的行为自动分类了。这就是反馈两个字的含义。举个例子3 个队列时间片 1、2、4进程到达时间运行时间P105P213P321t0P1 进 Q1跑 1 单位剩余 4时间片到降到 Q2t1P2 进 Q1跑 1 单位剩余 2时间片到降到 Q2t2P3 进 Q1跑 1 单位跑完了t3Q1 空了看 Q2。P1 先进来的跑 2 单位剩余 2时间片到降到 Q3t5P2 跑 2 单位跑完了t7Q1、Q2 都空了看 Q3。P1 跑 2 单位跑完了0 1 2 3 5 7 9 |--|--|--|-----|-----|-----| P1 P2 P3 P1 P2 P1 Q1 Q1 Q1 Q2 Q2 Q3平均等待时间 (430)/3 2.33。效果相当不错。但 MLFQ 也不是完美的。有个问题如果一个 CPU 密集型进程一直在最底层队列而上面不断有新进程进来它可能很久都轮不到。解决办法是优先级提升Priority Boost每隔一段时间把所有进程全部拉回 Q1 重新来。Linux 和 Windows 都有类似机制。实际操作系统怎么做的这部分是我自己翻源码和文档总结的教材上一般不会讲这么细。Linux CFSCompletely Fair SchedulerCFS 从 2.6.23 版本开始成为 Linux 默认调度器2007 年设计者是 Ingo Molnár。它没有显式的多级队列而是用了一个很巧妙的抽象——虚拟运行时间vruntime。核心逻辑// 简化版伪代码实际实现在 kernel/sched/fair.cvruntime实际运行时间*(NICE_0_LOAD/进程权重)// 每次调度选 vruntime 最小的进程nextrb_tree_leftmost(cfs_rq-tasks_timeline)vruntime 最小的进程就是被亏待最多的下一个就该它跑。nice 值影响权重nice 值低优先级高的进程权重大同样的实际运行时间换算成更少的 vruntime自然更频繁地被选中。数据结构是红黑树vruntime 最小的在最左端取出来就是 O(log n)。你可以直接在 Linux 上看 CFS 的运行时信息# 查看调度器统计信息cat/proc/sched_debug# 查看某个进程的调度信息cat/proc/pid/sched# 输出里有 se.vruntime虚拟运行时间、nr_switches切换次数等WindowsWindows 更直接就是多级反馈队列加优先级提升。它有 32 个优先级0~31其中 0~15 是普通优先级16~31 是实时优先级。普通线程的时间片用完后会降级但有一个优先级衰减机制——降级后过一段时间会自动回升。macOS / FreeBSD底层是 Mach 微内核macOS或 ULE 调度器FreeBSD都是 MLFQ 变体加了处理器亲和性优化。六、横向对比把五个算法放一起看FCFSSJF优先级HRNMLFQ平均等待时间长最短看设置较短短响应速度慢一般高优先级快一般快会不会饿死不会会会不会基本不会实现难度极低中中中高适合什么系统批处理批处理实时系统批处理通用系统如果让我画一条演进路线FCFS 太粗糙 → SJF 优化了平均等待时间但会饿死人 → HRN 解决了饥饿但不够灵活 → MLFQ 把前面几个的优点全揉进去了。不是说 MLFQ 就完美无缺它参数多队列数、时间片大小、提升周期调不好效果也一般。但在没有更好替代品的情况下它确实是工程上的最优解。七、容易踩的坑这块是我帮人复习时总结的都是真实犯过的错。坑一SJF 调度时忘了看到达时间。题目里 P1 在 t0 到达P2 在 t1 到达。t0 时刻做调度决策时P2 还没来呢不能选它。我见过不止一次有人把还没到达的进程也纳入比较。坑二SRTF 里相等时不抢占。当前进程剩余时间 新进程运行时间这时候不抢占当前进程继续跑。只有严格小于才抢。坑三MLFQ 里搞混降级和回 Q1的条件。时间片用完没跑完 → 降级。I/O 完成被唤醒 → 回 Q1。这两个方向是反的别记混了。坑四带权周转时间的分母。分母是实际运行时间也叫服务时间不是周转时间。我当年考研模拟考就在这个地方丢过分纯属粗心。坑五以为响应比是固定的。响应比随等待时间一直在变。每次调度决策时都要重新算。不是进程创建时算一次就完事了。坑六把周转时间和响应时间搞混。周转时间是从提交到全部完成响应时间是从提交到第一次有反应。一个进程可能 0.5 秒就有输出了响应时间 0.5s但要跑 30 秒才结束周转时间 30s。八、面试和考试常问的问题Q三级调度哪个是必须的低级调度。没有它 CPU 不知道下一个该跑谁系统直接瘫痪。高级调度只有批处理系统需要中级调度是可选的性能优化。QSJF 平均等待时间最短为什么实际不用两个原因。一是运行时间没法精确预知只能估算估不准效果就打折扣。二是会饿死长作业。实际系统用 MLFQ 或 CFS既接近 SJF 的效果又没有它的毛病。Q时间片设多大合适太小了上下文切换太频繁CPU 净忙着切换了。太大了退化成 FCFS响应慢。一般 10~100ms经验法则是让 80% 的进程能在一个时间片内跑完。Linux CFS 的做法更聪明——时间片不是固定的而是根据进程数量和 nice 值动态计算。Q什么是优先级反转怎么解决经典场景高优先级进程 H 等低优先级进程 L 持有的锁中优先级进程 M 把 L 抢占了。结果 H 间接被 M 挡住了——一个中优先级的进程反转了优先级关系。1997 年火星探路者号Mars Pathfinder就因为这个 bug 导致系统反复重启算是操作系统史上最著名的翻车之一。当时 NASA 的工程师通过远程调试在 1 亿公里外给探测器打了补丁启用了优先级继承协议才解决问题。解决办法两个优先级继承L 临时继承 H 的优先级M 就抢不走了和优先级天花板锁本身带一个最高优先级谁拿着锁谁就自动升到那个级别。QLinux CFS 的核心思想是什么一句话不追踪优先级追踪谁被亏待了。每个进程有个 vruntime虚拟运行时间跑得越多 vruntime 越大。每次调度选 vruntime 最小的——也就是被亏待最多的。nice 值影响 vruntime 的增长速度nice 值低优先级高的进程 vruntime 涨得慢自然更频繁地被选中。数据结构是红黑树vruntime 最小的在最左端取出来就是 O(log n)。Q怎么判断一个进程是被抢占还是主动让出 CPU 的看/proc/pid/status里的两个字段voluntary_ctxt_switches自愿切换主动让出比如等 I/Ononvoluntary_ctxt_switches非自愿切换被抢占比如时间片到了如果一个进程的 nonvoluntary 数值特别大说明它经常被抢占可能是优先级偏低或者系统负载太高。九、想继续深入的话如果你不满足于应付考试想真正搞懂调度推荐这个路径第一步把教材吃透。汤小丹《计算机操作系统》第三章或者 Silberschatz《操作系统概念》第九版 PDF 可在作者官网找到第五章。把课后题全做了尤其是画甘特图算指标的那种。第二步看看 Linux 怎么做的。Robert Love 的《Linux 内核设计与实现》第四章讲进程调度不长但把 CFS 的设计动机讲得很清楚。如果想看源码kernel/sched/fair.c是 CFS 的核心实现大概三千多行硬啃需要点耐心。建议配合 Linux 内核文档的调度器部分一起看。第三步了解实时调度。EDF最早截止时间优先和 RMS速率单调调度是实时系统的两大经典算法跟通用调度思路完全不同。FreeRTOS 的官方文档对优先级调度讲得很透彻。第四步看看多核和分布式调度。单核调度搞明白了多核的负载均衡、NUMA 感知调度是下一个层次。再往上就是 Kubernetes 那种集群级别的调度了思路其实也是相通的——在有限资源下做最优分配。最后说两句处理机调度这块内容说难不难说简单也不简单。难的不是算法本身——五个算法的逻辑都不复杂。难的是理解每个算法为什么这么设计以及它们之间的权衡关系。我始终觉得操作系统里最有趣的部分不是那些数据结构和算法而是背后的设计哲学在资源有限的世界里没有完美方案只有最适合当前场景的折中。调度算法如此内存管理如此文件系统也如此。好了就写到这里。如果这篇文章对你有帮助点个赞收个藏也算没白写。有问题评论区聊看到都会回。参考资料汤小丹, 梁红兵等.《计算机操作系统》第四版. 西安电子科技大学出版社.Silberschatz, Galvin, Gagne.Operating System Concepts(9th Edition). Wiley.Robert Love.Linux Kernel Development(3rd Edition). Addison-Wesley.Linux Kernel Scheduler DocumentationMars Pathfinder Priority Inversion Problem