Appearance
优先级调度
2026 大纲 二（二）4 CPU 调度算法的优先级调度，含静态/动态、抢占/非抢占两个维度，以及由它引出的优先级反转问题。指标口径与算例数据沿用 调度的基本概念与目标。
交互可视化
前面三个，其实都是它的特例
到这里已经有三种算法了，看起来各不相同。但换个角度看会发现—— 它们做的是同一件事：给每个进程算一个"该不该先跑"的分数，然后挑分数最高的。
FCFS 的分数是到达得早不早，SJF 的分数是作业短不短， RR 干脆不看分数、按轮次来。
把这个分数显式地拿出来当参数，就是优先级调度。 它不是第四种算法， 而是前面几种的统一形式——所谓某某算法，无非是"优先级函数取成什么样"。
这个视角很值钱：遇到一个没见过的调度算法，问三句话就能定它的行为—— 它的优先级函数是什么？这个函数随时间变不变？变了之后抢不抢占？
三句话对应两个互相独立的维度：抢占 / 非抢占，以及静态 / 动态。 静态优先级一旦赋值就不再变，实现简单但会饥饿； 动态优先级按"等得越久越高"（这就是老化）与"占 CPU 越久越低"调整。
⚠️ 有一条要先钉住：抢占改善不了最低优先级进程的处境。 抢占只让高优先级的人插队插得更快，低优先级的人该等还是等—— 治饥饿只能靠老化，这是两个不同维度的事。
这一节末尾还有一个专门的坑：优先级反转。 它是高优先级进程被低优先级进程间接卡住的现象， 而且必须凑齐三方才会发生——少一方就不成立。
一、它是整章的一般形式
只要把"优先级"理解成一个由进程属性算出来的数，前面每个算法都只是换了一个优先级函数——这不是类比，是可以逐个对上的：
| 算法 | 它的优先级函数 | 抢占性 | 优先级会不会变 |
|---|---|---|---|
| FCFS | 优先级 = 等待时间（等得越久越优先），等价于"到达越早越优先" | 非抢占 | 变（等待时间在涨），但相对次序不变 |
| SJF | 优先级 = 1 / 服务时间（作业越短越优先） | 非抢占 | 不变 |
| SRTF | 优先级 = 1 / 剩余时间 | 抢占 | 变 |
| HRRN | 优先级 = | 非抢占 | 变（随等待连续增长） |
| RR | 优先级与进程属性无关，只由"排到队首没有"决定 | 抢占（时钟中断） | — |
| 优先级调度 | 优先级由外部赋予，反映紧迫程度 | 两者皆可 | 两者皆可 |
教材正是这样统一的：FCFS 把等待时间当优先级，SJF 把作业长短当优先级，但这两种优先级都不能反映紧迫程度——所以才需要一个由外部赋值的优先级调度算法。
这张表的用处：遇到一个没见过的调度算法，先问"它的优先级函数是什么、这个函数随时间变不变、变了要不要重新抢占"，三个问题回答完，算法的行为就定了。
二、静态优先级与动态优先级
| 类型 | 何时确定 | 优点 | 缺点 |
|---|---|---|---|
| 静态优先级 | 创建进程时确定，整个运行期间保持不变，用一个范围内的整数（优先数）表示 | 简单易行、系统开销小 | 不够精确；低优先级进程可能长期得不到调度（饥饿） |
| 动态优先级 | 创建时先给一个初值，随进程推进或等待时间的增加而改变 | 灵活，可消解饥饿，可防止长作业垄断 CPU | 需要周期性重算，开销大 |
静态优先级的三条赋值依据：进程类型（系统进程如接收进程、对换进程高于一般用户进程）、对资源的需求（要求少的给较高优先级）、用户要求（按紧迫程度、所付费用）。另外两条常用的一般原则是交互型 > 非交互型与 I/O 密集型 > CPU 密集型——后者的理由要说清楚：
I/O 密集型进程拿到 CPU 后只用一小段就会去等 I/O ⇒ 优先让它跑，能让它尽快把 I/O 请求发出去 ⇒ I/O 设备提前忙起来，同时 CPU 立刻空出来给别人 ⇒ CPU 与外设并行度提高。反之若让 CPU 密集型先跑，I/O 设备会白白闲置一整段。
这与 FCFS 的护航效应是同一个道理的正反两面。
动态优先级依据两类信号调整：等待时间越长 → 优先级升高（这就是老化 Aging，防饥饿）；已占用 CPU 时间越长 → 优先级降低（防长作业垄断）。由此可推出老化的两个性质：它保证等待时间有上界（
若所有进程优先级初值相同且只按等待时间老化，那么最先进入就绪队列的进程优先级最先变得最高——动态优先级此时恰好退化成 FCFS，这也是上面那张"都是优先级调度特例"表的一个印证。
同样的老化机制在 多级反馈队列里以"周期性把低级队列进程提回高级队列"的形式出现，是同一件事的两种写法。
三、优先级反转问题
优先级反转（Priority Inversion）：高优先级进程被低优先级进程间接阻塞。
形成链条必须有三方，缺一方都不构成反转：
先拿到锁进入临界区 ⇒ 到达，需要同一把锁，只能阻塞 ⇒ 到达，优先级高于 、且不需要这把锁，于是抢占了 ⇒ 拿不到 CPU 就没法走完临界区、没法释放锁 ⇒ 只能继续等 ⇒ 结果是优先级最低的 事实上压住了优先级最高的 。
判据就在最后一句：真正压住
两种对策的共同思路是"让
| 对策 | 改动了什么 | 触发时机 | 代价与边界 |
|---|---|---|---|
| 优先级继承 (Priority Inheritance) | 改持锁进程的优先级： | 被动——只有当 | ① 继承可传递：若 |
| 优先级天花板 (Priority Ceiling) | 改锁的属性：给每把锁预先定一个"天花板优先级"＝所有可能访问它的进程中的最高优先级；任何进程一旦获得该锁，优先级立即提到天花板 | 主动——获得锁的瞬间就提升，不等 | ① 需要事先静态分析出"哪些进程会用这把锁"，动态系统里做不到；② 提升是无条件的，即使 |
一句话分界：继承是"出了事再补救"，天花板是"提前把事堵住"。
四、缺点
| 缺点 | 说明 | 判据／对策 |
|---|---|---|
| 饥饿 | 低优先级进程可能永远等不到 | 只在静态优先级下发生；判据是"排在它前面的进程数会不会无限增长"。对策是老化 |
| 优先级反转 | 见上节 | 对策是优先级继承或优先级天花板 |
| 优先级不易确定 | 外部赋值缺乏客观标准 | 动态优先级用等待/占用两类信号自动修正 |
同一组数据下抢占与非抢占各推一遍：分歧只源于一个时刻（想核对做题步骤、或看抢占到底改了哪几个指标时展开）
沿用共用进程数据，优先数越小优先级越高：
| 进程 | 到达时间 | 服务时间 | 优先数 |
|---|---|---|---|
| P1 | 0 | 7 | 3 |
| P2 | 2 | 4 | 1 |
| P3 | 4 | 1 | 4 |
| P4 | 5 | 4 | 2 |
非抢占式（只在当前进程完成时才做一次调度决策，中途不管来了谁）：
- t=0：只有 P1，执行 P1。这个决定一旦作出就不再更改——即使 t=2 来了优先级更高的 P2 也不换人。
- t=7：P1 完成。就绪的有 P2（1）、P3（4）、P4（2），选优先数最小的 P2。
- t=11：P2 完成。P3（4）、P4（2），选 P4。
- t=15：P4 完成，只剩 P3。
| 时间区间 | 0–7 | 7–11 | 11–15 | 15–16 |
|---|---|---|---|---|
| 执行进程 | P1 | P2 | P4 | P3 |
| 进程 | 完成时间 | 周转时间 | 带权周转时间 | 等待时间 | 响应时间 |
|---|---|---|---|---|---|
| P1 | 7 | 7 | 7/7 = 1.00 | 0 | 0 |
| P2 | 11 | 9 | 9/4 = 2.25 | 5 | 5 |
| P3 | 16 | 12 | 12/1 = 12.00 | 11 | 11 |
| P4 | 15 | 10 | 10/4 = 2.50 | 6 | 6 |
| 平均 | 9.50 | 4.44 | 5.50 | 5.50 |
抢占式（每当有新进程进入就绪队列，就把它的优先数与当前运行进程比较）：
- t=0：只有 P1（优先数 3），执行 P1。
- t=2：P2 到达，优先数 1 < 3，抢占。P1 剩余 5 回到就绪队列，执行 P2。
- t=4：P3 到达，优先数 4 > 1，不抢占；t=5：P4 到达，优先数 2 > 1，不抢占。
- t=6：P2 完成。就绪的有 P1（3）、P3（4）、P4（2），选 P4。
- t=10：P4 完成。P1（3）与 P3（4），选 P1。t=15：P1 完成，执行 P3。
| 时间区间 | 0–2 | 2–6 | 6–10 | 10–15 | 15–16 |
|---|---|---|---|---|---|
| 执行进程 | P1 | P2 | P4 | P1 | P3 |
| 进程 | 完成时间 | 周转时间 | 带权周转时间 | 等待时间（周转−服务） | 响应时间 |
|---|---|---|---|---|---|
| P1 | 15 | 15 | 15/7 ≈ 2.14 | 8 | 0 |
| P2 | 6 | 4 | 4/4 = 1.00 | 0 | 0 |
| P3 | 16 | 12 | 12/1 = 12.00 | 11 | 11 |
| P4 | 10 | 5 | 5/4 = 1.25 | 1 | 1 |
| 平均 | 9.00 | 4.10 | 5.00 | 3.00 |
| 指标 | 非抢占 | 抢占 | 差异来自哪里 |
|---|---|---|---|
| 平均周转时间 | 9.50 | 9.00 | 抢占让高优先级的 P2、P4 提前完成 |
| 平均带权周转 | 4.44 | 4.10 | 同上 |
| 平均等待时间 | 5.50 | 5.00 | 同上 |
| 平均响应时间 | 5.50 | 3.00 | 抢占式下 P2 一到就上 CPU，响应 0 |
| P2 完成时刻 | 11 | 6 | 唯一的分歧点在 t=2 |
| P1 完成时刻 | 7 | 15 | P1 被抢占后要重新排队 |
| P3（优先级最低）带权周转 | 12.00 | 12.00 | 两者都很难看——它的问题是优先级本身低，与抢不抢占无关 |
两张甘特图的全部分歧只源于 t=2 这一个时刻：非抢占式在那里什么也不做，抢占式在那里换了人，之后的差异都是这一步的连锁反应。
考点速记
- 优先级调度有两个互相独立的维度：抢占 / 非抢占、静态 / 动态。
- ⚠️前面的算法都是它的特例：FCFS 把"到达早晚"当优先级、SJF 把"作业长短"当优先级、HRRN 同时用上两者、RR 与进程属性无关。遇到陌生算法，问"优先级函数是什么、随时间变不变、变了抢不抢占"即可定其行为。
- 静态优先级按进程类型、对资源的需求、用户要求赋值，会饥饿。
- 动态优先级按两条信号调整：等待越久越高（这就是老化 Aging，防饥饿）、已占用 CPU 越久越低（防长作业垄断）。
档、调整周期 时等待上界为 。 - ⚠️抢占改善不了最低优先级进程的处境——抢占只让高优先级插队更快，治饥饿只能靠老化。这是两个不同维度的事。
- 典型的优先级赋值惯例：系统进程 > 用户进程、交互型 > 非交互型、I/O 密集型 > CPU 密集型。⚠️ 最后一条的理由是 I/O 密集型进程占用 CPU 的时间短，让它先跑能尽快把 I/O 发出去，从而让 CPU 与设备并行。
- 降低优先级的合理时机是进程刚使用完（占用了）一个时间片——它已经享受过服务了，该让别人来；⚠️ 而"进程刚从阻塞态变为就绪态"或"进程长期处于就绪队列"都应当提高优先级。
- 优先级反转是间接阻塞，必须凑齐三方才成立：持锁的低优先级
、等这把锁的高优先级 、不需要该锁却能抢占 的中优先级 。少一方就不发生。 - 两种对策的差别：优先级继承改的是持锁进程的优先级、被动触发（等到有人来等锁才提），需处理传递链；优先级天花板改的是锁的属性、主动触发（谁拿到锁就立刻提到该锁的天花板），需事先静态分析全部访问者，换来"最多被阻塞一次"与避免死锁。
这一节在真题里被考过的形式：
优先级调度是调度章手算题最多的一个——近年三道计算题全是它，另有两道概念题。
- 给各进程的到达时刻、优先级与执行时间，算周转时间或调度次序（2018-24 非抢占、2022-25 抢占、2023-29 抢占）。⚠️ 三处必须先在题干里圈出来：优先级数值大的优先还是小的优先（题目两种都出过，2022-25 是"值越小优先级越高"、2023-29 是"越大优先权越高"）、抢占还是非抢占、同优先级怎么排。第一处每年换，是最容易整题报废的地方。
- 问降低进程优先级的合理时机（2010-26）。答进程刚使用完一个时间片（速记第七条）。⚠️ 另三项（刚从阻塞变就绪、长期在就绪队列、刚被创建）都该提高或维持。
- 给各进程的计算时间与 I/O 时间，问怎样设置优先级能提高 CPU 利用率（2013-31）。答让 I/O 时间长（CPU 时间短）的进程优先级更高——速记第六条：先让它把 I/O 发出去，CPU 就能去跑别的。
- 基于优先数的动态调度大题（2016-46）。考的是老化机制怎么防饥饿，判据是速记第四、五条。
复习优先级：必须拿满，手算是重头。 做题前圈出那三件事（数值大小的方向、抢不抢占、同级怎么排）， 剩下就是按时刻推进。速记第五条（抢占治不了饥饿）和第七条（何时该降优先级）是概念题的固定落点。 优先级反转的三方条件与两种对策至今没单独考过，但它是理解"为什么加锁会引发调度问题"的关键，值得读懂。
易错：手算时默认"优先级数值大的先跑"。题目两种约定都出过，必须先看题干。
易错：认为抢占能解决饥饿。抢占只让高优先级插队更快，治饥饿只能靠老化。
易错：把"该降低优先级的时机"和"该提高的时机"搞反。刚用完一个时间片该降，刚从阻塞变就绪、等太久都该升。
易错：认为 CPU 密集型进程应该有更高优先级。反了——I/O 密集型优先，才能让 CPU 与设备并行。
易错：认为优先级反转只要有高低两个进程就会发生。必须凑齐三方，少了那个中优先级的
就不成立。
易错：把优先级继承与天花板的改动对象搞混。继承改进程的优先级（被动），天花板改锁的属性（主动）。
教材出处
- 汤小丹《计算机操作系统》3.2.4 优先级调度算法和高响应比优先调度算法（"FCFS 的等待时间就是优先级、SJF 的作业长短就是优先级，但都不能反映紧迫程度"），印刷 p90
- 汤小丹《计算机操作系统》3.3.3 优先级调度算法（抢占式与非抢占式的定义与比较规则、静态优先级的三条依据、动态优先级随等待与运行时间变化的规律），印刷 p94–p95
相关知识
调度的基本概念与目标｜时间片轮转调度｜高响应比优先调度｜多级反馈队列调度｜FCFS 先来先服务调度