COMP 3150Operating Systems

Module 2 · Unit 5 · Lesson 5 of 6

Round Robin Scheduling

The scheduling algorithm designed for time-sharing. Each process receives a fixed time slice — a quantum — and then returns to the tail of the ready queue. Round robin guarantees that every process receives the CPU regularly, which makes it the natural choice for interactive systems. The price is more context switches and a higher average waiting time than SJF.

01 Introduction

The algorithms in the previous three lessons all share a common assumption: that a process, once selected, should run until it blocks or terminates, or until a higher-priority process preempts it. FCFS runs to completion. SJF runs to completion (non-preemptive) or until a shorter job arrives (SRTF). Priority scheduling runs to completion (non-preemptive) or until a higher-priority job arrives (preemptive). In each case, a process can run for an arbitrarily long time if no other process qualifies for preemption.

Round robin scheduling takes a different approach. It is designed for time-sharing: the deliberate division of the CPU among several users or tasks. Instead of letting a process run until it blocks, round robin gives each process a fixed time quantum and, when the quantum expires, preempts the process and moves it to the tail of the ready queue. Every process receives the CPU on a regular schedule, and no process can monopolize the processor.

The algorithm is simple — a circular queue and a timer — but its behaviour depends critically on the size of the quantum. A quantum that is too long makes round robin degenerate into FCFS; a quantum that is too short maximizes responsiveness at the cost of context-switch overhead. The choice of quantum is the central design decision of round robin, and it is the main subject of this lesson.

Round robin is the default policy in many general-purpose systems, either directly or as a component of a hybrid scheduler. Linux's SCHED_RR policy is a round-robin variant, and the multilevel-feedback queues examined in Lesson 5.6 use round robin within each queue level. Understanding round robin is therefore essential for understanding how interactive systems actually schedule work.

Prerequisites

This lesson builds on Lessons 5.1–5.4. In particular, the distinction between preemptive and non-preemptive scheduling (Lesson 5.1), the metrics and criteria (Lesson 5.1), the analysis of FCFS (Lesson 5.2), and the priority machinery (Lesson 5.4) are all used here. The discussion of context-switch overhead in section 4.7 of Lesson 5.1 is especially relevant.

02 Learning objectives

By the end of this lesson you will be able to

  • Describe the round robin algorithm and trace a workload through a round-robin schedule.
  • Compute turnaround, waiting, and response times for a round-robin schedule.
  • Explain how the choice of time quantum affects response time, throughput, and overhead.
  • Analyse round robin against the standard scheduling criteria and compare it with FCFS and SJF.
  • Describe weighted and priority round robin and their real-world applications.

This lesson contributes to U5.2, U5.3, and U5.4, and to course learning outcomes CLO1, CLO3, and CLO6.

03 Required reading

  • Operating System Concepts — Chapter 5, Section 5.3.3, Round-Robin Scheduling. The standard treatment, including the discussion of quantum size and the worked example with four processes.
  • OSTEP — Chapter 7, Scheduling: Introduction, through the section on Round Robin. OSTEP's treatment emphasizes the trade-off between response time and turnaround time, which is the central theme of this lesson.
  • Tanenbaum & Bos — Modern Operating Systems, Chapter 2, Section 2.4.5, Round-Robin Scheduling. A complementary treatment that places round robin in the context of time-sharing systems.
  • Silberschatz et al. — Chapter 5, Section 5.5, Multilevel Queue Scheduling and Section 5.6, Multilevel Feedback Queue Scheduling. The discussion of how round robin is used within each queue of a multilevel scheduler.
  • Linux man pages: man 7 sched, man 2 sched_setscheduler, man 2 sched_rr_get_interval, man 1 chrt, man 2 sched_yield.

Reading strategy

Read the Silberschatz section first for the formal definition and the worked example. Then read OSTEP's section for the intuition about why round robin trades turnaround time for response time. Pay attention to the quantum-size discussion in both — this is the design decision that determines whether round robin behaves well or badly on a given workload. Keep the switch-cost measurement from Lesson 5.1 in mind as you read.

04 Core content

4.1 The algorithm

Round robin (RR) scheduling is defined by three rules:

  1. The ready queue is a circular queue. When a process becomes ready, it is appended to the tail.
  2. When the CPU becomes free, the process at the head of the queue is selected and given the CPU for a fixed time quantum q.
  3. If the process terminates or blocks before the quantum expires, the CPU is released immediately. If the process is still running when the quantum expires, it is preempted and appended to the tail of the queue.

