高响应比优先调度

2026 大纲 二（二）4 CPU 调度算法的 HRRN（高响应比优先），它是 FCFS 与 SJF 之间的折中。指标口径与算例数据沿用调度的基本概念与目标。

交互可视化

加载可视化中...

既想先跑短的，又不想饿死长的

SJF 用"作业短不短"当优先级，效果最优但会饿死长作业； FCFS 用"来得早不早"当优先级，不会饿死人但会被长作业堵住。

一个只看服务时间，一个只看等待时间。那把两个都放进优先级函数里呢？

HRRN 就是这么做的，它的比较键是响应比：

R = \frac{等待时间 + 服务时间}{服务时间} = 1 + \frac{W}{S}

这个式子值得多看一眼，因为它不是随便凑的。 $R$ 的含义恰好是 "如果现在就调度它，它将得到的带权周转时间"——所以"选 $R$ 最大的" 这句话真正的意思是先救那个已经被拖累得最狠的。

至于为什么要除以服务时间：等 10 秒对一个只需 1 秒的作业是灾难，对一个要跑 1 小时的作业不算什么。 除法把等待折算成了 相对于自身工作量的倍数，这样长短作业才可比。

由此可以直接读出两个退化情形：等待时间都一样时它退化为 SJF（只剩 $1 / S$ 在比）， 服务时间都一样时它退化为 FCFS（只剩 $W$ 在比）。它确实同时含着两者。

它不会饥饿——新到的进程 $R = 1$ 是最小值，插不了队；而等得久的进程 $R$ 会一直涨上去，总能轮到。代价是每次调度都要遍历重算，而且仍然需要预知服务时间。

一、响应比公式的来历

高响应比优先（Highest Response Ratio Next, HRRN）每次调度时选响应比最高的就绪进程：

R = \frac{等待时间 + 服务时间}{服务时间} = 1 + \frac{等待时间}{服务时间}

其中等待时间 $W$ 从进程到达算到本次调度发生的时刻，服务时间 $S$ 是进程的固有属性、不随时间变化。

公式不是拼凑出来的，它有一个精确的含义——讲透这一层，算法就从"背公式"变成"能推"：

设当前时刻为 $t$ ，进程 $i$ 于 $A_{i}$ 到达、服务时间 $S_{i}$ ，此刻已等待 $W_{i} = t - A_{i}$ 。假设现在就把它调度上 CPU——HRRN 是非抢占的，它会一口气跑完 ⇒ 完成时刻 $= t + S_{i}$ ⇒ 周转时间 $= (t + S_{i}) - A_{i} = W_{i} + S_{i}$ ⇒ 带权周转时间 $= \frac{W_{i} + S_{i}}{S_{i}} = R_{i}$ 。

教材是从另一个方向说同一件事：等待时间与服务时间之和就是系统对该作业的响应时间，所以 $R = \frac{响应时间}{要求服务时间}$ 。

二、为什么是折中方案

把公式写成 $R = 1 + \frac{W}{S}$ ，两个极端就一目了然：

情况	公式退化成	谁被选中	等价于
各进程等待时间相同	$R = 1 + \frac{常数}{S}$ ，只由 $S$ 决定	服务时间短的 R 更大	SJF
各进程服务时间相同	$R = 1 + \frac{W}{常数}$ ，只由 $W$ 决定	等待时间长的 R 更大	FCFS
一般情况	两者按比值权衡	被拖累倍数最大的	两个极端之间的连续过渡

用优先级调度那张表的语言说：HRRN 的优先级函数同时用上了"等了多久"和"要干多久"两类信息，而 FCFS 只用前者、SJF 只用后者。

三、只有非抢占式：与 SRTF 的对照

	SRTF	HRRN
运行者的比较键	剩余时间，在减小	响应比，冻结不变
等待者的比较键	剩余时间，不变	响应比，在增大
两者的关系	差距越拉越大	差距在缩小，必然交越
因此抢占检查	只需在新进程到达时做一次	需要连续重算，无固定检查时刻
结论	抢占式可行且开销可控	抢占式不可行，只保留非抢占式

判据就是这句话：两个比较键是在拉开还是在靠拢。

四、不会饥饿：严格说法

只说"R 随等待时间增大"是不够的——SJF 里长作业的等待时间也在增大，可它照样饿死。关键在于增大的量有没有进入比较键。第一层理由最直白：

刚到达的进程 $W = 0$ ⇒ $R = 1$ ，这是响应比的最小可能值（ $R = 1 + W / S \geq 1$ ）⇒ 任何已经等待过一段时间的进程，其 $R$ 都严格大于 1 ⇒ 新来者永远抢不到已等待者的前面。

这一条就是 HRRN 与 SJF 的根本分野：SJF 里一个刚到的短作业可以立刻插到所有长作业前面，而且可以无限次这样做；HRRN 里做不到。

