调度的基本概念与目标

2026 大纲 二（二）1 调度的基本概念 · 2 调度的目标 · 3 调度的实现。本篇是调度章的总纲：后续九篇算法共用这里定下的四个指标口径与同一组算例数据（到达 0/2/4/5、服务 7/4/1/4 的四个进程，换算法不换数据）。

有了进程和切换，还差最后一件事：下一个给谁

前面四节把"运行中的程序"这个对象造出来了，也讲清了它怎么被创建、怎么在几个状态之间转、以及怎么和别人通信。

但有一件事一直没问：当 CPU 空出来、就绪队列里躺着好几个进程时，下一个给谁？

这就是调度。它看起来只是"挑一个"，实际上要先回答三个不同层次的问题：

谁能进内存（高级调度／作业调度，决定一批作业里哪些被调入）→ 谁能留在内存（中级调度，把暂时不跑的换出去、又把该跑的换回来）→ 谁能上 CPU（低级调度／进程调度，这一层最频繁，是本章后面八篇算法的战场）。

三层的频率相差极大，而这个差别决定了它们各自能花多少心思：低级调度可能几毫秒一次，所以算法必须简单快速；高级调度可能几分钟才做一次，就可以慢慢算。

还有一层麻烦：调度的目标不是一个，而是一组互相冲突的指标。 想让平均周转时间短，就该优先跑短作业；可这样长作业会一直排不上（饥饿）。想让所有人都及时得到响应，就该频繁切换；可切换本身要花时间（开销）。 后面八种算法的差别，全部来自它们在这组冲突里站在哪一边。

这一节先把地基打好：三个层次、一组指标、调度在什么时机发生、哪些时刻不能调度，以及一套后续各篇共用的评价口径—— 周转、带权周转、等待、响应这四个量算错一个，后面几篇的手算题会跟着一起错。

一、调度的三个层次

调度的实质是资源分配，处理机调度分配的就是 CPU。一个作业从提交到完毕可能经历三级：

层次	别名	调度对象	典型周期	做的事
高级调度	作业调度、长程调度	作业	几分钟一次	从外存后备队列选作业调入内存，创建进程并分配资源（从"还不存在"到"存在且在内存"）
中级调度	内存调度、中程调度	已存在的进程	介于两者之间	把暂时不能运行的进程换出到外存（挂起），条件具备再换回（从"在内存"到"在外存"，或反过来）
低级调度	进程调度、短程调度	进程（或内核级线程）	10～100 ms 一次	从就绪队列选一个，把 CPU 交给它（从"就绪"到"运行"）

被中级调度换出的进程处于挂起（静止）状态，即静止就绪与静止阻塞——正是七状态模型比五状态模型多出来的那两个（见进程状态与转换）。频率还决定了算法的复杂度上限：进程调度几十毫秒跑一次，算法太复杂本身就吃掉 CPU 时间，所以低级调度算法必须简单。

中级调度为什么必须存在：从内存约束一步步推出来（觉得"它负责换入换出"这句话没有解释力时展开）

多道程序的道数越多，CPU 利用率越高 ⇒ 系统倾向于多放几个进程进内存 ⇒ 但内存容量有限，且有些进程正在长时间等 I/O、占着内存却不产出 ⇒ 必须有一种机制把这些"占着不动"的进程整体挪到外存腾地方 ⇒ 这就是中级调度。

所以中级调度的目的是提高内存利用率和系统吞吐量。三级并非都必须配置：低级调度是所有操作系统的必备功能；高级调度主要用于多道批处理系统，分时和实时系统一般不设；中级调度只有需要提高内存利用率时才引入。所以现实中既有三级调度模型，也有两级调度模型。

二、调度的目标：一组互相冲突的指标

分类	指标与含义	谁在乎
面向系统	资源利用率（CPU 与外设尽量都忙）、系统吞吐量（单位时间完成的作业数）、公平性（同类进程同等服务、不同类按紧急程度区分，故"公平"≠"平均"）、平衡性（别让 CPU 或外设单方面闲着）、策略强制执行（既定策略必须准确执行，哪怕造成延迟）	系统管理者
面向用户	响应时间、（作业）周转时间、截止期保证	提交作业的人

