Round-Robin and the Time-Quantum Tradeoff

What This Concept Is

Round-Robin (RR) gives each ready process a fixed time quantum (also called a time slice). When the quantum expires, the scheduler preempts the current process, puts it at the back of the ready queue, and picks the next one.

If there are N processes and quantum q, each process waits at most (N - 1) * q between its turns.

RR is preemptive and fair in access, but it is not optimal for average turnaround. Its job is to keep response time small so the system feels interactive.

Why It Matters Here

RR is the bridge from "I have a policy" to "my OS feels responsive." Every time-sharing OS is, at heart, round-robin plus refinements. MLFQ, CFS, and Windows' scheduler all inherit its core trick: preempt on a timer so no job can monopolize the CPU.

The time-quantum choice is also the prototype "tune a parameter" problem in systems:

Quantum too large -> RR degrades toward FCFS; response time suffers.
Quantum too small -> overhead of context switching dominates actual work.

Concrete Example

Three jobs arriving at t=0:

Job	Burst
A	5
B	3
C	8

RR with q = 2:

  0 2 4 6 8 10 12 14 15 16
  │A│B│C│A│B│ C│ A│ C│ │ │

Gantt steps:

t=0-2 A runs, then A preempted (remaining 3), queue: B, C, A
t=2-4 B runs, remaining 1, queue: C, A, B
t=4-6 C runs, remaining 6, queue: A, B, C
t=6-8 A runs, remaining 1, queue: B, C, A
t=8-9 B finishes (only 1 left), queue: C, A
t=9-11 C runs, remaining 4, queue: A, C
t=11-12 A finishes (only 1 left), queue: C
t=12-16 C runs to completion

Turnaround: A=12, B=9, C=16. Average = 12.33. SJF on the same set would give (3+8+16)/3 ≈ 9.

RR is worse on average turnaround but better on first response: every job starts executing by t=2, versus t=0, 3, 11 under SJF.

Common Confusion / Misconception

"Smaller quantum = more fair = better." Only up to a point. If a context switch costs, say, 10 µs and your quantum is 1 ms, you are paying 1% overhead -- fine. Shrink the quantum to 50 µs and overhead becomes 20%. The tradeoff curve has a sweet spot, typically a few milliseconds on general-purpose Linux.

"RR is fair." It is fair in time-slice count, not in any deeper sense. If one process sleeps on I/O for most of its quantum and another runs flat out, RR still counts them equally -- so CFS eventually replaces fixed quanta with virtual runtime (Concept 14).

How To Use It

Pick q using this triage:

What is the context-switch cost on this system (measure it with lmbench or perf sched)?
What is the target overhead ceiling? (A common rule of thumb: overhead <= 1% -> q >= 100 * switch_cost.)
What is the target response time? (Interactive users tolerate <= 100 ms.)

Then: switch_cost * 100 <= q <= target_response_time / N_typical_runnable_procs.

If these bounds cross, the workload is too heavy for the CPU; scaling up or capping N is the right fix, not a smaller q.

Check Yourself

Why is RR's average turnaround usually worse than SJF's?
Name two costs that grow as the quantum shrinks.
Under RR, what is the worst-case time between two consecutive slices of the same process, as a function of N and q?

Mini Drill or Application

Workload:

Job	Arrival	Burst
P1	0	4
P2	0	5
P3	0	2
P4	0	1

Draw the Gantt chart for q = 1 and q = 2.
Compute average turnaround and response time for both.
Write one sentence explaining which q you would pick if switch cost were 0.5 units per switch.

What This Concept Is​

Why It Matters Here​

Concrete Example​

Common Confusion / Misconception​

How To Use It​

Check Yourself​

Mini Drill or Application​

Read This Only If Stuck​