GATE CSE 2022 | Question: 32

Question

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

• A. $\text{P = 4, Q = 10, R = 6, S = 2}$
• B. $\text{P = 2, Q = 9, R = 5, S = 1}$
• C. $\text{P = 4, Q = 12, R = 5, S = 4}$
• D. $\text{P = 3, Q = 7, R = 7, S = 3}$

Comments

Just try to implement round robin algo for given options in option D there is no context switch from $R$ to $Q $ So that option D is false 

Answer 1

Answer : option D

---

Round Robin QUEUE :--  P,Q,R,S,P,Q,R,S,P,Q,R,S…..

Given that processes arrived in the order P,Q,R and S.

1. Switching to ready processes after termination of currently executing process also a context switch.
2. There is no context switch from S to P. ( Therefore P should be complete with in 1 TQ )
3. There are exactly two context switches from Q to R ( Therefore Q and R both should requires more than 1 TQ )
4. There is exactly one context switch from R to Q ( Therefore Q require more time than R )
5. Exactly one context swich from R to S. ( Therefore S should be complete with in 1 TQ otherwise another CS from R to S required.)
6. Exactly one conext switch from S to Q

Accumulating all the above points

QUEUE :---  P,Q,R,S,Q,R,Q

 

Given that time quantum = 4.

$0<P_{BT}\leq4$

$0<S_{BT}\leq4$

$8<Q_{BT}$

$4<R_{BT}\leq8$

 

in Option D, Q’s BT=7. Hence it is not possible.

Comments

Queue will be P->S->Q->R->Q->R 

then option D will work correctly 

as P<=4 , 4<Q<=8 , R > 4 and S <= 4

---

@abhi7251, processes arrived in P,Q,R and S order. Hence, S can’t be before Q in the first round.