Average waiting time in Round Robin scheduling

Question

Waiting time is defined as how long each process has to wait before it gets it's time slice. In scheduling algorithms such as Shorted Job First and First Come First Serve, we can find that waiting time easily when we just queue up the jobs and see how long each one had to wait before it got serviced.

When it comes to Round Robin or any other preemptive algorithms, we find that long running jobs spend a little time in CPU, when they are preempted and then wait for sometime for it's turn to execute and at some point in it's turn, it executes till completion. I wanted to findout the best way to understand 'waiting time' of the jobs in such a scheduling algorithm.

I found a formula which gives waiting time as:

Waiting Time = (Final Start Time - Previous Time in CPU - Arrival Time)

But I fail to understand the reasoning for this formula. For e.g. Consider a job A which has a burst time of 30 units and round-robin happens at every 5 units. There are two more jobs B(10) and C(15).

The order in which these will be serviced would be:

0 A 5 B 10 C 15 A 20 B 25 C 30 A 35 C 40 A 45 A 50 A 55

Waiting time for A = 40 - 5 - 0

• I choose 40 because, after 40 A never waits. It just gets its time slices and goes on and on.
• Choose 5 because A spent in process previouly between 30 and 35.
• 0 is the start time.

Well, I have a doubt in this formula as why was 15 A 20 is not accounted for? Intuitively, I unable to get how this is getting us the waiting time for A, when we are just accounting for the penultimate execution only and then subtracting the arrival time.

According to me, the waiting time for A should be:

• Final Start time - (sum of all times it spend in the processing).

If this formula is wrong, why is it?

Please help clarify my understanding of this concept.

Solution

You've misunderstood what the formula means by "previous time in CPU". This actually means the same thing as what you call "sum of all times it spend in the processing". (I guess "previous time in CPU" is supposed to be short for "total time previously spent running on the CPU", where "previously" means "before the final start".)

You still need to subtract the arrival time because the process obviously wasn't waiting before it arrived. (Just in case this is unclear: The "arrival time" is the time when the job was submitted to the scheduler.) In your example, the arrival time for all processes is 0, so this doesn't make a difference there, but in the general case, the arrival time needs to be taken into account.

Edit: If you look at the example on the webpage you linked to, process P1 takes two time slices of four time units each before its final start, and its "previous time in CPU" is calculated as 8, consistent with the interpretation above.

Comments

[Rob]

Please add some clarification to your post.