~/ Vjeran Grozdanic
~/posts/multi-level-feedback-queue/

Operating Systems: Three Easy Pieces - Multi-level feedback queue

Published March 18, 2026

Intro

My notes on multi-level feedback queue from the “Operating Systems: Three Easy Pieces” book. If you are interested in low level things, and how an operating system works under the hood, I can’t recommend this book enough.

Multi-level feedback queue

Multi-level feedback queue (MLFQ) is a dynamic CPU scheduling algorithm that uses multiple queues with different priority levels to manage processes. The name comes from those multiple queues.

I’ll just “borrow” the rules from the book, rules assume that we have jobs A and B:

  • Rule 1: If Priority(A) > Priority(B), A runs (B doesn’t)
    • the job in the higher priority queue will run first
  • Rule 2: If Priority(A) = Priority(B), both A and B run in round robin, in time slices
    • e.g. A runs for 10ms, then B runs for 10ms then A again for 10ms, …
  • Rule 3: When job enters the system, it is placed on the highest priority (topmost queue)
    • this allows interactivity, because interactive jobs are usually short, and user expects them to run fast, so this enables it
  • Rule 4: Once a job uses its time allotment on at a given level, its priority is reduced (it’s moved to the lower level queue)
    • “allotment” is the amount of time the job spends on the current level, before the scheduler reduces its priority. This “punishes” CPU heavy jobs to not take time away from short jobs.
  • Rule 5: After period S move all the jobs in the system to the topmost queue (highest prio)
    • without this, CPU heavy jobs would rarely run, because in the system there is almost always something that would end up in high priority queue, and once the job is in the lowest queue, it would never run

Strengths

  • good response time for interactive jobs
  • favors short jobs
  • adaptive
  • it can recover from “bad” initial placement

Drawbacks

  • it requires “voodoo constants” to tune number of queues, time slice per queue, …
  • starvation of low priority processes, if they fall to low priority queue, they rarely get CPU time
  • overhead of frequent queue management and context switching
  • unpredictable behavior because of priority changes