GATE CS 2022 Q32 — CPU Scheduling

To determine which option is not possible, let us trace the Round Robin scheduling with a time quantum of $q = 4$ and the initial ready queue order $[P, Q, R, S]$ at $t = 0$.

Let us test Option D with burst times $P = 3, Q = 7, R = 7, S = 3$:

1. $P$ runs for $3$ units and terminates. Ready queue: $[Q, R, S]$.
2. $Q$ runs for $4$ units (remaining: $3$) and is preempted. Ready queue: $[R, S, Q]$.
3. $R$ runs for $4$ units (remaining: $3$) and is preempted. Ready queue: $[S, Q, R]$.
4. $S$ runs for $3$ units and terminates. Ready queue: $[Q, R]$.
5. $Q$ runs for $3$ units and terminates. Ready queue: $[R]$.
6. $R$ runs for $3$ units and terminates.

The execution sequence of processes is: $$\text{P} \to \text{Q} \to \text{R} \to \text{S} \to \text{Q} \to \text{R}$$ Let us verify the constraints for this sequence:

• Context switch from $S$ to $Q$: Exactly $1$ (from $S \to Q$).
• Context switch from $Q$ to $R$: Exactly $2$ (first $Q \to R$, second $Q \to R$).
• Context switch from $R$ to $Q$: $0$ (there is no transition from $R$ to $Q$).