Round-robin scheduling and the time quantum
Share the CPU fairly by running each job for at most one quantum, then rotating the queue.
from collections import deque
def round_robin(bursts, quantum):
queue = deque(bursts.items())
time = 0
finish = {}
while queue:
name, remaining = queue.popleft()
run = min(quantum, remaining)
time += run
if remaining > run:
queue.append((name, remaining - run))
else:
finish[name] = time
return finish
bursts = {"A": 5, "B": 3, "C": 8}
finish = round_robin(bursts, 3)
print(finish)
waits = {name: finish[name] - bursts[name] for name in bursts}
print(waits)
assert sum(finish.values()) > 0{'B': 6, 'A': 11, 'C': 16}
{'A': 6, 'B': 3, 'C': 8}Explanation
Round robin is a preemptive policy designed for time-sharing. Ready processes wait in a FIFO queue. The scheduler runs the first one for at most a fixed time quantum. If the process has not finished, a timer interrupt preempts it and it goes to the back of the queue.
The quantum is the main tuning knob. If it is very large, round robin behaves like FCFS. If it is very small, the system spends a growing share of its time on context switches, which save one process's registers and restore another's, instead of doing useful work. A quantum somewhat larger than a typical interactive burst balances responsiveness against overhead.
The program simulates three jobs that all arrive at time 0 with bursts of 5, 3, and 8 and a quantum of 3. Job B finishes first even though it did not arrive first, because it needs only one quantum. For jobs that all arrive at time 0, waiting time is the finish time minus the burst time. Linux and other modern kernels use fair-share schedulers with priorities rather than plain round robin, but the idea of time slices is the same.
Explore the dry run
from collections import deque def round_robin(bursts, quantum): queue = deque(bursts.items()) time = 0 finish = {} while queue: name, remaining = queue.popleft() run = min(quantum, remaining) time += run if remaining > run: queue.append((name, remaining - run)) else: finish[name] = time return finish bursts = {"A": 5, "B": 3, "C": 8}finish = round_robin(bursts, 3)print(finish)waits = {name: finish[name] - bursts[name] for name in bursts}print(waits)assert sum(finish.values()) > 0Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| A job runs for a full quantum or until it finishes, whichever is shorter. | A runs 3 of 5 | — | |
| An unfinished job goes to the back of the queue with its remaining time. | queue: B, C, A(2) | — | |
| B needs only 3, so it completes at time 6, before A. | finish B = 6 | — | |
| Completion times: B at 6, A at 11, C at 16. | finish B = 6 | {'B': 6, 'A': 11, 'C': 16} | |
| With every arrival at 0, waiting time is finish minus burst: A waits 6, B waits 3, C waits 8. | finish B = 6 | {'B': 6, 'A': 11, 'C': 16}
{'A': 6, 'B': 3, 'C': 8} |
Cost and common mistakes
Each loop iteration is O(1) with a deque. The simulation runs about total_burst / quantum + n iterations.
- The wait formula finish − burst only holds when every job arrives at time 0. With later arrivals, subtract arrival time too.
- A quantum that is too small makes context-switch overhead dominate. One that is too large loses the responsiveness round robin is for.
- Round robin usually gives a higher average turnaround time than SJF. Its benefit is bounded response time, not minimum waiting.
Try it yourself
What are the finish times with a quantum of 8?
Reveal answer and reasoning
With a quantum at least as large as every burst, each job runs once to completion in queue order: A finishes at 5, B at 8, and C at 16. That is the same order FCFS would produce.