Round Robin

Definition and Overview

What is Round Robin?

Round Robin (RR) is a preemptive CPU scheduling algorithm designed for time-sharing systems. It assigns fixed time slices called time quanta to each process in the ready queue in cyclic order. Processes execute for a maximum of one quantum; if unfinished, they return to the queue's tail.

Historical Context

Introduced in early time-sharing OS designs, RR balances system responsiveness and fairness. It mitigates starvation and provides predictable CPU allocation.

Applicability

Used primarily in time-shared multi-user systems, embedded systems, and general-purpose OS schedulers where fairness and responsiveness are critical.

"Round Robin ensures equitable CPU distribution by cyclically allocating time slices, preventing monopolization by any single process." -- Abraham Silberschatz

Core Principles

Preemptive Scheduling

Scheduler forcibly interrupts running processes at quantum expiration, ensuring no process exceeds allocated CPU time.

Time Quantum Allocation

Each process receives a fixed time slice; quantum size affects responsiveness and throughput.

Fairness

Equal opportunity: all processes get CPU access in cyclic order, preventing starvation.

Context Switching

Frequent switches occur when processes exhaust quanta but remain unfinished, enabling multi-process interleaving.

Ready Queue Management

Processes queued FIFO; newly arrived processes join queue tail, maintaining order.

Mechanism and Operation

Process Queueing

All ready processes reside in a circular FIFO queue, accessed sequentially.

Dispatching

CPU dispatches process at queue head for a fixed time quantum or until termination/blocking.

Preemption

If process does not complete within quantum, it is preempted and re-queued at tail.

Process Termination

On completion, process leaves queue; scheduler selects next process.

Arrival Handling

New processes added to queue tail; no priority escalation.

while (readyQueue not empty): process = dequeue(readyQueue) run process for timeQuantum or until completion/blocking if process not finished: enqueue(process, readyQueue)

Time Quantum and Its Impact

Definition

Fixed duration a process executes before scheduler preempts.

Short Quantum Effects

Higher responsiveness; increased context switches; overhead rises; throughput may decrease.

Long Quantum Effects

Approaches First-Come, First-Served behavior; lower context switch overhead; increased response time.

Optimal Quantum Selection

Typically slightly larger than context switch time; balances throughput and latency.

Dynamic Quantum

Some systems adjust quantum based on system load to optimize performance.

Context Switching

Definition

Saving and loading process state during preemption to enable resumption.

Overhead

Consumes CPU cycles; overhead increases with frequent switching (small quantum).

Impact on Throughput

Excessive context switches reduce effective CPU time for processes.

Context Switch Components

CPU registers, program counter, memory maps saved/restored.

Optimization Techniques

Reducing switch frequency; hardware support for fast context save/restore.

ContextSwitch(process_out, process_in): save_state(process_out) load_state(process_in) update_memory_mappings(process_in) start_execution(process_in)

Advantages

Fairness

Equal CPU time distribution prevents process starvation.

Responsiveness

Suitable for interactive systems; fast response to user requests.

Predictability

Fixed time quantum ensures predictability in scheduling order.

Simple Implementation

Easy to implement with FIFO queue and timer interrupts.

Scalability

Handles large number of processes effectively.

Disadvantages

Context Switch Overhead

Frequent preemption causes overhead, reducing CPU efficiency.

Quantum Selection Sensitivity

Improper quantum size degrades performance; requires tuning.

Poor for CPU-bound Processes

Long CPU bursts get fragmented, increasing turnaround time.

Ignores Process Priorities

No inherent priority differentiation; all treated equally.

Potential Throughput Reduction

Excessive switching can reduce overall throughput.

Performance Metrics

Turnaround Time

Total time from process submission to completion; influenced by quantum and load.

Waiting Time

Time process spends in ready queue; minimized by fairness.

Response Time

Interval between submission and first CPU allocation; generally low.

CPU Utilization

Percentage of time CPU is busy; affected by context switch overhead.

Throughput

Number of processes completed per unit time; impacted by scheduling efficiency.

Comparison with Other Algorithms

First-Come, First-Served (FCFS)

RR improves responsiveness and fairness; FCFS can cause starvation and long wait times.

Shortest Job First (SJF)

SJF optimizes turnaround time but is non-preemptive and prone to starvation; RR is preemptive and fair.

Priority Scheduling

Priority algorithms favor important processes but may starve low priority; RR treats all equally.

Multilevel Queue

Combines priority and RR in levels; RR used within queues for fairness.

Multilevel Feedback Queue

Dynamic priorities with feedback; RR often serves as base algorithm for time slices.

ComparisonSummary = { "FCFS": {"Type": "Non-preemptive", "Fairness": "Low", "ResponseTime": "High"}, "SJF": {"Type": "Non-preemptive", "Fairness": "Low", "TurnaroundTime": "Optimal"}, "Priority": {"Type": "Preemptive/Non-preemptive", "Fairness": "Low", "StarvationRisk": "High"}, "RoundRobin": {"Type": "Preemptive", "Fairness": "High", "Responsiveness": "Good"}, "MLQ": {"Type": "Preemptive", "Fairness": "Moderate", "Complexity": "High"}}

Variations and Enhancements

Dynamic Quantum Round Robin

Adjusts quantum size based on load or process behavior to optimize performance.

Weighted Round Robin

Assigns weights to processes, granting proportionally larger quanta to higher-weighted processes.

Priority Round Robin

Combines priority scheduling with RR within each priority class.

Multi-Level Round Robin

Employs different quanta in multiple queues to favor interactive or CPU-bound jobs.

Quantum Adaptation Algorithms

Algorithms that vary quantum based on process burst estimation or past CPU usage.

Implementation Considerations

Timer Interrupts

Essential for enforcing quantum expiration and triggering preemption.

Process Control Block (PCB)

Stores process state; must be saved/restored during context switches.

Ready Queue Data Structure

Typically a circular FIFO queue; efficient enqueue/dequeue operations required.

Load Balancing

Ensuring even distribution in multiprocessor environments.

Quantum Tuning

System designers must empirically choose quantum to balance overhead and responsiveness.

Example and Walkthrough

Scenario Setup

Three processes P1, P2, P3 arrive at time 0 with burst times 10, 4, and 6 units respectively. Quantum = 4 units.

Execution Order

RR executes P1 (4 units), P2 (4 units), P3 (4 units), then P1 (4 units), P3 (2 units), P1 (2 units).

Gantt Chart

| P1 | P2 | P3 | P1 | P3 | P1 |0 4 8 12 16 18 20

Calculations

Turnaround Times: P1=20, P2=8, P3=18. Waiting Times: P1=10, P2=4, P3=12.

Analysis

RR ensures each process receives CPU time fairly; response time is low; waiting time varies with burst and order.

References

• Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts. Wiley, 2021. pp. 210-245.
• Tanenbaum, A. S., & Bos, H. Modern Operating Systems. Pearson, 2015. pp. 150-180.
• Stallings, W. Operating Systems: Internals and Design Principles. Pearson, 2018. pp. 320-355.
• Garg, S. K., & Garg, S. Performance Analysis of Round Robin Scheduling Algorithm. International Journal of Computer Applications, Vol. 50, 2012, pp. 25-31.
• Huang, R., & Chen, W. Dynamic Quantum Adjustment in Round Robin Scheduling. IEEE Transactions on Computers, Vol. 62, 2013, pp. 1053-1065.