Priority, starvation, aging, and MLFQ

The music player must never stutter. If it misses an audio frame, Aisha hears a click. So it should get the core ahead of the compile job.

Fine — give it a higher priority.

Now the compile job is at the back of a queue that never empties, because a new audio frame arrives every few milliseconds. The compile job waits. And waits. The laptop looks perfectly busy the entire time.

Why & what

Priority scheduling. Give every process a number. Always run the process with the best priority. It can be preemptive (a higher-priority arrival kicks out the current process) or not.

Priorities are set from things the OS knows or is told: how interactive the process is, whether it belongs to the system or to a user, and how much CPU it has recently used.

Notice that SJF is just priority scheduling where the priority is "shortest burst wins".

Starvation. A low-priority process may never run, because higher-priority work keeps arriving. Keep this separate from Module 5's deadlock, because interviews test the difference:

• Starvation — the process could run, but is never chosen. If the high-priority work ever stops, it runs. It is a scheduling failure.
• Deadlock — the process cannot run, ever, because it is waiting for something that will never be released. Nothing will fix it on its own.

Aging. The standard fix for starvation: the longer a process waits, the better its priority gets. Wait long enough and even the lowest-priority job climbs to the top and runs.

Aging is a small idea with a strong guarantee: nothing waits forever.

MLFQ — multilevel feedback queue. This is what real operating systems actually use, and it solves the problem SJF could not.

Several queues, each with a different priority and a different quantum. A process moves between them based on observed behaviour:

• Everything starts in the top queue, with a short quantum.
• Use up your whole quantum? You look CPU-heavy, so you are demoted to a lower queue with a longer quantum.
• Give up the core early to wait for I/O? You look interactive, so you stay high.
• Waited too long? Aging promotes you back up.

The result is that the editor and browser stay near the top and feel instant, while the compile job sinks to the bottom and gets long uninterrupted turns when nothing else needs the core.

The clever part: MLFQ never asks how long a job will run. It watches what the job did and predicts from that. SJF's impossible requirement is replaced by an observation.

How it works

1. A new process enters the top queue with the shortest quantum.
2. It runs when every queue above it is empty. Higher queues always win.
3. If it uses its whole quantum, it is demoted one level, where the quantum is longer but the priority is lower.
4. If it blocks for I/O before its quantum ends, it stays at its current level — it has proved it is interactive.
5. If it has waited too long, aging promotes it, which guarantees no process starves at the bottom.

Common confusion

"Starvation and deadlock are the same problem." They are not, and this is one of the most reliable interview traps in the whole subject. A starving process is waiting for a turn. A deadlocked process is waiting for a resource that will never come. Aging fixes the first. Nothing fixes the second on its own.

"A lower priority number means lower priority." It usually means the opposite. In most systems priority 0 is the highest. Whenever you are given a priority table in a question, check the convention before you draw anything.

"MLFQ needs to predict burst lengths." It does not, and this is the point of the whole design. It measures behaviour that already happened — did you use your whole turn or not — instead of guessing the future.

Interview angle

"What is starvation and how do you fix it?" Define it as indefinite waiting caused by scheduling choices, then say aging and explain it in one line: waiting time gradually raises priority, so every process eventually reaches the top.

"Difference between starvation and deadlock?" Prepare this one properly. A starved process can still run if conditions change; a deadlocked process cannot, ever. This question crosses into Module 5 and is a favourite for exactly that reason.

"How does a real OS schedule?" Say MLFQ and describe the feedback loop: demote processes that use their whole quantum, keep processes that block early, age everyone upward so nothing starves. Then land the sentence that ties the module together: it approximates "shortest job first" without ever needing to know how long a job will be.