A general-purpose system runs several kinds of work:

One ready queue and one scheduling rule must treat all of them through the same policy. A short quantum helps interactive response but creates unnecessary switching for long computations. A long quantum reduces switching but can delay newly runnable interactive work.

Multilevel queues address this tension by maintaining several ready queues with different policies.

Multilevel feedback queues go further: they observe how tasks use the CPU and move them between queues.

A Multilevel Queue (MLQ) scheduler divides runnable tasks into fixed classes. Each class has its own ready queue.

For example:

The scheduler makes two kinds of decisions:

The queues can therefore use different internal policies. Queue 1 might rotate through interactive tasks, while Queue 2 runs background jobs in arrival order.

The defining property of basic MLQ is:

A task is assigned to one queue and does not move between queues as its behavior changes.

A task's queue might be chosen from information such as:

Once assigned, the task stays in that class.

An interactive task I is placed in Queue 1 for its lifetime, and a batch task B is placed in Queue 2 for its lifetime.

This is straightforward when classifications are accurate and stable. It is inflexible when a task changes behavior.

A database maintenance process may alternate between brief control operations and long CPU-intensive phases. A permanently assigned label cannot describe both phases well.

Fixed classification also depends on trustworthy inputs. If every application declares itself interactive to obtain better service, the distinction stops being useful.

The scheduler needs a policy across queues. Two common models are strict priority and fixed CPU shares.

Strict priority between queues

The highest nonempty queue always runs:

If a Queue 0 task becomes runnable while Queue 2 is running, a preemptive implementation can interrupt Queue 2 immediately.

Strict priority provides strong preference, but lower queues can starve if a higher queue remains continuously nonempty.

Time allocation between queues

The scheduler can reserve a share of CPU time for each queue:

This protects lower queues from complete starvation. It can also leave a policy decision about unused shares: if Queue 0 is empty, should its reserved time remain idle or be borrowed by another queue?

Work-conserving designs lend unused capacity to queues that have runnable work. Fixed reservations give stronger isolation but may sacrifice utilization.

These percentages divide service between queues, not necessarily equally between tasks. If Queue 2 receives 10% and contains five CPU-bound tasks, its internal policy determines how that 10% is divided.

MLQ works best when the system already knows the correct class for each task.

Its main weaknesses are:

The system needs a way to infer behavior rather than relying entirely on fixed labels.

That is the role of feedback.

A Multilevel Feedback Queue (MLFQ) scheduler also maintains several priority queues, but tasks can move between them.

The scheduler treats recent CPU usage as feedback:

Demotion is earned by using the CPU, and a periodic boost is the only way back up. Without it, a task that once ran long would stay at the bottom no matter how it behaved afterward.

The word feedback is essential. The scheduler changes a task's effective priority based on observed execution rather than keeping one permanent class assignment.

Shortest-job-based scheduling performs well when CPU-burst lengths are known. Real operating systems do not know future burst lengths exactly.

MLFQ approximates short-job preference using behavior:

A newly created interactive task receives an early chance to run. If it needs only a short burst, it finishes or blocks without waiting behind long-running background work.

A CPU-bound task is not rejected. It continues making progress in lower queues, where longer quanta can reduce switching overhead.

MLFQ is an adaptive heuristic. It does not discover a task's exact future burst length or prove that a task is permanently interactive.

To reason precisely, we need complete rules. Consider this scheduler:

The quantum is the maximum length of one uninterrupted turn at that level.

The allotment is the total CPU service a task may consume at that level before being demoted. An allotment can span several turns.

Our rules are:

These are teaching rules, not universal MLFQ laws. Changing any of them changes the resulting schedule.

Suppose a task in Q0 has:

After its first full turn:

It returns to the back of Q0 rather than moving to Q1.

After another two units at Q0:

The task is then demoted to Q1.

Using multiple quanta per level lets tasks share a queue fairly while still requiring sustained CPU consumers to move downward.

We will schedule three tasks:

A is CPU-bound. B has short CPU bursts separated by waits. C is a short CPU-only task.