目标之间是冲突的，所以不同类型的系统各自砍掉一头：

系统类型	首要目标	被牺牲的（为什么）
批处理系统	平均周转时间短、吞吐量高、CPU 利用率高	响应时间——没有交互，无人等在终端前
分时系统	响应时间快、均衡性	周转时间与吞吐量——人坐在终端前敲命令，频繁切换有开销也认了
实时系统	截止期保证、可预测性	平均性能——错过截止期的正确结果等于错误结果，宁可整体慢也不能有一次超时

冲突最直观的一处：吞吐量高要求多跑短作业，CPU 利用率高要求多跑计算量大的作业——同一份就绪队列上这两条就是矛盾的。分时系统目标里的"均衡性"指响应快慢应与请求复杂度相适应。

三、调度的实现：调度程序由三个部件构成

部件	职责（一句话判据）
排队器	每当有进程转为就绪，把它插入相应就绪队列——只管组织，不做决策
调度程序（scheduler）	按调度算法从就绪队列中选出一个进程——只做决策，不碰寄存器
分派程序（dispatcher）	把选中进程摘下队列、完成上下文切换、交出 CPU 控制权，让它从断点恢复——只执行决策，不做选择
上下文切换器	保存当前进程的现场到 PCB、装入新进程的现场，由分派程序驱动

分派延迟（dispatch latency）：从选定新进程到它真正开始运行之间的这段时间，含上下文切换、切到用户态、跳到断点，全是纯开销。它决定时间片的下限（ $q$ 若与它同量级，CPU 大半时间在搬寄存器，量化见时间片轮转调度）与实时系统能保证的最短响应时间。教材还有一个更细的口径：一次处理机切换会发生两对上下文切换，因为分派程序自己也是一段要占用现场的代码。

四、调度的时机

判据只有一条：当前进程还能不能继续占着 CPU，或者是否出现了更该占 CPU 的进程。

场景	归入哪一类	抢占式才有？
当前进程运行结束 / 异常终止	不能继续占（进程没了）	否
当前进程主动阻塞（请求 I/O、执行 Block 原语）	不能继续占（它自己等着）	否
时间片用完	还能跑，但规则不许它继续占	是
更高优先级（或更短）的进程到达就绪队列	还能跑，但出现了更该占 CPU 的	是
中断/异常处理完毕，返回前	处理期间就绪队列可能已变化，返回前重新决策	视方式

前两行是非抢占式也会发生的调度，后两行是抢占式独有的——这正是抢占与非抢占的分界。

不能调度的三种情况——中断处理中、内核临界区中、原语等原子操作中——不是并列的三条，而是同一条理由的三种表现：调度这个动作本身要修改内核数据结构、要切换现场，凡是"半路被打断就会留下不一致状态"的时刻都不能调度。

三个"不能调度"时刻各自的推导，以及内核临界区与普通临界区为什么结论相反（想弄清访问打印机时为什么反而可以调度时展开）

时刻	推导
中断处理过程中	中断处理属于内核工作，此时现场信息尚未完整保存；中途换人会让被中断进程的现场丢失或错乱
进程在操作系统内核临界区中	内核临界区里正在修改就绪队列、PCB 链等调度程序自己要用的数据结构；此时调度，调度程序读到的就是半成品
原子操作过程中（原语执行中）	原语的定义就是"不可分割"，中间插入调度等于打破原子性；原语通常靠关中断实现，本身也屏蔽了调度

普通临界区则可以调度：进程访问打印机这类普通临界资源时，锁住的东西调度程序根本不碰，换人不影响它工作。按这条判据自己就能判新情况——进程正在修改一个用户态的共享链表？那是普通临界区，可以调度。

五、抢占式与非抢占式

方式	规则	检查时刻	硬件前提	适用
非抢占式	一旦把 CPU 分给某进程就让它一直运行，直到它完成或自己阻塞	只在当前进程完成/阻塞时发生一次调度	无特殊要求	批处理系统
抢占式	允许调度程序暂停运行中的进程，把 CPU 收回重新分配	新进程进入就绪队列、时间片到、中断返回前都要检查	必须有时钟中断	分时、实时系统

