How CFS Works: Virtual Runtime (vruntime)

The Scorekeeper

To track fairness, CFS keeps a score for every runnable process called vruntime (virtual runtime). Think of it as a stopwatch measuring how much CPU time a process has consumed, adjusted for its priority weight.

The rule of CFS is simple: the process with the lowest vruntime gets to run next.

Here is the cycle:

1. The process with the lowest vruntime is selected and placed on the CPU.
2. While it runs, its vruntime ticks upward.
3. Eventually, its vruntime exceeds that of another waiting process.
4. The scheduler preempts the running process and selects the new lowest-vruntime process.

Priority and Nice Values
CFS is not purely equal — it is weighted fair. A process's nice value (ranging from -20 to +19, default 0) determines how fast its vruntime accumulates. A process with a lower nice value (higher priority, e.g., nice = -10) has its vruntime tick up more slowly than a process with a higher nice value (lower priority, e.g., nice = +10). This means the high-priority process stays near the front of the queue longer and gets proportionally more CPU time — without ever completely starving lower-priority processes.

The Red-Black Tree
To find the lowest vruntime process in O(log n) time, CFS stores all runnable processes in a Red-Black Tree — a self-balancing binary search tree. The process with the lowest vruntime is always the leftmost node. Picking the next task is nearly instantaneous: the scheduler simply grabs the leftmost node. When a process is preempted, it is re-inserted into the tree at its new vruntime position.

The Scheduling Period
CFS does not switch processes after a fixed time slice. Instead, it targets a scheduling latency (also called the scheduling period) — a configurable window (default ~6ms on modern kernels) within which every runnable process should get at least one turn. If there are 10 runnable processes, each gets roughly 0.6ms per period. If there are 2, each gets ~3ms. This is why adding more runnable processes to a system increases context-switch frequency and can degrade throughput.