最高响应比优先 (HRRN) 调度算法

---

---

CPU 调度算法是在多编程环境中决定就绪队列中哪个进程应该接下来执行的策略。有多种调度策略，其中最高响应比优先 (HRRN) 调度算法旨在提供最优的调度解决方案之一。

最高响应比优先 (HRRN) 调度算法

HRRN 算法是一种非抢占式调度策略，它根据一个称为响应比的参数选择下一个要执行的进程。响应比的计算公式如下：

$$\mathrm{响应比 = \frac{(等待时间 + 服务时间)}{服务时间}}$$

这里，W 是进程到现在的等待时间，S 是进程的突发时间。

当多个进程准备执行时，调度程序计算每个进程的响应比，并将 CPU 分配给具有最高值的进程。由于 HRRN 是一种非抢占式算法，一旦进程获得 CPU 访问权，它就会执行到完成，然后另一个进程才能获得 CPU 访问权。

HRRN 调度的特点

• HRRN 算法是最优算法，因为它根据进程的响应比选择要执行的进程。
• HRRN 既优先考虑较短的进程，也优先考虑在就绪队列中等待时间较长的进程。
• 它被设想为最短作业优先算法的改进，解决了 SJF 算法的饥饿问题。
• 由于它是非抢占式的，因此当进程完成执行或当新的进程到达空闲的就绪队列时，调度程序就会被调用。
• 它不需要频繁的上下文切换。这有助于 CPU 主要专注于进程的执行。

HRRN 算法的工作原理

• 最初当 CPU 空闲时，当一个或多个新进程到达就绪队列时，调度程序就会被调用。首先让具有最短突发时间的进程进入。
• 当正在运行的进程完成执行后，计算就绪队列中每个进程的响应比。将具有最高响应比的进程分配给 CPU。
• 重复执行步骤 2，直到就绪队列中没有进程。

HRRN 调度算法示例

我们可以通过以下示例来了解 HRRN 调度算法的工作原理。

让我们考虑一个系统，该系统有四个进程同时到达，顺序为 P1、P2、P3 和 P4。每个进程的突发时间（以毫秒为单位）由下表给出：

4

10

P3

4

4

P4

8

5

让我们对它进行 HRRN 调度。我们将绘制甘特图并找到平均周转时间和平均等待时间。

甘特图生成

要生成甘特图，我们将找到调度程序每次被调用时的响应比。

在时间 = 0 毫秒时

系统中的进程：P1。

8

由于 P1 是唯一进程，因此它立即被调度。它在时间 = 6 毫秒时运行完成。

到此时间的甘特图是：

在时间 = 6 毫秒时

进程 P1 完成执行并离开系统。

系统中的进程：P2 和 P3，它们都在时间 = 4 毫秒到达。

P2 的响应比 = (W + S) / S = (2 + 10) / 10 = 1.2

8

P3 的响应比 = (W + S) / S = (2 + 4) / 4 = 1.5

由于 P3 的响应比更高，因此将 P3 分配给 CPU。

在时间 = 10 毫秒时

进程 P3 完成执行并离开系统。

系统中的进程：P2（在时间 = 4 毫秒到达）和 P4（在时间 = 8 毫秒到达）。

P2 的响应比 = (W + S) / S = (6 + 10) / 10 = 1.6

P4 的响应比 = (W + S) / S = (2 + 5) / 5 = 1.4

由于 P2 的响应比更高，因此将 P2 分配给 CPU。

在时间 = 20 毫秒时

进程 P2 完成执行并离开系统。

系统中唯一的进程是 P4，因此它立即被调度。

因此，最终的甘特图是：

由此我们将计算每个进程的周转时间和等待时间及其平均值。

进程的周转时间 = 完成时间 - 到达时间

TAT_P1 = T_P1 - AT_P1 = 6 - 0 = 6 毫秒

TAT_P2 = CT_P2 - AT_P2 = 20 - 4 = 16 毫秒

TAT_P3 = CT_P3 - AT_P3 = 10 - 4 = 6 毫秒

TAT_P4 = CT_P4 - AT_P4 = 25 - 8 = 17 毫秒

平均周转时间

= 各进程周转时间之和 / 进程数

= (TAT_P1 + TAT_P2 + TAT_P3 + TAT_P4) / 4

= (6 + 16 + 6 + 17) / 4 = 11.25 毫秒

等待时间由每个进程在就绪队列中等待的时间给出。对于非抢占式调度算法，每个进程的等待时间计算如下：

任何进程的等待时间 = CPU 进入时间 - 到达时间

WT_P1 = 0 - 0 = 0 毫秒

• WT_P2 = 10 - 4 = 6 毫秒
• WT_P3 = 6 - 4 = 2 毫秒
• WT_P4 = 20 - 8 = 12 毫秒
• 平均等待时间

= 各进程等待时间之和 / 进程数

• = (WT_P1 + WT_P2 + WT_P3 + WT_P4) / 4
• = (0 + 6 + 2 + 12) / 4 = 5 毫秒
• HRRN 调度的优点

HRRN 算法是最优算法之一。

它更喜欢较短的进程，因此具有最短作业优先调度算法的所有优点。