Round robin and the time quantum

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. HRRN ratio? from Lesson 2.1.3
2. SRTF average WT on the running example? from Lesson 2.1.2
3. Which state does a pre-empted process go to? from Lesson 1.1.1

1 · The Hook

In a game of carrom with four players, each takes one turn, then the next player goes; nobody waits more than three turns. Round robin (RR) gives every ready process a small time quantum in turn. It is how time-sharing systems feel responsive, and GATE asks you to trace it: who runs when, how many context switches, which completion time.

3 · Core Concept

Predict First — the answer

P1 0–2, P2 2–4, P3 4–5 (done), P1 5–7, P2 7–8 (done), P1 8–9 (done). Finish order: P3, P2, P1.

In plain words

Keep a queue of ready processes. Give the front process the CPU for at most q milliseconds. If it finishes, good; if not, it goes to the back of the queue. New arrivals also join the back. Repeat.

1. The rules (these notes' conventions)

1. The ready queue is FIFO.
2. The front process runs for min(q, remaining time).
3. Processes that arrive during that slice join the back of the queue as they arrive.
4. If the running process is not finished, it joins the back after any process that arrived at the same instant.

2. Running example with q = 4

• 0–4 P1 (P2, P3, P4, P5 arrive at 1, 2, 3, 4; P1 rejoins after P5).
• Queue: P2, P3, P4, P5, P1 → P2 4–8 (done), P3 8–12, P4 12–16, P5 16–18 (done), P1 18–22 (done), P3 22–26, P4 26–27 (done), P3 27–28 (done).

Average WT = 65/5 = 13; average response time = (0 + 3 + 6 + 9 + 12)/5 = 6. RR usually has a worse average waiting time than SJF but a much better response time: everyone starts soon.

3. Choosing the quantum

• q very large → RR becomes FCFS.
• q very small → many context switches: overhead dominates.
• With context-switch time s, the fraction of time doing useful work is about q/(q + s) (q = 4, s = 1 → 80%).
• With n processes in the queue, each waits at most (n − 1)·q before its next turn.
• Rule of thumb: about 80% of CPU bursts should be shorter than q.

4. Counting context switches

Count changes from one process to a different one in the Gantt chart (the very first dispatch is not usually counted; a process continuing after its own slice because nobody else is waiting is not a switch). Running example, q = 4: P1→P2→P3→P4→P5→P1→P3→P4→P3: 8 switches.

4 · Visual

Round robin, q = 4, running example

| P1  | P2  | P3  | P4  | P5 | P1  | P3  | P4 | P3 |
0     4     8     12    16   18    22    26   27   28
      ^ P5 arrived at 4, so it queues before the pre-empted P1

5 · Worked Examples

Example 1 Easy

All at 0, bursts 24, 3, 3, RR with q = 4. Average waiting time?

Solution

P1 0–4, P2 4–7, P3 7–10, P1 10–30: waits 6, 4, 7 → 17/3 ≈ 5.67.

Example 2 Medium

Running example with q = 2: completion time of P5?

Solution

Trace: P1 0–2, P2 2–4, P3 4–6, P1 6–8, P4 8–10, P5 10–12 → 12.

Example 3 GATE

A system uses RR with q = 10 ms and a context switch costs 2 ms. What fraction of CPU time is useful (all bursts long)?

Solution

10/(10 + 2) ≈ 0.833.

6 · GATE Traps

• A newly arrived process and a just-pre-empted one at the same instant: the arrival goes first (state the rule you use).
• When a process finishes before its quantum ends, the next process starts immediately.
• q → ∞ makes RR into FCFS, not SJF.
• Count context switches between different processes only.

7 · Memory Hook

"Run q, back of the line; new arrivals queue first."

8 · Connect the Dots

Real systems mix many kinds of processes (interactive, batch, system) and processes alternate CPU work with I/O waits. The last scheduling lesson covers multilevel queues and how to handle CPU and I/O bursts together.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 2 mark(s) — RR

Running example, RR with q = 4: average waiting time?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — RR

Running example, RR with q = 2: completion time of P1?

Numerical answer: ________

Q3 · NAT · 1 mark(s) — RR

All at 0 with bursts 5, 3, 1, RR with q = 2. Completion time of P2?

Numerical answer: ________

Q4 · NAT · 2 mark(s) — Context switches

Running example, RR with q = 3: number of context switches (changes between different processes; the first dispatch not counted)?

Numerical answer: ________

Q5 · MCQ · 1 mark(s) — Large quantum

If the time quantum is larger than every burst, round robin behaves like:

1. (A) SRTF
2. (B) SJF
3. (C) FCFS
4. (D) Priority

10 · Rule Card

• RR: FIFO ready queue; run min(q, remaining); unfinished → back; arrivals at the same instant queue before the pre-empted process.
• Large q → FCFS; small q → overhead; useful fraction q/(q + s); max wait between turns (n − 1)q.
• RR: worse average WT than SJF, better response time.
• Context switches: count changes between different processes.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

round robintime quantumready-queue order rulestime-sharingresponse time vs waiting timequantum size trade-offcontext-switch overhead q/(q + s)counting context switches