Question

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 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?

• 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

Hint:

In round-robin scheduling, each process gets a fixed time slice. The number of context switches depends on the burst times and the quantum.

Answer 1

The Correct Option is D

In a round-robin scheduling algorithm with a time quantum of 4 units, all ready processes are scheduled cyclically. A context switch occurs whenever the CPU moves from one process to another, either because a process exhausts its time quantum or completes execution. To check the feasibility of each option, we simulate the execution order and observe whether the implied number and pattern of context switches can occur.

Option (A): P = 4, Q = 10, R = 6, S = 2
- Process P completes exactly in one time quantum, causing a context switch to Q.
- Q and R require multiple time quanta, while S completes in one slice.
- The sequence of execution and completion naturally leads to the required context switches in a valid round-robin order.
Hence, this option is feasible.

Option (B): P = 2, Q = 9, R = 5, S = 1
- P and S complete before consuming a full time quantum.
- Q and R require multiple time slices, resulting in context switches between them.
- All switches follow the cyclic order without violating round-robin rules.
Hence, this option is feasible.

Option (C): P = 4, Q = 12, R = 5, S = 4
- P and S complete in exactly one time quantum each.
- Q requires three time slices and R requires two, leading to several context switches.
- The switching pattern remains consistent with round-robin scheduling.
Hence, this option is feasible.

Option (D): P = 3, Q = 7, R = 7, S = 3
- P and S complete before using a full time quantum.
- Q and R both require multiple time quanta.
- The implied execution order leads to a situation where a required cyclic context switch (from S back to P) cannot occur because P has already terminated.
- This breaks the expected round-robin switching pattern.
Hence, this option is not feasible.

Final Answer:
The configuration that is not possible under round-robin scheduling is (D).