Operating System - Multi-Level Queue Scheduling

What is Multi-Level Queue Scheduling?

Multi-Level Queue Scheduling is a CPU scheduling algorithm that divides the ready queue into multiple separate queues, each for a specific type of process, such as:

  • System processes

  • Interactive processes

  • Batch jobs

  • Background tasks

Each queue has its own scheduling algorithm (e.g., FCFS, Round Robin), and there is also a priority order among the queues themselves.

Key Concepts

  • Processes are permanently assigned to one queue based on characteristics (e.g., priority, memory usage, process type).

  • No movement between queues (in basic version).

  • CPU is allocated in two levels:

    1. Queue selection (which queue to choose from).

    2. Process scheduling within that queue.

Typical Queue Structure

Queue Level Process Type Scheduling Algorithm
1 System Processes Round Robin (RR)
2 Interactive Processes Shortest Job First
3 Batch Processes FCFS
4 Background Processes FCFS

Scheduling Rules

  1. Higher-priority queues always get the CPU first.

  2. If Queue 1 is empty → Scheduler checks Queue 2.

  3. Within each queue, its own algorithm decides the process order.

Example

Queues:

  • Queue 1 (System) → RR (Time Quantum = 2)

  • Queue 2 (User) → FCFS

Processes:

Process Queue Arrival Time Burst Time
P1 1 0 4
P2 2 1 3
P3 1 2 2
P4 2 3 4

Execution Flow

  • At time 0: Only P1 (Queue 1) → gets CPU

  • Round Robin in Queue 1:

    • P1 runs for 2 → remaining 2

    • P3 arrives at time 2 → join Queue 1

    • P3 runs for 2 → finishes

    • P1 runs for remaining 2 → finishes at time 6

  • Now Queue 1 is empty → move to Queue 2

    • P2 runs (FCFS) from 6 to 9

    • P4 runs from 9 to 13

Gantt Chart

Time → 0   2   4   6   9   13
        |P1|P3|P1|P2| P4 |

Advantages

  • Supports process separation (foreground vs background)

  • Flexible — different policies for different needs

  • Can prioritize critical system tasks

Disadvantages

  • Rigid — no movement between queues (in basic version)

  • Lower-priority processes may suffer from starvation

  • Difficult to tune queue parameters and priorities

Extension: Multilevel Feedback Queue

To overcome rigidity, we use Multilevel Feedback Queue Scheduling, which allows:

  • Processes to move between queues

  • Dynamically adjust priorities based on aging or behavior

Multi-Level Queue Scheduling organizes processes into multiple queues, each with its own policy, and schedules based on queue priority. It's great for separating process types but can lead to starvation if not managed carefully.