Multilevel Queue Scheduling

Introduction

In a large company, different types of work require different handling. The CEO's requests go through an executive assistant and get immediate attention. Regular employee requests go through a ticketing system. Maintenance requests go through a different queue entirely. Each type of work has its own queue with its own rules. This is exactly how multilevel queue scheduling works.

Multilevel Queue Scheduling partitions the ready queue into several separate queues. Each queue has its own scheduling algorithm, and there is a fixed scheduling policy between queues (usually priority-based). Processes are permanently assigned to a queue based on properties like process type, priority, or memory requirements.

How It Works

The key idea is classification. Processes are divided into categories, and each category gets its own queue with its own scheduling algorithm:

Rules of Multilevel Queue Scheduling

1. Permanent assignment — A process stays in its assigned queue forever. It cannot move between queues.
2. Inter-queue scheduling — Usually fixed-priority preemptive. The CPU serves the highest-priority non-empty queue.
3. Intra-queue scheduling — Each queue can use a different algorithm internally (RR, FCFS, SJF, etc.)

Detailed Example

Consider a system with three queues:

• Queue 1 (System): Priority scheduling, highest priority
• Queue 2 (Interactive): Round Robin with quantum = 4ms
• Queue 3 (Batch): FCFS, lowest priority

Execution Trace

Gantt Chart

Notice how P3 (batch process) had to wait until time 20 despite arriving at time 0. This illustrates the potential starvation problem in multilevel queue scheduling.

Scheduling Between Queues

There are two common approaches for inter-queue scheduling:

Fixed Priority (Preemptive)

The most common approach. Higher-priority queues always preempt lower ones. A batch process only runs when all system and interactive queues are empty. This maximizes responsiveness for important processes but can starve lower queues.

Time Slicing Between Queues

Each queue gets a percentage of CPU time. For example:

• System queue: 20% of CPU time
• Interactive queue: 60% of CPU time
• Batch queue: 20% of CPU time

This prevents starvation but reduces responsiveness for high-priority processes.

Comparison with Single Queue

Practical Example: Unix/Linux

Unix-like systems traditionally use a multilevel queue structure:

A real-time audio processing thread (priority 30) will always preempt a normal user process (priority 120) like a text editor or web browser.

Limitations

The biggest limitation of multilevel queue scheduling is its rigidity. Once a process is assigned to a queue, it stays there permanently. But what if a process changes behavior? A CPU-bound process might become I/O-bound, or a batch job might become urgent. The process cannot move to a more appropriate queue.

This limitation is addressed by the Multilevel Feedback Queue (covered separately), which allows processes to move between queues based on their behavior.

Real-World Analogy

Multilevel queue scheduling is like a hospital with different departments. Emergency patients go to the ER (highest priority, immediate attention). Scheduled surgery patients go to the surgical ward (high priority, Round Robin by appointment time). Outpatients go to the general clinic (lower priority, FCFS). A patient assigned to outpatient care cannot jump to the ER queue just because they have been waiting long — they are permanently assigned to their category based on their initial assessment.

Key Takeaways

• Multilevel queue scheduling uses multiple separate queues for different process categories
• Each queue can have its own scheduling algorithm (RR, FCFS, Priority, etc.)
• Processes are permanently assigned to queues and cannot move between them
• Inter-queue scheduling is typically fixed-priority preemptive (highest queue served first)
• Time slicing between queues can prevent starvation of lower-priority queues
• The rigidity of permanent queue assignment is the main drawback
• All modern operating systems use some form of multilevel queue scheduling
• The Multilevel Feedback Queue addresses the limitation by allowing queue migration