Round Robin and Multilevel Queue Scheduling

Interactive systems care about response time: a user who presses a key wants a reaction now, not after a long batch job finishes. Round robin (RR) achieves this by time slicing. Every ready process gets the CPU for at most one time quantum $q$, then goes to the back of the queue. Among $n$ ready processes, no process waits more than $(n - 1)$ quanta for its next turn.

Real systems mix interactive and batch work, so they use several ready queues with different policies. A multilevel queue assigns each process permanently to one queue; a multilevel feedback queue (MLFQ) moves processes between queues according to how they behave, so that short and interactive jobs float to the top without the scheduler knowing burst lengths in advance.

The same four-process workload as CPU Scheduling: Criteria, FCFS, SJF, SRTF and Priority is used, so the results can be compared directly.

Queue-order convention used in the traces. When a process arrives at the same instant that the running process's quantum expires, the new arrival joins the queue first and the preempted process goes behind it. A stated problem may use the opposite order; follow the problem.

Quantum size.

Waiting bound. With $n$ processes in the ready queue and switch time $s$, the gap between the end of one quantum of a process and the start of its next is at most $(n - 1)q + ns$: the other $n - 1$ processes run once each, and there are $n$ switches (one before each of their runs and one back). With free switching this is the familiar $(n - 1)q$.

The ready queue is split into separate queues, for example system, interactive and batch processes. Each process is placed in one queue for life, and each queue has its own algorithm (RR for interactive, FCFS for batch). Scheduling between queues is either:

Processes move between queues. A typical configuration:

An MLFQ is defined by: the number of queues, the algorithm and quantum of each, the demotion rule, the promotion (aging) rule, and the entry queue for new processes. A problem must give these explicitly; the traces use the rules just stated.

Response time bound. In RR with $n$ ready processes, between two consecutive quanta of one process every other process runs at most once, for at most $q$, with one switch $s$ before each run and one more switch back to the process. So the gap is at most $(n - 1)q + ns$. Example: $n = 3$, $q = 4$, $s = 1$ gives $8 + 3 = 11$ units.

Overhead. If every quantum is used in full, the useful fraction of CPU time is $q/(q + s)$. With $q = 4$ and $s = 1$, that is 80%, matching the example.

Number of quanta. A burst of length $B$ needs $\lceil B/q \rceil$ quanta in RR, so it is preempted $\lceil B/q \rceil - 1$ times (assuming other processes are always ready).

The workload (from the previous note, priorities not used):

Trace of the ready queue (head on the left):

Gantt: P1 0 to 2, P2 2 to 4, P1 4 to 6, P3 6 to 7, P2 7 to 9, P4 9 to 11, P1 11 to 13, P4 13 to 15, P1 15 to 16.

Average WT $= 5$, average TAT $= 9$, average RT $= 1.5$. Compare FCFS: average RT 4.75. Round robin gives up some waiting time to gain response time.

Average waiting time is not monotonic in $q$. It rose from $q = 2$ to $q = 3$ and fell again at $q = 4$. Smaller quanta generally tend to increase switching overhead, but the switch count is not a monotonic law for every workload. Exact counts require the arrivals, bursts, tie rules and switch-counting convention; for the displayed workload and model, use the counts in the table.

If each of the 8 switches at $q = 2$ costs 1 unit, the last process finishes at $16 + 8 = 24$ and CPU utilization falls to $16/24 = 2/3$. With $q = 4$ the same cost gives $16 + 4 = 20$ and utilization $16/20 = 80\%$.

Arrival at the instant a quantum expires. P1 (arrival 0, burst 4), P2 (1, 3), P3 (2, 2), $q = 2$. At time 2, P1's quantum expires and P3 arrives.

Both give an average WT of $11/3$, but individual completion times differ, so a question that asks about one process depends on the rule. P2 arrived at 1, before the quantum expired, so it is ahead of both under either rule.

A burst that ends exactly at the quantum. In the chart above, P1's second run uses its remaining 2 units, exactly one quantum. The process terminates; it is not put back in the queue, and no extra switch is counted for it.

A lone process. If only one process is ready when its quantum expires, it continues; whether that counts as a context switch is a convention. Only switches between different processes are counted, so a lone process that continues is not a switch, since no other process's state is loaded; read the question's rule.

Largest quantum for a response limit. Five processes are always ready, $s = 1$, and each process must wait at most 30 units between the end of one of its quanta and the start of its next. The bound $(n - 1)q + ns$ gives $4q + 5 \le 30$, so $q \le 6.25$ and the largest integer quantum is 6, with a gap of exactly 29. A simulation with $q = 6$ and $q = 7$ measures gaps of 29 and 33.

Q0 (RR, $q = 2$), Q1 (RR, $q = 4$), Q2 (FCFS), with the rules above. Jobs: A (arrival 0, burst 9), B (1, 3), C (2, 1).

Completion: A 13, B 10, C 5. Waiting: A 4, B 6, C 2. The short job C finishes first even though it arrived last, without the scheduler knowing any burst length.

Preemption across levels. Change C to arrive at 6 with burst 2. Then A runs 0 to 2 (to Q1), B 2 to 4 (to Q1), and A starts its Q1 quantum at 4. At 6, C arrives in Q0 and preempts A, which goes back to the tail of Q1 with 5 units left. C runs 6 to 8, B finishes 8 to 9, and A runs 9 to 13 in a fresh Q1 quantum. It uses all 4 units with 1 still left, so it is demoted to Q2 and finishes there, 13 to 14.

Common misconceptions.