Round Robin And Multi Level Queue - Learning Module

Loading content...

0/227

Round Robin Algorithm

The Democratic Scheduler

Imagine a classroom where students take turns answering questions. Each student gets exactly 30 seconds to speak before passing the turn to the next person. No one dominates the discussion—everyone gets fair, equal access to participate. This simple principle of rotational fairness lies at the heart of the Round Robin scheduling algorithm.

Round Robin (RR) is perhaps the most intuitively fair CPU scheduling algorithm ever devised. By giving each process a fixed slice of CPU time called a time quantum (or time slice), and cycling through processes in a circular queue, Round Robin guarantees that no process is starved of CPU access—a critical property for interactive systems where users expect responsive behavior.

From the early days of time-sharing systems in the 1960s to modern desktop operating systems, Round Robin has remained the foundational algorithm for achieving interactive responsiveness. Understanding Round Robin deeply is essential because virtually every modern scheduler either implements it directly or uses it as a building block within more sophisticated multi-level queue structures.

What You Will Master

By the end of this page, you will deeply understand: the mechanics of Round Robin scheduling, how the ready queue operates as a circular FIFO structure, the role of the timer interrupt in preemption, the mathematical analysis of turnaround and waiting times, the tradeoffs inherent in time quantum selection, and why Round Robin forms the backbone of interactive operating systems.

Historical Context and Motivation

To appreciate Round Robin's significance, we must understand the problem it was designed to solve. In the batch processing era of the 1950s and early 1960s, computers ran one job at a time until completion. Users submitted punch cards, waited hours or days, and received output. There was no interactivity—the machine belonged entirely to whoever's job was running.

The time-sharing revolution:

As computers became more powerful and expensive, researchers realized that while one program waited for I/O (disk, tape, terminal), the CPU sat idle. The goal of time-sharing was to multiplex the CPU among multiple users, giving each the illusion of having the entire machine to themselves.

The challenge was substantial: how do you divide the CPU fairly among dozens of users, each expecting instant responses to their commands? If one user ran a long computation, should everyone else wait?

The Round Robin solution:

Round Robin emerged as the elegant answer. By limiting each process to a fixed time slice before forcing a switch to the next process, no single job could monopolize the CPU. Every user got predictable, frequent access to compute resources, enabling the responsive interactive experience that time-sharing promised.

The algorithm's simplicity was also crucial. Early systems had limited memory and processing power—complex scheduling algorithms were impractical. Round Robin required only a simple circular queue and a timer interrupt, making it implementable even on hardware-constrained systems.

From CTSS to Today

The Compatible Time-Sharing System (CTSS), developed at MIT in 1961, was among the first systems to implement Round Robin. Its success demonstrated that time-sharing was viable, directly influencing Multics and eventually Unix. Today's Linux and Windows schedulers still incorporate Round Robin principles within their multi-level queue structures.

Round Robin Algorithm Mechanics

Round Robin is a preemptive scheduling algorithm that assigns a fixed time quantum to each process. The core mechanics involve three fundamental components working in concert:

The Circular Ready Queue:

The ready queue is organized as a First-In-First-Out (FIFO) queue with circular behavior. Processes enter at the tail and are dispatched from the head. When a process exhausts its time quantum without completing, it returns to the tail—creating a circular pattern of execution.

The Time Quantum:

The time quantum (also called time slice) is the maximum amount of CPU time allocated to a process before the scheduler preempts it. Typical values range from 10ms to 100ms in modern systems. This value is fixed for pure Round Robin, though multi-level queue variants may use different quanta at different priority levels.

The Timer Interrupt:

The hardware timer generates an interrupt when the quantum expires. This interrupt transfers control to the kernel's scheduler, which saves the current process's context, moves it to the queue's tail, and dispatches the next process from the head.

round_robin_scheduler.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
from collections import deque
from dataclasses import dataclass
from typing import List, Tuple
 
@dataclass
class Process:
    """Represents a process with scheduling metadata."""
    pid: int
    arrival_time: int
    burst_time: int          # Total CPU time needed
    remaining_time: int      # CPU time still remaining
    completion_time: int = 0
    turnaround_time: int = 0
    waiting_time: int = 0
    response_time: int = -1  # -1 means not yet responded
 
