scheduling - 在 SJF 算法中计算平均等待时间

Question

我了解抢占式 SJF 调度的工作原理，但我不知道如何计算平均等待时间。
这个示例取自 Galvin、Gagne 和 Silberschatz 的“OS 原则”。
他们将平均等待时间计算为：
((10-1)+(1-1)+(17-2)+(5-3)) / 4 = 6.5ms
这是如何计算的？请简化。
此外，如果您可以使用 RR 算法解决同样的问题，时间量为... 5ms（用于简单计算）并解释如何计算平均等待时间，那就太好了

Answer 1

看看图，计算一下每个进程，他等了多少时间：

P1在开始时运行1次（他是唯一的）因此他在这里等待0。然后，他从时间 1 等待到时间 10 -> 总等待时间 = (10-1)。

P2在时间1到达，并立即开始运行。所以他根本没有等待->（1-1）。

P3 在时间 2 到达，并在时间 17 -> (17-2) 开始运行。

P4 在时间 3 到达，并在时间 5 开始运行 -> 总等待时间 = (5-3)。

因此，平均等待时间 = ((10-1)+(1-1)+(17-2)+(5-3))/4 = 6.5ms。

编辑： 对于具有 5 个量子的 RR，这就是将要发生的事情：

P1 到达，并获得 5ms 的 quanta -> 在时间 5 中，他以剩余的突发 3 停止。接下来，P2 将从时间 5 开始运行到时间 9。（他的突发只有 4）。所以你让P2等待（5-1）。

P3 将从时间 9 到时间 14 开始运行，剩余脉冲数为 4。接下来，P4 将从时间 14 到时间 19 开始运行并结束。P4 的总等待时间为 (14-3)。

比 P1 将继续从时间 19 运行到时间 22 并将结束。P1 的总等待时间为 (19-5)。然后，P3 从时间 22 继续运行到时间 26。P3 的总等待时间为 (9-2) + (22-14)。

所以你得到平均运行时间 = ((5-1)+(14-3)+(19-5)+(9-2)+(22-14))/4 = 10.5ms