如何计算循环调度的平均等待时间？

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:此问题还涉及优先级算法作为辅助练习,请忽略循环算法的优先级列

Answer 1

您可以通过绘图计算等待时间,Gantt chart 因此第i个过程的等待时间等于Completion time - (Arrival time + Burst time ).

Answer 2

让我们首先尝试解决这个问题的简单版本，其中所有进程都在时间 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。

我想现在您应该已经了解这个公式是如何演变的了。理想情况下，人们希望调度的长度等于所有进程的执行时间之和。但并非所有的执行时间都是时间片的因素。因此，在某些时间片中，我们会遇到没有安排进程的漏洞。所以在实践中，调度的长度大于执行时间的总和。现在我们得到了总等待时间的差异。