Completely Fair Scheduler

The Completely Fair Scheduler (CFS) is the default process scheduler in the Linux kernel, introduced by Ingo Molnar in 2007 as a replacement for the O(1) scheduler. CFS abandons the traditional priority-queue and time-slice approaches in favor of a red-black tree that tracks the virtual runtime (vruntime) of each task. The core idea is elegant: the task with the smallest vruntime always runs next, and the scheduler continuously rebalances the tree to maintain this invariant.

Virtual runtime is a weighted measure of CPU time consumed, adjusted by a task's priority. A high-priority task accumulates vruntime more slowly than a low-priority task, meaning it gets scheduled more frequently. This produces a mathematically fair distribution of CPU time: over any sufficiently long interval, each task receives a share of the processor proportional to its weight. The fairness is not approximate; it is encoded in the data structure itself.

CFS represents a shift from heuristic scheduling to algorithmic scheduling. The O(1) scheduler used fixed time slices and priority arrays; CFS uses a continuous, self-balancing metric. This shift mirrors a broader trend in systems design: the replacement of hand-tuned parameters with principled mathematical structures. But the fairness CFS guarantees is local — it ensures fairness among tasks on a single CPU. It says nothing about fairness across NUMA nodes, nothing about I/O-bound versus CPU-bound tasks, and nothing about real-time deadlines. The "complete" in its name is an aspiration, not a description.