Multilevel Queue (MLQ) Scheduling in OS

Multilevel Queue (MLQ) scheduling is a CPU scheduling algorithm; it divides the ready queue into multiple separate queues based on the priority or type of processes. Every separate queue can use a different CPU scheduling algorithm. Generally, higher-priority queues are served before lower-priority queues.

Look at the following diagram where a ready queue is divided into three levels, where Level 1 contains the processes of higher priority and Level 3 contains the lowest priority.

Explain:

• System Processes (Level 1): Handle important OS tasks such as memory management and device control, so they have the highest priority and may use Round Robin (RR).
• Interactive Processes (Level 2): Directly interact with users, such as web browsers and text editors, so they need a quick response and may use Shortest Remaining Time First (SRTF).
• Batch Processes (Level 3): Perform background tasks such as report generation and data processing, so they usually have lower priority and may use First-Come, First-Served (FCFS).

In MLQ Scheduling, each queue can have its own CPU scheduling algorithm, while the queues themselves are managed according to their priority.

How Multilevel Queue Scheduling Works

In MLQ scheduling, processes are permanently assigned to a particular queue.

For example:

The CPU scheduler first decides which queue should get the CPU. Then, the scheduling algorithm associated with that queue selects a process.

Scheduling Between Queues

There are two common approaches for scheduling between queues:

1. Fixed-Priority Scheduling

Each queue is assigned a priority.

The higher-priority queue is always selected before the lower-priority queue.

Queue 1 → Highest
Queue 2 → Medium
Queue 3 → Lowest

A disadvantage is starvation. If higher-priority queues continuously contain processes, lower-priority processes may wait for a very long time.

2. Time-Slice Scheduling

The CPU time can be divided among different queues.

For example:

Queue 1 → 50% CPU time
Queue 2 → 30% CPU time
Queue 3 → 20% CPU time

This allows lower-priority queues to receive CPU time even when higher-priority queues have processes waiting.

Example of MLQ Scheduling

Consider:

Suppose:

• System Queue uses FCFS
• Interactive Queue uses Round Robin
• Batch Queue uses FCFS
• System Queue has the highest priority

The scheduler first handles P1 from the System Queue. After that, it can schedule processes from the lower-level queues according to the queue-selection policy.

Advantages of MLQ Scheduling

Multilevel Queue (MLQ) Scheduling offers several advantages by dividing processes into different queues based on their type or priority. Each queue can be managed according to the specific requirements of its processes.

• Separates different types of processes into different queues.
• Each queue can use a different CPU scheduling algorithm.
• Higher-priority processes receive CPU time quickly, improving response time.
• It is useful when processes have different requirements and priorities.
• Scheduling can be customized for each process category.

Disadvantages of MLQ Scheduling

Although MLQ Scheduling provides better organization and flexibility, it also has some limitations. The fixed assignment of processes to queues can cause unfairness and make the scheduling system more difficult to manage.

• Processes are usually permanently assigned to a specific queue.
• Lower-priority queues may suffer from starvation when higher-priority queues remain busy.
• The scheduling system is more complex than simple algorithms such as FCFS.
• Choosing suitable priorities for different queues can be difficult.
• A process normally cannot move between queues, even if its requirements change.

MLQ vs Multilevel Feedback Queue

The main difference is whether processes can move between queues.

Key Point

Multilevel Queue Scheduling divides the ready queue into multiple separate queues, where each queue can have its own scheduling algorithm and priority.