How to calculate average waiting time of Round robin scheduling?

Question

Given this table :

Those are the time lines (time slice = 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

Is there a simple way to calculate the average waiting time ?

Thanks

Note: that there are several finish times for each process !

Note2 : This question also involved priority algorithm as a side exercise , please disregard the priority column for the Round robin algorithm

Answer 1

Let's first try to solve the simple version of this problem where all process arrive at time 0. Assume we have n processes each with execution time as ei. Let the time slice be s. Let the number of time slices needed for each process be NSPi. Now we have NSPi = ceiling(ei/s). Time needed for a process i = NSPi * s. Length of the schedule = sum over i from 1 to n (NSPi). Waiting time for process i = finish time of i - execution time of i. But computing finish time of each process is complicated as each process has a different execution time. But since you just need the avg waiting time of RR algorithm for a specific instance, you could compute that as: (Length of the schedule - sum of execution time of all processes)/num of processes.

I guess by now you would have got an idea of how this formula has evolved. Ideally one would like the length of the schedule to be equal to the sum of execution time of all processes. But not all the execution times are a factor of the time slices. So in some time slice we get holes where no process is scheduled. So in practice, the length of the schedule is greater than the sum of execution times. Now we have their difference as the total waiting time.