Free lesson · Operating Systems

Round Robin simulation

Easy10 min readoperating-systemsosconcurrency

Giving Everyone a Turn

Round Robin (RR) is the scheduling algorithm that makes time-sharing possible. The idea is simple and elegant: give each process a fixed amount of CPU time - called a time quantum or time slice - and when that time is up, move to the next process. No process gets to monopolize the CPU. Everyone gets a turn. If a process does not finish within its quantum, it goes to the back of the ready queue and waits for its next turn.

Think of it like a group of friends passing around a microphone at a party. Each person gets 30 seconds to talk. When your 30 seconds are up, you pass the microphone to the next person, whether or not you finished your story. When your turn comes around again, you pick up where you left off.

Round Robin is the foundation of interactive computing. It is what allows you to type in a text editor while music plays in the background and a file downloads simultaneously. Each of those processes gets a small slice of CPU time in rapid succession, creating the illusion of simultaneous execution. Without Round Robin (or a descendant of it), your computer would feel like a batch processing system - one program runs to completion, then the next.

Round Robin is also the scheduling algorithm you are most likely to be asked to trace through in an interview. Interviewers love it because the quantum-size tradeoff reveals whether you understand the mechanics or are just reciting definitions.

How Round Robin Works

The algorithm maintains a circular FIFO queue of ready processes. The scheduler takes the process at the front of the queue and gives it the CPU for at most one time quantum. Two things can happen during that quantum:

The process finishes before the quantum expires. The process releases the CPU voluntarily, and the scheduler immediately picks the next process from the front of the queue. The unused portion of the quantum is not saved or given to the next process - it is simply not needed.

The quantum expires before the process finishes. A timer interrupt fires, the OS preempts the process, saves its state into its PCB, moves it to the back of the ready queue, and gives the CPU to the next process at the front of the queue. The preempted process will get another turn when it reaches the front again.

graph TD
    subgraph RR["Round Robin Scheduling"]
        FRONT["Front of Queue"] --> P1["P1"]
        P1 --> P2["P2"]
        P2 --> P3["P3"]
        P3 --> P4["P4"]
        P4 --> BACK["Back of Queue"]
    end
    
    CPU["CPU<br/>────<br/>Runs front process<br/>for one quantum"]
    
    FRONT -->|"dispatch"| CPU
    CPU -->|"quantum expires,<br/>process not done"| BACK
    CPU -->|"process finishes<br/>within quantum"| DONE["Process Complete"]

This diagram shows Round Robin scheduling. A circular queue holds processes P1 through P4. The scheduler dispatches the process at the front of the queue to the CPU, which runs it for one time quantum. If the quantum expires before the process finishes, the process moves to the back of the queue and waits for another turn. If the process finishes within the quantum, it exits the system.

A Worked Example

Let us trace through Round Robin with a time quantum of 4 ms. Four processes all arrive at time 0:

Time 0-4: P1 runs for 4 ms (its quantum). P1 has 6 ms remaining. P1 goes to the back of the queue. Time 4-8: P2 runs for 4 ms. P2 finishes (burst was exactly 4 ms). P2 exits. Time 8-12: P3 runs for 4 ms. P3 has 3 ms remaining. P3 goes to the back. Time 12-15: P4 runs for 3 ms. P4 finishes (burst was 3 ms, less than quantum). P4 exits. Time 15-19: P1 runs for 4 ms. P1 has 2 ms remaining. P1 goes to the back. Time 19-22: P3 runs for 3 ms. P3 finishes. P3 exits. Time 22-24: P1 runs for 2 ms. P1 finishes. P1 exits.

Compare this to FCFS (running P1→P2→P3→P4):

Round Robin's average waiting time (11.25) is better than FCFS (12.5) but worse than SJF (7.0). This is the expected relationship: SJF is optimal for average waiting time, Round Robin is in the middle, and FCFS is worst. But Round Robin has something the other two lack: bounded waiting time. No process waits more than (n-1) × quantum before getting its next turn, where n is the number of processes. This predictability is Round Robin's key advantage.

gantt
    title Round Robin (quantum = 4ms)
    dateFormat X
    axisFormat %s

    section Schedule
    P1 (4ms of 10)  :p1a, 0, 4
    P2 (4ms - done) :p2, 4, 8
    P3 (4ms of 7)   :p3a, 8, 12
    P4 (3ms - done) :p4, 12, 15
    P1 (4ms of 6)   :p1b, 15, 19
    P3 (3ms - done) :p3b, 19, 22
    P1 (2ms - done) :p1c, 22, 24

