How to calculate the average waiting time for Round robin planning?

Question

Given this table:

These are timelines (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 an easy way to calculate average wait time?

thanks

Note: that for each process there are several finishes!

Note 2 . This question also included the priority algorithm as a side exercise, please ignore the priority column for the Round robin algorithm.

Answer 1

Let us first try to solve a simple version of this problem when the whole process arrives at time 0. Suppose that n treats each with a run-time like ei . Let the time slice be s . Let the number of time slots required for each process be NSPi . Now we have NSPi = ceiling(ei/s) . The time required for the process is i = NSPi * s . Graph Length = sum over i from 1 to n (NSPi) . Process timeout i = finish time of i - execution time of i . But the end time for processing each process is complex, since each process has a different execution time. But since you just need the avg timeout for the RR algorithm for a specific instance, you can calculate this as: (Length of the schedule - sum of execution time of all processes)/num of processes .

You probably now have an idea of ​​how this formula evolved. Ideally, I would like the length of the graph to be equal to the sum of the execution time of all processes. But not all runtimes are a factor in time fragments. Therefore, for a certain period of time we get holes where the process is not planned. Thus, in practice, the length of the graph is longer than the sum of the execution time. Now we have a difference as the total waiting time.

Answer 2

You can calculate the wait time by drawing the Gantt chart , so the wait time of the i-th process is Completion time - (Arrival time + Burst time ) .

Answer 3

For RR, latency = time of last run - time of arrival - (prevention * quantum)

The last start time of P1 is 24 (when P1 runs the 3rd time in the Gantt chart) P1 is unloaded 2 times during its lifetime Quant = 4, Arrival = 0.

Waiting time P1 = 24 - 0 - (2 * 4) = 16 :)

Answer 4

| H | me | J | K | L | H | J | K | L | J | K | L | J | L | L | Too long, short answer: 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 s Too long, short answer: Here is the Gantt chart according to the planning algorithm RR Process [burst time, time slice, arrival time] H [8, 4, 0] I [4, 4, 5] J [16, 4, 8 ] k [12, 4, 11] L [20, constant = 4, 15]

Answer 5

I tried to 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; } 

Answer 6

My answer is on timeout and processing time

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