Imagine five friends sharing one game controller. If the first person plays until they finish the whole game, the others wait for hours. So they agree on a rule: everyone plays for 10 minutes, then passes the controller to the next person, and the line keeps going round and round. Nobody waits too long, and everyone makes progress.
That rule is Round Robin (RR) scheduling, and it is the heart of every time-sharing operating system.
Round Robin scheduling gives each ready process the CPU for at most one fixed time slice, called the time quantum. If the process has not finished when its quantum expires, it is preempted and placed at the back of the ready queue.
RR is basically FCFS plus a timer. It fixes FCFS's convoy effect without needing to know burst times (which SJF needs) and without letting anyone starve (which Priority Scheduling allows). In exchange, it pays for many more context switches, and the choice of quantum becomes the most important design decision.
How Round Robin Works
The ready queue is a circular FIFO queue. The scheduler repeats these steps:
Take the process at the head of the ready queue.
Set a timer to interrupt after one quantum
q, and dispatch the process.One of two things happens:
The burst finishes (or the process blocks for I/O) before the quantum ends. The process leaves the CPU voluntarily and the scheduler picks the next one immediately. The unused part of the quantum is not carried forward.
The timer interrupt fires. The OS saves the process's state, puts it at the tail of the ready queue, and picks the next one.
┌──────────────── preempted (quantum expired) ───────────────┐
↓ │
New → [ tail ... ready queue ... head ] → CPU (runs ≤ q) ──────────────┘
│
└→ finished / blocked for I/O
RR is preemptive, but the preemption comes from the clock, not from a "better" process arriving.
An Important Tie Rule
What if a new process arrives at exactly the same moment that the running process's quantum expires? Who goes into the queue first?
Standard convention (used in this chapter and in most exam solutions): newly arrived processes are added to the ready queue first, and then the preempted process is added behind them.
The reasoning is that the new process was "waiting at the door" before the running one was sent back. Some textbooks use the opposite order. If a question states a rule, follow it; if not, use this one and write it down in your answer.
Example 1: All Processes Arrive at Time 0
Quantum q = 3.
Process | Arrival Time | Burst Time |
|---|---|---|
P1 | 0 | 10 |
P2 | 0 | 4 |
P3 | 0 | 7 |
Step-by-step trace
Time Runs For Remaining after Ready queue after
---- ---- --- --------------- -----------------
0 P1 3 P1 = 7 P2, P3, P1
3 P2 3 P2 = 1 P3, P1, P2
6 P3 3 P3 = 4 P1, P2, P3
9 P1 3 P1 = 4 P2, P3, P1
12 P2 1 P2 = 0 (done) P3, P1
13 P3 3 P3 = 1 P1, P3
16 P1 3 P1 = 1 P3, P1
19 P3 1 P3 = 0 (done) P1
20 P1 1 P1 = 0 (done) -
| P1 | P2 | P3 | P1 | P2 | P3 | P1 | P3 | P1 |
0 3 6 9 12 13 16 19 20 21
Process | BT | CT | TAT | WT | RT |
|---|---|---|---|---|---|
P1 | 10 | 21 | 21 | 11 | 0 |
P2 | 4 | 13 | 13 | 9 | 3 |
P3 | 7 | 20 | 20 | 13 | 6 |
Average TAT = 54 / 3 = 18
Average WT = 33 / 3 = 11
Average RT = 9 / 3 = 3
Notice the pattern of response times: 0, 3, 6. With n processes, everyone gets a first turn within (n - 1) × q. That predictable, quick first response is what makes RR feel "interactive".
Also notice that P2 needed only 1 unit in its second turn at time 12, so it gave up the CPU early and P3 started at 13, not 15.
Example 2: Different Arrival Times
Quantum q = 2.
Process | Arrival Time | Burst Time |
|---|---|---|
P1 | 0 | 5 |
P2 | 1 | 3 |
P3 | 2 | 1 |
P4 | 3 | 2 |
P5 | 4 | 3 |
The secret to solving RR correctly is to write down the ready queue after every step. Most mistakes come from putting processes into the queue in the wrong order.
Step-by-step trace
t = 0 : queue = [P1]
P1 runs 0-2 (rem 3)
arrivals during/at end: P2 (1), P3 (2) → queue = [P2, P3]
then P1 goes to the tail → queue = [P2, P3, P1]
t = 2 : P2 runs 2-4 (rem 1)
arrivals: P4 (3), P5 (4) → queue = [P3, P1, P4, P5]
then P2 goes to the tail → queue = [P3, P1, P4, P5, P2]
(P5 arrived exactly at 4, so it goes BEFORE P2: our tie rule)
t = 4 : P3 runs 4-5, needs only 1 → done → queue = [P1, P4, P5, P2]
t = 5 : P1 runs 5-7 (rem 1) → queue = [P4, P5, P2, P1]
t = 7 : P4 runs 7-9 (rem 0) → done → queue = [P5, P2, P1]
t = 9 : P5 runs 9-11 (rem 1) → queue = [P2, P1, P5]
t = 11 : P2 runs 11-12 → done → queue = [P1, P5]
t = 12 : P1 runs 12-13 → done → queue = [P5]
t = 13 : P5 runs 13-14 → done → queue = []
| P1 | P2 | P3 | P1 | P4 | P5 | P2 | P1 | P5 |
0 2 4 5 7 9 11 12 13 14
Process | AT | BT | CT | TAT | WT | RT |
|---|---|---|---|---|---|---|
P1 | 0 | 5 | 13 | 13 | 8 | 0 |
P2 | 1 | 3 | 12 | 11 | 8 | 1 |
P3 | 2 | 1 | 5 | 3 | 2 | 2 |
P4 | 3 | 2 | 9 | 6 | 4 | 4 |
P5 | 4 | 3 | 14 | 10 | 7 | 5 |
Average TAT = 43 / 5 = 8.6
Average WT = 29 / 5 = 5.8
Average RT = 12 / 5 = 2.4
Context switches between processes = 8
What If We Used the Opposite Tie Rule?
If the preempted process were re-queued before processes arriving at that same instant, P1 would go ahead of P3 at time 2, and P2 ahead of P5 at time 4. The schedule becomes:
| P1 | P2 | P1 | P3 | P4 | P2 | P5 | P1 | P5 |
0 2 4 6 7 9 10 12 13 14
The individual times change (for example, P3 now finishes at 7 instead of 5, and the average response time becomes 15 / 5 = 3.0). In this particular case the average waiting time happens to stay 5.8, but in general it can change too. This is why stating your convention matters.
Round Robin in C
This program simulates RR with a circular queue, using the tie rule above (admit new arrivals first, then re-queue the preempted process). It uses the data from Example 2.
#include <stdio.h>
#define N 5
#define QUANTUM 2
/* A simple circular FIFO queue of process indexes. */
static int queue[N + 1], head = 0, tail = 0; /* holds at most N items */
static void enqueue(int x) { queue[tail] = x; tail = (tail + 1) % (N + 1); }
static int dequeue(void) { int x = queue[head]; head = (head + 1) % (N + 1); return x; }
static int empty(void) { return head == tail; }
int main(void) {
const char *name[N] = {"P1", "P2", "P3", "P4", "P5"};
int at[N] = {0, 1, 2, 3, 4}; /* must be sorted by arrival */
int bt[N] = {5, 3, 1, 2, 3};
int rem[N], ct[N], first[N];
for (int i = 0; i < N; i++) { rem[i] = bt[i]; first[i] = -1; }
int time = 0, next = 0, done = 0;
/* Admit every process that has arrived by 'time'. */
#define ADMIT() while (next < N && at[next] <= time) enqueue(next++)
ADMIT();
printf("Gantt:");
while (done < N) {
if (empty()) { /* CPU idle */
printf(" [%d]IDLE", time);
time = at[next];
ADMIT();
continue;
}
int p = dequeue();
int run = rem[p] < QUANTUM ? rem[p] : QUANTUM;
printf(" [%d]%s", time, name[p]);
if (first[p] == -1) first[p] = time;
time += run;
rem[p] -= run;
ADMIT(); /* arrivals first ... */
if (rem[p] > 0)
enqueue(p); /* ... then the preempted process */
else {
ct[p] = time;
done++;
}
}
printf(" [%d]\n\n", time);
double s_tat = 0, s_wt = 0, s_rt = 0;
printf("Proc AT BT CT TAT WT RT\n");
for (int i = 0; i < N; i++) {
int tat = ct[i] - at[i], wt = tat - bt[i], rt = first[i] - at[i];
s_tat += tat; s_wt += wt; s_rt += rt;
printf("%-4s %3d %3d %3d %4d %3d %3d\n",
name[i], at[i], bt[i], ct[i], tat, wt, rt);
}
printf("\nAverage TAT = %.2f\nAverage WT = %.2f\nAverage RT = %.2f\n",
s_tat / N, s_wt / N, s_rt / N);
return 0;
}Output:
Gantt: [0]P1 [2]P2 [4]P3 [5]P1 [7]P4 [9]P5 [11]P2 [12]P1 [13]P5 [14]
Proc AT BT CT TAT WT RT
P1 0 5 13 13 8 0
P2 1 3 12 11 8 1
P3 2 1 5 3 2 2
P4 3 2 9 6 4 4
P5 4 3 14 10 7 5
Average TAT = 8.60
Average WT = 5.80
Average RT = 2.40The two lines that implement the tie rule are ADMIT(); followed by enqueue(p);. Swap them and you get the opposite convention. The queue array has N + 1 slots because a circular queue that uses head == tail for "empty" must keep one slot unused.
Choosing the Time Quantum
The quantum controls everything about RR's behaviour. There are two extremes:
Quantum | Behaviour |
|---|---|
Very large (larger than every burst) | No process is ever preempted by the timer. RR becomes FCFS, with its convoy effect. |
Very small (close to the context-switch time) | Each of |
Same Processes, Different Quanta
Here is Example 2 solved with several quanta (switch cost ignored):
q | Avg TAT | Avg WT | Avg RT | Context switches |
|---|---|---|---|---|
1 | 8.0 | 5.2 | 1.2 | 13 |
2 | 8.6 | 5.8 | 2.4 | 8 |
3 | 7.4 | 4.6 | 3.4 | 5 |
4 | 8.4 | 5.6 | 3.8 | 5 |
5 or more | 7.4 | 4.6 | 4.6 | 4 (same as FCFS) |
Three lessons from this table:
Smaller quantum → better response time (1.2 at q = 1 vs 4.6 at q = 5).
Smaller quantum → many more context switches (13 vs 4).
Turnaround time does not improve steadily as the quantum grows. It went 8.0, 8.6, 7.4, 8.4, 7.4. It depends on how bursts happen to line up with the quantum.
The same effect appears in Example 1 (P1 = 10, P2 = 4, P3 = 7): the average TAT is 16.67 at q = 2, 18.0 at q = 3, and 16.0 at q = 4. Bigger is not always better, and smaller is not always better.
The Rule of Thumb
Choose the quantum so that most CPU bursts (a common guideline is about 80%) finish within one quantum, while the quantum stays much larger than the context-switch time.
Then short interactive bursts finish in a single turn (fast response), while only long CPU-bound bursts get cycled. Typical time slices in real systems are in the range of a few milliseconds to around 100 milliseconds, while a context switch costs on the order of microseconds.
The Cost of Context Switches
If every switch costs s time units and each quantum is q, then in the worst case (every process uses its full quantum):
CPU efficiency = q / (q + s)
q = 4 ms, s = 1 ms → 4 / 5 = 80% (20% wasted!)
q = 20 ms, s = 1 ms → 20 / 21 ≈ 95.2%
q = 100 ms, s = 1 ms → 100 / 101 ≈ 99.0%
Let's redo Example 2 (q = 2) with a context switch of 1 unit between different processes:
| P1 | CS | P2 | CS | P3 | CS | P1 | CS | P4 | CS | P5 | CS | P2 | CS | P1 | CS | P5 |
0 2 3 5 6 7 8 10 11 13 14 16 17 18 19 20 21 22
CT: P1 = 20, P2 = 18, P3 = 7, P4 = 13, P5 = 22
Average TAT = 70 / 5 = 14.0 (was 8.6 without overhead)
Average WT = 56 / 5 = 11.2 (was 5.8)
CPU utilization = 14 / 22 ≈ 63.64%
Eight switches added 8 units of pure overhead to 14 units of real work. That is why the quantum must be large compared to the switch time.
A Guaranteed Bound on Waiting
With n processes in the ready queue and quantum q, a process that has just been preempted waits at most
(n - 1) × q
before it runs again (plus switch overhead). For example, with 5 processes and q = 20 ms, no process waits more than 80 ms for its next turn. This bound is why RR has no starvation, and why users feel the system responding to them even when many programs are running.
Round Robin in Real Systems
Linux
SCHED_RR: a real-time policy that uses preemptive priority between levels and Round Robin among threads of the same priority. Its default time slice is visible in/proc/sys/kernel/sched_rr_timeslice_ms, which shows100(milliseconds) on a stock Ubuntu WSL2 kernel. A program can query it withsched_rr_get_interval().Normal Linux processes do not use a fixed quantum. The fair scheduler (EEVDF since Linux 6.6, CFS before it) divides CPU time in proportion to weights derived from nice values. You can think of it as a weighted, smarter descendant of Round Robin.
Multilevel feedback queues (next chapter) use RR inside each level, with different quanta per level.
Outside the CPU: RR is used to share network links between flows, to distribute requests across servers in load balancers ("round-robin DNS"), and in tournament scheduling.
Advantages and Disadvantages
Advantages | Disadvantages |
|---|---|
Fair: every process gets an equal share of CPU turns | Many context switches, especially with a small quantum |
No starvation; waiting bounded by | Performance depends heavily on the quantum |
Good response time, ideal for time-sharing and interactive systems | Average turnaround and waiting time often worse than SJF/SRTF |
Does not need burst-time knowledge | No notion of priority or importance in its pure form |
Simple to implement with a circular queue and a timer | If all bursts are equal and long, everyone finishes late (all processes finish near the end) |
The last point deserves a quick example: three processes of 10 units each with q = 1 finish at times 28, 29 and 30 (average TAT 29). FCFS would finish them at 10, 20 and 30 (average 20). When jobs are similar and long, RR's fairness actually hurts turnaround.
Common Mistakes
Adding the preempted process before new arrivals when the question expects the standard rule (or vice versa). Always state the rule you use.
Forgetting processes that arrived during a quantum. At t = 4 in Example 2, P4 arrived at 3 while P2 was running. It must already be in the queue.
Charging a full quantum when the burst is shorter. A process with 1 unit left uses 1 unit, and the next process starts immediately.
Putting a finished process back in the queue. Once its remaining time is 0, it leaves for good.
Using RT as WT. In RR, a process waits many times. Use
WT = TAT - BT.Thinking a smaller quantum always gives better turnaround. It improves response time, but turnaround can go up or down.
Interview Questions
What happens in Round Robin when the quantum is very large?
No process is preempted by the timer, so RR behaves exactly like FCFS.
What happens when the quantum is very small?
Response time improves, but context-switch overhead dominates and useful CPU work drops sharply.
Can Round Robin cause starvation?
No. Every process gets a turn within (n - 1) × q time units after being preempted.
How should the time quantum be chosen?
Large compared to the context-switch time, and long enough that most CPU bursts (roughly 80%) complete within one quantum.
Why is RR good for time-sharing systems?
It gives every user frequent, predictable turns on the CPU, so the system feels responsive even with many active programs.
Is RR preemptive? What triggers preemption?
Yes. Preemption is triggered by the timer interrupt when the quantum expires, not by the arrival of a higher-priority or shorter process.
With 4 processes and q = 50 ms, what is the longest a process waits between turns?
(4 - 1) × 50 = 150 ms, ignoring context-switch time.
The Main Idea
Round Robin lets every ready process run for at most one time quantum, then sends it to the back of the queue.
Take head of the ready queue
↓
Run for min(quantum, remaining time)
↓
Add new arrivals to the queue
↓
Not finished? → back to the tail
↓
Repeat
Key facts:
Type → Preemptive (timer-based)
Starvation → No, wait ≤ (n - 1) × q
q very large → becomes FCFS
q very small → processor sharing, heavy switch overhead
Efficiency → q / (q + s)
Good for → Time-sharing, interactive systems
Round Robin trades a little efficiency for a lot of fairness and responsiveness, and the quantum decides how good that trade is.
RR treats every process the same, and Priority Scheduling treats them very differently. In the next chapter, Multilevel Queue & Feedback Queue Scheduling, we combine the two: several queues with different priorities, Round Robin inside each, and processes that move between queues based on how they behave.