GATE CS 2019 Q41 — CPU Scheduling

We schedule the processes using preemptive Shortest Remaining Time First (SRTF) scheduling. Let us trace the execution from $t = 0$:

• At $t = 0$: Only $P_1$ is available. It starts executing.
• At $t = 1$: $P_2$ arrives with a burst time of $1$ ms. The remaining burst time of $P_1$ is $2$ ms. Since $1 < 2$, $P_2$ preempts $P_1$ and runs till completion at $t = 2$.
• At $t = 2$: $P_1$ resumes execution.
• At $t = 3$: $P_3$ arrives with a burst time of $3$ ms. The remaining burst time of $P_1$ is $1$ ms. Since $1 < 3$, $P_1$ continues execution till completion at $t = 4$.

At $t = 4$, $P_1$ and $P_2$ are completed. Let us calculate their waiting times (WT):

• $\text{WT}(P_1) = \text{Completion Time} - \text{Arrival Time} - \text{Burst Time} = 4 - 0 - 3 = 1\text{ ms}$
• $\text{WT}(P_2) = 2 - 1 - 1 = 0\text{ ms}$

We are given that the average waiting time of all four processes is $1$ ms. Therefore, the total waiting time is:

At $t = 4$, the remaining processes are $P_3$ (burst time = $3$) and $P_4$ (burst time = $Z$).

• If $Z \ge 3$, $P_3$ executes first from $t = 4$ to $t = 7$, and then $P_4$ executes. This gives $\text{WT}(P_3) = 7 - 3 - 3 = 1\text{ ms}$ and $\text{WT}(P_4) = (7+Z) - 4 - Z = 3\text{ ms}$. The sum of their waiting times would be $1 + 3 = 4\text{ ms}$, which is incorrect.
• If $Z < 3$, $P_4$ executes first from $t = 4$ to $t = 4+Z$, and then $P_3$ executes from $t = 4+Z$ to $t = 7+Z$. This gives:
  • $\text{WT}(P_4) = (4+Z) - 4 - Z = 0\text{ ms}$
  • $\text{WT}(P_3) = (7+Z) - 3 - 3 = Z + 1\text{ ms}$
  Setting the sum of waiting times to $3$: $$0 + (Z + 1) = 3 \implies Z = 2$$

Since $Z = 2$ satisfies the condition $Z < 3$, the value of $Z$ is $2$.