从"插不了队"到"等待时间有上界"的完整两步（想看"不会饥饿"怎么严格成立、以及过载这个前提从哪来时展开）

第二层：能超越 $J$ 的作业，服务时间必须严格小于 $J$ 。

设作业 $J$ 已等待 $W_{J}$ 、服务时间 $S_{J}$ ；作业 $k$ 在 $J$ 之后到达，故在同一时刻 $W_{k} < W_{J}$ 。 $k$ 要超越 $J$ ，需 $\frac{W_{k}}{S_{k}} > \frac{W_{J}}{S_{J}}$ ，即 $S_{k} < S_{J} \cdot \frac{W_{k}}{W_{J}} < S_{J}$ 。

第三层：因此等待时间有上界。 $R_{J} = 1 + W_{J} / S_{J}$ 随等待时间线性无上界地增长，而能压过它的只有那些"比它短、且已经等了相当久"的作业。只要系统不过载（新到作业的总服务需求增长不超过 CPU 的处理能力），这类作业的总量是有限的， $J$ 必然在有限时间内被调度。有上界，就不叫饥饿。

边界要交代清楚：如果系统持续过载（到达的工作量超过 CPU 能力），任何调度算法都会让某些作业无限期等待，这不是 HRRN 特有的问题。HRRN 的"不会饥饿"是在系统不过载的前提下成立的。

五、特点总结

特性	结论	判据／理由
抢占方式	只有非抢占式	运行者 R 冻结、等待者 R 上升，抢占式会持续交越，无固定检查时刻
是否饥饿	不会（系统不过载时）	新到者 R=1 是最小值，插不了队；能超越者必须更短且已等很久，总量有限
与 SJF 的关系	等待时间相同时等价于 SJF	分子中的 W 项成为常数
与 FCFS 的关系	服务时间相同时等价于 FCFS	分母成为常数
开销	明显大于 FCFS/SJF	每次调度都要遍历重算所有就绪进程的 R
依赖信息	仍需预知服务时间	与 SJF 一样，可用指数加权移动平均预测

响应比逐轮重算的完整走查，以及"改一个数就与 SJF 分道扬镳"（想在时间轴上看清 R 怎么随等待涨上来时展开）

沿用共用算例（到达 0/2/4/5、服务 7/4/1/4）。关键动作：只在"当前进程完成"的时刻才计算响应比，其余时刻什么也不做——HRRN 是非抢占的，中途算了也没用。

第一轮 t=0：只有 P1 到达， $R_{1} = (0 + 7) / 7 = 1$ ，别无选择，执行 P1 到 t=7。

第二轮 t=7（P1 完成，P2/P3/P4 均已到达）：

进程	到达	等待时间 $W = 7 - A$	服务 $S$	响应比 $R = (W + S) / S$
P2	2	7−2 = 5	4	(5+4)/4 = 2.25
P3	4	7−4 = 3	1	(3+1)/1 = 4.00 ← 最高
P4	5	7−5 = 2	4	(2+4)/4 = 1.50

选 P3。验证含义：P3 若此刻被调度，完成于 t=8，周转 8−4=4，带权周转 4/1 = 4.00——正好等于它的响应比。

第三轮 t=8（P3 完成）：必须全部重算，不能沿用上一轮的数。

进程	等待时间 $W = 8 - A$	服务 $S$	响应比
P2	8−2 = 6	4	(6+4)/4 = 2.50 ← 最高
P4	8−5 = 3	4	(3+4)/4 = 1.75

选 P2。注意 P2 的响应比从上一轮的 2.25 涨到了 2.50——它没做任何事，只是又多等了 1 个时间单位。这就是"随等待增长"的实际形态。

第四轮 t=12（P2 完成）：只剩 P4， $R_{4} = (7 + 4) / 4 = 2.75$ ，执行至 t=16。

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

进程	完成时间	周转时间	带权周转时间	等待时间	响应时间
P1	7	7	7/7 = 1.00	0	0
P3	8	4	4/1 = 4.00	3	3
P2	12	10	10/4 = 2.50	6	6
P4	16	11	11/4 = 2.75	7	7
平均		8.00	2.56	4.00	4.00

本例结果与 SJF 完全相同（甘特图逐段一致），这是数据凑巧——t=7 那一轮里 P3 的服务时间只有 1，等待项被 1 除之后放得极大，短作业优势压过了等待优势。

换一个数就会分道扬镳：只把 P2 的服务时间从 4 改成 6（其余不动），t=8 那一轮变成：

进程	等待 $W = 8 - A$	服务 $S$	响应比
P2	6	6	(6+6)/6 = 2.00 ← HRRN 选它
P4	3	4	(3+4)/4 = 1.75

