GATE CS 2017 Set 1 Q24 — CPU Scheduling

We use the preemptive Shortest Remaining Time First (SRTF) scheduling algorithm. Let us trace the execution step-by-step using a Gantt chart:

Gantt Chart:

Step-by-step Execution:

• At $t = 0$: Only $P_1$ is available. It runs for $3\text{ ms}$ (remaining burst time of $P_1 = 4$).
• At $t = 3$: $P_2$ arrives with burst time $3$. Since $3 < 4$, $P_2$ preempts $P_1$.
• At $t = 5$: $P_3$ arrives with burst time $5$. The remaining burst time of $P_2$ is $1$. Since $1 < 5$, $P_2$ continues and finishes at $t = 6$.
• At $t = 6$: $P_4$ arrives with burst time $2$. The available processes are $P_1$ (remaining $4$), $P_3$ (remaining $5$), and $P_4$ (remaining $2$). $P_4$ is scheduled and finishes at $t = 8$.
• At $t = 8$: Between $P_1$ (remaining $4$) and $P_3$ (remaining $5$), $P_1$ is scheduled and finishes at $t = 12$.
• At $t = 12$: $P_3$ is scheduled and finishes at $t = 17$.

Metrics Calculation:

$$\begin{array}{|c|c|c|c|c|c|} \hline \textbf{Process} & \textbf{Arrival Time (AT)} & \textbf{Burst Time (BT)} & \textbf{Completion Time (CT)} & \textbf{Turnaround Time (TAT)} & \textbf{Waiting Time (WT)} \\ \hline P_1 & 0 & 7 & 12 & 12 & 5 \\ \hline P_2 & 3 & 3 & 6 & 3 & 0 \\ \hline P_3 & 5 & 5 & 17 & 12 & 7 \\ \hline P_4 & 6 & 2 & 8 & 2 & 0 \\ \hline \end{array}$$

$$\text{Average Waiting Time} = \frac{5 + 0 + 7 + 0}{4} = \frac{12}{4} = 3\text{ ms}$$