algorithm - Round Robin 调度中的平均等待时间

Question

等待时间定义为每个进程在获得时间片之前必须等待的时间。在 Shorted Job First 和 First Come First Serve 等调度算法中，我们可以很容易地发现等待时间，当我们只是将作业排队并查看每个作业在得到服务之前需要等待多长时间。

当谈到 Round Robin 或任何其他抢占式算法时，我们发现长时间运行的作业会在 CPU 中花费一点时间，当它们被抢占时，然后等待一段时间轮到它执行，在轮到它的某个时刻，它执行直到完成。我想找出了解此类调度算法中作业“等待时间”的最佳方法。

我找到了一个 formula等待时间为:

Waiting Time = (Final Start Time - Previous Time in CPU - Arrival Time)

但是我不明白这个公式的推理。例如考虑一个工作 A，其突发时间为 30 个单位，并且每 5 个单位发生一次循环。还有两个作业 B(10) 和 C(15)。

这些服务的顺序是:

0 A 5 B 10 C 15 A 20 B 25 C 30 A 35 C 40 A 45 A 50 A 55

A 的等待时间 = 40 - 5 - 0

• 我选择 40 是因为，40 之后 A 永远不会等待。它只是得到它的时间片并继续下去。
• 选择 5，因为 A 之前在流程中的花费在 30 到 35 之间。
• 0 是开始时间。

嗯，我对这个公式有疑问，为什么 15 A 20 没有计算在内？直觉上，当我们只考虑倒数第二个执行然后减去到达时间时，我无法理解这是如何让我们等待 A 的时间。

按照我的说法，A的等待时间应该是:

• 最终开始时间 -(它在处理中花费的所有时间的总和)。

如果这个公式是错误的，为什么？

请帮助澄清我对这个概念的理解。

Answer 1

您误解了公式中“先前在 CPU 中的时间”的含义。这实际上与您所说的“它在处理过程中花费的所有时间的总和”具有相同的含义。 (我猜“previous time in CPU”应该是“total time previously spent running on the CPU”的缩写，其中“previously”的意思是“最后开始之前”。)

您仍然需要减去到达时间，因为在到达之前进程显然没有等待。 (以防万一不清楚:“到达时间”是作业提交给调度程序的时间。)在您的示例中，所有进程的到达时间都是 0，所以这没有什么区别，但是在一般情况下，需要考虑到达时间。

编辑:如果您查看链接到的网页上的示例，进程 P1 在其最终启动之前需要两个时间片，每个时间片为四个时间单位，其“先前在 CPU 中的时间”计算为 8，与解释如上。