六、闲逛进程

就绪队列空了 CPU 也不能停——取指令是硬件自动进行的，它必须一直有指令可取。操作系统的答案是设置一个闲逛进程（idle process）：优先级最低、不占用 CPU 以外的任何资源、永远不会被阻塞、一有进程就绪立即让位、执行期间仍响应中断，并常用停机类指令（如 HLT）让 CPU 进低功耗态。

最容易搞反的一条：它不是"什么都不做"，而是"什么都不做但随时能被中断唤醒"——这就是"死循环空转"与"HLT 等中断"的区别。

七、内核级线程与用户级线程的调度

这一条要的是调度视角：谁是调度器眼中的对象——用户级线程下内核只感知进程，线程之间谁先跑由进程内的线程库决定；内核级线程下每个线程都是内核的调度对象。实现机制见线程（内核级与用户级）。

上面两节的完整表格：闲逛进程六条性质为什么每一条都必然，两类线程在调度视角下的六条差异（想弄清它们是不是要死记时展开）

闲逛进程的性质全部可以从"存在的唯一理由是给 CPU 一件事做"推出来：

性质	为什么必然如此
优先级最低	它只是占位；只要有任何一个真正的进程就绪，就必须立刻让位
一旦有进程就绪就立即让出 CPU	同上，这是"最低优先级"在抢占式调度下的直接后果
不占用除 CPU 外的任何资源	它若申请内存或做 I/O 就可能阻塞、与真实进程争抢，违背"随时可让位"
永远不会被阻塞	它不等任何事件——若它能被阻塞，就会出现"就绪队列空、闲逛进程也不能跑"的空档
🔴 执行期间仍能响应中断	中断不能被它屏蔽——否则 I/O 完成中断进不来，被阻塞的进程永远醒不过来，系统就死了
常用停机类指令（如 HLT）让 CPU 进低功耗	空循环白白耗电；HLT 让 CPU 停在等中断的低功耗态，一来中断即恢复，功耗和发热都低得多

两类线程在调度视角下的差异：

调度问题	用户级线程（线程库支持）	内核级线程（内核支持）
内核调度的对象是谁	进程。内核根本不知道线程存在	线程。内核为每个线程建 TCB，按线程调度
线程之间谁先跑，由谁决定	由进程内的线程库决定，是一次"局部调度"，不进内核	由内核的调度程序决定，是一次真正的系统调度
切换要不要进内核态	不要，全程用户态	要（一进一出）
能否利用多核并行	不能——一个进程同一时刻只在一个核上	能——同一进程的多个线程可同时上不同的核
一个线程阻塞的后果	整个进程被阻塞（多对一模型）	只阻塞该线程，同进程其他线程照常运行
一个进程分到的 CPU 份额	与它开了几个线程无关（内核按进程分）	与线程数有关（线程多的进程占得多）

最后两行是要害：

用户级线程由线程库在进程内调度、内核只感知进程 ⇒ 内核给这个进程分配的是一份 CPU 时间 ⇒ 该进程内所有线程只能瓜分这一份 ⇒ 任一线程发起阻塞式系统调用时，内核阻塞的是它眼里唯一的调度对象（整个进程）⇒ 一个线程阻塞，全部线程停摆。

反过来，内核级线程下每个线程都是独立调度对象，一个开了 10 个线程的进程会拿到比单线程进程多得多的 CPU 时间——这也是"对进程公平"与"对用户公平"分歧的另一个来源，见公平调度算法。

八、评价指标：统一口径（后续各篇共用）

设进程 $i$ 的到达时刻为 $A_{i}$ 、需要的 CPU 服务时间为 $S_{i}$ 、实际完成时刻为 $C_{i}$ 、首次获得 CPU 的时刻为 $F_{i}$ 。

CPU 利用率 = \frac{CPU 有效工作时间}{CPU 有效工作时间 + CPU 空闲等待时间}

分母是总运行时间；"有效工作时间"不含上下文切换本身。系统吞吐量是单位时间内完成的作业数，所以多跑短作业吞吐量就高。

