process - 如何计算轮转调度的平均等待时间？

Question

给定此表:

这些是时间线(时间片= 4):

|p1|p1|p2|p3|p4|p5|p1|p2|p3|p4|p5|p2|p3|p4|p5|p2|p3|p4|p5|p2|p3|p3|
0  4  8 12 16  20 24 28 32 36 40 44 48 52 56 60 64 68 69 72 75 79 80

是否有一种简单的方法来计算平均等待时间？

谢谢

注意:每个过程有多个完成时间!

注2 :该问题也涉及优先级算法，作为辅助练习，请忽略Round robin算法的优先级列

Answer 1

让我们首先尝试解决此问题的简单版本，其中所有进程都在时间0到达。
假设我们有n进程，每个进程的执行时间为ei。让时间片为s。
让每个进程所需的时间片数量为NSPi。
现在我们有了NSPi = ceiling(ei/s)。处理所需的时间i = NSPi * s。计划的长度= sum over i from 1 to n (NSPi)。
等待过程i = finish time of i - execution time of i的时间。但是，由于每个进程具有不同的执行时间，因此每个进程的计算完成时间很复杂。但由于您只需要特定实例的RR算法的平均等待时间，因此可以将其计算为:(Length of the schedule - sum of execution time of all processes)/num of processes。

我猜到现在您已经对这个公式的演变有了一个想法。理想情况下，希望调度程序的长度等于所有进程的执行时间之和。但是，并非所有执行时间都是时间片的一个因素。因此，在某个时间片中，我们会遇到没有计划任何流程的漏洞。因此，实际上，调度的长度大于执行时间的总和。现在，我们将它们的差异作为总等待时间。