Round Robin CPU Scheduling

1. 1The ready queue is FIFO. Dispatch the process at the front and start a timer set to one quantum.
2. 2If the process finishes or blocks before the timer fires, it leaves and the next process is dispatched immediately.
3. 3If the timer fires first, the interrupt preempts the process, its context is saved, and it goes to the back of the queue.
4. 4Repeat. Every process gets the CPU at regular intervals, forever, until it is done.

With n processes and quantum q, nobody waits more than (n − 1) × q before their next turn. That bounded response time is the guarantee Round Robin exists to give — and no other algorithm here provides it.

The quantum is the only tuning knob, and both extremes fail:

• Too large and every process finishes inside its slice — the timer never fires and Round Robin degenerates into plain FCFS, convoy effect and all.
• Too small and the CPU spends its life context switching. If a switch costs 10 µs and the quantum is 100 µs, you are burning 10% of the machine on overhead alone.

The rule of thumb is that the quantum should be large compared to a context switch, and long enough that roughly 80% of CPU bursts finish within it. Real systems land at 10–100 ms against context switches measured in microseconds.

Turnaround time is not monotonic in the quantum — increasing it does not steadily improve average turnaround. The best value has to be found for the workload, not derived.

Arrival time

When the process shows up in the ready queue. The scheduler cannot pick something that has not arrived yet — that single rule decides most exam answers.

Burst time

How long this process needs the CPU for, uninterrupted, before it would block or finish. Also called CPU burst.

Ready queue

Every process that could run right now but does not have the CPU. Scheduling is entirely the question of who gets pulled out of here next.

Preemptive vs non-preemptive

A non-preemptive scheduler cannot take the CPU back — once dispatched, a process runs until it blocks or finishes. A preemptive one can interrupt it mid-burst.

Context switch

Saving one process's registers and loading another's. Pure overhead: real work stops while it happens, typically a few microseconds.

Starvation

A process that stays runnable but never gets picked, because something more attractive keeps arriving. The classic fix is ageing — slowly raising the priority of anything that has waited a long time.

On the same three processes that made FCFS look terrible (bursts 24, 3, 3, all arriving at t = 0), with a quantum of 4:

Round Robin is nowhere near SJF's average — and it never will be, because it deliberately ignores burst length. What it buys instead is that P2 and P3 start running at t = 4 and t = 7 rather than t = 24, and that no process can ever starve. In an interactive system that trade is not close.