GATE Overflow Test Series | Mixed Subjects | Test 4 | Question: 17

Question

Consider the following set of processes, assumed to have arrived at time $0$. Consider the CPU scheduling algorithms Shortest Job First (SJF) and Round Robin (RR). For RR, assume that the processes are scheduled in the order $P_1, P_2, P_3, P_4$.
$$\begin{array}{|l|l|l|l|l|} \hline \text{Processes} & P_1 & P_2 & P_3 & P_4
\\\hline \text{Burst time (in ms)} & 10& 9 & 4 & 6
\\\hline \end{array}$$
If the time quantum for RR is $5$ ms, then the absolute value of the difference between the average turnaround times (in ms) of SJF and RR (round off to $2$ decimal places is _________

Answer 1

 

SJF:

P3

P4

P2

P1

0       4          10         19           29

 

Round Robin:

Time Quantum = 5ms

Ready Queue : P1, P2, P3, P4, P1, P2, P4

P1

P2

P3

P4

P1

P2

P4

0      5       10      14       19       24      28         29

 

Processes	A.T.	B.T.	T.A.T for SJF	T.A.T for Round Robin
P1	0	10	29	24
P2	0	9	19	28
P3	0	4	4	14
P4	0	6	10	29

 

Average Turn Around Time for SJF = $\frac{29 + 19 + 4+10}{4}$ = 15.50

 

Average Turn Around Time for Round Robin = $\frac{24 + 28 + 14+29}{4}$ = 23.75

Absolute Difference between the Average Turn Around Time for Round Robin and Average Turn Around Time for SJF  is 8.25.

So, Answer is 8.25

Answer 2

Shortest Job First (SJF):

$$\begin{array}{|c|c|c|} \hline \textbf{Process Name} & \textbf{AT} & \textbf{BT} & \textbf{CT} & \textbf{TAT}
\\\hline P_{1} & 0 & 10 & 29 & 29
\\\hline P_{2} & 0 & 9 & 19 & 19
\\\hline P_{3} & 0 & 4 & 4 & 4
\\\hline P_{4} & 0 & 6 & 10 & 10
\\\hline \end{array}$$

$\text{Turn around time  =  Completion time – Arrival time}$

Grantt chart:

Average turn around time $ = \dfrac{29+19+4+10}{4} = \dfrac{62}{4} = 15.5\;\text{msec}$

Round robin scheduling with time quantum $ = 5\;\text{msec}:$

$$\begin{array}{|c|c|c|} \hline \textbf{Process Name} & \textbf{AT} & \textbf{BT} & \textbf{CT} & \textbf{TAT}
\\\hline P_{1} & 0 & 10 & 24 & 24
\\\hline P_{2} & 0 & 9 & 28 & 28
\\\hline P_{3} & 0 & 4 & 14 & 14
\\\hline P_{4} & 0 & 6 & 29 & 29
\\\hline \end{array}$$

$\text{Turn around time  =  Completion time – Arrival time}$

Queue$:P_{1}P_{2}P_{3}P_{4}P_{1}P_{2}P_{4}$

Grantt chart:

Average turn around time $ = \dfrac{ 24+28+14+29}{4} = \dfrac{95}{4} = 23.75\;\text{msec}$

The difference between the average turnaround times (in ms) of SJF and RR $ =  \mid 15.5 – 23.75 \mid  = \mid – 8.25 \mid = 8.25\;\text{msec}.$

So, the correct answer is $8.25\;\text{msec}.$