def round_robin_scheduler(
    processes: List[Process], 
    time_quantum: int
) -> Tuple[List[Process], List[str]]:
    """
    Implements the Round Robin scheduling algorithm.
    
    Args:
        processes: List of processes to schedule
        time_quantum: Fixed time slice for each process
        
    Returns:
        Tuple of (scheduled processes with metrics, execution log)
    """
    # Sort by arrival time for proper simulation
    processes = sorted(processes, key=lambda p: p.arrival_time)
    
    # Initialize ready queue (circular FIFO)
    ready_queue = deque()
    
    current_time = 0
    completed = 0
    n = len(processes)
    process_index = 0  # Next process to potentially add
    execution_log = []
    
    # Add initial processes that arrive at time 0
    while process_index < n and processes[process_index].arrival_time <= current_time:
        ready_queue.append(processes[process_index])
        process_index += 1
    
    while completed < n:
        if not ready_queue:
            # CPU idle - jump to next arrival
            if process_index < n:
                current_time = processes[process_index].arrival_time
                while process_index < n and processes[process_index].arrival_time <= current_time:
                    ready_queue.append(processes[process_index])
                    process_index += 1
            continue
        
        # Dispatch process from head of queue
        current_process = ready_queue.popleft()
        
        # Record response time (first time on CPU)
        if current_process.response_time == -1:
            current_process.response_time = current_time - current_process.arrival_time
        
        # Execute for quantum or until completion
        execution_time = min(time_quantum, current_process.remaining_time)
        
        execution_log.append(
            f"[{current_time:4d}-{current_time + execution_time:4d}] "
            f"P{current_process.pid} executes ({execution_time}ms)"
        )
        
        current_process.remaining_time -= execution_time
        current_time += execution_time
        
        # Add newly arrived processes to queue
        while process_index < n and processes[process_index].arrival_time <= current_time:
            ready_queue.append(processes[process_index])
            process_index += 1
        
        if current_process.remaining_time > 0:
            # Process not complete - return to tail of queue
            ready_queue.append(current_process)
            execution_log.append(
                f"        P{current_process.pid} preempted, "
                f"{current_process.remaining_time}ms remaining"
            )
        else:
            # Process completed
            completed += 1
            current_process.completion_time = current_time
            current_process.turnaround_time = (
                current_process.completion_time - current_process.arrival_time
            )
            current_process.waiting_time = (
                current_process.turnaround_time - current_process.burst_time
            )
            execution_log.append(
                f"        P{current_process.pid} completed at time {current_time}"
            )
    
    return processes, execution_log
 
 
# Example: Simulate Round Robin with 4 processes
if __name__ == "__main__":
    processes = [
        Process(pid=1, arrival_time=0, burst_time=24, remaining_time=24),
        Process(pid=2, arrival_time=1, burst_time=3, remaining_time=3),
        Process(pid=3, arrival_time=2, burst_time=3, remaining_time=3),
        Process(pid=4, arrival_time=3, burst_time=6, remaining_time=6),
    ]
    
    time_quantum = 4  # 4ms time slice
    
    scheduled, log = round_robin_scheduler(processes, time_quantum)
    
    print("=" * 60)
    print(f"Round Robin Scheduling (Quantum = {time_quantum}ms)")
    print("=" * 60)
    
    print("\nExecution Timeline:")
    for entry in log:
        print(f"  {entry}")
    
    print("\n" + "-" * 60)
    print(f"{'PID':^5} {'Arrival':^8} {'Burst':^6} {'Finish':^7} "
          f"{'TAT':^6} {'Wait':^6} {'Resp':^6}")
    print("-" * 60)
    
    for p in scheduled:
        print(f"{p.pid:^5} {p.arrival_time:^8} {p.burst_time:^6} "
              f"{p.completion_time:^7} {p.turnaround_time:^6} "
              f"{p.waiting_time:^6} {p.response_time:^6}")
    
    avg_tat = sum(p.turnaround_time for p in scheduled) / len(scheduled)
    avg_wait = sum(p.waiting_time for p in scheduled) / len(scheduled)
    avg_resp = sum(p.response_time for p in scheduled) / len(scheduled)
    
    print("-" * 60)
    print(f"Averages: TAT={avg_tat:.2f}ms, Wait={avg_wait:.2f}ms, "
          f"Response={avg_resp:.2f}ms")

