The GATE Grind

GATE 2024 CS (CS2) – Question 37

Operating System · CPU and I/O Scheduling · 2 marks · Multiple choice

Consider a single processor system with four processes A, B, C, and D, where for each process the first value is its arrival time, and the second value is its CPU burst time: A (0, 10), B (2, 6), C (4, 3), and D (6, 7). Which one of the following options gives the average waiting times when preemptive Shortest Remaining Time First (SRTF) and Non-Preemptive Shortest Job First (NP-SJF) CPU scheduling algorithms are applied to the processes?

  1. SRTF = 6, NP-SJF = 7
  2. SRTF = 6, NP-SJF = 7.5
  3. SRTF = 7, NP-SJF = 7.5
  4. SRTF = 7, NP-SJF = 8.5

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) SRTF = 6, NP-SJF = 7.5

Explanation

Processes (arrival, burst): A(0,10), B(2,6), C(4,3), D(6,7).

**SRTF (preemptive):**
- $t=0$–$2$: A runs (remaining 8 at $t=2$).
- $t=2$: B arrives (6 < 8), so B runs. At $t=4$ B has 4 left.
- $t=4$: C arrives (3 < 4), so C runs, and finishes at $t=7$ (D arriving at 6 has 7 > 1, no preemption).
- $t=7$: remaining A 8, B 4, D 7: B runs $7$–$11$.
- $t=11$: D (7) < A (8): D runs $11$–$18$. Then A runs $18$–$26$.

Completion: C 7, B 11, D 18, A 26. Waiting time $=$ completion $-$ arrival $-$ burst:
A $=26-0-10=16$, B $=11-2-6=3$, C $=7-4-3=0$, D $=18-6-7=5$. Sum $=24$, average $=\mathbf{6}$.

**NP-SJF:** A runs $0$–$10$ (alone at $t=0$). At $t=10$ the ready jobs are B(6), C(3), D(7): C $10$–$13$, B $13$–$19$, D $19$–$26$.
Waiting: A $0$, C $10-4=6$, B $13-2=11$, D $19-6=13$. Sum $=30$, average $=\mathbf{7.5}$.

SRTF $=6$, NP-SJF $=7.5$: option (B).

More CPU and I/O Scheduling questions

All CPU and I/O Scheduling questions →