Consider four processes P, Q, R, and S scheduled on a CPU as per round robin algorithm with a time quantum of 4 units. The processes arrive in the order P, Q, R, S, all at time t = 0. There is exactly one context switch from S to Q, exactly one context switch from R to Q, and exactly two context switches from Q to R. There is no context switch from S to P. Switching to a ready process after the termination of another process is also considered a context switch. Which one of the following is NOT possible as CPU burst time (in time units) of these processes?

Let us trace the Round Robin scheduling execution order with time quantum $TQ = 4$ for each option:

Initial ready queue at $t = 0$: $[\text{P}, \text{Q}, \text{R}, \text{S}]$

Testing Option (A): $\text{P}=4, \text{Q}=10, \text{R}=6, \text{S}=2$

1. P runs for 4 units ($0$ to $4$), terminates. Ready queue: $[\text{Q}, \text{R}, \text{S}]$. Switch: $\text{P} \to \text{Q}$.

2. Q runs for 4 units ($4$ to $8$), rem $\text{Q}=6$. Ready queue: $[\text{R}, \text{S}, \text{Q}]$. Switch: $\text{Q} \to \text{R}$ (1st $\text{Q} \to \text{R}$).

3. R runs for 4 units ($8$ to $12$), rem $\text{R}=2$. Ready queue: $[\text{S}, \text{Q}, \text{R}]$. Switch: $\text{R} \to \text{S}$.

4. S runs for 2 units ($12$ to $14$), terminates. Ready queue: $[\text{Q}, \text{R}]$. Switch: $\text{S} \to \text{Q}$ (1st $\text{S} \to \text{Q}$).

5. Q runs for 4 units ($14$ to $18$), rem $\text{Q}=2$. Ready queue: $[\text{R}, \text{Q}]$. Switch: $\text{Q} \to \text{R}$ (2nd $\text{Q} \to \text{R}$).

6. R runs for 2 units ($18$ to $20$), terminates. Ready queue: $[\text{Q}]$. Switch: $\text{R} \to \text{Q}$ (1st $\text{R} \to \text{Q}$).

7. Q runs for 2 units ($20$ to $22$), terminates.

• Sequence of context switches: $\text{P}\to\text{Q}\to\text{R}\to\text{S}\to\text{Q}\to\text{R}\to\text{Q}$.

• Exactly one $\text{S} \to \text{Q}$, exactly one $\text{R} \to \text{Q}$, exactly two $\text{Q} \to \text{R}$, zero $\text{S} \to \text{P}$. This is possible.

Testing Option (B): $\text{P}=2, \text{Q}=9, \text{R}=5, \text{S}=1$

• Execution order: $\text{P}(2) \to \text{Q}(4) \to \text{R}(4) \to \text{S}(1) \to \text{Q}(4) \to \text{R}(1) \to \text{Q}(1)$.

• Switches: $\text{P}\to\text{Q}\to\text{R}\to\text{S}\to\text{Q}\to\text{R}\to\text{Q}$. Conditions satisfied.

Testing Option (C): $\text{P}=4, \text{Q}=12, \text{R}=5, \text{S}=4$

• Execution order: $\text{P}(4) \to \text{Q}(4) \to \text{R}(4) \to \text{S}(4) \to \text{Q}(4) \to \text{R}(1) \to \text{Q}(4)$.

• Switches: $\text{P}\to\text{Q}\to\text{R}\to\text{S}\to\text{Q}\to\text{R}\to\text{Q}$. Conditions satisfied.

Testing Option (D): $\text{P}=3, \text{Q}=7, \text{R}=7, \text{S}=3$

1. P runs for 3 units ($0$ to $3$), terminates. Ready queue: $[\text{Q}, \text{R}, \text{S}]$. Switch: $\text{P} \to \text{Q}$.

2. Q runs for 4 units ($3$ to $7$), rem $\text{Q}=3$. Ready queue: $[\text{R}, \text{S}, \text{Q}]$. Switch: $\text{Q} \to \text{R}$ (1st $\text{Q} \to \text{R}$).

3. R runs for 4 units ($7$ to $11$), rem $\text{R}=3$. Ready queue: $[\text{S}, \text{Q}, \text{R}]$. Switch: $\text{R} \to \text{S}$.

4. S runs for 3 units ($11$ to $14$), terminates. Ready queue: $[\text{Q}, \text{R}]$. Switch: $\text{S} \to \text{Q}$ (1st $\text{S} \to \text{Q}$).

5. Q runs for 3 units ($14$ to $17$), terminates. Ready queue: $[\text{R}]$. Switch: $\text{Q} \to \text{R}$ (2nd $\text{Q} \to \text{R}$).

6. R runs for 3 units ($17$ to $20$), terminates.

• Sequence of context switches: $\text{P}\to\text{Q}\to\text{R}\to\text{S}\to\text{Q}\to\text{R}$.

• Here, the context switch from R to Q is 0 (after R finishes at the end, CPU goes idle, no switch to Q). Thus, condition "exactly one context switch from R to Q" is violated.

Therefore, option D is NOT possible.