GATE 2022 CS – Question 42
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?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (D) P = 3, Q = 7, R = 7, S = 3
Explanation
Round robin with quantum 4: simulate each option and count the context switches (we need exactly one S→Q, one R→Q, two Q→R and no S→P). Option (D) fails because **R→Q never occurs**.
Option (D): $P=3,Q=7,R=7,S=3$. Run order: P (finishes at 3), Q (4 units), R (4 units), S (finishes), then Q (3 units, finishes), then R (3 units, finishes). Context switches: P→Q, Q→R, R→S, S→Q, Q→R. So S→Q appears once and Q→R twice, but there is **no R→Q** switch.
Option (A) $P=4,Q=10,R=6,S=2$: P finishes, Q4, R4, S finishes, Q4 (S→Q), R2 (Q→R) finishes, Q2 (R→Q) finishes. Switches S→Q once, Q→R twice, R→Q once. Valid.
Options (B) and (C) similarly satisfy all four counts. So (D) is not possible.