CPU scheduling: Round Robin, priority and multilevel queues
45 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Round Robin is the favourite follow-up after FCFS and SJF: "Draw the chart for quantum 2, then tell me what happens when the quantum is huge." The interviewer is checking your queue rule at ties and whether you know the trade-offs.
Round Robin with a time quantum: worked example
Round Robin is a preemptive algorithm that keeps ready processes in a FIFO queue and lets each one run for at most one time quantum before going to the back.
The program below runs Round Robin with q = 2 on five processes (arrivals 0 to 4, bursts 5, 3, 1, 2 and 3) and prints the Gantt chart, finish times and waiting times.
Example 1 · Round Robin simulator (q = 2)
from collections import deque
name = ["P1", "P2", "P3", "P4", "P5"]arrival = [0, 1, 2, 3, 4]burst = [5, 3, 1, 2, 3]q, n = 2, len(name)
left, finish = burst[:], [0] * nready = deque()time = nxt = 0gantt = "0"while nxt < n and arrival[nxt] <= time: ready.append(nxt) nxt += 1while ready or nxt < n: if not ready: # CPU idle until the next arrival time = arrival[nxt] while nxt < n and arrival[nxt] <= time: ready.append(nxt) nxt += 1 p = ready.popleft() run = min(q, left[p]) time += run left[p] -= run gantt += f" [{name[p]}] {time}" while nxt < n and arrival[nxt] <= time: # arrivals join first ready.append(nxt) nxt += 1 if left[p] > 0: # then the preempted one ready.append(p) else: finish[p] = timeprint("Gantt:", gantt)total = 0for i in range(n): wt = finish[i] - arrival[i] - burst[i] total += wt print(f"{name[i]}: finish {finish[i]}, WT {wt}")print(f"Average WT = {total / n:.2f}")Gantt: 0 [P1] 2 [P2] 4 [P3] 5 [P1] 7 [P4] 9 [P5] 11 [P2] 12 [P1] 13 [P5] 14 P1: finish 13, WT 8 P2: finish 12, WT 8 P3: finish 5, WT 2 P4: finish 9, WT 4 P5: finish 14, WT 7 Average WT = 5.80
What this code does
- At time 2, P2 and P3 have arrived; they join the queue before P1 goes back, so the order is P2, P3, P1. The comments mark this rule.
- P3 needs only 1 ms, so it gives up the CPU after 1 ms instead of a full quantum.
If a process is not finished when its quantum ends, it is preempted and goes to the back of the queue. When a new process arrives at the same moment a quantum ends, the usual textbook convention puts the new arrival in the queue first; state this assumption in an exam.
- A process that finishes early releases the CPU at once.
- Waiting time = completion − arrival − burst, exactly as before.
- With n ready processes, nobody waits more than (n − 1) × q for the next turn.
- Round Robin has no starvation: every process gets a turn each round.
Find the bug
Find the wrong line
Each Round Robin working has one wrong line. Click it.
q = 4. P1 needs 6 ms and P2 needs 3 ms; both arrive at 0.
Round 1 of 2Choosing the quantum: too small vs too large
Time quantum is the fixed maximum slice of CPU time a process gets in one turn under Round Robin, after which a timer interrupt hands the CPU to the next process.
The program below runs Round Robin on three jobs of 24, 3 and 3 ms, all arriving at 0, with quantum 1, 2, 4, 8 and 30, and prints the average waiting time and the context switches.
Example 2 · Effect of the quantum size
from collections import deque
def simulate(burst, q): """All jobs arrive at time 0. Returns (total waiting, context switches).""" time = switches = total_wait = 0 last = None left = burst[:] ready = deque(range(len(burst))) while ready: p = ready.popleft() if last is not None and last != p: switches += 1 last = p run = min(q, left[p]) time += run left[p] -= run if left[p] > 0: ready.append(p) else: total_wait += time - burst[p] return total_wait, switches
burst = [24, 3, 3]for q in (1, 2, 4, 8, 30): wait, switches = simulate(burst, q) print(f"q = {q:2d}: avg WT = {wait / 3:5.2f}, context switches = {switches}")q = 1: avg WT = 5.67, context switches = 9 q = 2: avg WT = 6.33, context switches = 6 q = 4: avg WT = 5.67, context switches = 3 q = 8: avg WT = 8.33, context switches = 3 q = 30: avg WT = 17.00, context switches = 2
What this code does
- With q = 30 every job finishes in one turn, so RR equals FCFS (average wait 17). Small quanta help the short jobs but add many switches.
- q = 4 is the classic textbook case: average wait 17 ÷ 3 = 5.67 with only 3 switches, a good balance for this data.
If q is very large, every process finishes within one quantum and Round Robin becomes FCFS. If q is very small, the CPU spends a large share of its time on context switches.
A common rule of thumb is to choose q so that about 80% of CPU bursts finish within one quantum, and to keep q much larger than the context-switch time. Real systems use roughly 10 to 100 ms.
Predict the output
Quantum trade-offs
Pick the output for each quantum choice.
Round 1 of 2
A 9 ms quantum and a 1 ms context switch. What percentage of time goes to switching?
Priority scheduling, starvation and aging
Priority scheduling gives the CPU to the ready process with the highest priority; many textbooks use a smaller number for a higher priority.
The program below runs non-preemptive priority scheduling on five jobs that arrive at time 0, then shows how aging improves the priority number of a process that keeps waiting.
Example 3 · Priority scheduling and aging
# Non-preemptive priority, all arrive at 0. Smaller number = higher priority.jobs = [("P1", 10, 3), ("P2", 1, 1), ("P3", 2, 4), ("P4", 1, 5), ("P5", 5, 2)] # name, burst, prioritytime = total_wait = 0gantt = "0"for name, burst, prio in sorted(jobs, key=lambda j: j[2]): total_wait += time time += burst gantt += f" [{name}] {time}"print("Gantt:", gantt)print(f"Average WT = {total_wait / len(jobs):.2f}")
# Aging: every 10 ms of waiting improves a priority number by 1.priority = 127for waited in range(0, 41, 10): print(f"Waited {waited} ms -> priority {priority - waited // 10}")Gantt: 0 [P2] 1 [P5] 6 [P1] 16 [P3] 18 [P4] 19 Average WT = 8.20 Waited 0 ms -> priority 127 Waited 10 ms -> priority 126 Waited 20 ms -> priority 125 Waited 30 ms -> priority 124 Waited 40 ms -> priority 123
What this code does
- The order follows priority numbers 1, 2, 3, 4, 5: P2, P5, P1, P3, P4. Average wait is (0 + 1 + 6 + 16 + 18) ÷ 5 = 8.2.
- The aging loop shows the idea: a process stuck at priority 127 improves steadily while it waits, so it cannot wait forever.
Always check the question: some systems treat a bigger number as higher priority. Priority scheduling can be preemptive (a higher-priority arrival takes the CPU) or non-preemptive, and SJF is the special case where priority = predicted burst.
Its danger is starvation: a low-priority process may never run if higher-priority work keeps arriving. Aging fixes this by slowly raising the priority of a process the longer it waits, so in the end it becomes the most important and runs.
Predict the output
Who runs, and how does aging help?
A smaller number means a higher priority.
Round 1 of 2
Three jobs are ready at time 0. Which one runs first?
Multilevel and multilevel feedback queues
MLFQ (multilevel feedback queue) uses several queues with different quanta and moves processes between them: CPU-heavy jobs sink to lower queues and long waiters can rise.
A multilevel queue splits the ready queue into separate queues, for example system, interactive and batch, each with its own algorithm. The design below and the program after it use three levels.
Q0: RR, q = 8 (new jobs start here)Q1: RR, q = 16 (jobs that used all of q = 8)Q2: FCFS (jobs that used all of q = 16)A lower queue runs only when all higher queues are empty.Example 4 · A three-level feedback queue
from collections import deque
name = ["A", "B", "C"] # all arrive at time 0left = [30, 6, 20]quantum = [8, 16, None] # Q2 is FCFS: no limitqueues = [deque(), deque(), deque()]queues[0].extend(range(3))
time = 0for level, queue in enumerate(queues): while queue: p = queue.popleft() run = left[p] if quantum[level] is None else min(quantum[level], left[p]) time += run left[p] -= run what = "finished" if left[p] == 0 else f"moved to Q{level + 1}" print(f"Q{level}: {name[p]} ran {run} ms, t={time}, {what}") if left[p] > 0: queues[level + 1].append(p)Q0: A ran 8 ms, t=8, moved to Q1 Q0: B ran 6 ms, t=14, finished Q0: C ran 8 ms, t=22, moved to Q1 Q1: A ran 16 ms, t=38, moved to Q2 Q1: C ran 12 ms, t=50, finished Q2: A ran 6 ms, t=56, finished
What this code does
- B (6 ms) finishes in its first quantum at the top level, at time 14. Short jobs get through fast without the OS knowing their length in advance.
- A is CPU-heavy, uses every quantum and sinks to Q2. With no new arrivals the lower queue simply runs when the upper ones are empty; a list of three
dequeobjects is the three queues.
In a plain multilevel queue a process stays in its queue for life, and higher queues usually have absolute priority over lower ones. In an MLFQ new processes start at the top with a small quantum; a process that uses its whole quantum moves down, and one that waits too long may move up (aging).
Short and interactive jobs therefore finish quickly at the top, while CPU-heavy jobs sink to lower queues with longer quanta.
Order of execution
The life of a CPU-heavy job
Job A needs 30 ms. Put its journey through the three queues in order.
Interview questions with model answers
Scheduling questions mix definitions ("What is aging?"), comparisons ("RR vs FCFS") and small numericals done aloud. A strong answer gives the definition, one number or example, and the trade-off.
- Must say: RR = FCFS + preemption by quantum; no starvation.
- Must say: q too large gives FCFS; q too small gives switching overhead.
- Must say: priority leads to starvation, and aging is the fix.
- Must say: MLFQ moves CPU-heavy jobs down and can move waiting jobs up.
Find the bug
Weak spoken answers
Each spoken answer has one wrong sentence. Click it.
Answer to "Compare Round Robin and SJF."
Round 1 of 2Next step
Check your understanding
12 quick questions