HRRN 示例

引言

HRRN 是 Highest Response Ratio Next Scheduling（最高响应比优先调度）的缩写。它是一种最优的调度算法。它是一种非抢占式调度算法，这意味着如果当前有一个进程正在执行，并且有一个新进程到达内存，而它的突发时间比当前正在运行的进程短，那么当前正在运行的进程不会被放入就绪队列，它可以在没有任何中断的情况下完成执行。

在下面的示例中，有 5 个进程。它们的到达时间和突发时间在表中给出。

在时间 0，进程 P0 到达，CPU 突发时间为 3 个单位。由于到目前为止这是唯一的进程，因此它将立即被调度。

P0 执行了 3 个单位，此时，只有一个进程 P1 在时间 3 到达。它将立即被调度，因为操作系统没有选择。

P1 执行了 5 个单位。此时，所有进程都可用了。我们需要计算所有剩余作业的响应比。

由于 P3 的响应比最高，因此 P3 将首先被调度。

P3 执行了 1 个单位。下一个可用进程是 P2 和 P4。让我们计算它们的响应比。

P2 的响应比更高，因此 P2 将被调度。

现在，唯一可用的进程是 P4，其突发时间为 2 个单位，因为没有其他进程可用，因此它将被调度。

等待时间 = 13/5

示例 1

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

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

GANTT 图生成

要生成 GANTT 图，我们将在调度程序被调用时计算每个实例的响应比。

在时间 = 0ms

系统中的进程：P1。

由于 P1 是唯一的进程，它会被立即调度。它在时间 = 6ms 完成。

到目前为止的 GANTT 图是 -

在时间 = 6ms

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

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

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

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

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

到目前为止的 GANTT 图是 -

在时间 = 10ms

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

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

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

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

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

到目前为止的 GANTT 图是 -

在时间 = 20ms

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

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

因此，最终的 GANTT 图是 -

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

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

TAT_P1 = CT_P1 - AT_P1 = 6 - 0 = 6 ms

TAT_P2 = CT_P2 - AT_P2 = 20 - 4 = 16 ms

TAT_P3 = CT_P3 - AT_P3 = 10 - 4 = 6 ms

TAT_P4 = CT_P4 - AT_P4 = 25 - 8 = 17 ms

平均周转时间

= 每个进程周转时间之和 / 进程数量

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

= (6 + 16 + 6 + 17) / 4 = 11.25 ms

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

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

WT_P1 = 0 - 0 = 0 ms

WT_P2 = 10 - 4 = 6 ms

WT_P3 = 6 - 4 = 2 ms

WT_P4 = 20 - 8 = 12 ms

平均等待时间

= 每个进程等待时间之和 / 进程数量

= (WT_P1 + WT_P2 + WT_P3 + WT_P4) / 4

= (0 + 6 + 2 + 12) / 4 = 5 ms

示例 2

这里，我们有几个具有不同突发时间和到达时间的进程，以及一个 GANTT 图来表示 CPU 分配时间。

说明

以上示例的解释如下：

• 在时间=0 时，就绪队列中没有进程可用，因此从 0 到 1 的时间是 CPU 空闲时间。因此，0 到 1 被视为 CPU 空闲时间。
• 在时间=1 时，只有进程 P1 在就绪队列中可用。因此，进程 P1 执行直到完成。
• 在进程 P1 之后，在时间=4 时，只有进程 P2 到达，因此进程 P2 执行，因为操作系统没有其他选择。
• 在时间=10 时，进程 P3、P4 和 P5 在就绪队列中。因此，为了调度 P2 之后的下一个进程，我们需要计算响应比。
• 在此步骤中，我们将计算 P3、P4 和 P5 的响应比。

响应比 = W+S/S

RR(P3) = [(10-5) +8]/8

= 1.625

RR(P4) = [(10-7) +4]/4

= 1.75

RR(P5) = [(10-8) +5]/5

= 1.4

从以上结果可以看出，进程 P4 具有最高的响应比，因此进程 P4 在 P2 之后被调度。

• 在时间 t=10，由于响应比值大，执行进程 P4。
• 现在在就绪队列中，我们有两个进程 P3 和 P5。在 P4 执行后，让我们计算 P3 和 P5 的响应比。

