Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 66 ยท CPU Scheduling

Round Robin Scheduling

Learn Round Robin CPU scheduling: the time quantum, ready queue rotation, a worked Gantt chart, how the quantum affects response time and overhead, and a runnable simulator.

Round Robin (RR) is the scheduling algorithm designed for time-sharing systems. Every process gets a small slice of CPU time called the time quantum (or time slice), typically 10 to 100 milliseconds. When the slice ends, the process goes to the back of the ready queue and the next one runs. Everyone takes turns, like children sharing a swing with a timer.

RR is essentially FCFS plus preemption by a timer. It guarantees that every process gets the CPU regularly, so nobody starves and response time stays small, which is why it forms the basis of the scheduler in most desktop and server systems. In this lesson you will work through an example by hand and in code, and study the one tuning knob that matters: the length of the quantum.

How Round Robin works

Circular ready queue Processes line up in order.
Run one quantum Or less, if the burst ends sooner.
Back of the queue If not finished, go to the end.

A timer interrupt enforces the quantum.

1 / 2

The algorithm

  1. Keep the ready queue as a FIFO circular list.
  2. Take the first process; let it run for at most one quantum q.
  3. If it finishes within q, it leaves the system and the scheduler moves on immediately.
  4. If it does not finish, a timer interrupt preempts it and it goes to the back of the queue.
  5. Newly arrived processes join the back of the queue. (Convention: if a new arrival and a preempted process land in the queue at the same instant, the new arrival goes first. Exam questions state their convention.)

If there are n processes in the queue, a process waits at most (n - 1) ร— q before its next turn. This gives a hard bound on response time, something SJF and priority scheduling cannot do.

A worked example

Workload (quantum q = 3): A(0,6), B(1,8), C(2,2), D(3,4), E(4,3).

  • 0-3: A runs (3 left). B, C and D arrive meanwhile. Queue after the slice: B, C, D, A (D arrives at 3, the same instant A is preempted, so D goes first).
  • 3-6: B runs (5 left); E arrives at 4. Queue: C, D, A, E, B.
  • 6-8: C runs and finishes (burst 2 is shorter than the quantum, so the CPU moves on at once).
  • 8-11: D (1 left). 11-14: A finishes. 14-17: E finishes. 17-20: B (2 left). 20-21: D finishes. 21-23: B finishes.

Run the simulator to confirm the chart; it is the authority when your hand-drawn chart and the code disagree.

Python Round Robin simulator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Effect of the time quantum

Change the quantum and compare. Run this experiment with a table of quantums. The extreme cases are instructive:

  • q very large (larger than every burst): RR becomes FCFS.
  • q tiny (one unit): RR approximates processor sharing: each of n processes seems to run at 1/n speed, but the context-switch overhead explodes.
Python Quantum sweep

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the table from the top: a small quantum gives the best response time but the most switches and the longest finishing time once each switch costs something; a huge quantum gives the FCFS numbers (waiting 9.20, response 9.20, the FCFS values from the earlier lesson) with few switches. The usual rule: pick a quantum a bit larger than a typical interactive burst, so most bursts finish within one slice.

Strengths and weaknesses

Strength Weakness
Fair: every process gets regular turns Average waiting time is often higher than SJF
No starvation Many context switches if the quantum is small
Bounded response time (n-1) ร— q Performance depends heavily on the quantum
Simple, preemptive, good for interactive systems All processes are treated equally, no priorities (see multilevel queues)

A related observation: for jobs of the same length RR has worse turnaround than FCFS, because all jobs finish at about the same late time instead of one by one. RR optimizes response time, not turnaround time.

Real schedulers

Linux's default Completely Fair Scheduler (CFS, later EEVDF) is a refinement of the sharing idea: it tracks how much CPU time each task has received and always runs the one that has received the least, with the slice length depending on the number of tasks. Windows uses priority-based RR: highest-priority ready threads run in turn with a quantum of a few clock ticks.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In Round Robin, what happens to a process that does not finish within its quantum?

    A timer interrupt preempts it and it waits for its next turn at the end of the queue.
  2. 2. What does RR degenerate into if the quantum is larger than every burst?

    Every process finishes in its first turn, so the order is just arrival order.
  3. 3. With 6 processes in the ready queue and a quantum of 20 ms, what is the longest wait before a process gets its next turn?

    At most (n - 1) ร— q = 5 ร— 20 = 100 ms.
  4. 4. What is the downside of a very small quantum?

    Switching dominates the time, so useful work per unit time falls.
  5. 5. Round Robin is designed mainly for

    Its fairness and bounded response time suit interactive users.

Summary

  • RR gives each ready process a fixed time quantum in turn; preempted processes go to the back of the queue.
  • It is fair, starvation-free and has a bounded response time of (n - 1) ร— q.
  • The quantum is the key parameter: tiny gives overhead, huge gives FCFS.
  • It tends to have higher average turnaround and waiting time than SJF but far better response.

Next: Multilevel Queue and Feedback Scheduling