GATE CS 2014 Set 3 Q32 — CPU Scheduling

To find the average waiting time using the Shortest Remaining Time First (SRTF) scheduling algorithm, we track the execution of processes step-by-step:

• At $t = 0$: Only $\text{P1}$ is in the ready queue. It starts execution.
• At $t = 2$: $\text{P2}$ arrives with a burst time of $4$ ms. The remaining burst time of $\text{P1}$ is $10$ ms. Since $\text{P2}$ has a shorter remaining time ($4 < 10$), $\text{P2}$ preempts $\text{P1}$.
• At $t = 3$: $\text{P3}$ arrives with a burst time of $6$ ms. The remaining burst time of $\text{P2}$ is $3$ ms. Since $\text{P2}$ still has the shortest remaining time ($3 < 6$), $\text{P2}$ continues.
• At $t = 6$: $\text{P2}$ finishes execution. The ready queue contains $\text{P1}$ (remaining $10$ ms) and $\text{P3}$ (remaining $6$ ms). $\text{P3}$ starts execution.
• At $t = 8$: $\text{P4}$ arrives with a burst time of $5$ ms. The remaining burst time of $\text{P3}$ is $4$ ms. Since $\text{P3}$ has a shorter remaining time ($4 < 5$), $\text{P3}$ continues.
• At $t = 12$: $\text{P3}$ finishes execution. The ready queue contains $\text{P4}$ (remaining $5$ ms) and $\text{P1}$ (remaining $10$ ms). $\text{P4}$ starts execution.
• At $t = 17$: $\text{P4}$ finishes execution. $\text{P1}$ resumes and runs to completion.
• At $t = 27$: $\text{P1}$ finishes execution.

Gantt Chart:

$$\begin{array}{|c|c|c|c|c|} \hline \text{P1} & \text{P2} & \text{P3} & \text{P4} & \text{P1} \\ \hline 0 \quad\quad 2 & 2 \quad\quad 6 & 6 \quad\quad 12 & 12 \quad\quad 17 & 17 \quad\quad 27 \\ \hline \end{array}$$

Now, we calculate the Completion Time (CT), Turnaround Time (TAT = CT - AT), and Waiting Time (WT = TAT - BT) for each process:

$$\text{Average Waiting Time} = \frac{15 + 0 + 3 + 4}{4} = \frac{22}{4} = 5.5 \text{ ms}$$