When "good enough on average" is not enough
Everything you have learned about CPU scheduling so far has chased the same goal: good behaviour on average. Round robin keeps everyone responsive on average; SJF minimises the average waiting time; the multilevel feedback queue guesses which jobs are interactive and treats them kindly. For a laptop or a web server, average is exactly the right target — if your music player occasionally waits an extra few milliseconds, nobody dies.
But now picture the software inside a car's airbag controller, a pacemaker, or a factory robot's arm. Here a task is not just "important" — it has a deadline, a wall-clock instant by which it absolutely must finish. An airbag that fires 50 milliseconds late is worse than useless. This is the domain of real-time scheduling, and it changes the question entirely. We no longer ask "how do we keep the average happy?" We ask "can we PROVE, before the system ever runs, that every deadline will always be met?"
Two real-time schedulers: fixed priority vs the nearest deadline
Most real-time work is periodic: a task wakes up every so often, does a fixed chunk of work, and must finish before its next wake-up. Read the temperature every 10 milliseconds; refresh the display every 16. So each task has a period (how often it runs) and an execution time (how long one run takes). Given a pile of such tasks on one CPU, the two famous algorithms differ only in how they assign priorities.
Rate-monotonic scheduling is the simpler one: it hands the highest priority to the task with the shortest period, and never changes its mind. Run more often, get treated as more urgent — that is the whole rule. Because the priorities are fixed once and for all, rate-monotonic scheduling is easy to implement and easy to reason about. Its catch is that it cannot always use the whole CPU: even when a deadline-respecting schedule exists, rate-monotonic may fail to find it once the CPU gets too crowded (roughly past 69% utilisation in the worst case).
Earliest-deadline-first is the cleverer one: at every instant it runs whichever ready task has the nearest deadline, recomputing priorities on the fly as deadlines approach. The payoff is striking — EDF is optimal for a single CPU: if any scheduler can meet all the deadlines, EDF can too, and it can squeeze the CPU all the way to 100% utilisation. The price is more bookkeeping (it must constantly re-sort by deadline) and a nastier failure mode: when an overloaded rate-monotonic system breaks, the lowest-priority task misses first, predictably; when an overloaded EDF system breaks, it can cascade and miss deadlines all over the place.
T1: period 4 ms, run 1 ms T2: period 5 ms, run 2 ms Rate-monotonic (T1 shorter period => higher priority): | T1 | T2 | T2 | T1 | T2 | T2 | T1 | ... ^T1 always wins ties; fixed forever Earliest-deadline-first (run the nearest deadline): | T1 | T2 | T2 | ... whoever's deadline is closest right now ^priorities recomputed as deadlines move
More than one CPU: sharing the work without chaos
Until now we have quietly assumed one CPU and asked only "who runs next?". Every modern machine, though, has several CPU cores, so the real question becomes "who runs WHERE, and on which core?" This is multiprocessor scheduling, and it brings genuinely new problems. The cleanest design gives all cores one shared ready queue and lets any idle core grab the next process — simple, but every core now fights over that one queue's lock, which becomes a bottleneck as you add cores. So most real systems give each core its OWN run queue instead, and the hard part becomes keeping those queues balanced.
If each core has its own queue, one core can be swamped with ten processes while its neighbour sits idle — a waste of a whole CPU. The fix is load balancing: the kernel periodically checks for lopsided queues and migrates work across. There are two flavours — push migration, where a busy core's runqueue actively shoves a task onto an idle one, and pull migration, where an idle core reaches over and steals a task from a busier neighbour. Real kernels do both. Think of supermarket checkout lanes: a staff member either waves you to an empty till (push), or an idle cashier calls "next customer over here" (pull).
But there is a tension hiding here. Moving a process to a different core is not free, because each core has its own fast local cache full of that process's recently used data. Migrate the process and you leave its warm cache behind; on the new core it starts "cold" and must reload everything from main memory, which is far slower. The kernel's preference for keeping a process on the SAME core it last ran on is called processor affinity — exactly the TLB-and-cache wisdom from the memory rung, applied to scheduling: warm data near where it is used is gold, so do not throw it away lightly.
A real scheduler: Linux's Completely Fair Scheduler
Time to see how all this theory lands in a real, shipping operating system. For over a decade Linux's default scheduler for ordinary tasks was the Completely Fair Scheduler, or CFS, and its central idea is delightfully simple. Instead of fixed time slices, CFS tracks how much CPU time each runnable task has already received — a number it calls virtual runtime — and always runs the task that has gotten the LEAST so far. The task that has been most starved goes next. It is the fairness of round robin, but continuous rather than chopped into rigid quanta.
How does "give the CPU to whoever has run least" handle priority? Through the virtual-runtime clock's SPEED. A high-priority task's virtual runtime ticks up slowly, so even after a lot of real CPU time it still looks under-served and keeps getting picked; a low-priority task's clock races ahead, so it quickly looks "satisfied" and steps aside. Same fairness rule, different clock rates — elegant, and far less fiddly than the towers of feedback queues from the previous guide. To pick the least-served task fast, CFS keeps all runnable tasks in a balanced tree sorted by virtual runtime, so finding the next one to run is cheap even with thousands of tasks.
- Three tasks become runnable. CFS records each one's virtual runtime; a brand-new task starts near the current minimum so it is not unfairly favoured nor starved.
- The dispatcher picks the task with the smallest virtual runtime — the one most behind — and runs it. (This is the dispatcher doing its context switch, exactly as in guide one.)
- As that task runs, its virtual runtime climbs — slowly if it is high priority, fast if it is low. After a small slice, the kernel checks whether someone else is now further behind.
- If a more-starved task now exists (or one just woke up), CFS preempts the current task and switches to the new most-behind one. Then repeat forever — fairness is maintained continuously, not at fixed quantum boundaries.
Two honest caveats keep CFS from sounding like magic. First, "completely fair" is an ideal, not a literal promise — on real hardware with finite timers, caches, and affinity costs, CFS only APPROXIMATES perfect fairness, much as LRU only approximates the unrealizable optimal page-replacement. Second, CFS is for ordinary tasks; Linux runs genuine real-time tasks (your EDF and fixed-priority deadline work) on entirely SEPARATE scheduling classes that always outrank CFS. And in fact Linux has since been moving its default to a newer scheduler called EEVDF — a reminder that even shipping schedulers keep evolving.
The whole rung, in one picture
Step back and the five guides form one arc. You started by asking why we schedule at all — because a process alternates between bursts of computing and waiting on I/O, so the CPU is free far more often than you would think, and a scheduler decides who fills the gap. Then came the family of algorithms, each fixing the last one's flaw: FCFS is fair but suffers the convoy effect; SJF is optimal for waiting time but needs a crystal ball and can starve big jobs; round robin guarantees responsiveness but its time quantum must be tuned just right; priorities risk starvation until aging rescues the forgotten.
This final guide lifted all of that into the real world. The classic algorithms optimise an average; real-time scheduling demands a proof about the worst case; multicore scheduling fights to keep many cores busy without losing cache warmth; and a real kernel like Linux blends these ideas — fairness for normal work via virtual runtime, separate strict classes for deadlines, careful migration that respects affinity. No single algorithm wins everywhere, which is the deepest lesson of the whole rung: scheduling is not about finding the one best policy, but about knowing which trade-off your particular machine and workload actually need.