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

等待时间定义为每个进程在获得时间片之前必须等待多长时间。 在调度算法(例如Shorted Job First和First Come First Serve)中,我们可以轻松地找到等待时间,当我们排队作业并查看每个人在服务之前必须等待多长时间。 当谈到Round Robin或任何其他抢占式算法时,我们发现长时间运行的作业在CPU中花费一点时间,当它们被抢占然后等待一段时间轮到它执行时,在它的某个时刻,它会执行直到完成。我想找到理解这种调度算法中作业“等待时间”的最佳方法。 我找到了一个公式,给出了等待时间:
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的等候时间应该是: 最终开始时间 - (它在处理中花费的所有时间的总和)。 如果这个公式错了,为什么呢? 请帮助澄清我对这个概念的理解。     
已邀请:
你误解了“以前的CPU时间”中公式的含义。这实际上意味着与你所谓的“它在处理中花费的所有时间的总和”相同的东西。 (我猜“CPU中的上一次”应该是“先前在CPU上运行的总时间”的缩写,其中“先前”表示“在最终启动之前”。) 你仍然需要减去到达时间,因为这个过程显然没有在它到达之前等待。 (以防万一不清楚:“到达时间”是将作业提交给调度程序的时间。)在您的示例中,所有进程的到达时间为0,因此这不会产生任何影响,但是在一般情况下,需要考虑到达时间。 编辑:如果您查看您链接到的网页上的示例,进程P1在最终开始之前每次采用四个时间单位的两个时间片,并且其“CPU中的前一个时间”计算为8,与上面的解释一致。     
最后等待   值 - (时间量×(n-1)) 这里
n
表示进程到达甘特图时的次数。     

要回复问题请先登录注册