CSE Roadmap

Core tier · about 4 hours · 6 parts

Part 5 of 6 · 3 min read

Measured slices

Round robin on a real machine

In plain words: A program can see its own turns. It pins itself to one processor, then reads the clock in a tight loop. Each time two readings are far apart (more than 100 microseconds), the process was off the processor, and the gap is the wait. The stretches between gaps are its turns. Competing spinners are started on the same processor.

competitors 0: ... on-CPU run 30.25 ms on average, off-CPU gap 0.34 ms
competitors 1: ... on-CPU run  3.52 ms on average, off-CPU gap 3.63 ms
competitors 3: ... on-CPU run  3.39 ms on average, off-CPU gap 10.43 ms

Reading the output:

  • With no competitor, the process keeps the processor. The few small gaps are interrupts, and the long average run (30 ms) is only the stretch between them.
  • With one competitor, turns of about 3.5 ms alternate with waits of about 3.6 ms. This is round robin with two processes: each waits one turn of the other.
  • With three competitors, the turns stay near 3.4 ms, and the wait grows to about 10.4 ms, close to 3 × 3.4. This matches the rule of section 1: the wait is (n − 1) turns.

Linux does not use plain round robin (page 5 explains the policy it uses), but with equal processes it behaves like it, and the measured turn is a few milliseconds.

The effect on a person is simple. A program that waits for a key should respond in well under 100 milliseconds, so with ten ready processes of 3.5 ms turns, the program waits about 31 ms for its turn, and nobody notices. With a thousand, the wait is several seconds, and the machine feels frozen.

Common mistake

Believing that a smaller quantum is always better because response is faster. Switching costs time, caches go cold (Level 1, page 5), and turnaround time can get worse.

Interview angle

Answer in your head first, then open it.

How does round robin work?

A FIFO queue and a fixed quantum: run the front process for at most one quantum, then move it to the back.

What happens if the quantum is very large? Very small?

Large: it becomes FCFS. Small: most time is lost in switching.

Is round robin optimal for turnaround time?

No. It improves response time and fairness but not the average turnaround.

How long does a process wait between turns?

At most (n − 1) × q when n processes are ready.

Does round robin starve anyone?

No, each process gets a turn within a bounded time.

Check yourself: 1. What did the measured wait become with three competitors, and what does the rule predict? 2. Which part of the output shows that Linux gave each equal process a turn? 3. Why would a thousand ready processes feel frozen?

Words you will meet

Word Meaning
Round robin Turns in a circle, one quantum each
Time quantum The longest uninterrupted run
Time slice Another name for the quantum
Context-switch overhead Time spent switching, as a share of all time

Quick notes

  • Round robin is a preemptive scheduling policy that keeps the ready processes in a first-in, first-out queue and runs the process at the front for at most one time quantum.
  • The time quantum (or time slice) is the longest period for which a process may run before the timer interrupt returns control to the scheduler, and it is the main tuning parameter of round robin.
  • Context-switch overhead is the share of processor time spent switching between processes instead of running them, equal to s ÷ (q + s) for a switch cost s and a quantum q.