指标	定义式	从哪一刻起算	到哪一刻为止	刻画什么体验
周转时间 $T_{i}$	$T_{i} = C_{i} - A_{i}$	进程/作业到达（提交）	全部执行完毕	用户从提交到拿到结果等了多久
带权周转时间 $W_{i}$	$W_{i} = \frac{T_{i}}{S_{i}}$	—（比值，无量纲）	—	实际花的时间是纯干活时间的几倍
等待时间	$T_{i} - S_{i}$	到达	完成	这段时间里有多少是在干等
响应时间	$F_{i} - A_{i}$	到达（用户提交请求）	首次获得响应（首次被调度上 CPU）	敲下命令后多久有反应

平均值一律是算术平均： $\bar{T} = \frac{1}{n} \sum T_{i}$ ， $\bar{W} = \frac{1}{n} \sum \frac{T_{i}}{S_{i}}$ 。三条边界各有理由： $W_{i} \geq 1$ 是因为 $T_{i} \geq S_{i}$ ，周转时间至少包含服务时间本身；平均带权周转必须先算比值再平均，"平均周转 ÷ 平均服务"一般不等于它；抢占式下等待时间是所有等待段之和，进程被抢占后重新排队那段也要计入，所以只能用 $T_{i} - S_{i}$ ——周转时间里除去它真正占用 CPU 的 $S_{i}$ ，剩下的必然全是等待。

四个指标在同一组数据上各算一遍：非抢占与抢占下等待、响应为何分离（想看口径怎么落到数字上时展开）

四个进程的到达时间与服务时间如下（后续各篇共用这组数据）：

进程	到达时间 $A_{i}$	服务时间 $S_{i}$
P1	0	7
P2	2	4
P3	4	1
P4	5	4

第一步：画甘特图。 一切指标都从完成时刻推出来，所以必须先把时间轴排定。非抢占按到达顺序：

时间区间	0–7	7–11	11–12	12–16
执行进程	P1	P2	P3	P4

第二步：逐个进程套定义式。 等待时间直接用 $T_{i} - S_{i}$ ，不要试图去数"它等了几段"。

进程	$C_{i}$	周转 $T_{i} = C_{i} - A_{i}$	带权 $W_{i} = T_{i} / S_{i}$	等待 $= T_{i} - S_{i}$	首次上 CPU $F_{i}$	响应 $= F_{i} - A_{i}$
P1	7	7−0 = 7	7/7 = 1.00	0	0	0
P2	11	11−2 = 9	9/4 = 2.25	5	7	5
P3	12	12−4 = 8	8/1 = 8.00	7	11	7
P4	16	16−5 = 11	11/4 = 2.75	7	12	7

\bar{T} = \frac{7 + 9 + 8 + 11}{4} = 8.75, \bar{W} = \frac{1.00 + 2.25 + 8.00 + 2.75}{4} = 3.50

\overset{―}{等待} = \frac{0 + 5 + 7 + 7}{4} = 4.75, \overset{―}{响应} = \frac{0 + 5 + 7 + 7}{4} = 4.75

第三步：验证边界。 每个 $W_{i} \geq 1$ ✓；非抢占式下平均等待与平均响应相等（4.75 = 4.75）✓——每个进程首次上 CPU 后就一直跑到完成。

第四步：换成抢占式（每当新进程到达就重新比较剩余时间），看哪一条口径变了。

时间区间	0–2	2–4	4–5	5–7	7–11	11–16
执行进程	P1	P2	P3	P2	P4	P1

进程	$C_{i}$	周转 $T_{i}$	带权 $W_{i}$	等待 $= T_{i} - S_{i}$	首次上 CPU $F_{i}$	响应
P1	16	16	16/7 ≈ 2.29	9	0	0
P2	7	5	5/4 = 1.25	1	2	0
P3	5	1	1/1 = 1.00	0	4	0
P4	11	6	6/4 = 1.50	2	7	2

\bar{T} = \frac{16 + 5 + 1 + 6}{4} = 7.00, \overset{―}{等待} = \frac{9 + 1 + 0 + 2}{4} = 3.00, \overset{―}{响应} = \frac{0 + 0 + 0 + 2}{4} = 0.50

