GATE 2024 CS2 Q.37: solution and answer

Official answer: BSource: Official answer key, GATE 2024 CS2 (IISc Bengaluru)

1. Process table: $$\begin{array}{ccc}\text{Process}& \text{Arrival}& \text{Burst}\\ A& 0& 10\\ B& 2& 6\\ C& 4& 3\\ D& 6& 7\end{array}$$ Waiting time $=$ completion $-$ arrival $-$ burst.

2. SRTF timeline: A runs 0 to 2 (remaining 8). At 2, B arrives with 6, less than 8, so B preempts A and runs 2 to 4 (remaining 4). At 4, C arrives with 3, less than B's remaining 4, so C preempts B.

3. C runs 4 to 7. D arrives at 6 with 7, but C has 1 left, so C continues and finishes at 7. Remaining times are A 8, B 4, D 7, so B runs 7 to 11, then D runs 11 to 18, then A runs 18 to 26.

4. SRTF Gantt chart: $$\begin{array}{cccccc}A& B& C& B& D& A\\ 0\text{-}2& 2\text{-}4& 4\text{-}7& 7\text{-}11& 11\text{-}18& 18\text{-}26\end{array}$$

5. SRTF waiting times: $W_A=26-0-10=16$, $W_B=11-2-6=3$, $W_C=7-4-3=0$, $W_D=18-6-7=5$. Total $=24$, average $=24/4=6$.

6. NP-SJF timeline: A starts at 0 and runs to 10 with no preemption. At 10, B (6), C (3) and D (7) are waiting, so the shortest, C, runs 10 to 13, then B (6) runs 13 to 19, then D runs 19 to 26.

7. NP-SJF waiting times: $W_A=0$, $W_C=10-4=6$, $W_B=13-2=11$, $W_D=19-6=13$. Total $=30$, average $=30/4=7.5$.

8. So SRTF $=6$ and NP-SJF $=7.5$, which is option (B).