循环轮询 (RR) 调度算法

在 CPU 调度策略中，循环轮询调度是最有效和最广泛使用的调度算法之一，它不仅适用于操作系统的进程调度，也适用于网络调度。

循环轮询 (RR) 调度

这种调度策略的名字来源于古老的循环轮询原则，该原则主张所有参与者都应该轮流平等地共享资产或机会。在 RR 调度中，每个进程获得相等的时间片（或时间量子），依次在 CPU 上执行。当一个进程轮到它时，它会执行分配的时间片，然后释放 CPU 供队列中的下一个进程使用。如果进程还有剩余的突发时间，则将其发送到队列的末尾。进程按照先到先服务（FCFS）的原则进入队列。

循环轮询调度是抢占式的，这意味着正在运行的进程可能会被另一个进程中断并发送到就绪队列，即使它尚未在 CPU 中完成整个执行。它是先到先服务 (FCFS) 调度算法的抢占式版本。

循环轮询调度的特点

• RR 是一种公平的调度策略，所有进程都获得平等的份额以轮流执行。
• 它是一种抢占式调度方法，正在执行的进程必须在时间量子到期后放弃对 CPU 的控制。
• 通过 RR 调度策略，任何进程都不会发生饥饿现象。
• 它因其简单的运行原理而被广泛使用。
• RR 调度的性能很大程度上取决于所选择的时间量子。

循环轮询调度的运行原理

• 任何到达系统的新的进程都以 FCFS 的方式插入到就绪队列的末尾。
• 队列中的第一个进程被移除并分配到 CPU。
• 如果所需的突发时间小于或等于时间量子，则该进程运行到完成。当进程完成执行时，调度程序被调用以让就绪队列中的下一个进程进入 CPU。
• 如果所需的突发时间大于时间量子，则进程执行到分配的时间量子。然后更新其 PCB（进程控制块）状态，并将其添加到队列的末尾。发生上下文切换，就绪队列中的下一个进程被分配到 CPU。
• 重复上述步骤，直到就绪队列中没有更多进程。

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

循环轮询调度的示例

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

让我们考虑时间量子为 2 毫秒，并对它执行 RR 调度。我们将绘制甘特图并找到平均周转时间和平均等待时间。

时间量子为 2 毫秒的甘特图

平均周转时间

平均 TAT = 每个进程的周转时间之和 / 进程数

$\mathrm{= \: (TAT_{P1} \: + \: TAT_{P2} \: + \: TAT_{P3} \: + \: TAT_{P4})/4}$

= ( 24 + 28 + 22+ 16) / 4 = 22.5 毫秒

为了计算每个进程的等待时间，我们将时间量子乘以进程在就绪队列中等待的时间片数。

平均等待时间

平均 WT = 每个进程的等待时间之和 / 进程数

$\mathrm{= \: (WT_{P1} \: + \: WT_{P2} \: + \: WT_{P3} \: + \: WT_{P4})/4}$

= ( 8*2 + 9*2+ 8*2+ 6*2) / 4 = 15.5 毫秒

循环轮询调度的优点

• 循环轮询调度是最公平的调度算法，所有进程都获得相等的时间量子进行执行。
• 在 RR 调度中，完全消除了任何进程由于在就绪队列中无限期等待而导致的饥饿现象。
• 它不需要任何复杂的方法来计算每个进程的 CPU 突发时间，然后才能进行调度。
• 它非常易于实现，因此在各种情况下都有应用。
• 在 RR 调度中不会发生像先到先服务 CPU (FCFS) 调度中那样的车队效应。

循环轮询调度的缺点

• 循环轮询调度的性能高度依赖于所选择的时间量子。这需要在实施之前进行谨慎的分析，否则无法获得所需的结果。
• 如果选择的时间量子过大，大多数进程将在突发时间内完成。实际上，RR 调度将充当 FCFS 调度。因此，FCFS 的所有限制都将进入系统。
• 如果选择的时间量子过小，CPU 将非常忙于上下文切换，即在 CPU 和内存之间交换进和交换出进程。这将降低系统的吞吐量，因为更多的时间将花费在上下文切换上，而不是进程的实际执行上。
• RR 调度没有提供为进程分配优先级的范围。因此，需要高优先级的系统进程与后台进程获得相同的优先级。这通常会影响系统的整体性能。

结论

如果正确实现，循环轮询调度可以为调度问题提供最简单和最佳的解决方案。为了避免该算法的缺点，正在研究和实施许多 RR 调度的变体。有助于提供接近完美时间量子的一个变体是动态时间量子调度。在这里，时间量子根据系统中进程的行为动态变化。另一个变体，自私循环轮询调度，为进程分配优先级，并为高优先级进程提供更多 CPU 时间片。