GATE CS 2015 Set 3 Q34 — CPU Scheduling

Theoretically, Shortest Remaining Time First (SRTF) (preemptive SJF) is optimal and always yields the minimum average turnaround time (and average waiting time) for any given set of processes. Let us verify this by calculating the Turnaround Time ($\text{TAT} = \text{Completion Time} - \text{Arrival Time}$) for each scheduling scheme.

1. Shortest Remaining Time First (SRTF):

• At $t = 0$: Process $A$ runs.
• At $t = 1$: $B$ arrives. Remaining time of $A$ is $2$, which is less than $B$'s burst $6$. $A$ continues.
• At $t = 3$: $A$ completes. $\text{CT}(A) = 3$. $B$ starts running.
• At $t = 4$: $C$ arrives (burst $4$). Remaining time of $B$ is $5$. Since $4 < 5$, $C$ preempts $B$.
• At $t = 6$: $D$ arrives (burst $2$). Remaining time of $C$ is $2$. Since $D$ and $C$ both have remaining time $2$, we can run $D$ (or continue $C$). Let's run $D$.
• At $t = 8$: $D$ completes. $\text{CT}(D) = 8$. $C$ resumes.
• At $t = 10$: $C$ completes. $\text{CT}(C) = 10$. $B$ resumes.
• At $t = 15$: $B$ completes. $\text{CT}(B) = 15$.

Calculating TAT for SRTF:

• $\text{TAT}(A) = 3 - 0 = 3$
• $\text{TAT}(B) = 15 - 1 = 14$
• $\text{TAT}(C) = 10 - 4 = 6$
• $\text{TAT}(D) = 8 - 6 = 2$
• Average TAT = $\frac{3 + 14 + 6 + 2}{4} = 6.25$

2. Non-preemptive SJF:

• $A$ runs from $0$ to $3$ ($\text{CT} = 3, \text{TAT} = 3$).
• $B$ runs from $3$ to $9$ ($\text{CT} = 9, \text{TAT} = 8$).
• $D$ runs from $9$ to $11$ ($\text{CT} = 11, \text{TAT} = 5$).
• $C$ runs from $11$ to $15$ ($\text{CT} = 15, \text{TAT} = 11$).
• Average TAT = $\frac{3 + 8 + 11 + 5}{4} = 6.75$

3. First Come First Serve (FCFS):

• $A$ runs $0$ to $3$ ($\text{TAT} = 3$), $B$ runs $3$ to $9$ ($\text{TAT} = 8$), $C$ runs $9$ to $13$ ($\text{TAT} = 9$), $D$ runs $13$ to $15$ ($\text{TAT} = 9$).
• Average TAT = $\frac{3 + 8 + 9 + 9}{4} = 7.25$

Thus, Shortest Remaining Time First (SRTF) gives the lowest average turnaround time.