The algorithm is preemptive: the timer interrupt at the end of the quantum forcibly takes the CPU away from the running process. This is different from the preemption in SRTF or preemptive priority scheduling, where preemption is triggered by the arrival of a qualifying process. In round robin, preemption is time-driven: it happens periodically, regardless of what has arrived.

The circular queue is what gives the algorithm its name. Every process that does not finish within its quantum returns to the tail, so the CPU rotates through the ready set in a cycle. On a single-core system, only one process runs at a time, but every ready process is guaranteed to run within one quantum of the previous process's completion.

4.2 The time quantum

The time quantum is the central design parameter of round robin. It is the length of time each process is allowed to run before being preempted. The choice of quantum determines almost everything about the algorithm's behaviour.

  • If the quantum is very large (larger than the longest burst in the workload), no process is ever preempted, and round robin degenerates to FCFS. The convoy effect of FCFS reappears, along with its poor response time.
  • If the quantum is very small (much smaller than the typical burst), every process is preempted many times before it completes. The context- switch overhead becomes a significant fraction of the total CPU time, and throughput suffers.
  • If the quantum is comparable to the typical burst length, most processes complete within a single quantum, and the algorithm approximates SJF for the short jobs while still guaranteeing a bounded response time for the long ones. This is the regime general-purpose systems aim for.

The quantum is typically between 10 and 100 milliseconds on a general-purpose system, with 10 ms being a common choice. The context-switch cost on modern hardware is on the order of a few microseconds, so a 10 ms quantum loses well under one percent of the CPU to switching. Historical systems used much larger quanta (100 ms or more) because their context-switch costs were higher.

Round robin scheduling with a time quantum of 4 A Gantt chart showing round robin scheduling of three processes with a time quantum of 4 time units. P1 runs 0-4, P2 runs 4-8, P3 runs 8-12, P1 runs 12-16, P2 runs 16-20, P3 runs 20-24, P1 runs 24-28, P2 runs 28-32, P3 runs 32-36, P1 runs 36-40. Completion times: P1 at 40, P2 at 32, P3 at 36. Total elapsed time is 40 units. ROUND ROBIN WITH QUANTUM = 4 CPU P1 P2 P3 P1 P2 P3 P1 P2 P3 P1 q q q q q q q q q 0 4 8 12 16 20 24 28 32 36 40 P1 (burst 12) P2 (burst 8) P3 (burst 12) quantum expiry Metrics for this schedule (q = 4) Completion: P1 = 40, P2 = 32, P3 = 36 Turnaround: P1 = 40, P2 = 32, P3 = 36 · Average turnaround = 36.0 Waiting: P1 = 28, P2 = 24, P3 = 24 · Average waiting = 25.33 Response: P1 = 0, P2 = 4, P3 = 8 · Average response = 4.0 Every process receives the CPU within one quantum of the previous one — the response-time guarantee of round robin. The waiting time is high compared to SJF, but the response time is low and the maximum wait is bounded. Average waiting vs. average response Waiting 25.33 Response 4.0 Round robin trades high average waiting time for low and bounded response time.
Figure 5.5 — Round robin with a quantum of 4 time units. Three processes with bursts 12, 8, and 12 rotate through the CPU. Every process runs once per cycle, so the response time is bounded by the number of ready processes times the quantum. The average waiting time is high — 25.33 units — because the processes are repeatedly preempted, but the average response time is only 4 units, and no process waits more than 28 units.

4.3 The response-time guarantee

The defining property of round robin is that it provides a bounded response time. If there are n ready processes and the quantum is q, then any process that becomes ready will receive the CPU within (n − 1) × q time units, provided no higher-priority process is competing for the CPU. This bound is independent of the burst lengths of the other processes, which is what makes round robin suitable for interactive systems.

Compare this to FCFS, where a process can wait for the sum of all the burst times ahead of it — a quantity that is unbounded in the worst case. And compare it to SJF, where a long process can wait indefinitely if short processes keep arriving. Round robin's bound is the reason it is the default policy in so many interactive systems: the user experience is predictable regardless of what other processes are doing.

The bound assumes that the number of ready processes does not grow during the wait. If new processes arrive, the bound increases by q for each new process that enters the queue ahead of the waiting process. On a heavily loaded system, the bound can become large in practice even though it is finite in theory.

4.4 Choosing the quantum

The quantum is the most important design parameter of round robin. It is chosen to balance three considerations.