Step-by-step algorithm execution:

Initialization: All processes are sorted by arrival time. A ready queue (deque) is initialized. The current time starts at 0.
Process arrival handling: As simulation time advances, processes with arrival times ≤ current time are added to the ready queue tail.
Dispatch: The process at the head of the ready queue is selected for execution.
Execution: The process runs for either its full quantum or its remaining burst time—whichever is smaller.
Preemption check: If the process exhausted its quantum but isn't complete, it's moved to the tail of the ready queue. If complete, its metrics are calculated.
Repeat: Steps 2-5 continue until all processes complete.

Gantt Chart Analysis

A Gantt chart provides visual insight into Round Robin's execution pattern. Let's trace through a concrete example with four processes and a time quantum of 4ms.

Process Set:

Process Arrival and Burst Times
Process	Arrival Time	Burst Time (ms)
P1	0	24
P2	1	3
P3	2	3
P4	3	6

Execution Trace with Time Quantum = 4ms:

Converting Mermaid diagram...

Detailed Execution Timeline:

Time	Event	Queue State (after event)
0	P1 arrives, starts executing	[]
1	P2 arrives	[P2]
2	P3 arrives	[P2, P3]
3	P4 arrives	[P2, P3, P4]
4	P1 quantum expires, preempted	[P2, P3, P4, P1]
4	P2 starts	[P3, P4, P1]
7	P2 completes (burst < quantum)	[P3, P4, P1]
7	P3 starts	[P4, P1]
10	P3 completes	[P4, P1]
10	P4 starts	[P1]
14	P4 quantum expires, preempted	[P1, P4]
14	P1 starts	[P4]
18	P1 quantum expires, preempted	[P4, P1]
18	P4 starts	[P1]
20	P4 completes	[P1]
20	P1 starts	[]
...	P1 continues with remaining 16ms
36	P1 completes	[]

Key Observation: Short Jobs Finish Early

Notice how P2 and P3 (burst time < quantum) complete in their first turn, while P1 cycles through the queue multiple times. This demonstrates Round Robin's favorable treatment of short jobs—they experience minimal waiting relative to their burst times, which is excellent for interactive responsiveness.

Mathematical Analysis

Understanding Round Robin quantitatively requires analyzing its key performance metrics: turnaround time, waiting time, and response time.

Continuing our example with Q = 4ms:

Round Robin Performance Metrics
Process	Arrival	Burst	Completion	Turnaround	Waiting	Response
P1	0	24	36	36 - 0 = 36	36 - 24 = 12	0 - 0 = 0
P2	1	3	7	7 - 1 = 6	6 - 3 = 3	4 - 1 = 3
P3	2	3	10	10 - 2 = 8	8 - 3 = 5	7 - 2 = 5
P4	3	6	20	20 - 3 = 17	17 - 6 = 11	14 - 3 = 11

Average Metrics:

Average Turnaround Time = (36 + 6 + 8 + 17) / 4 = 16.75 ms
Average Waiting Time = (12 + 3 + 5 + 11) / 4 = 7.75 ms
Average Response Time = (0 + 3 + 5 + 11) / 4 = 4.75 ms

Theoretical Bounds:

For a system with n processes, each with burst time Bᵢ and time quantum Q:

Response Time Bound: $$Response_i ≤ (n - 1) × Q$$

This upper bound occurs when process i arrives just after process i-1 starts its quantum, meaning i must wait for all other (n-1) processes to each execute one quantum before getting its first turn.

Waiting Time Relationship: $$Waiting_i = Turnaround_i - Burst_i$$

For identical processes (all same burst time B): $$Average\ Turnaround = \frac{(n + 1) × B}{2}$$

