How the Linux Completely Fair Scheduler Allocates CPU Time

The Completely Fair Scheduler (CFS) is the default process scheduler for normal tasks in the Linux kernel, designed to maximize CPU utilization while ensuring balanced, deterministic access for competing processes. Instead of relying on traditional fixed time slices, CFS models an ideal multi-tasking processor on hardware by tracking the execution time of each task through a metric known as virtual runtime (vruntime). This article breaks down how CFS uses vruntime, process priorities, and red-black trees to allocate CPU time dynamically and equitably.

The Concept of Virtual Runtime

At the core of CFS is vruntime, an individual counter assigned to every runnable task that tracks how much CPU time the task has consumed. In a completely fair system, every runnable process would have an identical vruntime.

When a process executes on the CPU, its physical execution time is scaled and added to its vruntime. The scheduler constantly monitors this metric across all active processes. The process with the lowest vruntime has received the least CPU time relative to its entitlement, making it the highest priority candidate to run next.

Priority and Nice Values

CFS does not bypass process priorities; instead, it scales vruntime accumulation using the standard Linux "nice" level (ranging from -20 to +19).

Each nice level maps to an internal numerical weight:

• High-priority tasks (negative nice values) have larger weights. Their physical execution time is divided by this larger weight, causing their vruntime to increase slowly. Consequently, they remain at the front of the execution queue longer and receive more physical CPU time.
• Low-priority tasks (positive nice values) have smaller weights. Their physical time is divided by a smaller weight, causing their vruntime to advance rapidly. They move to the back of the queue faster, receiving less physical CPU time.

The Red-Black Tree Architecture

To manage tasks efficiently, CFS maintains all runnable processes in a time-ordered red-black tree (a self-balancing binary search tree):

1. Ordering: Tasks are sorted inside the tree based entirely on their vruntime.
2. Task Selection: The task with the smallest vruntime always resides at the leftmost position of the tree. The scheduler simply retrieves this leftmost node (rb_leftmost), an operation that occurs in \(O(1)\) time because the pointer to the leftmost node is cached.
3. Reinsertion: Once a chosen task runs for its allocated slice, its vruntime is updated. If the task is still runnable, it is reinserted into the tree in \(O(\log N)\) time, where \(N\) is the number of runnable tasks.

Dynamic Time Slices and Latency Tuning

CFS dynamically calculates how long a selected process runs using two parameters:

• Target Latency (sysctl_sched_latency): The period of time in which every runnable task should run at least once. The total duration is divided among all active tasks proportionally based on their weights.
• Minimum Granularity (sysctl_sched_min_granularity): To prevent performance degradation from excessive context switching when hundreds of tasks are running, CFS enforces a floor on how small a time slice can be.

If the number of running processes causes the calculated time slice to drop below the minimum granularity, the target latency expands to ensure each process gets a productive execution window.

Handling Sleeping Tasks and New Processes

When a task sleeps (e.g., waiting for I/O), its vruntime remains static while running tasks continue to advance theirs. If an I/O-bound task woke up with its original vruntime, it would monopolize the CPU until it caught up with the others.

To prevent this starvation:

• Waking Tasks: CFS normalizes the vruntime of waking tasks by setting it to a value slightly behind the minimum vruntime present in the tree. This grants the returning task a brief burst of CPU time to remain responsive without starving other workloads.
• New Tasks: Child processes spawned via fork() are initialized with a vruntime relative to their parent or the tree's current baseline, preventing a process from gaining unlimited CPU access by repeatedly creating child tasks.