2.3Round robin
The idea
Round robin gives each process a fixed time quantum in turn, then moves it to the back of the queue.
Think of it like this: Children sharing one swing: each gets a minute, then goes to the back of the line.
Why it exists
It is fair and gives quick first responses, which is why interactive systems use it. The quantum is the dial that trades response for overhead.
How it works
- Keep a FIFO ready queue.
- Run the head for min(q, remaining).
- Add anything that arrived meanwhile before putting the preempted process at the tail.
- Repeat. Waiting time = completion − arrival − burst.
Worked example: q = 3, bursts 8, 4, 9, 5, all arrive at 0
Order of slices: P1 3, P2 3, P3 3, P4 3, P1 3, P2 1, P3 3, P4 2, P1 2, P3 3. Everything finishes at 26 (the sum of the bursts, since nobody ever idles).
Now play with it
- →Change the quantum from 3 to 100 and watch the chart become FCFS.
- →Set q = 1 and count the context switches.
| Process | Arrival | Burst | Completion | Turnaround | Waiting | Response |
|---|---|---|---|---|---|---|
| P1 | 0 | 8 | 23 | 23 | 15 | 0 |
| P2 | 1 | 4 | 16 | 15 | 11 | 2 |
| P3 | 2 | 9 | 26 | 24 | 15 | 4 |
| P4 | 3 | 5 | 21 | 18 | 13 | 6 |
Turnaround = completion − arrival. Waiting = turnaround − burst. Response = first run − arrival. Ties go to the earlier arrival, then the earlier row. In round robin, a process that arrives while another runs joins the queue before the preempted one.
Make q huge and the efficiency tends to 1 but RR becomes FCFS; make q tiny and the overhead swallows the CPU.
Check yourself
With a very small time quantum, round robin
Exam notes (the dense version)
Each process gets a time quantum q, then goes to the back of the ready queue. Preemptive, fair, good response time. A very large q behaves like FCFS; a very small q wastes time on context switches. With n processes the longest a process waits for its first turn is (n − 1)q. When a process arrives at the same instant a quantum ends, the usual convention is: the new arrival enters the queue before the preempted process.
Previous year questions: CPU Scheduling (13)
PYQs are grouped by topic, so this is the full set for CPU Scheduling; try the ones that match this subtopic. Open all 13 on the topic page.