GATE CS 2022 Q.42: CPU Scheduling

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?

P = 4, Q = 10, R = 6, S = 2

P = 2, Q = 9, R = 5, S = 1

P = 4, Q = 12, R = 5, S = 4

P = 3, Q = 7, R = 7, S = 3

Official answer and solution

Official answer: D
From: Official GATE 2022 answer key

Solution

Simulate round robin execution for each candidate set of burst times and count context switches between processes.

Round Robin scheduling with quantum $q = 4$ . Initial queue at $t=0$ : $P, Q, R, S$ .

Evaluating Option (D) where $P=3, Q=7, R=7, S=3$ :

$t = 0$ : $P$ executes for 3 units, terminates at $t=3$ . Ready queue: $Q, R, S$ . Context switch to $Q$ .
$t = 3$ : $Q$ runs for 4 units (quantum expires, remaining = 3). Ready queue: $R, S, Q$ . Context switch from $Q$ to $R$ (1st switch $Q \to R$ ).
$t = 7$ : $R$ runs for 4 units (quantum expires, remaining = 3). Ready queue: $S, Q, R$ . Context switch from $R$ to $S$ .
$t = 11$ : $S$ runs for 3 units, terminates at $t=14$ . Ready queue: $Q, R$ . Context switch from $S$ to $Q$ (1st switch $S \to Q$ ).
$t = 14$ : $Q$ runs for 3 units, terminates at $t=17$ . Ready queue: $R$ . Context switch from $Q$ to $R$ (2nd switch $Q \to R$ ).
$t = 17$ : $R$ runs for 3 units, terminates at $t=20$ .

In this execution, there is NO context switch from $R$ to $Q$ (after $R$ runs, control passes to $S$ in round 1, and in round 2 $R$ is the last process to run). However, the problem statement requires exactly one context switch from $R$ to $Q$ . Therefore, the burst times in Option (D) cannot produce the specified context switches.

Final answer

Option (D)

Common trap

Overlooking the requirement for a context switch from R to Q.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2022 Computer Science and Information Technology (CS)
Question: 42 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source