1. Introduction

Multilevel Feedback Queue (MLFQ) is one of the most sophisticated and widely used CPU scheduling algorithms. It was developed to overcome the limitations of both simple scheduling algorithms and Multilevel Queue Scheduling.

Unlike Multilevel Queue Scheduling, where processes are permanently assigned to a queue, MLFQ allows processes to move dynamically between queues based on their observed behavior. The scheduler continuously monitors how processes use the CPU and adjusts their priority accordingly.

The central goal of MLFQ is to simultaneously achieve:

• Good responsiveness

• High CPU utilization

• Fairness

• Low turnaround time

MLFQ is particularly important because it approximates the behavior of the optimal SJF scheduling algorithm without requiring prior knowledge of process burst times.

For this reason, MLFQ forms the conceptual foundation of many modern operating system schedulers.

2. Motivation

Multilevel Queue Scheduling introduced the idea of multiple queues but suffered from several significant limitations.

Limitation 1: Fixed Queue Assignment

Once a process was assigned to a queue:

Queue Assignment
      ↓
Permanent

The process could not move to another queue.

This made the system inflexible.

Limitation 2: No Adaptability

A process might change its behavior during execution.

Example:

Initially CPU-Bound
        ↓
Later Interactive

Yet the scheduler could not react.

Limitation 3: Starvation

In fixed-priority queue systems:

High Priority Queue
        ↓
Always Busy

Lower-priority queues could be starved indefinitely.

Need for Improvement

An effective scheduler should:

• Adapt to process behavior

• Reward interactive processes

• Penalize CPU-bound processes

• Prevent starvation

MLFQ was designed to achieve these objectives.

3. Core Idea

The fundamental idea behind MLFQ is:

Use feedback from process behavior to dynamically adjust process priorities.

Rather than assigning fixed priorities, the scheduler observes:

• CPU usage

• Execution patterns

• Waiting time

and modifies queue placement accordingly.

Key Principles

Multiple Priority Queues

Processes are distributed across several queues.

Dynamic Movement

Processes may move:

Upward

or

Downward

between queues.

Behavior-Based Scheduling

Scheduling decisions depend on:

• CPU burst behavior

• Interaction patterns

• Waiting duration

rather than predefined classifications.

4. Structure of MLFQ

A typical MLFQ scheduler contains multiple queues arranged in priority order.

Conceptual Model

Queue 1 (Highest Priority)

Round Robin
Quantum = 4 ms

------------------------

Queue 2

Round Robin
Quantum = 8 ms

------------------------

Queue 3

Round Robin
Quantum = 16 ms

------------------------

Queue 4 (Lowest Priority)

FCFS or RR
Large Quantum

Priority Relationship

Queue 1
   ↑

Queue 2
   ↑

Queue 3
   ↑

Queue 4

Higher queues have:

• Higher priority

• Smaller time quantum

Lower queues have:

• Lower priority

• Larger time quantum

Why Different Quantums?

Interactive processes benefit from:

Small Quantum

because responsiveness improves.

CPU-bound processes benefit from:

Large Quantum

because context-switch overhead decreases.

5. Working Mechanism

MLFQ continuously adjusts priorities using feedback.

Rule 1: New Processes Start at Highest Priority

Whenever a process enters the system:

New Process
      ↓
Queue 1

This gives every process an opportunity to receive fast service.

Rule 2: Full Quantum Usage Causes Demotion

If a process consumes its entire quantum:

Uses Entire Quantum
         ↓
CPU-Bound Behavior
         ↓
Move Down

The scheduler assumes the process is CPU-intensive.

Rule 3: Early Yield Preserves Priority

If a process voluntarily releases the CPU before quantum expiration:

Requests I/O
       ↓
Interactive Behavior
       ↓
Remain High Priority

The scheduler rewards this behavior.

Rule 4: Highest Priority Queue Executes First

The scheduler always chooses:

Highest Non-Empty Queue

before considering lower queues.

6. Scheduling Flow

The execution flow typically follows this pattern.

Queue 1
   ↓
Execute

Uses Full Quantum?
   ↓
Yes

Move To Queue 2
   ↓
Execute

Uses Full Quantum?
   ↓
Yes