RR (P3) = [(14-5) +8]/8

=2.125

RR (P5) = [(14-8) +5]/5

=2.2

从以上结果可以看出，进程 P5 具有最高的响应比，因此进程 P5 在 P4 之后被调度。

• 在 t=14 时，进程 P5 被执行。
• 在 P5 完全执行后，P3 在就绪队列中，所以在时间 t=19，P3 被执行。

在下表中，我们将计算所有进程的周转时间、等待时间和完成时间。

平均等待时间是通过将所有进程的等待时间相加，然后除以进程数来计算的。

平均等待时间 = 所有进程的等待时间 / 进程数

平均等待时间=0+1+14+3+6/5=24/5 = 4.8ms

示例 3

考虑具有以下到达时间和突发时间的 5 个进程集 -

如果 CPU 调度策略是 Highest Response Ratio Next，则计算平均等待时间和平均周转时间。

解决方案

步骤 01

• 在 t = 0 时，只有进程 P0 在就绪队列中可用。
• 因此，进程 P0 执行直到完成。

步骤 02

• 在 t = 3 时，只有进程 P1 在就绪队列中可用。
• 因此，进程 P1 执行直到完成。

步骤 03

在 t = 9 时，进程 P2、P3 和 P4 在就绪队列中可用。

• 具有最高响应比的进程将首先执行。

响应比是

• 进程 P2 的响应比 = [(9-4) + 4] / 4 = 9 / 4 = 2.25
• 进程 P3 的响应比 = [(9-6) + 5] / 5 = 8 / 5 = 1.6
• 进程 P4 的响应比 = [(9-8) + 2] / 2 = 3 / 2 = 1.5

由于进程 P2 具有最高的响应比，因此进程 P2 执行直到完成。

步骤 04

• 在 t = 13 时，进程 P3 和 P4 在就绪队列中可用。
• 具有最高响应比的进程将首先执行。

响应比计算如下 -

• 进程 P3 的响应比 = [(13-6) + 5] / 5 = 12 / 5 = 2.4
• 进程 P4 的响应比 = [(13-8) + 2] / 2 = 7 / 2 = 3.5

由于进程 P4 具有最高的响应比，因此进程 P4 执行直到完成。

步骤 05

• 在 t = 15 时，只有进程 P3 在就绪队列中可用。
• 因此，进程 P3 执行直到完成。

现在，我们知道

• 周转时间 = 退出时间 - 到达时间
• 等待时间 = 周转时间 - 突发时间

现在，

• 平均周转时间 = (3 + 7 + 9 + 14 + 7) / 5 = 40 / 5 = 8 单位
• 平均等待时间 = (0 + 1 + 5 + 9 + 5) / 5 = 20 / 5 = 4 单位

C 语言中的 HRRN 调度示例

下面是 HRRN 调度的 C 程序

// Highest Response Ratio Next (HRRN) 调度的 C 程序

输出

常见问题

1. HRRN 在实际系统中是如何使用的？

HRRN 主要用于作业调度系统，其中进程的突发时间差异很大，例如批处理系统，以最小化等待时间并避免进程饿死。

2. 实现 HRRN 的常见挑战是什么？

• 动态计算每个进程的响应比。
• 确保每个进程的等待时间跟踪准确。
• 处理大量进程而不会产生显着的计算开销。

3. HRRN 如何处理 CPU 密集型和 I/O 密集型进程？

HRRN 倾向于偏爱等待时间较长的进程，其中可能包括突发时间较短的 I/O 密集型进程。CPU 密集型进程在累积了足够的等待时间后可能会被调度。

4. HRRN 调度的主要缺点是什么？

主要缺点是维护准确的等待时间和动态计算所有进程的响应比可能会增加复杂性。

5. HRRN 能否与其他调度算法结合使用？

是的，HRRN 可以与其他算法（如 Round Robin）结合使用，以处理不同的工作负载，确保公平性和响应性。

6. HRRN 如何防止饿死？

与 SJF 不同，HRRN 随着等待时间的增加而增加响应比，从而确保即使是较长的进程最终也会被调度。