GATE CS 2016 Set 2 Q47 — CPU Scheduling

To find the average turnaround time, we trace the execution of the processes using the Preemptive Shortest Remaining Time First (SRTF) scheduling algorithm.

Gantt Chart Execution:

• At $t = 0$: Only $P_1$ is available. It runs for $3$ ms.
• At $t = 3$: $P_2$ arrives. Remaining time of $P_1 = 7$ ms, and burst time of $P_2 = 6$ ms. Since $6 < 7$, $P_2$ preempts $P_1$ and runs.
• At $t = 7$: $P_3$ arrives. Remaining time of $P_2 = 2$ ms, and burst time of $P_3 = 1$ ms. Since $1 < 2$, $P_3$ preempts $P_2$ and runs.
• At $t = 8$: $P_3$ completes. $P_4$ arrives with burst time $3$ ms. The remaining times are: $P_1 (7)$, $P_2 (2)$, and $P_4 (3)$. $P_2$ has the shortest remaining time, so it runs and completes at $t = 10$.
• At $t = 10$: Remaining processes are $P_1 (7)$ and $P_4 (3)$. $P_4$ runs and completes at $t = 13$.
• At $t = 13$: Finally, $P_1$ runs and completes at $t = 20$.

The Gantt chart is represented as:

$$\begin{array}{|c|c|c|c|c|c|} \hline \text{ } P_1 \text{ } & \text{ } P_2 \text{ } & \text{ } P_3 \text{ } & \text{ } P_2 \text{ } & \text{ } P_4 \text{ } & \text{ } P_1 \text{ } \\ \hline 0 \quad\quad 3 & 3 \quad\quad 7 & 7 \quad\quad 8 & 8 \quad\quad 10 & 10 \quad\quad 13 & 13 \quad\quad 20 \\ \hline \end{array}$$

Turnaround Time (TAT) Calculation:
$\text{Turnaround Time (TAT)} = \text{Completion Time (CT)} - \text{Arrival Time (AT)}$

$$\text{Average Turnaround Time} = \frac{20 + 7 + 1 + 5}{4} = \frac{33}{4} = 8.25 \text{ ms}$$