This assumes all processes arrive at time 0 and is derived from the arithmetic series of completion times.

Comparison with SJF

For our example, let's compare with SJF (non-preemptive). SJF would execute in order P2, P3, P4, P1 with average waiting time = (0 + 2 + 5 + 11) / 4 = 4.5ms. Round Robin's 7.75ms average waiting time is higher, but the maximum waiting time (11ms for P4) is lower than SJF's theoretical maximum for long jobs. This tradeoff—higher average but lower variance—is the essence of fairness.

The Role of Context Switches

Round Robin's fairness comes at a cost: context switch overhead. Every time the scheduler preempts one process and dispatches another, the system must:

Save the current process state: Register contents, program counter, stack pointer, floating-point registers, and processor state words are copied to the PCB.
Update scheduling structures: The process queue and timing metadata must be updated.
Restore the new process state: The next process's saved state is loaded from its PCB into the CPU.
Cache/TLB effects: The new process has different memory working sets, causing cache misses and TLB flushes that degrade performance.

Quantifying the overhead:

Modern context switch times range from 1-10 microseconds for the direct switching cost. However, indirect costs (cache warming, TLB refills) can effectively add another 10-100 microseconds of lost productivity per switch.

Impact on effective throughput:

Let's analyze how context switch overhead affects Round Robin:

Context Switch Overhead Analysis (Q = 10ms, switch = 0.5ms)
Metric	Without Overhead	With Overhead	Impact
Usable time per quantum	10ms (100%)	10ms - 0.5ms = 9.5ms	5% overhead
CPU utilization	100%	9.5/10 = 95%	-5%
1-second throughput (equal jobs)	100 quanta	95 quanta of work	-5 quanta
Long job (100ms burst)	10 quanta	10 switches = 5ms lost	5% penalty

The overhead amplification problem:

As time quantum decreases, the proportion of time spent on context switches increases dramatically:

Overhead vs. Time Quantum (Assume 0.5ms switch time)
Time Quantum	Switches per 100ms	Total Overhead	CPU Utilization
100ms	1	0.5ms	99.5%
50ms	2	1.0ms	99.0%
10ms	10	5.0ms	95.0%
5ms	20	10.0ms	90.0%
1ms	100	50.0ms	50.0%

The Critical Tradeoff

This table reveals Round Robin's fundamental dilemma: smaller quanta improve responsiveness but increase overhead. A 1ms quantum means half the CPU is wasted on switching! This tradeoff drives the careful quantum selection we'll explore in the next page.

Round Robin Properties

Round Robin exhibits several distinctive properties that make it suitable for specific workloads while limiting its applicability in others:

Strengths

•Fairness: Every process gets equal CPU share over time. No starvation possible.
•Bounded Response Time: Maximum response time is (n-1) × Q, which is predictable.
•Simple Implementation: Only requires a FIFO queue and timer—easy to implement correctly.
•Good for Interactive Systems: Users experience consistent responsiveness.
•No Priority Inversion Issues: All processes are equal, eliminating priority-related bugs.

Weaknesses

•Context Switch Overhead: Frequent switches reduce effective throughput.
•Quantum Selection Sensitivity: Performance highly dependent on choosing the right Q.
•Poor for Mixed Workloads: Can't differentiate I/O-bound from CPU-bound processes.
•Higher Average Waiting Time: Compared to SJF for batch workloads.
•No Priority Support: Critical processes can't preempt less important ones.

Behavioral Analysis with Time Quantum Extremes:

When Q → ∞ (very large quantum): Round Robin degenerates to FCFS. Each process runs to completion before the next starts. Response times become unbounded for later arrivals.

When Q → 0 (infinitely small quantum): Theoretically, this is called processor sharing—each of n processes receives exactly 1/n of the CPU simultaneously (like a perfectly time-multiplexed system). In practice, context switch overhead would consume 100% of CPU.

The sweet spot: Optimal quantum balances responsiveness (small Q) against overhead (large Q). Common values range from 10-100ms, with 10-20ms being typical for interactive systems.

The Processor Sharing Model

