GATE 2022 CS Q.42: solution and answer

GATE 2022 · CSQ.42 · 2 marks · MCQ

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 NOT possible as CPU burst time (in time units) of these processes?

(A)
P = 4, Q = 10, R = 6, S = 2
(B)
P = 2, Q = 9, R = 5, S = 1
(C)
P = 4, Q = 12, R = 5, S = 4
(D)
P = 3, Q = 7, R = 7, S = 3

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Option (D) $P = 3, Q = 7, R = 7, S = 3$ is the one that is NOT possible.

Official answer: DSource: Official answer key, GATE 2022 CS (IIT Kharagpur)

All four processes arrive at $t = 0$ in the order $P, Q, R, S$ . In each round every unfinished process runs for $min (4, remaining)$ units. A switch is counted between consecutive CPU slices, including the switch to the next ready process after a process terminates.
The required switch counts are: $S \to Q$ exactly once, $R \to Q$ exactly once, $Q \to R$ exactly twice, and no $S \to P$ .
Option A ( $P = 4, Q = 10, R = 6, S = 2$ ): P finishes in round 1. Q runs 4 (6 left), R runs 4 (2 left), S runs 2 and finishes. Round 2: Q runs 4 (2 left), R runs 2 and finishes, Q runs 2 and finishes. Order: $P, Q, R, S, Q, R, Q$ . Counts: $S \to Q$ once, $Q \to R$ twice, $R \to Q$ once, no $S \to P$ . Possible.
Option B ( $P = 2, Q = 9, R = 5, S = 1$ ): P finishes. Q runs 4 (5 left), R runs 4 (1 left), S runs 1 and finishes. Then Q runs 4 (1 left), R runs 1 and finishes, Q runs 1 and finishes. Order: $P, Q, R, S, Q, R, Q$ , with the same counts as A. Possible.
Option C ( $P = 4, Q = 12, R = 5, S = 4$ ): P finishes. Q runs 4 (8 left), R runs 4 (1 left), S runs 4 and finishes. Then Q runs 4 (4 left), R runs 1 and finishes, Q runs 4 and finishes. Order: $P, Q, R, S, Q, R, Q$ , with the same counts as A. Possible.
Option D ( $P = 3, Q = 7, R = 7, S = 3$ ): P finishes in round 1. Q runs 4 (3 left), R runs 4 (3 left), S runs 3 and finishes. Round 2: Q runs 3 and finishes, then R runs 3 and finishes. Order: $P, Q, R, S, Q, R$ .
In D, $S \to Q$ occurs once and $Q \to R$ occurs twice, but Q finishes before R in round 2, so no $R \to Q$ switch ever occurs. The condition of exactly one $R \to Q$ switch fails, so D is not possible. The answer is D.

KEY IDEA

Simulate round robin with quantum 4, write the order of CPU slices, and count the adjacent pairs. The required switches ( $S \to Q$ once, $R \to Q$ once, $Q \to R$ twice) need the order $P, Q, R, S, Q, R, Q$ . That means P and S end in round 1, Q needs three slices and R needs two slices, and R finishes before Q.

WATCH OUT FOR

Forgetting that the move to the next ready process after a termination counts as a context switch. Another slip is checking only $S \to Q$ and $Q \to R$ in option D and missing that $R \to Q$ never occurs, because Q finishes in round 2 before R gets its second slice.

From the GATE 2022 CS paper. Every question of this paper · Download the full paper · All 8 CPU scheduling questions, with notes

GATE 2022 CS Q.42: solution and answer

Answer and solution

More CPU scheduling questions