FIFO, priority and multi-level feedback

What does each simple ordering cost, and how does a feedback queue approximate shortest-first without knowing sizes?

FIFO

FIFO (first in, first out) serves jobs in arrival order. It needs zero information and zero state, and that is its entire case.

Its real property is about distribution, not efficiency. Among work-conserving policies, FIFO minimizes the variance of waiting time. Everybody waits for what was ahead of them, and nothing jumps the line, so waits are as even as they can be.

The failure is the other side of the same coin. Your wait is inherited from whatever sits ahead of you. So the variance of wait is dominated by the variance of job sizes. Head-of-line blocking (a small job stuck behind a huge one at the front of the line) is not a bug in FIFO. It is FIFO. This is the principle "variance costs more than volume": a few huge jobs in the line hurt everyone behind them more than many average jobs would.

The cure is never "make FIFO smarter." The cure is to add queues, which is what the next three policies do.

FIFO trades mean for predictability, and pays with the variance of whatever is ahead of you.

Priority

Priority scheduling adds an ordering key: higher priority runs first. The key has to come from somewhere, and two failures follow mechanically.

1. Starvation. Nothing bounds a low-priority job's wait, because the arrival rate of high-priority work does not have to fall to zero. The standard fix is aging: make the effective priority a function of the time waited. For example, effective = base_priority + 1 per 10 minutes waited. After enough waiting, any job reaches the top. Notice what aging does: it quietly turns priority back into a fairness policy. Starvation is also the one ordering failure that can last forever without alarming anyone: mean latency, throughput and utilization all look fine. To see it you need the age distribution of pending work, and almost nothing exports that by default.
2. Inflation. If users set their own priority, the distribution converges to everyone at the maximum. This is exactly what happened to Lena. Priority stays stratified only if the person setting it pays for it, or does not control it.

Priority also collides with locking: a low-priority task that holds a lock needed by a high-priority task makes the high-priority task wait on the low-priority one (priority inversion).

Priority is an ordering imposed by whoever supplies the key. It is unbounded below (starvation) and inflationary above.

Multi-level feedback: the workaround for unknown duration

Here is the practical answer to the missing number. Multi-level feedback queue (MLFQ): admit every job at the top priority. As a job consumes CPU time, demote it to a lower-priority queue. A job that finishes quickly is never demoted. A long job sinks.

Queue 0 (top):    each job may use up to 1 s of service, then moves down
Queue 1:          each job may use up to 10 s, then moves down
Queue 2 (bottom): everything else
Always serve the highest non-empty queue.

This approximates shortest-job-first using observed service instead of declared size. It converts an unknowable input (how long will this take?) into a measurable one (how long has it run so far?). The price is that it penalizes long jobs that were going to be long anyway. Every "short query acceleration" feature in a data warehouse is this idea. The warehouse form is the short-query lane.