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
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.
|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;
}
priorityalgorithm as a side exercise , please disregard the priority column for the Round robin algorithm – JAN