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
5Working / How It Works
- Round Robin Execution:
- OS sets hardware timer interrupt to Time Quantum .
- CPU executes process at head of Ready Queue.
- If process completes before , it yields CPU and exits.
- If process exceeds , 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 , move all jobs to the top queue (Aging).
6Types / Components / Characteristics
- Impact of Time Quantum Size in Round Robin:
- If TQ is extremely large (): Round Robin degrades into non-preemptive FCFS.
- If TQ is extremely small (): 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 ) |
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:
- t = 0 to 3 ms: P1 runs for 3 ms (P1 remaining = 7). Queue:
[P2, P3, P1]. - t = 3 to 6 ms: P2 runs for 3 ms (P2 remaining = 1). Queue:
[P3, P1, P2]. - t = 6 to 8 ms: P3 runs for 2 ms and terminates at t=8 ms. Queue:
[P1, P2]. - t = 8 to 11 ms: P1 runs for 3 ms (P1 remaining = 4). Queue:
[P2, P1]. - t = 11 to 12 ms: P2 runs for 1 ms and terminates at t=12 ms. Queue:
[P1]. - 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
- 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. - Conceptual Question: Explain how MLFQ dynamically differentiates between I/O-bound and CPU-bound processes.
- Application Question: Solve a Round Robin scheduling problem for 4 processes with and calculate average turnaround time.