这一步为什么重要：P1 的等待时间是 9，但它 $F_{1} = 0$ ——若按"首次上 CPU 时刻 − 到达时刻"算会得到 0，错了 9 个单位。P1 在 2–11 之间被踢下 CPU 又重新排队，这段重新等待必须计入。抢占式下等待与响应彻底分离（3.00 ≠ 0.50），这就是第 3 条边界的用处。

考点速记

三个层次：高级（作业调度）决定谁能进内存、中级决定谁能留在内存、低级（进程调度）决定谁能上 CPU。频率相差极大，所以低级调度的算法必须简单快速。
调度机制由四部分构成：排队器 + scheduler（选人） + dispatcher（交权） + 上下文切换器。从选定到真正运行的那段纯开销叫分派延迟。
可以调度的时机：进程结束、进程阻塞、时间片用完、中断处理结束、创建新进程后、系统调用完成返回用户态时。⚠️这些全都算"可能引起调度程序执行"。
⚠️不能调度的时机只有三类：中断处理过程中、内核临界区中（内核数据结构处于中间状态）、原语执行中（要保证原子性）。普通（用户）临界区中是可以调度的——它只是进程自己的临界区，切走了别的进程也不会来动它。
⚠️抢占式调度以时钟中断为硬件前提。分时系统实现时间片轮转，靠的是时钟中断处理程序（每次中断扣减剩余时间片）、进程控制块（记录剩余时间片）、进程就绪队列（时间片用完后回到队尾）三样；阻塞队列与时间片轮转无关。
⚠️时间片用完，进程从执行态变为就绪态，不是阻塞态——它什么都不缺，只是被抢走了 CPU（与进程状态与转换速记第三条同一条）。
时间片大小的取舍：时间片越短，切换次数越多、系统开销越大。影响它的主要因素是响应时间、系统开销、就绪进程数。
⚠️时间片轮转不会导致饥饿——每个进程按轮次都能拿到 CPU。会饥饿的是"按某个键排序"的算法：静态优先数调度（低优先级永远排不上）、短作业优先（无论抢占与否，长作业都可能一直被插队）。
设计多级反馈队列要定四件事：队列的数量、各队列的优先级、各队列各用什么调度算法、进程在队列间的迁移条件。四条都要考虑。
就绪队列用单链表 + 按优先级有序时：插入 $O (n)$ （要找位置）、取最高优先级 $O (1)$ （取表头）。⚠️ 两个复杂度不一样，别一起答。
四指标统一口径（后续各篇共用）：周转 = 完成 − 到达；带权周转 = 周转 / 服务（恒 $\geq 1$ ，⚠️平均值必须先算比值再平均）；等待 = 周转 − 服务（抢占与非抢占通用）；响应 = 首次上 CPU − 到达（非抢占下与等待重合，抢占下必然分离）。

这一节在真题里被考过的形式：

cpu-scheduling-concepts 挂了 17 道题，其中一半是具体算法的手算题（在优先级调度、高响应比优先等篇讲）， 本页练习区渲染的题比本节内容宽，属正常。真正落在本节的按问法分四类：

① 什么时候能调度、什么时候不能（2012-30、2021-27）。2012-30 答在进程处于临界区时不能进行处理机调度是错的——⚠️ 判据是速记第四条：不能调度的只有中断处理中、内核临界区中、原语执行中三类，普通临界区可以调度。2021-27 答四条全部（中断处理结束、进程阻塞、进程执行结束、时间片用完）都可能引起调度。
② 时间片轮转靠什么实现、时间片用完会怎样（2021-25、2017-27）。2021-25 答时钟中断处理程序 + 进程控制块 + 进程就绪队列三样，阻塞队列无关。2017-27 的错项是"时间片用完后进程状态由执行态变为阻塞态"——⚠️是变为就绪态（速记第六条）。
③ 哪些算法会饥饿（2014-23）。答时间片轮转不会；静态优先数、抢占式与非抢占式短作业优先都会。判据是速记第八条：按轮次来的不饿，按某个键排序的会饿。
④ 设计与实现细节（2020-26、2025-25）。2020-26 答设计多级反馈队列要考虑的四条全部；2025-25 答单链表就绪队列的插入 $O (n)$ 、取最高优先级 $O (1)$ 。
⑤ 多道下的时间计算（2012-29）。两个作业各含"计算—I/O—计算"三段，问最少总时间。做法是排时间线，让 CPU 与 I/O 尽量重叠，判据与操作系统基本概念那道瓶颈资源题同源。