Theoretically, as Q → 0 with zero overhead, each of n processes completes at time n × burst_time / n = burst_time. This 'processor sharing' model is useful for mathematical analysis of fair queuing systems, even though it's physically unrealizable.

Implementation Considerations

Implementing Round Robin in a real operating system involves several subtle design decisions that affect correctness and performance:

1. Queue Insertion Policy for New Arrivals:

When a new process arrives while another is executing, should it be inserted:

At the tail (standard): New process waits behind all queued processes
At the head (aggressive): New process gets next turn

The standard tail insertion is almost universally used because head insertion can starve existing processes under high arrival rates.

2. Handling Early Completion (Burst < Quantum):

When a process completes before its quantum expires:

Immediate dispatch: Switch to next process immediately (wastes no time)
Wait for quantum: Process sits idle until timer fires (wastes time)

No practical system waits—immediate dispatch is universal.

3. I/O Blocking During Quantum:

When a process blocks for I/O mid-quantum:

The process moves to the I/O wait queue
The scheduler immediately dispatches the next ready process
Upon I/O completion, the process returns to the tail of the ready queue
Its remaining quantum is typically not preserved (it gets a fresh quantum)

4. Timer Resolution:

The hardware timer must have sufficient resolution to accurately measure quanta. Modern systems use high-precision timers (HPET, TSC) accurate to microseconds or nanoseconds.

rr_kernel_structure.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
/* Simplified Round Robin kernel data structures */
 
#include <stdint.h>
#include <stdbool.h>
 
#define TIME_QUANTUM_MS 10
#define MAX_PROCESSES 256
 
typedef enum {
    PROCESS_READY,
    PROCESS_RUNNING,
    PROCESS_BLOCKED,
    PROCESS_TERMINATED
} ProcessState;
 
typedef struct Process {
    uint32_t pid;
    ProcessState state;
    
    /* Saved CPU context for context switching */
    uint64_t registers[16];
    uint64_t program_counter;
    uint64_t stack_pointer;
    uint64_t flags;
    
    /* Scheduling metadata */
    uint64_t quantum_remaining_ticks;
    uint64_t total_cpu_time;
    
    /* Queue linkage */
    struct Process* next;
    struct Process* prev;
} Process;
 
typedef struct {
    Process* head;
    Process* tail;
    uint32_t count;
} ReadyQueue;
 
/* Global scheduler state */
static ReadyQueue ready_queue;
static Process* current_process = NULL;
static uint64_t ticks_per_quantum;
 
/* Initialize the scheduler */
void scheduler_init(uint64_t timer_frequency_hz) {
    ready_queue.head = NULL;
    ready_queue.tail = NULL;
    ready_queue.count = 0;
    
    /* Calculate ticks per quantum based on timer frequency */
    ticks_per_quantum = (timer_frequency_hz * TIME_QUANTUM_MS) / 1000;
}
 
/* Add process to tail of ready queue */
void enqueue_ready(Process* proc) {
    proc->state = PROCESS_READY;
    proc->next = NULL;
    proc->prev = ready_queue.tail;
    
    if (ready_queue.tail) {
        ready_queue.tail->next = proc;
    } else {
        ready_queue.head = proc;
    }
    ready_queue.tail = proc;
    ready_queue.count++;
}
 
/* Remove and return process from head of ready queue */
Process* dequeue_ready(void) {
    if (!ready_queue.head) return NULL;
    
    Process* proc = ready_queue.head;
    ready_queue.head = proc->next;
    
    if (ready_queue.head) {
        ready_queue.head->prev = NULL;
    } else {
        ready_queue.tail = NULL;
    }
    
    proc->next = NULL;
    proc->prev = NULL;
    ready_queue.count--;
    
    return proc;
}
 
/* Timer interrupt handler - called every tick */
void timer_interrupt_handler(void) {
    if (!current_process) return;
    
    current_process->total_cpu_time++;
    current_process->quantum_remaining_ticks--;
    
    if (current_process->quantum_remaining_ticks == 0) {
        /* Quantum expired - preempt and reschedule */
        schedule();
    }
}
 
