HRRN算法（Highest Response Ratio Next）

定义：

HRRN（最高响应比优先）是一种非抢占式调度算法，旨在平衡任务的等待时间和执行时间。该算法根据任务的响应比（Response Ratio）来决定下一个执行的任务。响应比的计算公式为：

其中：

• 等待时间： 任务从到达时开始的等待时间。

• 服务时间： 任务的执行时间。

核心思想： 优先执行响应比最大的任务。响应比越大，意味着任务的等待时间越长，因此越优先执行。这样可以避免长时间等待的任务一直被延迟，从而减少“饥饿”现象。

特点：

• 非抢占式： 一旦任务开始执行，不会被打断。

• 响应比动态变化： 随着任务的等待时间增长，响应比会增大，增加了任务被执行的机会。

• 解决了SJF算法的饥饿问题： HRRN算法通过考虑等待时间，避免了SJF算法中长任务因为一直等待短任务而被“饿死”的问题。

优缺点：

• 优点：

  • 避免饥饿： 通过考虑任务的等待时间，避免了短任务一直占用CPU导致长任务得不到执行的饥饿问题。

  • 平衡任务的公平性和优先级： 通过响应比来平衡执行时间和等待时间，公平性较好。

  • 减少了等待时间： 相比FCFS和SJF，HRRN通过动态调整优先级，较好地减少了长任务的等待时间。

• 缺点：

  • 计算复杂： 需要不断更新等待时间，因此在某些情况下比其他的简单算法（如FCFS、SJF）稍显复杂。

  • 适用性差： 如果任务的到达时间不可预测或频繁变化，响应比的计算和更新可能会影响系统的性能。

  • 计算量大： 由于需要不断计算响应比，系统的计算开销较大，特别是在任务数目较多时。

适用场景：

HRRN 适用于任务有不同执行时间且任务间等待时间差异较大的系统，能够有效避免饥饿现象。适用于负载变化较小，能够提前了解任务到达和执行信息的环境。

HRRN算法例题

假设有 4 个任务，它们的到达时间和服务时间（执行时间）如下：

任务	到达时间 (Arrival Time)	服务时间 (Burst Time)
P1	0	6
P2	1	8
P3	2	7
P4	3	3

步骤 1：计算响应比并执行

HRRN 算法每次选择 响应比最大 的任务进行执行。响应比计算公式如下：

响应比=等待时间+服务时间服务时间\text{响应比} = \frac{\text{等待时间} + \text{服务时间}}{\text{服务时间}}

• P1：到达时间 0，服务时间 6，初始等待时间为 0，响应比 = (0 + 6) / 6 = 1
• P2：到达时间 1，服务时间 8，初始等待时间为 0，响应比 = (0 + 8) / 8 = 1
• P3：到达时间 2，服务时间 7，初始等待时间为 0，响应比 = (0 + 7) / 7 = 1
• P4：到达时间 3，服务时间 3，初始等待时间为 0，响应比 = (0 + 3) / 3 = 1

初始时，所有任务的响应比相同，因此可以选择 最早到达的任务，即 P1，进行执行。

步骤 2：执行过程

• 1. P1（到达时间 0，服务时间 6）执行，完成时间为 6。

• 2. P2（到达时间 1，服务时间 8）此时已经到达，P3（到达时间 2，服务时间 7）和 P4（到达时间 3，服务时间 3）也都到达。

  • 计算响应比：

    • P2：等待时间 = 6 - 1 = 5，响应比 = (5 + 8) / 8 = 1.625

    • P3：等待时间 = 6 - 2 = 4，响应比 = (4 + 7) / 7 = 1.571

    • P4：等待时间 = 6 - 3 = 3，响应比 = (3 + 3) / 3 = 2

  • P4 响应比最大，执行。

• 3. P4 执行，完成时间为 6 + 3 = 9。

• 4. P2 和 P3 剩下待执行，计算响应比：

  • P2：等待时间 = 9 - 1 = 8，响应比 = (8 + 8) / 8 = 2

  • P3：等待时间 = 9 - 2 = 7，响应比 = (7 + 7) / 7 = 2

  • 因为 P2 和 P3 响应比相同，可以选择最早到达的任务，即 P2。

• 5. P2 执行，完成时间为 9 + 8 = 17。

• 6. 最后执行 P3，完成时间为 17 + 7 = 24。

步骤 3：计算周转时间 (Turnaround Time) 和等待时间 (Waiting Time)

P1：
周转时间 = 完成时间 - 到达时间 = 6 - 0 = 6
等待时间 = 周转时间 - 服务时间 = 6 - 6 = 0
P2：
周转时间 = 完成时间 - 到达时间 = 17 - 1 = 16
等待时间 = 周转时间 - 服务时间 = 16 - 8 = 8
P3：
周转时间 = 完成时间 - 到达时间 = 24 - 2 = 22
等待时间 = 周转时间 - 服务时间 = 22 - 7 = 15
P4：
周转时间 = 完成时间 - 到达时间 = 9 - 3 = 6
等待时间 = 周转时间 - 服务时间 = 6 - 3 = 3

表格总结

任务	到达时间	服务时间	完成时间	周转时间	等待时间
P1	0	6	6	6	0
P2	1	8	17	16	8
P3	2	7	24	22	15
P4	3	3	9	6	3

平均等待时间：
平均等待时间=0+8+15+34=6.5\text{平均等待时间} = \frac{0 + 8 + 15 + 3}{4} = 6.5

平均周转时间：
平均周转时间=6+16+22+64=12.5\text{平均周转时间} = \frac{6 + 16 + 22 + 6}{4} = 12.5

分析

在这个例子中，HRRN 算法通过选择响应比最大的任务，平衡了等待时间和执行时间，从而避免了饥饿现象。具体来说：

• P4 在等待时间较长时被优先执行，确保了短任务不会一直被长任务阻塞。
• 相比于 SJF 算法，HRRN 更加公平，避免了长任务的饥饿问题，且每次选择的任务执行时间更灵活。

HRRN优缺点

• 优点：通过动态响应比的调整，避免了SJF算法的饥饿问题，能够平衡任务的公平性和优先级。
• 缺点：计算和更新响应比需要一定的计算资源，且随着任务数的增多，可能会增加系统的开销。