CODEWITHSUNDEEP
processschedulinggantt-chart
JAN
JAN

Reputation: 21895

How to calculate average waiting time of Round robin scheduling?

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

Upvotes: 9

Views: 112192

Answers (7)

Sandun
Sandun

Reputation: 101

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

Upvotes: 2

Mike-wei
Mike-wei

Reputation: 1

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

Upvotes: 0

Ashis Kr. Das
Ashis Kr. Das

Reputation: 21

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

Upvotes: 2

user3919801
user3919801

Reputation: 529

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

Upvotes: 11

Jay_Jay
Jay_Jay

Reputation: 11

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

Upvotes: -1

user2242139
user2242139

Reputation: 11

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

Upvotes: 1

arunmoezhi
arunmoezhi

Reputation: 3200

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.

Upvotes: 1

Related Questions