the Completely Fair Scheduler (CFS) and EEVDF
/ see-eff-ess /
How should a scheduler divide CPU time among many tasks fairly? One natural idea: imagine an ideal machine that could run all N runnable tasks literally at once, each getting exactly 1/N of the CPU's speed. No real CPU can do that, but you can approximate it: track how much CPU time each task has actually received, and always run next whichever task has fallen furthest behind its fair share. That is the idea behind Linux's Completely Fair Scheduler (CFS), which served as Linux's default process scheduler for over fifteen years.
Concretely, CFS gave each task a virtual runtime - roughly, how much CPU time it has consumed, weighted by its priority (a higher-priority/lower-nice task accumulates virtual runtime more slowly, so it is allowed to run more). The scheduler keeps runnable tasks ordered by virtual runtime in a self-balancing tree (a red-black tree) and always picks the task with the smallest virtual runtime - the one most starved relative to its weight - to run next. As that task runs, its virtual runtime climbs, and eventually another task becomes the most-behind and gets its turn. This naturally hands more CPU to tasks that have had less, without fixed time slices for every task. In 2023 Linux replaced CFS's core with EEVDF (Earliest Eligible Virtual Deadline First), which keeps the fairness idea but adds an explicit notion of latency/deadline so it can better serve tasks that need to respond quickly.
Two things worth holding onto. First, 'fair' here is weighted fairness, not identical time for everyone - priority (nice) tilts each task's share, so a high-priority task fairly gets more, not an equal slice. Second, CFS and EEVDF are one scheduling class among several: the kernel runs real-time scheduling classes (for tasks with strict timing needs) at strictly higher priority than the normal/fair class, so 'completely fair' describes how ordinary tasks share leftover CPU, after real-time tasks have taken what they need. The lesson is that even an elegant fairness algorithm is a deliberate trade-off, layered with other policies for different kinds of work.
CFS picks the runnable task with the smallest virtual runtime (most behind its weighted fair share); running it raises its vruntime until another task becomes the most-behind. EEVDF (2023+) adds a deadline so latency-sensitive tasks respond sooner.
Always run the most-behind task; its virtual runtime then rises and another takes its place. EEVDF adds explicit deadlines.
'Completely fair' means weighted fairness, not equal time - priority/nice deliberately skews each task's share. And fair scheduling is just one scheduling class: real-time classes run at strictly higher priority, so CFS/EEVDF governs how normal tasks split whatever CPU is left after real-time work.