Topic 4.3 · CPU Scheduling Algorithms

Round Robin (RR), MLQ & MLFQ Schedulers

4 min read1 question to test yourself

1Definition

  • Round Robin (RR): A preemptive CPU scheduling algorithm designed for time-sharing systems where each process gets a small fixed slice of CPU time (Time Quantum / TQ).
  • Multilevel Queue (MLQ): Divides the Ready Queue into separate sub-queues (e.g., System, Interactive, Batch) with fixed priorities and independent algorithms.
  • Multilevel Feedback Queue (MLFQ): An adaptive scheduling algorithm that allows processes to move between queues based on their historical CPU burst behavior, incorporating aging to eliminate starvation.

2Simple Explanation

  • Round Robin is like sharing a single video game controller among 4 friends. Each person gets 2 minutes (Time Quantum) to play. When 2 minutes expire, the controller is handed to the next person, and the previous player goes to the back of the line. No single person monopolizes the game, ensuring high responsiveness.
  • MLQ creates separate lines: VIPs (System jobs) get the CPU first, normal guests (Interactive jobs) second, and background tasks (Batch jobs) last. However, if VIPs keep coming, background tasks starve.
  • MLFQ fixes MLQ's rigidity. If a job consumes its entire time slice repeatedly (CPU-heavy), MLFQ demotes it to a lower queue. If a job waits too long in a lower queue, MLFQ promotes it to a higher queue (Aging).

3Real-Life Example / Analogy

  • Round Robin: Speed dating, where each participant gets exactly 3 minutes to talk before a whistle blows and everyone rotates.
  • MLQ: An airport check-in area with separate lines for First Class, Business Class, and Economy Class.
  • MLFQ: A theme park queue system. Short rides pass quickly in the fast line. If a ride takes a long time, the visitor is moved to the regular line so others aren't blocked.

4Diagram / Visual Representation

Yes

No

Ready queue

Select next process (FCFS order)

Burst time < time quantum?

Run to completion

Run for one quantum

Terminated

Quantum expires

Move process to tail of ready queue

Quantum used · demote

Quantum used · demote

Aging can promote process

Aging can promote process

Queue 0 · Highest priority
Round Robin · 8 ms quantum

Queue 1 · Medium priority
Round Robin · 16 ms quantum

Queue 2 · Lowest priority
FCFS

5Working / How It Works

  • Round Robin Execution:
    1. OS sets hardware timer interrupt to Time Quantum TQTQ.
    2. CPU executes process at head of Ready Queue.
    3. If process completes before TQTQ, it yields CPU and exits.
    4. If process exceeds TQTQ, hardware timer fires interrupt -> OS preempts process -> Saves state to PCB -> Appends process to tail of Ready Queue -> Dispatches next job.
  • MLFQ Execution Rules:
    • Rule 1: If Priority(A) > Priority(B), A runs.
    • Rule 2: If Priority(A) == Priority(B), A & B run in Round Robin.
    • Rule 3: New jobs enter highest-priority queue.
    • Rule 4: If a job uses up its time quantum in a queue, its priority is reduced (moved down 1 queue).
    • Rule 5: After time period SS, move all jobs to the top queue (Aging).

6Types / Components / Characteristics

  • Impact of Time Quantum Size in Round Robin:
    • If TQ is extremely large (TQ→∞TQ\rightarrow \infty): Round Robin degrades into non-preemptive FCFS.
    • If TQ is extremely small (TQ→0TQ\rightarrow 0): Excessive context-switching overhead stalls the processor.
  • MLQ vs. MLFQ:
Metric / Parameter Multilevel Queue (MLQ) Multilevel Feedback Queue (MLFQ)
Process Movement Fixed; processes cannot switch queues Dynamic; processes move up/down queues
Flexibility Rigid design Highly flexible and adaptive
Starvation Risk High for lower-priority queues Low (Eliminated via Rule 5 Aging)
Configuration Easy Complex (Must tune queue count, TQ, aging SS)

7Solved Examples / Problems

Problem: Given processes P1 (BT=10), P2 (BT=4), P3 (BT=2) arriving at t=0, trace Round Robin execution for Time Quantum TQ = 3 ms. Solution:

  1. t = 0 to 3 ms: P1 runs for 3 ms (P1 remaining = 7). Queue: [P2, P3, P1].
  2. t = 3 to 6 ms: P2 runs for 3 ms (P2 remaining = 1). Queue: [P3, P1, P2].
  3. t = 6 to 8 ms: P3 runs for 2 ms and terminates at t=8 ms. Queue: [P1, P2].
  4. t = 8 to 11 ms: P1 runs for 3 ms (P1 remaining = 4). Queue: [P2, P1].
  5. t = 11 to 12 ms: P2 runs for 1 ms and terminates at t=12 ms. Queue: [P1].
  6. t = 12 to 16 ms: P1 runs remaining 4 ms and terminates at t=16 ms.
  • Gantt Chart: [ P1 (0-3) | P2 (3-6) | P3 (6-8) | P1 (8-11) | P2 (11-12) | P1 (12-16) ].

8Advantages, Disadvantages & Applications

  • Round Robin Advantages: Highly responsive, low starvation, zero convoy effect.
  • Disadvantages: High context-switching overhead if TQ is chosen poorly.
  • MLFQ Advantages: Best general-purpose OS scheduler (used in Linux, macOS, Windows); automatically optimizes both interactive short jobs and long batch computations.

9Important Points to Remember

  • If Round Robin Time Quantum is too small, context-switch overhead dominates execution time.
  • MLFQ uses aging to move long-waiting processes to higher-priority queues, preventing starvation.

10Test Your Understanding

  1. MCQ: What happens to a Round Robin scheduling algorithm if the Time Quantum is set to an infinitely large value?
    • A) It turns into Shortest Job First (SJF).
    • B) It degrades into First-Come First-Served (FCFS).
    • C) It triggers system thrashing.
    • D) It causes infinite CPU context switches.
    Show answer
    B.
  2. Conceptual Question: Explain how MLFQ dynamically differentiates between I/O-bound and CPU-bound processes.
  3. Application Question: Solve a Round Robin scheduling problem for 4 processes with TQ=4 msTQ = 4\text{ ms} and calculate average turnaround time.

Finished this topic?

0 of 27 topics read in Operating Systems

Handwritten notes for the exam

Unit-wise SPPU notes and PYQs for this subject.

Helpful? Share it with your class

Free for everyone, no login needed.

Share topic