This Gantt chart shows Round Robin scheduling with a 4ms quantum. P1 runs for 4ms, then P2 runs for 4ms and finishes, then P3 runs for 4ms, then P4 runs for 3ms and finishes, then P1 gets another 4ms, then P3 gets its remaining 3ms and finishes, and finally P1 gets its last 2ms and finishes. The total schedule spans 24ms.

The Quantum Size Tradeoff

The time quantum is the single most important parameter in Round Robin, and choosing the right size is a tradeoff between response time and throughput. This tradeoff is what interviewers test when they ask about Round Robin.

Very Small Quantum (e.g., 1 ms)

Response time: excellent. Every process gets a turn every few milliseconds. The system feels very responsive - each process makes a little progress frequently.

Throughput: terrible. Every 1 ms, the OS performs a context switch. If each context switch takes 10 microseconds, the overhead is 10 / 1000 = 1% of CPU time spent switching. That sounds acceptable, but with 100 processes in the queue, a process gets 1 ms of CPU time every 100 ms - and 1% of each of those milliseconds is wasted on switching. As the quantum approaches the context switch time, a larger and larger fraction of CPU time is wasted on overhead instead of useful work. At the extreme, if the quantum equals the context switch time, the CPU spends 50% of its time switching and only 50% doing useful work.

Very Large Quantum (e.g., 100 seconds)

Throughput: excellent. Context switches are rare, so almost all CPU time goes to useful work. Each process runs for a long time before being preempted.

Response time: terrible. If a process just missed its turn and there are 10 processes in the queue, it waits 10 × 100 = 1,000 seconds for its next turn. The system feels completely unresponsive. In fact, with a large enough quantum, Round Robin degenerates into FCFS - each process runs to completion (or for a very long time) before the next one starts.

The Sweet Spot

The optimal quantum balances response time and throughput. The rule of thumb is: the quantum should be large enough that most CPU bursts complete within a single quantum (so processes finish without being preempted, avoiding unnecessary context switches) but small enough that interactive processes get frequent turns (so the system feels responsive).

In practice, typical quantum sizes are 10-100 milliseconds. Linux's default time slice for normal-priority processes is about 4-6 ms (though CFS uses a different mechanism than fixed quanta, which we will cover in Topic 07). Windows uses quanta of 20-60 ms depending on whether the process is in the foreground or background.

A useful guideline: about 80% of CPU bursts should complete within a single quantum. If most processes are I/O-bound (they use the CPU for a few milliseconds then block on I/O), a quantum of 10-20 ms lets them finish without preemption. The remaining 20% of processes (CPU-bound) will be preempted at the quantum boundary, which is acceptable.

The Math Behind the Tradeoff

Let us make the tradeoff concrete with numbers. Suppose the context switch overhead is 0.1 ms (100 microseconds - realistic on modern hardware).

With a quantum of 1 ms: context switch overhead is 0.1 / (1.0 + 0.1) = 9.1% of CPU time wasted on switching. For 100 processes, each process gets a turn every 110 ms (100 × 1.1 ms). Response time is good at 110 ms, but nearly 10% of CPU time is overhead.

With a quantum of 10 ms: context switch overhead is 0.1 / (10.0 + 0.1) = 0.99% - nearly negligible. For 100 processes, each gets a turn every 1,010 ms (about 1 second). Response time is worse, but CPU utilization is excellent.

With a quantum of 100 ms: context switch overhead is 0.1 / (100.0 + 0.1) = 0.1% - essentially zero. But each process waits up to 10 seconds between turns with 100 processes. The system feels frozen for interactive use.

These numbers show why the sweet spot is typically 10-100 ms. Below 10 ms, context switch overhead starts to become noticeable. Above 100 ms, response time becomes unacceptable for interactive use. Within this range, the exact choice depends on the workload - more interactive workloads favor smaller quanta, while batch-oriented workloads favor larger quanta.

Interview: "Explain Round Robin scheduling. How does the quantum size affect performance?"

"Round Robin gives each process a fixed time slice called a quantum. Processes run in a circular queue - each gets one quantum, then goes to the back of the queue. It is preemptive: the timer interrupt forces a context switch when the quantum expires.

The quantum size is the key tradeoff. A small quantum gives excellent response time - every process gets frequent turns - but increases context switch overhead, reducing throughput. A large quantum reduces switching overhead but increases response time and eventually degenerates into FCFS if the quantum is larger than most burst times.

