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

Impossible

Isn't there a textbook formula for that? – Lejeune

@pst: There is , but here every process has several running times , hence there are several finish-times , for each process – Impossible

basic round robin does not take into account priorities? furhtermore basic round robin should always be deterministic? and how did you get your sequence? part of the question? – Cabby

@OsamaJaved: This question also involved priority algorithm as a side exercise , please disregard the priority column for the Round robin algorithm – Impossible

@ron: so p1 always ends at 28 , p2 always ends at 75 , p3 ends at 80, p4 ends at 69 and p5 at 72?. Essentially in this system there is only one finish time possible for each process? (Your first note contradicts this statement.) If not then how? – Cabby

I also don't understand the multiple end times comment - the table explicitly states one run for each process - not sure where the multiple runs come in – Cottier

the schedule you have posted is not correct. In round robin algorithm, the scheduler wakes up periodically (period = time slice) and schedules the next process. So in you schedule even though p4 completes its execution at time 69, the scheduler will not know that.it will wake up at 72 and schedule the next job. So at the time from 69 to 72, the CPU would be idle even though there are other processes waiting. – Fix

@arunmoezhi: So the times that I posted are incorrect ? where exactly is the mistake ? 10x – Impossible

Schedule length would be 4 * (ceil(12/4) + ceil(19/4) + ceil(21/4) + ..) = 4*(3+5+6+4+4) = 22*4=88 – Fix

@Fix That isn't how the scheduler works. When a process ends before the time quantum has elapsed control is released and context switches to the next process. It doesn't just idle while there is a queue. – Latticework

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.

Fix

For different arrival times it is easier to draw out the schedule and then compute the total waiting time by hand. For each process compute finish time - arrival time - execution time. Then take avg over all processes. – Fix

How would this apply to question 4 in the following: isro.gov.in/sites/default/files/pdf/recruitment/oldquepapers/sc/… . None of the options is correct by this logic. Please help. – Schoolhouse

Answer 2

You can calculate Waiting time by drawing Gantt chart so waiting time of ith process is equal to Completion time - (Arrival time + Burst time ) .

Mellman

Not Applicable here. – Schoolhouse

Answer 3

For RR, Waiting time = Last start time - arrival time - (preemption * quantum)

P1's last start time is 24 (when P1 running for 3rd time in Gannt chart) P1 preempted 2 times in it's lifetime Quantum = 4, Arrival = 0.

WaitingTime of P1 = 24 - 0 - (2 * 4) = 16 :)

Silvas

Answer 4

Here is one of the easier ways to find the Average Waiting Time (also added the Average Turnaround Time and Average Response Time). But you should know how to draw a Gantt chart for the Round Robin CPU scheduling.

Gantt Chart 
|P1|P1|P2|P3|P1|P4|P2|P5|P3|P4|P2|P5|P3|P4|P2|P5|P3|P4|P2|P5|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

• Turnaround Time = Completion Time - Arrival Time

• Waiting Time = Turnaround Time - Burst Time

  Process	AT	BT	CT	RS	TT	WT
  P1	0	12	20	0	20 - 0 = 20	20 - 12 = 8
  P2	5	19	72	3	72 - 5 = 67	67 - 19 = 48
  P3	8	21	80	4	80 - 8 = 72	72 - 21 = 51
  P4	11	13	69	9	69 - 11 = 58	58 - 13 = 45
  P5	15	15	75	13	75 - 15 = 60	60 - 15 = 45

Hence,

• Average Turnaround Time = (20+67+72+58+60)/5 = 55.4ms
• Average Waiting Time = (8+48+51+45+45)/5 = 39.4ms
• Average Response Time = (0+3+4+9+13)/5 = 5.8ms

AT - Arrival Time, BT - Burst Time, CT - Completion Time, RS - Response Time, TT - Turnaround Time, WT - Waiting Time

Sanborn

Thanks for you answer, really helped clarify some stuff for me. I think you made a small mistake though, response time should be (0+3+4+9+13)/5 = 5.8 You got the right answer so I'm assuming you just inputted the calculation wrong, P3 arrives at 8 and begins running at 12, so the value is 4, not 7 – Kingsley

Answer 5

|H |I |J |K |L | H| J| K|L |J |K|L |J |L |L | Its too lengthy, your answer in short is this: 0 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 average waiting time = ((H - arrival time) + (I - arrival time) + (J - arrival time) + (K - arrival time) + (L - arrival time))/ 5 =(24- 0) + (8-5) + (52 - 8) + (44-11) + (60 - 15)/ 5= 29.8 m sec Its too lengthy, your answer in short is this: Here it the Gantt chart of RR scheduling algorithm Process[burst time, time quantum, arrival time] H[8, 4, 0] I[4, 4, 5] J[16, 4, 8] k[12, 4, 11] L[20, constant = 4, 15]

Septicidal

Answer 6

I tried implement it in java:

public static float waitingTimieRobin(int[] arrival, int[] run, int q) {
    Queue<Integer> orderQueue = new LinkedList<>();
    orderQueue.add(0);
    Set<Integer> orderSet = new HashSet<>();
    orderSet.add(0);

    float sumTime = 0.0f;

    int curTime = 0;
    while (!isOver(run)) {

        int order = orderQueue.poll();
        orderSet.remove(order);
        int arrTime = arrival[order];
        int runtime = run[order];
        sumTime += (curTime - arrTime);
        if (runtime <= q) {
            curTime += runtime;
            run[order] = 0;
        } else {
            curTime += q;
            arrival[order] = curTime;
            run[order] = runtime - q;
        }

        for (int i = 0; i < run.length; i++) {
            if (arrival[i] > curTime) {
                break;
            } else if (i != order && run[i] != 0 && !orderSet.contains(i)) {
                orderQueue.add(i);
                orderSet.add(i);
            }
        }

        if(arrival[order] == curTime && run[order] != 0 && !orderSet.contains(order)) {
            orderQueue.add(order);
            orderSet.add(order);
        }
    }

    return sumTime / arrival.length;
}

public static boolean isOver(int[] run) {
    for (int runtime : run) {
        if (runtime > 0) {
            return false;
        }
    }
    return true;
}

Beacham

Although this code may help to solve the problem, it doesn't explain why and/or how it answers the question. Providing this additional context would significantly improve its long-term educational value. Please edit your answer to add explanation, including what limitations and assumptions apply. – Lotetgaronne

Answer 7

My answer is for the waiting time and turnaround time is

Waiting time: (16+51+51+45+42)/5=41 Turnaround time : (28+70+72+58+57)/5=57

Nahtanha

Maybe explain why it so. – Enlarger

Could you please elaborate on your answer? Where do you get the values you use to calculate from, always try to at least add a minimal explanation, otherwise your answer might not be of much use to other people looking for a answer to this question. – Revamp