而 SJF 在同一时刻比较的是服务时间 6 与 4，会选 P4。P2 靠"已经等了 6 个单位"赢得了这一轮，而 SJF 完全看不见这个信息。 这正是 HRRN 存在的理由。

考点速记

HRRN 选响应比 $R$ 最大者， $R = 1 + W / S$ （ $W$ 等待时间、 $S$ 服务时间）。
⚠️** $R$ 的含义是"若现在调度它、它将得到的带权周转时间"——所以"选 $R$ 最大"就是先救被拖累得最狠的那个。除以服务时间是把等待折算成相对自身工作量的倍数**，这样长短作业才可比。
两个退化情形：等待时间相同则退化为 SJF（只剩 $1 / S$ 在比），服务时间相同则退化为 FCFS（只剩 $W$ 在比）。
⚠️HRRN 只有非抢占式——运行者的 $R$ 冻结、等待者的 $R$ 持续上升，两键必然交越且没有固定的检查时刻，与 SRTF"两键越拉越开"正好相反。
它不会饥饿（系统不过载时）：新到者 $R = 1$ 是最小值、插不了队；能超越某个长作业的必须更短且已等很久，这样的进程数量有限，故等待有上界。
代价两条：每次调度都要遍历重算全部 $R$ ；而且仍然需要预知服务时间。

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

两道题都是概念题，考的是同一件事——"既要短任务优先、又不能饿死人"，这个组合只有 HRRN 满足。

问哪种调度算法综合考虑了进程的等待时间和执行时间（2009-24）。答高响应比优先。⚠️ 判据就在公式里： $R = 1 + W / S$ 同时含着等待时间 $W$ 与服务时间 $S$ ，而 FCFS 只看 $W$ 、SJF 只看 $S$ 。
问哪种算法满足短任务优先且不会发生饥饿（2011-23）。答高响应比优先。⚠️ 另三项各缺一半：SJF / SRTF 短任务优先但会饿死长作业；FCFS 不饿人但不满足短任务优先；RR 两条都不满足（它根本不比长短）。这道题是速记第三、五条的直接考法——HRRN 恰好把 SJF 与 FCFS 的优点各取一半。

复习优先级：必须拿满，但只考概念不考手算。 把公式 $R = 1 + W / S$ 与它的含义（"将得到的带权周转时间"）记住，两道题就都是送分。第四条（只有非抢占式）与第三条（两个退化情形）是选项里的常见素材。手算 HRRN 至今没考过，会算即可。

易错：认为 HRRN 有抢占式版本。只有非抢占——两个键会交越，没有固定的检查时刻。

易错：认为 HRRN 会饥饿。不会——新到者 $R = 1$ 是最小值，而等久了 $R$ 会一直涨上去。

易错：把响应比写成 $W / S$ 漏掉那个 1。 $R = 1 + W / S$ ，它是带权周转时间，最小值为 1。

易错：认为 HRRN 不需要预知服务时间。仍然需要—— $S$ 就在公式的分母上。

易错：把"综合考虑等待时间和执行时间"当成 SJF 或 FCFS。只有 HRRN 两个都看。

教材出处

汤小丹《计算机操作系统》3.2.4 优先级调度算法和高响应比优先调度算法（响应比公式及其"等待时间与服务时间之和就是系统对该作业的响应时间，故该优先级相当于响应比 $R_{P} =$ 响应时间 / 要求服务时间"的表述，以及等待时间相同偏向 SJF、服务时间相同偏向 FCFS、长作业优先级随等待提高三条推论），印刷 p90–p91

真题练习

2025Q252分 2024Q302分 2021Q252分 2020Q262分 2019Q272分 2017Q232分 2016Q466分 2014Q232分 2013Q312分 2011Q232分 2010Q262分 2009Q242分

高响应比优先调度

交互可视化

既想先跑短的，又不想饿死长的

一、响应比公式的来历

二、为什么是折中方案

三、只有非抢占式：与 SRTF 的对照

四、不会饥饿：严格说法

五、特点总结

考点速记

相关知识

真题练习

相关真题（12题）

相关文章

高响应比优先调度 ​

交互可视化 ​

既想先跑短的，又不想饿死长的 ​

一、响应比公式的来历 ​

二、为什么是折中方案 ​

三、只有非抢占式：与 SRTF 的对照 ​

四、不会饥饿：严格说法 ​

五、特点总结 ​

考点速记 ​

相关知识 ​

真题练习 ​

相关真题（12题）

相关文章

高响应比优先调度

交互可视化

既想先跑短的，又不想饿死长的

一、响应比公式的来历

二、为什么是折中方案

三、只有非抢占式：与 SRTF 的对照

四、不会饥饿：严格说法

五、特点总结

考点速记

相关知识

真题练习