GATE CS 2004 Q46 — CPU Scheduling

We can determine the execution order using the preemptive Shortest Remaining Processing Time First (SRPT) scheduling algorithm by tracing the Gantt chart step-by-step:

• At $t = 0$: Only $P_1$ is in the ready queue with a remaining burst time of $5$. $P_1$ starts executing.
• At $t = 1$: $P_2$ arrives with burst time $3$. The remaining time for $P_1$ is $4$. Since $3 < 4$, $P_2$ preempts $P_1$.
• At $t = 2$: $P_3$ arrives with burst time $3$. The remaining time for $P_2$ is $2$. Since $2 < 3$, $P_2$ continues executing.
• At $t = 4$: $P_2$ finishes execution. $P_4$ arrives with burst time $1$. The remaining times are $P_1 (4)$, $P_3 (3)$, and $P_4 (1)$. $P_4$ has the shortest remaining time and executes.
• At $t = 5$: $P_4$ finishes execution. The remaining times are $P_3 (3)$ and $P_1 (4)$. $P_3$ executes.
• At $t = 8$: $P_3$ finishes execution. $P_1$ executes for its remaining $4$ units.
• At $t = 12$: $P_1$ finishes execution.

The Gantt chart is as follows:

[P1: 0-1] [P2: 1-4] [P4: 4-5] [P3: 5-8] [P1: 8-12]

Now, we calculate the Turnaround Time ($\text{TAT} = \text{Completion Time} - \text{Arrival Time}$):

$$\text{Average Turnaround Time} = \frac{12 + 3 + 6 + 1}{4} = \frac{22}{4} = 5.50\text{ ms}$$