Considerations in choosing the time quantum
Consideration Small quantum Large quantum
Response time Excellent — the bound is (n−1)×q Poor — a process may wait for the whole quantum of every other process
Context-switch overhead High — many switches per unit of useful work Low — few switches
Throughput Low — overhead reduces useful work High — more time spent on user work
Fairness High — every process runs regularly Low — the schedule approaches FCFS
Turnaround time High — processes are interrupted repeatedly Lower — processes finish with fewer interruptions

The trade-off is quantified by the effective CPU utilization formula from Lesson 5.1: 

Utilization = q / (q + switch_cost)

For a 10 ms quantum and a 5 µs switch cost, the utilization is 10/(10 + 0.005) ≈ 99.95 percent. For a 1 ms quantum, it is 1/(1 + 0.005) ≈ 99.5 percent. The overhead is small in isolation, but the effect compounds because a context switch also disrupts the CPU caches and the TLB, which can cost far more than the register save and restore itself. These indirect costs — cache pollution and TLB misses — are often more significant than the direct switch cost, and they push the practical minimum quantum higher than the simple formula suggests.

The 80% rule of thumb

A common guideline is that the quantum should be long enough that about 80 percent of CPU bursts complete within a single quantum. This ensures that most processes are not preempted at all, keeping the overhead low, while the remaining 20 percent — the longer bursts — are preempted and rotated, preserving the response-time guarantee. The value of 80 percent is empirical; it was chosen because the burst-length distribution of typical workloads makes it a good compromise. On a workload with different burst characteristics, the optimal quantum may differ.

4.5 Round robin and the standard criteria

Applying the criteria from Lesson 5.1 to round robin gives the following assessment.

Round robin against the standard scheduling criteria
Criterion Assessment Notes
CPU utilization Good, slightly reduced by switches Overhead is small for reasonable quanta; the CPU is rarely idle.
Throughput Moderate Lower than FCFS or SJF because of switch overhead, but not dramatically so.
Turnaround time Poor Interrupting processes extends their completion time. The average turnaround is higher than SJF.
Waiting time High average, low maximum Every process waits through many quanta, but no process waits indefinitely.
Response time Excellent and bounded The defining strength of round robin. Every process runs within (n−1)×q.
Fairness Excellent Every process receives an equal share of the CPU over time. No starvation is possible.
Predictability Excellent The response-time bound is a formal guarantee, not an empirical observation.

Round robin is the mirror image of SJF. SJF is excellent on average metrics and poor on fairness and predictability; round robin is excellent on fairness and predictability and poor on average metrics. This is the fundamental trade-off of scheduling, and it is why general-purpose systems use hybrid policies — such as the multilevel-feedback queues of Lesson 5.6 — that attempt to capture the strengths of both.

4.6 Round robin versus FCFS and SJF

A direct comparison on the same workload makes the trade-off concrete. Consider four processes arriving at time 0 with burst times 6, 4, 10, and 2, and a quantum of 4.

Metric FCFS SJF RR (q=4)
Average turnaround14.011.016.0
Average waiting8.55.510.5
Average response8.55.53.0
Maximum response16124

Round robin is worse than both FCFS and SJF on average turnaround and waiting time. But its maximum response time is 4 units — one quantum — compared to 12 for SJF and 16 for FCFS. For an interactive system, where the maximum response time determines the worst-case user experience, this is a decisive advantage.

4.7 Variants of round robin

Pure round robin gives every process an equal share of the CPU. Several variants adjust the algorithm to give different shares to different processes, or to respond to different workload characteristics.

Weighted round robin
Each process is assigned a weight, and it receives a number of consecutive quanta proportional to its weight. A process with weight 2 receives twice as many quanta as a process with weight 1 in each cycle. Weighted round robin is common in network schedulers, where it is used to allocate bandwidth among flows, and in virtual machine hypervisors, where it allocates CPU time among virtual machines.
Priority round robin
Processes are organized into priority levels, and round robin is used within each level. A process in a higher level always runs before a process in a lower level, but processes within the same level share the CPU equally. This is the structure of the multilevel queue scheduler examined in Lesson 5.6.
Deficit round robin
A variant used in network scheduling in which each flow accumulates a deficit when it does not use its full quantum, and can spend the deficit in a later cycle. This handles variable-size packets better than pure weighted round robin.
Multilevel feedback queue
A generalization in which processes move between queue levels based on their observed behaviour. Short jobs stay in the highest-priority queue with the shortest quantum; long jobs sink to lower-priority queues with longer quanta. This is the closest approximation to SJF among practical schedulers, and it is examined in detail in Lesson 5.6.

