Python中的轮询调度算法

引言

在本篇文章中，我们将学习 Python 中的轮转调度算法。轮转法是一种 CPU 调度算法，其中每个进程在轮转过程中被分配一个时间片。它是先来先服务（FCFS）CPU 调度算法的抢占版本。

轮转 CPU 调度算法通常侧重于时间共享的进程。进程或任务在抢占模式下允许运行的时间量称为时间量子。队列中的所有进程或任务当前都会被分配 CPU。如果进程在此时间完成执行，则事务将终止。否则，让进程返回等待列表并等待一段时间。下一轮将完成。

什么是轮转调度？

轮转调度是一种抢占调度算法，其中每个进程都有一个时间片或量子用于执行。CPU 调度以循环顺序将 CPU 时间分配给进程，因此这种调度算法被称为“轮转”。当进程过期时，它将被取消并添加到等待队列的末尾。下一个程序将获得 CPU 时间片。

每个周期的持续时间或量子通常很小，通常在 10 到 100 毫秒之间。时间小的优点是每个进程获得更多的 CPU 时间，并且通过改变进程的频率可以有效地利用 CPU。

轮转 CPU 调度算法的特点是什么？

Python 中的轮转 CPU 调度算法有一些特点，如下所示：

1. 该算法简单易用。它不会出现饥饿问题，因为进程会获得相当多的 CPU 时间。
2. 轮转调度算法被广泛使用。
3. 作为核心 CPU 调度中最常用的技术之一。
4. 它是抢占式的，因为进程大部分时间只分配 CPU。
5. 缺点是内容切换成本更高。
6. 切片时间应尽可能小，并分配给需要完成的特定任务。但是，根据执行的操作，情况可能会发生变化。
7. 优先级操作将被添加到队列的末尾。
8. 在固定时间后，CPU 会被传输到下一个进程，称为量子时间或切片时间。
9. 轮转 CPU 调度算法是一种实时算法，可以在特定时间响应事件。
10. 轮转 CPU 调度算法是一种时钟驱动的混合模型。
11. 它是最古老、最公平、最简单的算法之一。

轮转 CPU 调度算法的优点是什么？

Python 中的轮转 CPU 调度算法有一些优点，如下所示：

1. 公平性体现在每个进程获得相等的 CPU 时间。
2. 新的设计进程将被添加到就绪队列的末尾。
3. 轮转 CPU 调度算法经常使用时间共享，并为每个作业分配时间或间隔。
4. 在执行竞争性轮转 CPU 调度算法时，会为不同的任务分配特定的时间。
5. 在此期间，每个进程在达到特定量子时间后会重置。

轮转 CPU 调度算法的缺点是什么？

Python 中的轮转 CPU 调度算法有一些缺点，如下所示：

1. 在这里，等待时间和响应时间非常长。
2. 轮转 CPU 调度提供的吞吐量较低。
3. 在此算法中可能会发生内容切换。
4. 甘特图看起来非常大（如果调度的时间量子很小。例如，如果提供 1 毫秒的时间，则会产生一个大的调度）。
5. 此调度中的时间消耗是由于量子小。

轮转调度算法通过示例进行描述。

这里我们举例说明 Python 中的轮转调度算法，如下所示：

示例

给定时间量子 = 2，考虑下表中四个进程 P1、P2、P3 和 P4 的到达时间和突发时间。

轮转 CPU 调度算法将按照以下步骤运行

当时间 = 0 时，

执行从进程 P1 开始，突发时间为 6，到达时间为 0。这里，每个操作执行 2 毫秒（量子时间）。P2 和 P3 仍在队列中等待。

当时间 = 2 时，

进程 P2 和 P3 到达就绪队列，P2 开始完成 TQ 周期。

当时间 = 4 时，

进程 P4 到达就绪队列，然后 P3 执行 TQ 周期。

当时间 = 6 时，

然后，P3 进程完成其执行，P1 进程开始在其 TQ 周期内执行，因为它在 b 中排在下一位。

当时间 = 8 时，

当 P4 进程开始运行时，它未达到时间量子周期，因为其突发时间为 1。因此，它仅执行 1 毫秒。

当时间 = 9 时，

然后，P4 进程完成其执行，P2 进程作为就绪队列中的下一个步骤执行 TQ 周期。

当时间 = 11 时，

然后，P2 进程完成其执行，P1 进程成功开始其执行；它仅需 1 毫秒即可完成。

当时间 = 12 时

然后，P1 进程完成了其执行，并且整个进程的执行如下所示。

如何使用轮转 CPU 调度算法计算完成时间 (CT)、周转时间 (TAT) 和等待时间 (WT)？

在这里，我们将学习如何在轮转 CPU 调度算法中计算以下时间。

完成时间 (CT)

这是进程执行完成的时间。

周转时间 (TAT)

它指的是进程的完成时间和到达时间之间的时间差。

周转时间 (TAT) = (完成时间 - 到达时间) = (CT - AT)

等待时间 (WT)

它指的是周转时间 (TAT) 和突发时间之间的时间差。

等待时间 = 周转时间 - 突发时间

现在，我们在下表中计算周转时间 (TAT) 和等待时间 (WT)

所以，

现在平均周转时间 = (12 + 10 + 4 + 5) / 4 = 7.75

平均等待时间 = (6 + 6 + 2 + 6) / 4 = 5

编写一个轮转 CPU 调度的程序，其中所有进程的到达时间均为 0。

计算等待时间 (WT) 的一些步骤

1. 首先，我们创建一个 rem_bt[] 数组来监控进程的附加突发时间。此数组最初是突发时间数组 bt[] 的副本。
2. 然后，我们创建另一个 wt[] 数组或等待时间数组来存储操作的等待时间。将此数组初始化为 0。
3. 初始化时间: t = 0
4. 当所有操作都尚未完成时，继续进行。如果不是，则对第 i 个进程执行以下操作。
5. 如果 rem_bt[i] > Quantum
   1. t = t + Quantum
   2. rem_bt[i] -= Quantum;
6. 否则 // 结束此操作的循环
7. t = t + rem_bt[i];
8. wt[i] = t - bt[i]
9. rem_bt[i] = 0; // 此处进程已完成

有了等待时间后，我们就可以计算周转时间或 tat[i] 为等待时间和突发时间的总和，例如，wt[i] + bt[i]

程序代码

在这里，我们编写了 Python 中轮转调度算法的程序代码。代码现在如下所示：

输出

现在，我们在 Python 中编译上述代码，成功编译后运行它。输出如下：

Processes    Burst Time     Waiting Time    Turn-Around Time
  1 		 5 		 7 		 12
  2 		 3 		 6 		 9
  3 		 8 		 8 		 16

The Average Waiting Time is 7.00000 
The Average Turn Around Time is 12.33333