The sweet spot is a quantum large enough that most CPU bursts complete within it (avoiding unnecessary preemption) but small enough for responsive interactivity. Typical values are 10-100 ms. The rule of thumb is that about 80% of CPU bursts should finish within a single quantum."

Round Robin vs FCFS and SJF

Understanding where Round Robin sits relative to the other algorithms helps you make informed comparisons in interviews.

Versus FCFS: Round Robin eliminates the convoy effect. A long CPU-bound process cannot block short processes because it is preempted after one quantum. The short processes get their turn between the long process's quanta. Round Robin trades slightly higher overhead (context switches at each quantum boundary) for dramatically better response time and fairness.

Versus SJF: Round Robin does not optimize for average waiting time - it does not consider burst length at all. SJF achieves lower average waiting time by prioritizing short jobs. But SJF can starve long jobs, while Round Robin guarantees that every process gets a turn within a bounded time. Round Robin also does not require knowing burst times in advance, which is a significant practical advantage.

The key insight: Round Robin optimizes for fairness and response time, not for average waiting time. It ensures that no process waits too long between turns, even if that means the total time to complete all processes is suboptimal. This makes it ideal for interactive systems where responsiveness matters more than throughput.

Round Robin with I/O

In real systems, processes do not just use the CPU - they also do I/O. When a process blocks on I/O during its quantum, it leaves the CPU immediately (it does not waste the rest of its quantum waiting). The scheduler picks the next process from the ready queue.

When the I/O completes, the process returns to the ready queue and waits for its next turn. This interaction between CPU scheduling and I/O is important because it means I/O-bound processes naturally use less than their full quantum. They run for a few milliseconds, issue an I/O request, and block. When they return to the ready queue, they are placed at the back and must wait for their turn again.

This creates an unfairness: I/O-bound processes effectively get penalized for being well-behaved. They use only a fraction of their quantum, but they wait the same amount of time (one full rotation of the queue) as CPU-bound processes that use their entire quantum. Some Round Robin variants address this by giving I/O-bound processes a credit - placing them at the front of the queue (or in a higher-priority queue) when they return from I/O. The Multi-Level Feedback Queue (Topic 07) handles this naturally by promoting I/O-bound processes to higher-priority queues.

from collections import deque

# Round Robin simulation
processes = [
    {"name": "P1", "burst": 10, "remaining": 10},
    {"name": "P2", "burst": 4,  "remaining": 4},
    {"name": "P3", "burst": 7,  "remaining": 7},
    {"name": "P4", "burst": 3,  "remaining": 3},
]

quantum = 4
time = 0
queue = deque(processes)
completion = {}
timeline = []

while queue:
    proc = queue.popleft()
    run_time = min(quantum, proc["remaining"])
    
    timeline.append(f"Time {time}-{time+run_time}: {proc['name']} runs ({run_time}ms)")
    
    time += run_time
    proc["remaining"] -= run_time
    
    if proc["remaining"] == 0:
        completion[proc["name"]] = time
        timeline.append(f"  → {proc['name']} DONE at time {time}")
    else:
        queue.append(proc)
        timeline.append(f"  → {proc['name']} preempted, {proc['remaining']}ms remaining")

for line in timeline:
    print(line)

print(f"\nCompletion times: {completion}")
total_burst = sum(p["burst"] for p in processes)
print(f"Total CPU time: {total_burst}ms, Total elapsed: {time}ms")

Tip: For interviews: Being able to trace through a Round Robin schedule by hand - writing out the queue state at each step, noting when processes are preempted versus when they finish, and calculating the final metrics - is a skill that interviewers directly test. Practice until you can do it without hesitation for 4-5 processes with different burst times.

Exercise: Starter: Given processes P1 (burst=5), P2 (burst=3), P3 (burst=1), P4 (burst=7), all arriving at time 0, trace through Round Robin with quantum=2. Draw the Gantt chart and calculate average waiting time.

Intermediate: Using the same processes, calculate the average waiting time for quantum=1, quantum=2, quantum=4, and quantum=100 (effectively FCFS). Plot or tabulate how average waiting time changes with quantum size. At what quantum size does Round Robin degenerate into FCFS for this workload?

Advanced: Consider a system with 100 processes, 90 of which are I/O-bound (average CPU burst = 2 ms) and 10 of which are CPU-bound (average CPU burst = 200 ms). The quantum is 10 ms. How often does each I/O-bound process get a turn? How often does each CPU-bound process get a turn? What is the approximate response time for an I/O-bound process? What would you change about the scheduler to improve the I/O-bound processes' experience?

Back to Operating Systems