4.8 Round robin in real systems

Round robin appears in many systems, sometimes as the primary policy and sometimes as a component.

  • Linux SCHED_RR. Linux's real-time round-robin policy. A task with SCHED_RR runs for a fixed quantum (the default is 100 ms, adjustable through the sched_rr_timeslice_ms interface) and is then moved to the tail of its priority level's queue. Real-time tasks always run before ordinary tasks, and higher real- time priorities run before lower ones.
  • Classic UNIX time-sharing. The original UNIX scheduler used a multilevel-feedback variant of round robin. Each priority level had a different quantum, and the scheduler moved processes between levels based on their CPU usage.
  • Network schedulers. Weighted round robin is a standard policy in network interface cards and switches, where it is used to give each flow a fair share of the link bandwidth.
  • Virtual machine hypervisors. Xen and KVM use credit-based or weighted round-robin policies to allocate physical CPU time among virtual machines.
  • Cluster and batch schedulers. Some schedulers offer a round-robin policy for allocating jobs to nodes, particularly when the jobs are expected to be similar in resource requirements.

4.9 Common misconceptions

"Round robin is always fair."

Round robin is fair in the sense that every process receives an equal share of the CPU. It is not fair in the sense that every process completes in proportion to its needs — a long process completes much later than a short one, even under round robin.

"A smaller quantum is always better."

A smaller quantum improves response time but increases context-switch overhead and reduces throughput. The optimal quantum is a compromise, and on some workloads a larger quantum is better.

"Round robin minimizes average waiting time."

No — SJF minimizes average waiting time. Round robin minimizes the maximum response time and provides a bound on waiting, but its average waiting time is worse than SJF's.

"Round robin is only for interactive systems."

Round robin is used in network schedulers, virtual machine hypervisors, and some batch schedulers. Its fairness guarantee is valuable in any context where equal sharing is the goal.

"Preemption is the same as in priority scheduling."

The preemption in round robin is time-driven: it happens at quantum expiry, regardless of what has arrived. In priority scheduling, preemption is event-driven: it happens when a higher-priority process becomes ready.

"Round robin and FCFS are the same when q is large."

They are the same only when the quantum exceeds the longest burst. For a quantum larger than most bursts but smaller than the longest, round robin still preempts the long bursts, so the two algorithms differ.

05 Worked example

The following example traces a round-robin schedule in detail, computes the standard metrics, and demonstrates the effect of varying the quantum size on the same workload.

Round robin on a mixed workload

Five processes arrive at time 0 with the burst times shown. The quantum is 4 time units.

Process Arrival Burst
P108
P204
P3012
P402
P506

The schedule. The ready queue is circular, and processes are appended in arrival order. The trace is: 

| P1 | P2 | P3 | P4 | P5 | P1 | P3 | P5 | P3 |
0    4    8    12   14   18   22   26   32

Working through the trace:

  • 0–4: P1 runs for its first quantum (remaining 4). Appended to the tail.
  • 4–8: P2 runs for its first quantum and completes at time 8 (burst 4). It is not re-queued.
  • 8–12: P3 runs for its first quantum (remaining 8). Appended to the tail.
  • 12–14: P4 runs for its first quantum and completes at time 14 (burst 2). It uses only 2 of its 4-unit quantum.
  • 14–18: P5 runs for its first quantum (remaining 2). Appended to the tail.
  • 18–22: P1 runs for its second quantum and completes at time 22 (remaining 4).
  • 22–26: P3 runs for its second quantum (remaining 4). Appended to the tail.
  • 26–28: P5 runs for its second quantum and completes at time 28 (remaining 2).
  • 28–32: P3 runs for its third quantum and completes at time 32 (remaining 4).

The completion times are 22, 8, 32, 14, and 28 respectively.

Process Burst First run Completion Turnaround Waiting Response
P1802222140
P2448844
P31283232208
P421214141212
P561428282214
Average 20.8 14.4 7.6

Maximum waiting time: 22 (P5). Maximum response time: 14 (P5).

Varying the quantum

The following table shows the effect of changing the quantum on the same workload, using the formulas from this lesson. The switch cost is assumed to be 0.1 time units per switch, exaggerated for visibility.

Quantum Avg turnaround Avg waiting Avg response Max response Switches Overhead
222.416.05.28151.5
420.814.47.61480.8
819.212.812.42030.3
1618.412.016.02410.1