/* Main scheduling function */
void schedule(void) {
    /* Save current process context if running */
    if (current_process && current_process->state == PROCESS_RUNNING) {
        save_context(current_process);
        enqueue_ready(current_process);  /* Return to tail */
    }
    
    /* Get next process from head */
    current_process = dequeue_ready();
    
    if (current_process) {
        current_process->state = PROCESS_RUNNING;
        current_process->quantum_remaining_ticks = ticks_per_quantum;
        restore_context(current_process);
        /* Control transfers to process */
    } else {
        /* No ready process - enter idle */
        idle_loop();
    }
}

Round Robin Variants

Pure Round Robin treats all processes identically, but several variants address its limitations:

1. Weighted Round Robin (WRR):

Processes are assigned weights that determine their share of CPU time. A process with weight 2 gets twice as many quanta per cycle as a process with weight 1.

$$CPU\ Share_i = \frac{Weight_i}{\sum_{j=1}^{n} Weight_j}$$

Used in network scheduling (e.g., packet queuing) and virtualization hypervisors.

2. Deficit Round Robin (DRR):

Each process has a 'deficit counter' that accumulates unused capacity. If a process can't use its full quantum (e.g., waiting for I/O), the unused portion is credited for later. This provides fairer long-term allocation.

3. Virtual Round Robin (VRR):

Designed to address the I/O-bound process penalty in standard RR. Processes returning from I/O wait are placed in an auxiliary queue with priority over the main ready queue, ensuring I/O-bound processes get faster response.

4. Selfish Round Robin (SRR):

New processes start at low priority and gradually increase their priority based on waiting time. This combines Round Robin with aging to prevent starvation while still favoring long-running processes.

Round Robin Variant Comparison
Variant	Key Innovation	Use Case	Complexity
Standard RR	Equal time slices	General-purpose interactive	Low
Weighted RR	Proportional time by weight	Resource allocation, VMs	Low-Medium
Deficit RR	Carry-over unused quota	Network fair queuing	Medium
Virtual RR	I/O-bound process boost	Mixed workload systems	Medium
Selfish RR	Priority aging	Servers with varying loads	Medium

Modern Evolution

Modern schedulers like Linux's CFS don't use pure Round Robin, but the Round Robin principle—cycling through processes with bounded time allocations—remains foundational. CFS effectively implements a highly refined weighted Round Robin using virtual runtime tracking.

Summary: Round Robin Algorithm

We have thoroughly explored the Round Robin scheduling algorithm—the foundational preemptive scheduler that enables fair time-sharing in modern operating systems.

Key Takeaways

•Core Mechanism: Round Robin uses a fixed time quantum to cycle through processes in a FIFO queue, preempting any process that exceeds its allocated slice.
•Fairness Guarantee: Every process receives an equal share of CPU time; no process can monopolize the processor, making starvation impossible.
•Response Time Bound: Maximum response time is (n-1) × Q, providing predictable latency for interactive systems.
•Context Switch Overhead: The algorithm's fairness comes at the cost of frequent context switches, which consume CPU cycles and cause cache disruption.
•Quantum Sensitivity: Small quanta improve responsiveness but increase overhead; large quanta reduce overhead but hurt interactivity. Typical values are 10-100ms.
•Extremes Analysis: As Q → ∞, RR becomes FCFS; as Q → 0, it approaches processor sharing (with infinite overhead).
•Variants Exist: Weighted, Deficit, Virtual, and Selfish Round Robin address limitations for specific workloads.
•Foundation for Modern Schedulers: Multi-level queue schedulers use Round Robin at individual priority levels, combining its fairness with priority differentiation.

Looking Ahead:

The next page dives deep into time quantum selection—one of the most critical tuning parameters in operating system design. We'll analyze the mathematical tradeoffs, examine empirical studies, and understand how to choose optimal quantum values for different workload types.

Page Complete

You now possess a comprehensive understanding of the Round Robin scheduling algorithm—its mechanics, mathematics, properties, implementation, and variants. This knowledge forms the essential foundation for understanding modern multi-level schedulers.