Appearance
高响应比优先调度
考情分析
HRRN 是 FCFS 和 SJF 的折中方案，408 真题中以计算题形式出现。属于 🔥🔥 中高频考点。
FCFS 偏心长作业，SJF 偏心短作业——能不能综合考虑"等了多久"和"要干多久"，让两边都不吃亏？HRRN 用一个响应比公式做到了这一点。
算法规则
高响应比优先（Highest Response Ratio Next, HRRN）：每次调度时计算所有就绪进程的响应比，选择响应比最高的进程执行。
HRRN 是非抢占式算法。
为什么是折中方案
| 情况 | 响应比表现 | 等同于 |
|---|---|---|
| 等待时间相同 | 服务时间短的 R 更大 | 偏向 SJF |
| 服务时间相同 | 等待时间长的 R 更大 | 偏向 FCFS |
| 随等待时间增加 | 长作业的 R 逐渐增大 | 不会饥饿 |
调度示例
| 进程 | 到达时间 | 服务时间 |
|---|---|---|
| P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |
t=0：只有 P1 到达，执行 P1。
t=7（P1 完成，计算各进程的响应比）：
| 进程 | 等待时间 | 服务时间 | 响应比 |
|---|---|---|---|
| P2 | 7-2=5 | 4 | (5+4)/4 = 2.25 |
| P3 | 7-4=3 | 1 | (3+1)/1 = 4.00 ← 最高 |
| P4 | 7-5=2 | 4 | (2+4)/4 = 1.50 |
选择 P3 执行。
t=8（P3 完成）：
| 进程 | 等待时间 | 服务时间 | 响应比 |
|---|---|---|---|
| P2 | 8-2=6 | 4 | (6+4)/4 = 2.50 ← 最高 |
| P4 | 8-5=3 | 4 | (3+4)/4 = 1.75 |
选择 P2 执行。
t=12（P2 完成）：执行 P4。
时间: 0 7 8 12 16
├───────────┤──┤────────┤────────┤
P1 P3 P2 P4| 进程 | 完成时间 | 周转时间 | 带权周转时间 |
|---|---|---|---|
| P1 | 7 | 7 | 1.00 |
| P3 | 8 | 4 | 4.00 |
| P2 | 12 | 10 | 2.50 |
| P4 | 16 | 11 | 2.75 |
| 平均 | 8.00 | 2.56 |
交互可视化
特点总结
| 特性 | 结论 |
|---|---|
| 抢占方式 | 非抢占式 |
| 是否饥饿 | 不会饥饿（等待越久响应比越高） |
| 适用场景 | 兼顾长短作业 |
| 缺点 | 每次调度都要计算所有进程的响应比，开销大 |
考研高频考点
- 🔥🔥🔥 响应比的计算公式和具体数值计算
- 🔥🔥 HRRN 综合了 FCFS 和 SJF 的优点
- 🔥🔥 HRRN 不会导致饥饿
- 🔥 HRRN 只有非抢占式实现
到这里，单队列的调度算法都介绍完了。但实际系统中不同类型的进程差异很大，能不能用多个队列分开管理？下一篇看多级队列调度。