The pattern is clear. As the quantum grows, average turnaround and waiting time improve (the schedule approaches FCFS), and the number of context switches drops. But average and maximum response time both deteriorate. At a quantum of 16, every process completes within its first quantum, so the schedule is indistinguishable from FCFS on this workload, with the convoy-effect response times that implies.

Comparison with FCFS and SJF

For reference, the same workload under FCFS (arrival order) and SJF (shortest first) gives the following metrics.

Metric FCFS SJF RR (q=4)
Average turnaround20.016.420.8
Average waiting13.610.014.4
Average response13.610.07.6
Maximum response262614
Maximum waiting262622

Round robin has the worst average turnaround and waiting time of the three, but the best maximum response time. SJF has the best average metrics but the worst maximum response time. FCFS is dominated on almost every metric. The choice depends on which statistic matters for the workload — and for an interactive system, the maximum response time is often the one that determines user experience.

The effect of arrival times

The example above has all processes arriving at time 0. With realistic arrival times, the behaviour of round robin changes. A process that arrives while a short process is running may still be preempted at the end of the quantum, so its response time is bounded by the quantum regardless of what is running. But a process that arrives while a long process is running must wait for the current quantum to expire, which can be up to q time units. The bound on response time is therefore (n) × q rather than (n − 1) × q, because the arriving process may have to wait for the currently running process to finish its quantum before it enters the queue. This is a small difference in practice, but it matters for the formal analysis.

Adding dispatch latency

Suppose each context switch costs 0.5 time units. Round robin with a quantum of 4 has 8 switches in this example, so it loses 4 time units to overhead. The effective utilization is 4/(4 + 0.5) ≈ 88.9 percent — a significant loss. With a quantum of 8, the same workload needs only 3 switches, and the effective utilization is 8/(8 + 0.5) ≈ 94.1 percent. The overhead depends on the number of switches, which depends on the quantum, which is why the choice of quantum is a genuine engineering decision rather than an arbitrary one.

On a real system, the switch cost is on the order of microseconds while the quantum is on the order of milliseconds. The utilization loss is small — well under one percent for typical quanta — and the choice of quantum is dominated by the response-time requirement rather than by the overhead. But the relative cost of a smaller quantum is real: a system with a 1 ms quantum does more than twice the switching work of a system with a 10 ms quantum, even though both are "fast enough" in absolute terms.

06 Interactive activity

Activity · implement and explore round robin

This activity extends the simulator from Lesson 5.4 to round robin and explores the effect of quantum size on a real system. Work through the steps in your course VM.

  1. Implement round robin in the simulator. Modify the priority-scheduling simulator so that scheduling is round robin. The ready queue is a circular FIFO; each process runs for at most q time units before being preempted and re-queued. 
    /* Sketch:
   struct proc *queue[100];
   int head = 0, tail = 0;
   // enqueue: append at tail
   // dequeue: remove from head
   while (completed < n) {
       if (queue empty) advance time to next arrival;
       p = dequeue();
       run p for min(q, p.remaining) time units;
       advance time;
       enqueue any arrivals during this interval;
       if (p.remaining == 0) mark completed;
       else enqueue(p);
   } */
    Run the simulator on the worked-example workload with q = 4 and verify the numbers match the table.
  2. Vary the quantum. Run the simulator on the same workload with q = 1, 2, 4, 8, 16, and 32. Tabulate the average turnaround, average waiting, average response, and maximum response for each. Plot or comment on the trend. At what quantum does the schedule become indistinguishable from FCFS?
  3. Compare to FCFS and SJF. Add a command-line option to the simulator to select FCFS, SJF, or RR. Run all three on the same workload and produce a side-by-side table. Which algorithm gives the best average response? Which gives the best maximum response? Which gives the best average turnaround?
  4. Measure the context-switch cost. Run the switch-cost program from Lesson 5.1 to measure the cost of a sched_yield-based handoff. Using the formula from section 4.4, compute the effective CPU utilization for quanta of 1 ms, 10 ms, and 100 ms on a machine with that switch cost. At what quantum does the overhead exceed one percent?
  5. Observe round robin in Linux. Use chrt -r to run a process under the SCHED_RR policy and observe its behaviour. Because SCHED_RR is a real-time policy, the process will run ahead of ordinary tasks; use a short-lived process and be prepared to terminate it. 
    sudo chrt -r 50 sleep 60 &
