1. Introduction

Round Robin (RR) is one of the most widely used CPU scheduling algorithms and serves as the foundation of many modern time-sharing operating systems. It was specifically designed to provide fairness among competing processes by ensuring that every process receives a portion of CPU time.

Unlike FCFS and SJF, which may allow one process to occupy the CPU for long periods, Round Robin distributes CPU time equally among all ready processes.

The fundamental idea is:

Every process gets a fixed amount of CPU time called a Time Quantum (or Time Slice).

If a process completes within its allotted quantum, it leaves the system. Otherwise, it is preempted and placed at the end of the ready queue, allowing other processes to execute.

Because CPU time is shared cyclically among all processes, Round Robin provides:

• Good responsiveness

• Fair CPU allocation

• Prevention of starvation

These properties make it particularly suitable for:

• Interactive systems

• Time-sharing environments

• Multi-user operating systems

Round Robin is one of the most important scheduling algorithms because it balances fairness and responsiveness while remaining relatively simple to implement.

2. Basic Concept

Round Robin scheduling is based on the principle of:

Equal CPU sharing among all ready processes.

Processes are maintained in a circular queue.

Each process receives:

Time Quantum = q

units of CPU time.

If the process finishes before the quantum expires:

Process Completes
      ↓
Leaves System

Otherwise:

Quantum Expires
      ↓
Process Preempted
      ↓
Moved To End Of Queue

The scheduler then allocates the CPU to the next process in the queue.

This cycle continues until all processes complete execution.

Key Idea

Equal Opportunity
For Every Process

No process can monopolize the CPU.

3. Working Mechanism

The Round Robin scheduler continuously cycles through the ready queue.

Whenever a process receives the CPU:

1. Allocate CPU for one quantum.

2. Execute process.

3. Check whether process completed.

4. If completed → remove process.

5. If not completed → move process to end of queue.

6. Select next process.

Execution Rule

Execute For q Units

Finished?
   |
  Yes → Exit
   |
  No
   ↓
Move To End Of Queue

Conceptual Example

Ready Queue:

[P1, P2, P3]

Execution order:

P1 → P2 → P3
       ↓
P1 → P2 → P3
       ↓
Continue Until Completion

The CPU rotates among processes in a circular manner.

4. Example

Consider the following processes:

Time Quantum:

q = 2

5. Step-by-Step Execution

Time 0 – 2

Only P1 is available.

Execute:

P1

Remaining burst:

5 − 2 = 3

P1 returns to ready queue.

Time 2 – 4

Ready Queue:

[P2, P3, P1]

Execute:

P2

Remaining burst:

4 − 2 = 2

P2 returns to queue.

Time 4 – 6

Execute:

P3

Remaining burst:

2 − 2 = 0

P3 completes.

Time 6 – 8

Execute:

P1

Remaining burst:

3 − 2 = 1

P1 returns to queue.

Time 8 – 10

Execute:

P2

Remaining burst:

2 − 2 = 0

P2 completes.

Time 10 – 11

Execute:

P1

Remaining burst:

1 − 1 = 0

P1 completes.

6. Gantt Chart

0    2    4    6    8    10   11

|P1|P2|P3|P1|P2|P1|

7. Calculations

Completion Time (CT)

Turnaround Time (TAT)

Definition:

Calculations

P1

11 − 0 = 11

P2

10 − 1 = 9

P3

6 − 2 = 4

Waiting Time (WT)

Definition:

Calculations

P1

11 − 5 = 6

P2

9 − 4 = 5

P3

4 − 2 = 2

Average Waiting Time

Average WT = 4.33 units

Average Turnaround Time

Average TAT = 8 units

8. Key Parameter: Time Quantum

The performance of Round Robin depends heavily on:

Time Quantum (q)

The value of q determines:

• Responsiveness

• Context-switch overhead

• Overall performance

Choosing an appropriate quantum is one of the most important design decisions.

Case 1: Very Large Quantum

Suppose:

q = 100

and most processes require less than 100 units.

Then:

No Preemption Occurs

Execution becomes:

P1 → P2 → P3

This is essentially:

FCFS Scheduling

Result

• Low overhead

• Poor response time

Case 2: Very Small Quantum

Suppose:

q = 1

Processes are interrupted constantly.

Example:

P1 → P2 → P3 → P1 → P2 → P3 ...

Many context switches occur.

Result

• Excellent responsiveness

• High CPU overhead

9. Trade-off

The choice of quantum creates a trade-off.

Goal

Choose a quantum that balances:

• Responsiveness

• CPU efficiency

• Context-switch overhead

Most operating systems use quantums ranging from:

10 ms – 100 ms

depending on workload.

10. Characteristics

Round Robin possesses several important characteristics.

Preemptive Scheduling

Processes may be interrupted when their quantum expires.

Fair CPU Allocation

Every process receives CPU time regularly.

Circular Queue

Processes are organized in cyclic order.

Time-Sharing Oriented

Specifically designed for interactive environments.

No Process Dominance

Long processes cannot monopolize the CPU.

11. Advantages

11.1 Ensures Fairness

Each process receives equal CPU opportunity.

P1 → P2 → P3 → P1 → P2 → P3

No process is permanently ignored.

11.2 Prevents Starvation

Unlike SJF, SRTF, and Priority Scheduling:

Every Process
Eventually Gets CPU

Thus starvation is eliminated.

11.3 Good Response Time

Users receive quick feedback.

Interactive applications become responsive.

Examples:

• Terminals

• Browsers

• Editors

11.4 Ideal for Time-Sharing Systems

Multiple users can share CPU resources effectively.

This is why RR became the standard scheduling algorithm for early time-sharing systems.

12. Disadvantages

12.1 Context Switching Overhead

Every quantum expiration causes:

Save State
Load State
Switch Process

Frequent switching increases CPU overhead.

12.2 Performance Depends on Quantum

Poor quantum selection can significantly degrade performance.

Too large:

Behaves Like FCFS

Too small:

Too Many Context Switches

12.3 Not Optimal for Waiting Time

Round Robin emphasizes fairness.

It does not minimize:

• Waiting time

• Turnaround time

as effectively as SJF or SRTF.

12.4 Increased Scheduling Complexity

Compared to FCFS:

• More scheduling decisions

• More queue management

• More context switching

are required.

13. Comparison with Other Algorithms

Key Difference

FCFS

Arrival Order

SJF

Shortest Job

SRTF

Shortest Remaining Time

Round Robin

Equal CPU Sharing

Real-World Usage

Round Robin is extensively used in:

Time-Sharing Operating Systems

Multiple users share CPU fairly.

Interactive Systems

Examples:

• Desktop operating systems

• Terminal systems

Network Servers

Ensures requests receive regular CPU access.

Many modern schedulers incorporate Round Robin concepts within larger scheduling frameworks.

Performance Summary