复习优先级：必须拿满，本节是后面八篇算法的公共地基。 速记第十一条那套指标口径要一次记准——带权周转要先算比值再平均、等待时间抢占与非抢占通用，这两处一错，后面几篇的手算题会跟着一起错。第四条（普通临界区可以调度）和第六条（时间片用完变就绪不是阻塞）是概念题的固定考点。

易错：认为进程处于临界区时不能调度。只有内核临界区不能；普通临界区可以。

易错：认为时间片用完进程进入阻塞态。是就绪态——它什么都不缺，只是被抢走了 CPU。

易错：认为时间片轮转也会饥饿。按轮次来的不会；会饿的是按某个键排序的算法。

易错：算平均带权周转时用"平均周转 ÷ 平均服务"。必须先算每个进程的比值再平均。

易错：把响应时间和等待时间当成一回事。非抢占下重合，抢占下必然分离。

易错：认为阻塞队列参与时间片轮转的实现。用到的是时钟中断处理程序 + PCB + 就绪队列。

易错：单链表就绪队列的插入与取最值答同一个复杂度。插入 $O (n)$ 、取最高优先级 $O (1)$ 。

教材出处

汤小丹《计算机操作系统》3.1.1 处理机调度的层次（高级/中级/低级调度的定义与频率），印刷 p85–p86
汤小丹《计算机操作系统》3.1.2 处理机调度算法的目标（共同目标、批处理/分时/实时三类系统的目标，CPU 利用率与带权周转时间的定义式），印刷 p86–p87
汤小丹《计算机操作系统》3.3.1 进程调度的任务、机制和方式（排队器/分派器/上下文切换器三部件，两对上下文切换，抢占三原则），印刷 p91–p92
孙钟秀、费翔林《操作系统教程》第 6 版 2.5.2 选择处理器调度算法的原则（面向系统与面向用户两类性能指标的划分），印刷 p73

真题练习

2026Q457分 2025Q252分 2023Q292分 2022Q252分 2021Q252分 2021Q272分 2020Q262分 2018Q242分 2017Q272分 2016Q466分 2015Q252分 2014Q232分 2013Q312分 2012Q292分 2012Q302分 2010Q262分 2009Q242分

调度的基本概念与目标

有了进程和切换，还差最后一件事：下一个给谁

一、调度的三个层次

二、调度的目标：一组互相冲突的指标

三、调度的实现：调度程序由三个部件构成

四、调度的时机

五、抢占式与非抢占式

六、闲逛进程

七、内核级线程与用户级线程的调度

八、评价指标：统一口径（后续各篇共用）

考点速记

相关知识

真题练习

相关真题（17题）

相关文章

调度的基本概念与目标 ​

有了进程和切换，还差最后一件事：下一个给谁 ​

一、调度的三个层次 ​

二、调度的目标：一组互相冲突的指标 ​

三、调度的实现：调度程序由三个部件构成 ​

四、调度的时机 ​

五、抢占式与非抢占式 ​

六、闲逛进程 ​

七、内核级线程与用户级线程的调度 ​

八、评价指标：统一口径（后续各篇共用） ​

考点速记 ​

相关知识 ​

真题练习 ​

相关真题（17题）

相关文章

调度的基本概念与目标

有了进程和切换，还差最后一件事：下一个给谁

一、调度的三个层次

二、调度的目标：一组互相冲突的指标

三、调度的实现：调度程序由三个部件构成

四、调度的时机

五、抢占式与非抢占式

六、闲逛进程

七、内核级线程与用户级线程的调度

八、评价指标：统一口径（后续各篇共用）

考点速记

相关知识

真题练习