Assume:

Total CPU service is:

A arrives at time 0 and enters Q0:

A runs for the Q0 quantum of two units:

B arrives at time 1 and waits in Q0. C arrives at the time-2 boundary. A has used one quantum but not its full Q0 allotment, so it returns to Q0.

Using the boundary-arrival rule:

A is not demoted yet. Demotion depends on the four-unit allotment, not one two-unit quantum.

B runs from time 2 to 3. Its first CPU burst finishes after one unit, so B blocks for three time units:

B retains its Q0 level because it did not exhaust the allotment.

C runs from time 3 to 5 for one full Q0 quantum:

C returns to the back of Q0. The queues are:

A runs from time 5 to 7.

B wakes at time 6 and joins the back of Q0. Because A is also in Q0, B does not preempt it; same-level tasks wait for the running task's turn to end.

At time 7:

A has exhausted its Q0 allotment and moves to Q1:

C runs from time 7 to 9. It receives its remaining two CPU units and completes.

B then runs from time 9 to 10. Its second CPU burst completes, and B blocks for another three units:

Q0 becomes empty, so the scheduler selects A from Q1.

A begins a four-unit Q1 quantum at time 10:

At time 13, B wakes in Q0. Q0 outranks Q1, so B preempts A.

At the interruption:

B runs from time 13 to 14, finishes its final one-unit CPU burst, and completes.

A resumes at time 14. Under our rules, it first receives the one remaining unit from its interrupted Q1 quantum:

No other task is ready, so A immediately receives another Q1 quantum from time 15 to 19:

A has exhausted its Q1 allotment and moves to Q2 with four CPU units remaining. It runs from time 19 to 23 and completes.

A starts in Q0 like everyone else and sinks as it keeps using full quanta. B and C stay in Q0 throughout, which is why their turns keep coming.

A's final interval contains:

A runs from time 14 to 19 in Q1, then from 19 to 23 in Q2.

Expanding the execution service by task:

Verify the totals:

A starts at the top like every new task. Its sustained CPU use consumes the Q0 allotment, then the Q1 allotment, so it descends to Q2.

C is also CPU-bound, but its entire four-unit burst fits within the Q0 allotment. It completes before being demoted.

B repeatedly blocks after one CPU unit. It uses only three of its four Q0 allotment units before completing, so it remains at the highest level.

B's wakeup at time 13 preempts A because B is in Q0 while A is in Q1. B does not preempt A at time 6 because both are in Q0.

The scheduler did not know that A needed 16 units or that B would use one-unit bursts. Queue movement emerged from observed CPU usage.

Because B blocks for I/O, waiting time cannot be computed as turnaround minus CPU time alone.

A never blocks:

A's ready-wait intervals are:

B arrives at time 1 and completes at time 14:

B waits one unit from arrival to its first run and three units after waking at time 6:

C never blocks:

Its ready-wait intervals are time 2 to 3 and time 5 to 7.

The trace favors B's short bursts without eliminating A's progress.

Demotion alone does not prevent starvation.

Suppose A has reached Q2 while new tasks continually enter Q0. If Q0 never becomes empty, strict priority prevents A from running again:

MLFQ commonly includes a priority boost. At a configured interval, the scheduler promotes runnable tasks to the highest queue and resets their level accounting:

The exact ordering after a boost is part of the policy. A system may preserve relative order, place older tasks first, or use another deterministic rule.

The boost gives demoted tasks a renewed opportunity to compete at the top. It also helps a task whose behavior has changed: a formerly CPU-bound task may have entered a new interactive phase.

Priority boosting and aging solve related problems in different ways.

Aging typically improves an individual task's effective priority as its ready-queue wait grows.

Global boosting periodically promotes many or all runnable tasks together.

Aging can provide smoother, per-task promotion. A global boost is conceptually simple and prevents tasks from remaining permanently trapped at a low level.

Neither operation creates CPU capacity. After promotion, tasks still share the top queue and may wait behind other runnable work.

Consider a naive rule:

Demote a task only if it uses one entire quantum without blocking.

A CPU-intensive task can exploit this rule by giving up the CPU just before each quantum ends:

If every yield resets its accounting, the task consumes substantial CPU while remaining at the highest priority.

The solution is to track cumulative CPU service at each level:

Blocking, yielding, and higher-level preemption do not erase CPU service already consumed at that level.

Our worked MLFQ uses this rule. B's three short bursts consume three cumulative Q0 units, while A's two Q0 turns consume its full four-unit allotment.

High queues favor responsiveness, so their quanta are often short. A new task receives an early turn, and one CPU-bound task cannot occupy the top level continuously.

Lower queues contain work that has demonstrated sustained CPU demand. Longer quanta can reduce context-switch frequency and preserve locality:

A longer low-level quantum does not mean low-level work becomes more important. It means that when the scheduler chooses low-level work, allowing a longer continuous run may be more efficient.

High-level arrivals can still preempt that run under a strict-priority MLFQ.

An MLFQ is a family of policies, not one fully specified algorithm. Its behavior depends on several choices.

Number of queues

More levels allow finer distinctions in observed CPU usage. They also increase implementation and tuning complexity.

Quantum at each level

Short upper-level quanta improve rotation speed. Longer lower-level quanta reduce switching for sustained computation.

Allotment at each level

The allotment determines how much total CPU service a task receives before demotion. It may equal one quantum or span several.

New-task placement

Starting new tasks at the top gives them an optimistic opportunity to behave interactively. Starting too many untrusted tasks at the top can temporarily delay established lower-level work.

Wakeup behavior

A waking task might return to its previous level, receive a promotion, or be placed according to a separate rule. The decision affects interactive response and resistance to gaming.

Boost interval

A short interval protects lower queues quickly but weakens the meaning of demotion. A long interval preserves differentiation but permits longer starvation.

Accounting rules

The scheduler must define whether usage survives blocking, yielding, preemption, and a change of queue. Incomplete accounting makes both calculations and implementations inconsistent.

The presence of several queues does not make a scheduler an MLFQ. Tasks must be able to move in response to behavior or waiting.

A simplified scheduler can be expressed as follows:

When a task executes:

When a turn ends:

At a global boost:

The pseudocode makes the policy explicit. A real implementation can maintain the same behavior using more efficient event tracking and queue structures.

MLFQ problems are easier when queue state and per-task accounting are written down after every event.

For each task, track:

Stop the timeline at:

At each event:

Do not demote a task merely because higher-priority work preempted it. Demotion follows CPU service consumed, not wall-clock time spent waiting.

After the schedule is complete, verify that every task received exactly its required CPU time and that no lower queue ran while an eligible higher queue was nonempty.

An application worker system can use fixed priority lanes:

That resembles MLQ. It is simple, but a constant urgent workload can starve the background queue unless the worker pool reserves capacity or periodically serves lower lanes.

An adaptive worker system can use feedback. Jobs that consume repeated execution budgets may move to a slower batch lane, while brief jobs remain in a fast lane. Aged jobs can move upward after waiting too long.

Application jobs introduce an extra difficulty: operating-system threads can be preempted transparently, but an application-level job may not be safely interruptible. Moving partially completed work between worker queues may require checkpoints, idempotency, and explicit state management.

The scheduling ideas still transfer:

Multilevel Queue scheduling divides tasks into fixed classes, gives each class its own ready queue, and uses a policy such as strict priority or fixed CPU shares between queues. Its simplicity comes at the cost of inflexible classification and possible starvation.

Multilevel Feedback Queue scheduling moves tasks according to observed CPU use. New and short-burst tasks receive high priority, sustained CPU consumers descend toward longer-quantum queues, and higher-level work can preempt lower-level execution.

A complete MLFQ must define quanta, per-level allotments, cumulative accounting, wakeup behavior, tie rules, and priority boosts. Feedback improves adaptability, while persistent accounting prevents gaming and periodic promotion protects low-level tasks from indefinite starvation.