the Completely Fair Scheduler
/ CFS /
Imagine a perfectly fair parent dividing attention among several children: ideally each child would get an exactly equal share at every instant. You cannot literally split yourself, but you can keep careful track of who has had the least attention so far and always turn to that child next. The Completely Fair Scheduler (CFS), the long-time default in the Linux kernel, runs the CPU on exactly this principle — give the CPU next to whoever has gotten the least so far.
How it works: CFS gives every runnable task a number called its virtual runtime — roughly, how much CPU time it has used, but weighted by priority so a higher-priority (lower nice value) task accumulates virtual runtime more slowly and thus is favored. Instead of fixed time slices, CFS always picks the runnable task with the smallest virtual runtime to run next, then lets it run until its virtual runtime catches up to the others. To find that minimum quickly even with many tasks, CFS keeps the tasks ordered by virtual runtime in a balanced binary tree (a red-black tree), so picking the next task is fast. The result approximates an idealized processor that runs all tasks simultaneously at fractional speed, sharing time in proportion to weight.
Why it matters and the honest details: CFS shows how the classical ideas in this field — fairness, priorities, response time, multicore balancing — come together in a real, widely deployed system rather than a textbook example. It is not flawless or eternal: tuning interactivity, group scheduling (sharing fairly between users or containers via control groups), and multicore load balancing add real complexity, and in fact recent Linux kernels have begun moving to a newer scheduler (EEVDF) that refines the same fairness goal. CFS is best understood as one concrete, influential answer to the central question of this whole field — how to share one processor fairly and efficiently.
Three equal-priority tasks A, B, C start with virtual runtime 0. CFS runs A; A's virtual runtime grows, so now B and C are smaller and one of them runs next. Over time all three accumulate virtual runtime at the same rate, so each ends up with about a third of the CPU. Give A a higher priority and its virtual runtime grows more slowly, so it gets a larger share.
CFS always runs the task with the least virtual runtime, approximating perfectly fair sharing weighted by priority.
CFS is not a real-time scheduler — completely fair sharing is the opposite of meeting hard deadlines, so Linux runs real-time tasks under separate policies. Also, recent Linux versions are replacing CFS with EEVDF, so completely fair is a snapshot, not the final word.