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.

Answer 2

P   AT

P

Q

R

S

 

By looking at options and 4th statement we can say that P,S will be finished in 1 time slice.

 

Time = 0 Ready Queue = S,R,Q

P

 

Time = 4 Ready Queue = S,R Context Switch: Q to R

Q

 

Time = 8 Ready Queue = Q,S

R

 

Time = 12 Ready Queue = R,Q

S

 

Time = 16 Ready Queue = R Context Switch: S to Q

Q

 

Time = 20 Ready Queue = Q Context Switch: Q to R

R

 

Time = 24 Ready Queue = null Context Switch: R to Q

Q

 

Q will have 3 TQ hence burst time of: 7<BT(Q)<13