Multilevel Queue (MLQ) Scheduling

Introduction

Multilevel Queue (MLQ) Scheduling is a CPU scheduling algorithm used in systems where processes are classified into different priority levels. Instead of having a single ready queue, the processes are divided into multiple queues, each with its own scheduling policy.

💡 Key Idea:

• Processes are grouped into different categories based on their characteristics (e.g., foreground vs. background processes, system vs. user processes).
• Each queue has its own scheduling algorithm (e.g., FCFS, SJF, RR).
• Queues have different priority levels, and a higher-priority queue is always executed before a lower-priority queue.

---

How Multilevel Queue Scheduling Works

1. Processes are assigned to a specific queue based on attributes like process type, memory size, priority, etc.
2. Each queue has a unique scheduling algorithm (e.g., one queue may use Round-Robin, while another uses FCFS).
3. Higher-priority queues get CPU first.
4. If a queue is empty, the scheduler moves to the next lower-priority queue.
5. Processes do not move between queues (Unlike Multilevel Feedback Queue Scheduling).

---

Structure of Multilevel Queue Scheduling

A typical MLQ system may have five queues:

1. System Processes Queue (Highest Priority) – FCFS
2. Interactive Processes Queue – Round-Robin
3. Foreground User Processes Queue – SJF
4. Background Batch Processes Queue – FCFS
5. Low-Priority Processes Queue (Lowest Priority) – FCFS

📌 Example Queue Structure:

-------------------------------------------------------
| System Processes (Highest Priority)  |  FCFS       |
-------------------------------------------------------
| Interactive Processes                 |  RR        |
-------------------------------------------------------
| Foreground User Processes              |  SJF       |
-------------------------------------------------------
| Background Batch Processes             |  FCFS      |
-------------------------------------------------------
| Low-Priority Processes (Lowest)        |  FCFS      |
-------------------------------------------------------

---

Example of Multilevel Queue Scheduling

Given Processes:

Process	Arrival Time (AT)	Burst Time (BT)	Queue Type
P1	0 ms	5 ms	System Process (FCFS)
P2	1 ms	8 ms	Interactive Process (RR)
P3	2 ms	4 ms	Foreground Process (SJF)
P4	3 ms	6 ms	Background Process (FCFS)

Step-by-Step Execution (Using MLQ with Priority Order)

1. P1 starts execution first (Highest priority → System Process).
2. P3 starts next (Foreground process → SJF scheduling).
3. P2 starts execution (Interactive process → Round-Robin).
4. P4 starts last (Lowest priority → Background process).

Gantt Chart (Execution Order Based on Queues)

| P1 | P1 | P1 | P1 | P1 | P3 | P3 | P3 | P3 | P2 | P2 | P2 | P2 | P4 | P4 | P4 | P4 | P4 | P4 |
0    1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   16   17   18   19

Calculation of Turnaround Time (TAT) & Waiting Time (WT):

Process	Arrival Time (AT)	Burst Time (BT)	Completion Time (CT)	Turnaround Time (TAT) = CT – AT	Waiting Time (WT) = TAT – BT
P1	0 ms	5 ms	5 ms	5 ms	0 ms
P2	1 ms	8 ms	12 ms	11 ms	3 ms
P3	2 ms	4 ms	9 ms	7 ms	3 ms
P4	3 ms	6 ms	19 ms	16 ms	10 ms

---

Advantages of Multilevel Queue Scheduling

✔ Efficient for handling different process types → Prioritizes important tasks.
✔ Multiple scheduling algorithms in one system → Each queue can use the most suitable algorithm.
✔ Good for multi-user systems and real-time environments → System processes get priority.
✔ Prevents CPU starvation of high-priority processes → Ensures critical processes run first.

---

Disadvantages of Multilevel Queue Scheduling

✖ Rigid queue classification → Processes cannot move between queues, leading to inefficiency.
✖ Lower-priority processes may suffer starvation → If higher-priority queues are always busy, lower queues may never execute.
✖ Complex implementation → Needs careful design and management of queue policies.
✖ Not flexible → Unlike Multilevel Feedback Queue (MLFQ), processes are permanently assigned to a queue.

---

When to Use Multilevel Queue Scheduling?

• Suitable for systems that run different types of processes, such as OS kernels, cloud computing, and servers.
• Used in environments where real-time tasks must be handled separately from batch processes.
• Not ideal for general-purpose personal computers, where dynamic process movement is needed.

---

Comparison with Other Scheduling Algorithms

Scheduling Algorithm	Preemptive?	Suitable for?	Starvation Risk?	Complexity
FCFS	❌ No	Batch Systems	✅ High	❌ Low
SJF	❌ No (SJF), ✅ Yes (SRTF)	Batch, Priority Systems	✅ High	✅ Moderate
Round-Robin	✅ Yes	Time-Sharing Systems	❌ Low	✅ Moderate
Multilevel Queue	✅ Yes	Multi-user Environments	✅ High	❌ High

---

Conclusion

Multilevel Queue Scheduling is efficient for systems with distinct process categories, such as system, interactive, and batch processes. However, its rigid structure can lead to starvation of lower-priority processes. Unlike Multilevel Feedback Queue (MLFQ), MLQ does not allow process movement between queues, making it less flexible.