Move To Queue 3

Over time:

CPU-Bound Processes
        ↓
Lower Queues

while:

Interactive Processes
        ↓
Higher Queues

remain near the top.

7. Key Rules of MLFQ

Although implementations vary, most MLFQ schedulers follow several standard rules.

Rule 1

Higher-priority queues are always served before lower-priority queues.

Q1 > Q2 > Q3 > Q4

Rule 2

Processes within the same queue use:

Round Robin

scheduling.

Rule 3

Using the full quantum results in:

Demotion

to a lower-priority queue.

Rule 4

Processes that wait too long receive:

Priority Boost

through aging.

Rule 5

New processes begin in the highest-priority queue.

These rules collectively enable adaptive scheduling.

8. Example Scenario

Consider two processes.

Process A: Interactive Process

Behavior:

CPU Burst = Short

Frequent I/O

Execution:

Queue 1
      ↓
Uses Small Burst
      ↓
Remains Queue 1

Result:

Fast Response Time

Process B: CPU-Bound Process

Behavior:

Long CPU Bursts

Execution:

Queue 1
      ↓
Uses Full Quantum
      ↓
Queue 2
      ↓
Uses Full Quantum
      ↓
Queue 3

Result:

Runs In Lower Queues

This separation naturally prioritizes interactive tasks.

9. Characteristics

MLFQ possesses several important characteristics.

Dynamic Priority Adjustment

Priorities change during execution.

Feedback-Based Scheduling

Decisions depend on observed behavior.

Multiple Scheduling Levels

Several queues coexist.

Combination of Techniques

MLFQ incorporates ideas from:

• Priority Scheduling

• Round Robin

• Aging

Adaptive Behavior

The scheduler continuously adjusts to workload changes.

10. Advantages

10.1 Adaptive Scheduling

The scheduler automatically adjusts priorities.

Example:

Interactive Process
       ↓
High Priority

CPU-Bound Process
       ↓
Lower Priority

No manual classification is required.

10.2 Good for Mixed Workloads

Real systems contain:

• Interactive applications

• System services

• Batch jobs

• Background tasks

MLFQ handles all effectively.

10.3 Excellent Responsiveness

Interactive processes remain in higher queues.

Users receive:

Fast Feedback

and better responsiveness.

10.4 Reduces Starvation

Through aging and priority boosting:

Waiting Process
       ↓
Priority Increase
       ↓
Eventually Executes

Starvation is greatly reduced.

10.5 Approximates SJF

One of the most important properties:

MLFQ approximates SJF without knowing burst times.

Short processes naturally remain at higher priorities.

Long processes gradually move downward.

11. Disadvantages

11.1 Complexity

MLFQ is significantly more complicated than:

• FCFS

• SJF

• Round Robin

The scheduler must manage:

• Multiple queues

• Dynamic priorities

• Aging policies

11.2 Parameter Selection

Several parameters must be chosen carefully.

Examples:

Number Of Queues

Time Quantum

Priority Boost Interval

Demotion Rules

Poor choices can significantly reduce performance.

11.3 Implementation Difficulty

Compared to simple algorithms:

More Data Structures

More Scheduling Logic

More Maintenance

are required.

12. Comparison with Multilevel Queue

Key Difference

Multilevel Queue

Queue Assignment
      ↓
Permanent

MLFQ

Queue Assignment
      ↓
Changes Dynamically

This is the defining distinction.

13. Key Insight

The single most important insight about MLFQ is:

It approximates SJF without requiring knowledge of future burst times.

Short jobs typically:

Use Small CPU Bursts
       ↓
Remain High Priority

Long jobs typically:

Consume Full Quantums
        ↓
Move Lower

Thus MLFQ naturally favors short processes while still allowing long processes to make progress.

This behavior closely resembles SJF scheduling.

14. Real-World Relevance

MLFQ has had enormous influence on modern operating systems.

Many schedulers use MLFQ concepts such as:

• Dynamic priorities

• Feedback-based scheduling

• Priority boosting

• Aging

Examples include:

• BSD schedulers

• Windows scheduling concepts

• Earlier Linux scheduler designs

Although modern schedulers are more sophisticated, many still employ MLFQ-like principles.

Performance Summary