How to calculate average waiting time of Round robin scheduling?

StackOverflow https://stackoverflow.com/questions/11644659

  •  23-06-2021
  •  | 
  •  

Question

Given this table : enter image description here

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

Was it helpful?

Solution

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.

OTHER TIPS

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

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 :)

|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]

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;
}

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

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top