ExtendedSource checked

Multilevel Feedback Queue

Uses several priority queues and moves tasks based on their behavior.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Scheduling
Difficulty: Intermediate
Family: Adaptive Scheduling
Tier: Extended
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 0
Relationships: 1
Code example: Ready
Visualization: Ready
Aliases: MLFQ

Overview

A Multilevel Feedback Queue favors interactive jobs while gradually lowering priority for CPU-heavy tasks.

Core Concepts

task orderingprocess schedulingqueue frontieradaptive schedulingready queuetask priorityresource allocation

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(1)

Average

O(n + c)

Worst

O(n + c)

Space

O(n)

When to Use

Use Multilevel Feedback Queue when you need to maintain multiple ready queues.
Use it for general-purpose CPU scheduling with inputs like ready tasks.
Use it when tasks, priorities, deadlines, or resource limits drive execution order.
Use it when the Adaptive Scheduling tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when fairness, latency, and throughput requirements conflict but are not prioritized.
Avoid it when the required output is not adaptive execution schedule.

What It Does

Maintains multiple ready queues
Moves tasks between queues based on runtime behavior

Use Cases

General-purpose CPU scheduling
Interactive systems
Balancing responsiveness and throughput

Inputs

Ready tasks
Queue levels
Time quanta

Outputs

Adaptive execution schedule

Pseudocode

1.Place new tasks in a high-priority queue
2.Always choose the highest non-empty queue
3.Run a task for that queue's time slice
4.Demote tasks that use their full slice
5.Periodically boost waiting tasks

Canonical Example

Input: tasks = A(4ms), B(2ms), C(1ms)
Output: execution order and completion times
Explanation: Multilevel Feedback Queue: The scheduler chooses which task should run next according to its rule.

Implementation Notes

Keep the input contract explicit: Ready tasks; Queue levels; Time quanta.
Use this step as the implementation spine: Place new tasks in a high-priority queue.
Then preserve the next state change: Always choose the highest non-empty queue.
Record arrival time, remaining work, and completion time so schedule metrics can be checked.

Common Pitfalls

MLFQ behavior depends on queue count, quantum sizes, and boost policy.
Ignoring starvation, preemption cost, or inaccurate duration estimates.
Returning adaptive execution schedule without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show tasks moving between priority queues over time.

Step 1 of 5: Place new tasks in a high-priority queue

feedback-queues

Notes

Multilevel Feedback Queue operates in O(n + c) time and O(n) space within the Adaptive Scheduling family. Often compared with Round Robin Scheduling and Priority Scheduling.

Sources (1)

What each reference supports for this entry.

Operating System Concepts

Book

Operating-systems reference for multilevel feedback queues, priority demotion, and time-slice scheduling.

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discovery Open map

UsesRound Robin Scheduling

Scheduling · Foundation

Multilevel feedback queues often use round-robin service within individual priority queues.

Compare with this

Relationships

View full relationship page