操作系统中的进程调度算法：最高响应比优先（Highest Response Ratio Next, HRRN） 1. 问题描述 最高响应比优先（HRRN）是一种非抢占式的进程调度算法，旨在平衡作业的等待时间和执行时间，避免饥饿现象。它通过计算每个进程的“响应比”，选择响应比最高的进程优先执行。响应比的定义为： \[ \text{响应比} = \frac{\text{等待时间} + \text{预计执行时间}}{\text{预计执行时间}} \] 其中， 等待时间 是进程在就绪队列中等待的时长， 预计执行时间 是进程需要占用CPU的时间。响应比越高，表示进程的“优先程度”越高。 2. 为什么需要HRRN？ 短作业优先（SJF）的缺陷 ：SJF优先执行短作业，但可能导致长作业因持续被短作业插队而饥饿。 先来先服务（FCFS）的缺陷 ：FCFS公平但效率低，短作业可能因长作业阻塞而等待过久。 HRRN的折中 ：通过响应比动态调整优先级，既照顾短作业（执行时间短则分母小，响应比易升高），又兼顾长作业（等待时间越长，分子增大，响应比逐渐升高）。 3. HRRN的调度步骤 假设就绪队列中有若干进程，每个进程已知预计执行时间（由用户或系统估算）。调度过程如下： 初始状态 ：所有进程按到达时间进入就绪队列，初始等待时间为0。 选择首个进程 ：第一个到达的进程先执行（非抢占式）。 计算响应比 ：当当前进程执行完毕后，根据此时各进程的等待时间重新计算响应比。 等待时间 = 当前时间 - 进程到达时间 - 已执行时间（对于未执行过的进程，已执行时间为0）。 选择最高响应比进程 ：选取响应比最大的进程投入运行。 重复步骤3-4 ：直到所有进程执行完毕。 4. 举例说明 假设有三个进程如下（到达时间均为0）： | 进程 | 到达时间 | 预计执行时间 | |------|----------|--------------| | P1 | 0 | 5单位 | | P2 | 0 | 3单位 | | P3 | 0 | 8单位 | 调度过程 ： 时刻0 ：所有进程就绪。初始响应比计算（等待时间=0）： P1响应比 = (0+5)/5 = 1.0 P2响应比 = (0+3)/3 = 1.0 P3响应比 = (0+8)/8 = 1.0 响应比相同，按FCFS选择P1执行。 时刻5 ：P1执行完毕。此时P2和P3的等待时间均为5，重新计算响应比： P2响应比 = (5+3)/3 ≈ 2.67 P3响应比 = (5+8)/8 = 1.625 选择响应比更高的P2执行。 时刻8 ：P2执行完毕。此时P3等待时间=8，响应比 = (8+8)/8 = 2.0（无其他进程，直接执行）。 时刻16 ：P3执行完毕。 调度顺序 ：P1 → P2 → P3。 对比SJF ：若用SJF，顺序为P2→P1→P3，但P3需等待8单位时间；HRRN通过响应比让P2在等待5单位后优先于P3执行，减少了平均等待时间。 5. HRRN的优缺点 优点 ： 避免饥饿：长作业等待越久，响应比越高，最终会被调度。 平衡效率与公平：兼顾短作业和长作业的需求。 缺点 ： 非抢占式：无法及时响应紧急任务。 需要预知执行时间：实际中难以精确估算。 计算开销：每次调度需遍历队列计算响应比。 6. 实际应用与变体 HRRN较少直接用于现代操作系统（因需预知执行时间），但其思想影响了后续算法（如Linux CFS中的动态优先级调整）。可结合抢占机制改进为 动态优先级调度 ，例如根据等待时间周期性提升进程优先级。