Linux's CFS turns fairness into a data structure problem: runnable tasks sit in a red-black tree keyed by vruntime, the leftmost node runs next, and the time slice each task gets scales with its weight. This diagram shows the flow: tasks arrive on per-CPU runqueues, the tree is rebalanced with every insert and removal, preempted and sleeping tasks return to the tree, and load balancing migrates work between CPUs. The ordering matters because it is the entire scheduler: no separate priority queue, no handcrafted timeslicing — just a sorted tree and a rule about who runs longest without running. The done state: each CPU's tree holds exactly the runnable tasks, with the fairest one at the leftmost node.
Scheduler Queue Flow
CFS scheduler queue flow: red-black trees by vruntime, leftmost-node picks, weighted time slices, wakeups, and load balancing.
The Runtime Theory Team07 stages
trace / request.md
readyNew threads, woken tasks, and unblocked processes enter a per-CPU runqueue, each carrying its vruntime — accumulated virtual CPU time — and its weight from the nice value.