Not all jobs are equal
So far this rung has assumed a kind of democracy. FCFS served jobs in arrival order; SJF favored the short ones; round robin sliced time into fair, equal turns. But in real life some work simply matters more than other work. The audio thread keeping your music from stuttering deserves the CPU before a background backup. A kernel housekeeping task that frees memory should outrank a screensaver. We need a way to say so — and that way is priority scheduling.
The idea is delightfully simple. Give every process a number — its priority — and whenever the short-term scheduler must pick, it hands the CPU to the ready process with the most urgent number. (A famous, annoying gotcha: on many systems a lower number means higher priority, so priority 0 beats priority 9. Always check which convention your textbook or kernel uses.) Like the other algorithms, priority scheduling comes in two flavors. The non-preemptive version lets a running process keep the CPU until it blocks or finishes; the preemptive version, the moment a higher-priority process becomes ready, snatches the CPU away mid-burst and gives it to the newcomer.
The trap hidden inside every priority scheme: starvation
Priority scheduling carries a quiet, dangerous flaw. Imagine a busy hospital where the most urgent patient always goes first. That is exactly right for emergencies — but if urgent cases keep arriving, a patient with a mild complaint could sit in the waiting room forever, technically next in line for their priority but never actually called. In a computer this is starvation (also called indefinite blocking): a low-priority process is perfectly ready to run, yet a steady stream of higher-priority work means it never reaches the front. It is not stuck or broken — it is simply, endlessly, passed over.
How real is this? There is a wonderful piece of folklore: when MIT's IBM 7094 was finally shut down in 1973, operators reportedly found a low-priority job submitted in 1967 that had never run — starved for six years. Whether or not the dates are exact, the lesson is iron: any scheme that always prefers high priority will, under enough load, let some unlucky low-priority process wait without bound. Starvation is the price of caring about priority, and you cannot wish it away by being careful with your numbers.
Aging: the gentle cure
The fix is as humane as the problem. If the danger is waiting forever, then make waiting itself earn you something. Aging is the rule that the longer a process has been waiting in the ready queue, the more its priority slowly rises. Think of a deli counter where, on top of your ticket number, the staff bump up anyone who has been standing too long — eventually even the lowliest customer climbs to the front and gets served. A process that starts at priority 9 might gain a step every few seconds it sits ignored, until one day it outranks the busy high-priority crowd and finally runs.
Aging works because it guarantees an upper bound on waiting: if your priority is always climbing, you must eventually reach the top, so no process waits forever and starvation is broken. This is worth pausing on, because it is the same shape of guarantee you will meet again in concurrency under the name bounded waiting — the promise that everyone gets their turn within some finite number of others' turns. Aging is the scheduler's way of keeping that promise.
When priority breaks itself: priority inversion
Here is an honest twist that real systems hit. Suppose a low-priority process is holding a lock that a high-priority process needs. The high-priority process is forced to wait — fair enough, locks must be respected. But now a stream of medium-priority processes keeps preempting the low-priority lock-holder, so it never finishes and never releases the lock. The result is upside-down: the high-priority process is effectively stuck behind medium-priority work, all because of a lowly lock-holder it cannot help. This is priority inversion, and it is not a hypothetical — it famously froze NASA's Mars Pathfinder rover in 1997, which kept resetting itself until engineers diagnosed it from millions of miles away.
The standard cure is priority inheritance: while the low-priority process holds a lock that a high-priority process is waiting for, it temporarily borrows that high priority, finishes its work fast, releases the lock, and drops back down. The honest point for now is just this: priorities are powerful, but they interact with locking in ways that can quietly defeat the very ranking you set up. You will understand the locks behind this story properly in the concurrency rung — for here, simply file away that priority is not a fortress, and a careless mix of priorities and shared resources can invert the whole order.
The multilevel feedback queue: a scheduler that learns
Now we can assemble the masterpiece of classic scheduling. Start with a simpler idea, the multilevel queue: instead of one ready line, keep several, each with its own priority and its own algorithm. Picture an airport with separate lines for first class, business, and economy — interactive jobs in the top line, batch jobs in the bottom, and the scheduler always serves a higher line before a lower one. The trouble is that a process is born into one line and stuck there forever. But a job's behavior is not fixed: a program that was crunching numbers a second ago might start waiting on the keyboard now. Why not let it switch lines?
That single addition — letting a process move between queues based on how it actually behaves — gives us the multilevel feedback queue (MLFQ), arguably the most influential scheduler ever designed. The "feedback" is the magic: the scheduler watches each process and reshelves it. The rules are beautifully intuitive. Every process starts in the top, highest-priority queue, which uses round robin with a small time quantum. If a process uses up its whole quantum without blocking, it looks CPU-bound and greedy, so it is demoted to a lower queue with a longer quantum. If instead it gives up the CPU early to wait for I/O, it looks interactive and well-behaved, so it stays high or is promoted.
Step back and admire what this achieves without ever being told a process's type. Short, interactive jobs naturally float to the top and feel snappy (great response time), because they keep blocking before they exhaust their quantum. Long, CPU-bound jobs naturally sink to the bottom, where they still run — just out of the way of the interactive crowd — and the longer quanta down there mean fewer wasteful context switches. The scheduler approximates SJF's benefits using only past behavior, no crystal ball required. And to stop the sunken jobs from starving, MLFQ periodically bumps everyone back to the top — which is exactly aging, wearing a different hat.
Q0 (quantum 8ms, round robin) <-- new jobs start here; interactive jobs stay
| used full quantum, didn't block? -> demote
v
Q1 (quantum 16ms, round robin)
| used full quantum again? -> demote
v
Q2 (quantum 32ms, FCFS) <-- long CPU-bound jobs settle here
Rule: always run a job from the highest non-empty queue.
Periodically: move EVERY job back up to Q0 (this is aging -> no starvation)From textbook to the real machine
Be honest about the cost of all this cleverness: MLFQ has knobs, and tuning them is genuinely hard. How many queues? How long should each quantum be? How often should you bump everyone back to the top to prevent starvation? Set the boost too rarely and long jobs starve; too often and you erase the careful sorting you just did and gameable programs can cheat by issuing a tiny pointless I/O right before their quantum ends, faking interactivity to stay high. There is no universally perfect setting — the right values depend on your workload, which is precisely why this is an engineering problem and not a solved equation.
It is worth knowing that the most widely deployed scheduler on Earth took a different road. For years Linux ran the Completely Fair Scheduler (CFS), which threw out fixed priority levels and discrete queues entirely. Instead it tracks how much CPU time each runnable process has received and always picks the one that has gotten the least, as if every process were owed an equal slice of an idealized perfectly-shared CPU. Priorities still exist — a "nice" value tilts how fast a process accrues its virtual runtime — but the core idea is fairness by accounting rather than ranking by queues. The full story of CFS, real-time scheduling, and how all this stretches across multiple cores is the subject of the final guide in this rung.