PID=$!
chrt -p $PID
cat /proc/$PID/sched | head -30
kill $PID
    Look for the scheduling policy, the runtime, and the quantum in the /proc/<pid>/sched output.
  6. Observe the effect of nice on rotation. Run three CPU-bound processes with nice values 0, 5, and 10 simultaneously and observe their CPU shares over a 20-second period. The Linux CFS scheduler does not use round robin, but it does give each process a fair share proportional to its weight. Compare the observed shares to the shares that pure round robin would produce (equal shares). How does CFS differ from round robin? 
    nice -n 0  yes > /dev/null &
nice -n 5  yes > /dev/null &
nice -n 10 yes > /dev/null &
sleep 20
ps -o pid,ni,pcpu,comm -C yes
kill %1 %2 %3
  7. Measure the response time of an interactive task. Run a CPU-bound process in the background, then measure the time it takes for a short interactive command to complete. Repeat with several CPU-bound processes running. The measured time is the effective response time the scheduler provides. 
    yes > /dev/null &
yes > /dev/null &
yes > /dev/null &
time ls -la /usr/bin > /dev/null
kill %1 %2 %3
    Compare the interactive command's completion time when the system is idle and when it is loaded. The difference is the scheduling delay, which round robin is designed to bound.

Reflect: round robin provides a bounded response time but a poor average turnaround time. In a system where users care about the average completion time more than the responsiveness — for example, a batch system that runs overnight jobs — would you choose round robin or SJF? What if the users are submitting jobs from an interactive terminal? How does the choice depend on the workload?

07 Knowledge check

Check your understanding

Question 1

Describe the round robin algorithm. What is the role of the time quantum? What happens if the quantum is very large, and what happens if it is very small?

Show answer
Round robin maintains a circular queue of ready processes. When the CPU becomes free, the process at the head of the queue is selected and runs for at most one time quantum q. If the process terminates or blocks before the quantum expires, the CPU is released immediately. If the process is still running when the quantum expires, it is preempted and appended to the tail of the queue. The time quantum is the length of time each process is allowed to run before being preempted. Its size determines the algorithm's behaviour. If the quantum is very large — larger than the longest CPU burst in the workload — no process is ever preempted, and round robin degenerates into FCFS, with its convoy effect and poor response time. If the quantum is very small — much smaller than the typical burst — every process is preempted many times before it completes, and the context-switch overhead becomes a significant fraction of the total CPU time, reducing throughput. The optimal quantum is a compromise, typically between 10 and 100 milliseconds on a general-purpose system.

Question 2

What is the response-time bound for round robin with n ready processes and quantum q? Why is this bound important for interactive systems?

Show answer
With n ready processes and quantum q, any process that becomes ready will receive the CPU within (n − 1) × q time units, provided no new processes arrive during the wait. The bound is important for interactive systems because it guarantees that the user's actions will be responded to within a predictable time, regardless of what other processes are doing. A user typing at a terminal will see a character echo within at most (n − 1) × q units — a bound the user can rely on. Compare this to FCFS, where a process can wait for the sum of all the burst times ahead of it — a quantity that is unbounded in the worst case — or to SJF, where a long process can wait indefinitely if short processes keep arriving. Round robin's bound is the reason it is the default policy in so many interactive systems. If new processes arrive during the wait, the bound increases by q for each new process that enters the queue ahead, so on a heavily loaded system the practical bound can be large — but it remains finite and predictable.

Question 3

Four processes arrive at time 0 with burst times 3, 5, 7, and 9. Using a quantum of 4, trace the round-robin schedule, list the completion times, and compute the average waiting time and average response time.

Show answer
The schedule with q = 4, processes in arrival order P1 (3), P2 (5), P3 (7), P4 (9): 

| P1 | P2 | P3 | P4 | P2 | P3 | P4 | P3 | P4 | P4 |
0    3    7    11   15   16   20   24   27   31   35
Working through:
  • 0–3: P1 runs 3 units and completes (burst 3 < q).
  • 3–7: P2 runs 4 units (remaining 1).
  • 7–11: P3 runs 4 units (remaining 3).
  • 11–15: P4 runs 4 units (remaining 5).
  • 15–16: P2 runs 1 unit and completes.
  • 16–20: P3 runs 4 units (remaining 3, but it only needs 3 more, so it completes at 19). Actually P3 has 3 remaining, so it completes at 19.
  • Adjusting: P3 runs 16–19 and completes.
  • 19–23: P4 runs 4 units (remaining 1).
  • 23–24: P4 runs 1 unit and completes.
Corrected schedule: 
| P1 | P2 | P3 | P4 | P2 | P3 | P4 | P4 |
0    3    7    11   15   16   19   23   24
Completion times: P1 = 3, P2 = 16, P3 = 19, P4 = 24.

Turnaround: P1 = 3, P2 = 16, P3 = 19, P4 = 24. Average turnaround = (3 + 16 + 19 + 24)/4 = 15.5.

Waiting: P1 = 0, P2 = 11, P3 = 12, P4 = 15. Average waiting = (0 + 11 + 12 + 15)/4 = 9.5.

Response: P1 = 0, P2 = 3, P3 = 7, P4 = 11. Average response = (0 + 3 + 7 + 11)/4 = 5.25.

Maximum response = 11 (P4). The response-time bound is (n − 1) × q = 3 × 4 = 12, and the observed maximum is 11, within the bound.

Question 4

Compare round robin with FCFS and SJF on the criteria of average waiting time, average response time, maximum response time, and fairness. Which algorithm would you choose for an interactive system, and which for a batch system? Explain.

Show answer
On average waiting time, SJF is best, FCFS and round robin are worse, and round robin is usually the worst of the three because it interrupts processes that would otherwise complete. On average response time, round robin is best, because every process runs within one quantum. On maximum response time, round robin is dramatically better: it is bounded by (n − 1) × q, while FCFS and SJF can have unbounded maximums. On fairness, round robin and FCFS are good — every process is treated equally — while SJF is poor because it can starve long jobs. For an interactive system, round robin is the right choice: the maximum response time is what determines the user's experience, and round robin bounds it. The worse average turnaround time is a price worth paying. For a batch system, SJF is the right choice: the average turnaround time determines throughput and cost, and there is no interactive user to be frustrated by a long wait. The choice depends on which statistic matters for the workload, and the two algorithms optimize different statistics.

Question 5

What is weighted round robin, and how does it differ from pure round robin? Describe one application in which weighted round robin is used, and explain why the weights are necessary.

Show answer
Weighted round robin assigns each process or flow a weight and gives it a number of consecutive quanta proportional to its weight in each cycle. A process with weight 2 receives twice as many quanta as a process with weight 1, so it receives twice the share of the CPU (or link bandwidth, in the network case). Pure round robin is the special case where all weights are equal. Weighted round robin is used in network schedulers, where it allocates link bandwidth among flows. The weights are necessary because different flows have different requirements: a video stream needs more bandwidth than a text chat, and the scheduler must allocate the link accordingly. Without weights, every flow would receive the same share, and the video stream would receive far less than it needs while the chat received far more. Weighted round robin is also used in virtual machine hypervisors, where it allocates physical CPU time among virtual machines according to the resources each has been assigned, and in quality-of-service systems where different classes of traffic have different service-level agreements.

08 Unit discussion

Discussion prompt

Round robin gives every process an equal share of the CPU. This is the simplest possible notion of fairness, and it is what makes round robin the default policy in so many interactive systems. But it is not the only possible notion. Weighted round robin gives processes different shares based on their weights. Priority scheduling gives some processes more than others based on their priority. And SJF gives short processes more CPU time than long ones, on the grounds that this minimizes the average waiting time.

Which notion of fairness is right for a general-purpose operating system? Should a process that has been running for hours receive the same share of the CPU as one that was just started? Should a user's interactive shell receive the same share as a background compilation? Should a process that has just been created receive the same share as one that has been waiting a long time?

The Linux CFS scheduler answers these questions in a particular way: it gives every process a share of the CPU proportional to its weight, but the weight is adjusted dynamically based on the process's behaviour and on the nice value set by the user. Is this the right answer? What would you change? Post your response to the Unit 5 discussion forum and reply to at least two classmates. Supports CLO1, CLO3, and CLO7.

09 Practice exercise

This ungraded exercise consolidates the lesson and prepares you for Lab 4. Aim to spend 60–90 minutes on it.

  1. Trace round robin by hand. For the workload below, construct the Gantt chart for round robin with q = 3, compute the completion, turnaround, waiting, and response times for each process, and report the averages and the maximum waiting and response times. Then verify your answers using the simulator from the interactive activity.
    Process Arrival Burst
    P107
    P214
    P329
    P435
    P542
  2. Vary the quantum. For the workload in question 1, run the simulator with q = 1, 2, 3, 4, 5, 8, and 16. Tabulate the average turnaround, average waiting, average response, and maximum response for each. Plot the results on a graph with the quantum on the x-axis and the metrics on the y-axis. Identify the quantum at which the schedule becomes indistinguishable from FCFS. What does this tell you about the relationship between round robin and FCFS?
  3. Compare round robin to FCFS and SJF. For the workload in question 1, compute the metrics under FCFS (arrival order), SJF, and round robin with q = 3. Present the results in a table and write a paragraph explaining which algorithm you would choose for an interactive system and which for a batch system.
  4. Compute effective utilization. Suppose the context-switch cost is 3 microseconds. Compute the effective CPU utilization for quanta of 1 ms, 5 ms, 10 ms, 50 ms, and 100 ms. At what quantum does the overhead exceed one percent? At what quantum does it exceed five percent? What does this suggest about the minimum practical quantum on a modern system?
  5. Design a weighted round robin policy. Suppose you have three classes of process: interactive shells, batch jobs, and background system tasks. Design a weighted round robin policy that gives interactive shells three times the CPU share of batch jobs, and batch jobs twice the share of background tasks. Specify the weights and the quantum. Run the simulator with your policy on a workload containing processes from all three classes, and report the CPU share each class receives.
  6. Measure the response-time bound. Run the interactive-task measurement from the interactive activity with a varying number of CPU-bound background processes: 0, 1, 2, 4, 8. Record the time it takes for the short command to complete in each case. Plot the relationship between the number of background processes and the response time. Does the relationship match the (n − 1) × q bound? What does the measurement tell you about the effective quantum that Linux uses?
  7. Read the round-robin sections of Silberschatz and OSTEP. Read the round-robin sections in both textbooks and note where they agree and where they differ. Which treatment do you find clearer on the quantum-size trade-off? Write a short paragraph summarising the differences.

10 Summary

  • Round robin (RR) scheduling gives each process a fixed time quantum and moves it to the tail of the ready queue when the quantum expires. It is preemptive, and its preemption is time-driven rather than event-driven.
  • The time quantum is the central design parameter. A large quantum makes round robin degenerate into FCFS; a small quantum maximizes responsiveness at the cost of context-switch overhead. Typical values on a general-purpose system are 10–100 milliseconds.
  • Round robin provides a bounded response time: with n ready processes and quantum q, a newly ready process receives the CPU within (n − 1) × q time units. This bound is independent of the other processes' burst lengths, which is what makes round robin suitable for interactive systems.
  • Round robin is excellent on response time, fairness, and predictability. It is poor on average waiting time and average turnaround time, because it interrupts processes that would otherwise complete.
  • Round robin is the mirror image of SJF: SJF optimizes the average metrics and neglects fairness and predictability; round robin optimizes fairness and predictability and neglects the average metrics. This is the fundamental trade-off of scheduling.
  • Weighted round robin gives processes different shares based on their weights. It is used in network schedulers, virtual machine hypervisors, and quality-of-service systems.
  • Priority round robin combines priority levels with round robin within each level. This is the structure of the multilevel queue scheduler examined in Lesson 5.6.
  • Round robin appears in real systems as Linux's SCHED_RR policy, in classic UNIX time-sharing, in network schedulers, in virtual machine hypervisors, and as a component of multilevel schedulers.
  • The effective CPU utilization is q / (q + switch_cost). For a 10 ms quantum and a few-microsecond switch cost, the loss is well under one percent. The choice of quantum is dominated by the response-time requirement rather than by the overhead.

Looking ahead

Round robin gives every process an equal share of the CPU, and it provides a bounded response time. But it is not the only way to combine the strengths of the algorithms we have seen. The final lesson of Unit 5 examines multilevel queue scheduling and multilevel feedback queue scheduling, which combine multiple scheduling policies — including round robin, priority scheduling, and FCFS — into a single scheduler. The multilevel feedback queue is the closest practical approximation to SJF, and it is the basis of the Linux CFS scheduler and the Windows thread scheduler. Lesson 5.6 covers the design, the implementation, and the analysis of these hybrid schedulers, and closes the unit with a discussion of how the classical algorithms we have studied appear in modern systems.

11 References

  • Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 5, Sections 5.3.3, 5.5, and 5.6.
  • Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapters 7 and 8. Available online at ostep.org.
  • Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 2, Section 2.4.5.
  • Love, R. Linux System Programming, 2nd ed., Chapter 3.
  • Linux man-pages: man 7 sched, man 2 sched_setscheduler, man 2 sched_rr_get_interval, man 2 sched_yield, man 1 chrt, man 5 proc (the /proc/<pid>/sched interface).
  • Shreedhar, M., & Varghese, G. Efficient Fair Queueing Using Deficit Round Robin. IEEE/ACM Transactions on Networking, 1996. The reference for deficit round robin.
👤