CFS CPU Time Allocation and Virtual Runtime

Introduction

In our last lesson, we explored the full lifecycle of a Linux process, from its creation via fork() and transformation with execve(), to its termination with exit(). We saw how a process can be in the TASK_RUNNING state, making it eligible for CPU time. On a typical system, there are dozens, if not hundreds, of these runnable tasks. This raises a fundamental question: how does the kernel decide which task gets to run next, and for how long?

This is the job of the CPU scheduler. Today, we'll dive into the default scheduler for normal tasks in Linux, the Completely Fair Scheduler (CFS). Our learning outcome is to describe how CFS allocates CPU time using virtual runtime. We will dissect its core principle of "ideal fairness" and the clever mechanism—virtual runtime—that the kernel uses to approximate this ideal on real hardware. This is a cornerstone of kernel performance and a frequent topic in advanced technical interviews.

1. The Goal: Ideal Fairness

Before diving into the implementation, let's understand the philosophy behind CFS. Its goal is to be "completely fair." But what does that mean?

Imagine an ideal, hypothetical CPU that could run all runnable tasks simultaneously, each getting an equal fraction of the processor's power. If you have 2 tasks, each runs at 50% speed. If you have 10 tasks, each runs at 10% speed. On this ideal CPU, all tasks would get a perfectly fair share of the processing power.

Of course, real CPUs can only execute one instruction stream at a time per core. The central idea of CFS is to model this "ideal multitasking CPU" on real hardware.

#210 Linux Kernel Scheduler Developer | David Vernet

To begin, let's hear from a Linux kernel scheduler developer, David Vernet. He provides a concise, high-level overview of the scheduler's purpose and introduces the core concepts of fairness and virtual runtime.

Watch from 03:28 to 06:33. As you watch, focus on: The fundamental problem the scheduler solves (finite cores, many tasks). The definition of fairness as giving each task its 'fair slice' of the CPU. The introduction of 'vruntime' (virtual runtime) as the mechanism to track which task has run the least and should run next.

The key takeaway is that CFS's main principle is to always run the task that has run the least so far. To track this, it uses a special accounting variable.

2. Virtual Runtime (vruntime)

The mechanism CFS uses to track how much time a task has been allowed to run is called virtual runtime, or vruntime. You can think of it as a task's "fairness odometer." Unlike a real-world clock that ticks at a constant rate for everyone, a task's vruntime clock ticks at a rate proportional to its priority.

CFS Scheduler - The Linux Kernel documentation

The official kernel documentation gives the most precise definition of this concept. Let's read the introduction to the CFS design document.

Read sections 1 ('OVERVIEW') and 2 ('FEW IMPLEMENTATION DETAILS'). Pay close attention to how it defines the 'ideal, precise multi-tasking CPU' and how p->se.vruntime is used to model it.

As the documentation states, CFS always picks the task with the smallest vruntime. This is the core of the algorithm.

But how is vruntime calculated? It's not simply the nanoseconds a task has spent on the CPU. This is where priorities, or nice values, come into play.

A task's vruntime accumulates based on its actual runtime, but it's weighted. A higher-priority task (with a lower nice value) accumulates vruntime more slowly than a lower-priority task (with a higher nice value). Because the scheduler always picks the task with the lowest vruntime, the higher-priority task gets to run more often or for longer, as it takes more physical time for its vruntime to catch up to others.

The formula for updating vruntime is:

vruntime + = Δ t_{exec} \times (\frac{weight _{nice 0}}{weight _{task}})

Where:

$Δ t_{exec}$ is the actual time the task just spent on the CPU.
$weight_{nice 0}$ is the weight corresponding to a default-priority task (nice value of 0). This is a baseline weight, defined in the kernel as 1024.
$weight_{task}$ is the weight of the current task, derived from its nice value.

This formula shows that for a nice 0 task, the weight ratio is 1, so vruntime increases at the same rate as actual time. For a high-priority task (e.g., nice -10), its weight is much larger than 1024, making the ratio less than 1, so its vruntime grows slowly. For a low-priority task (e.g., nice +10), its weight is smaller than 1024, making the ratio greater than 1, so its vruntime grows quickly.

3. The Red-Black Tree: Finding the "Next" Task

The scheduler needs an efficient way to find the task with the minimum vruntime among all runnable tasks. A simple linked list would be too slow to search and sort, especially with many tasks.

CFS solves this by organizing all runnable tasks in a red-black tree, a type of self-balancing binary search tree. The tree is ordered by vruntime.

Linux CFS Data Structures and Red-Black Tree — This diagram illustrates the relationship between key kernel data structures. Each `task_struct` contains a `sched_entity`. This entity includes an `rb_node`, which is what allows the task to be inserted into the CFS runqueue's red-black tree (`tasks_timeline`), ordered by `vruntime`.

Here's how it works:

Finding the next task: The task with the lowest vruntime is always the leftmost node in the tree. Finding it is an extremely fast operation.
Running a task: The scheduler picks this leftmost task and lets it run for a time slice.
Updating the tree: After the task runs, its vruntime is updated. It is then re-inserted into the red-black tree at a new position corresponding to its new vruntime. Since its vruntime has increased, it will be placed further to the right in the tree.

This process ensures that over time, every task gets a chance to become the "leftmost" node and execute on the CPU.

#23 Completely Fair Scheduling | Introduction to Operating Systems

This video provides a clear, academic explanation of the red-black tree's role in CFS.

Watch from 06:49 to 10:24. The video explains: How tasks are stored in the red-black tree, ordered by vruntime. How the scheduler efficiently picks the leftmost node. The lifecycle of a task moving from the left side of the tree to the right as it executes and its vruntime increases.

4. A Worked Example

Let's solidify this with a concrete example, similar to one you might be asked to walk through in an interview.

Consider two CPU-bound tasks:

Task A: nice = 0 (weight = 1024)
Task B: nice = 5 (weight = 335)

The scheduler aims to give every task a chance to run within a target latency period (e.g., sched_latency = 6ms). The time slice for each task is proportional to its weight.

Total weight = 1024 + 335 = 1359
Task A's slice = $6 ms \times \frac{1024}{1359} \approx 4.52 ms$
Task B's slice = $6 ms \times \frac{335}{1359} \approx 1.48 ms$

Now let's trace their vruntime values. Assume both start at vruntime = 0.

Step	Runs	Duration	$Δ v_{A}$	$Δ v_{B}$	$v_{A}$	$v_{B}$	Next to Run (min vruntime)
0	-	-	-	-	0	0	A (higher weight breaks tie)
1	A	4.52ms	4.52	0	4.52	0	B (0 < 4.52)
2	B	1.48ms	0	4.53	4.52	4.53	A (4.52 < 4.53)
3	A	4.52ms	4.52	0	9.04	4.53	B (4.53 < 9.04)
4	B	1.48ms	0	4.53	9.04	9.06	A (9.04 < 9.06)

vruntime calculation check:

For Task A (nice 0), $Δ v_{A} = 4.52 ms \times \frac{1024}{1024} = 4.52$ .
For Task B (nice 5), $Δ v_{B} = 1.48 ms \times \frac{1024}{335} \approx 1.48 \times 3.06 \approx 4.53$ .

Notice the magic here: even though the tasks ran for different amounts of physical time (4.52ms vs 1.48ms), their virtual runtime increased by almost the exact same amount. CFS's goal is to keep the vruntime of all tasks in the system as close as possible. This is the definition of "fair."

[PDF] (Advanced) Linux Kernel Programming - Lecture 07: CPU ...

The following slides provide a very dense and useful reference for these calculations, including the weight tables.

Review slides 18, 19, 22, and 41. You don't need to memorize the entire weight table, but focus on: Slide 18/19: The worked example we just discussed. Slide 22: The direct comparison of Linux's vruntime to the theoretical concept of Stride Scheduling. Slide 41: How nice values map to weights, and the rationale for the geometric mapping (each nice step has a proportional effect on CPU share).

5. Interview Scenario

Your ability to articulate this mechanism clearly is key for a senior role interview.

Question: "Imagine you have two identical, CPU-bound processes. You use the renice command to change the priority of one of them to +10. Walk me through how the Linux CFS scheduler will now give that process less CPU time than its counterpart. Mention the specific data structures and values involved."

Your Thought Process & Answer:

Initial State: Before renice, both processes have the same nice value (default 0), and thus the same weight. CFS gives them roughly equal CPU time because their vruntime increases at the same rate.
Effect of renice: Changing the nice value to +10 assigns the process a much smaller weight from the kernel's prio_to_weight table.
Core Mechanism - vruntime: The core of the answer lies in the vruntime update formula: $vruntime + = Δ t_{exec} \times (weight_{nice 0} / weight_{task})$ .
Connecting the dots: For the nice +10 process, its weight_task is now low. This makes the fraction (weight_nice 0 / weight_task) significantly greater than 1. Consequently, for every nanosecond of physical time it runs, its vruntime increases much faster than the nice 0 process.
Scheduler Action: The CFS scheduler always maintains all runnable tasks in a red-black tree, ordered by vruntime. It always picks the task with the lowest vruntime (the leftmost node) to run next.
Putting it together: Because the nice +10 process's vruntime accumulates so quickly, it will very rapidly cease to be the task with the minimum vruntime. The nice 0 process's vruntime will be lower for longer periods, so the scheduler will consistently pick it more often. The result is that the nice +10 process gets significantly less CPU time, achieving the desired priority behavior in a fair and predictable way.

Conclusion

Today we've unpacked the core logic of the Completely Fair Scheduler. You've learned that its simple-sounding goal—to give every task a fair share of the CPU—is implemented through an elegant and powerful mechanism.

Key Takeaways:

Goal: CFS models an "ideal, precise multi-tasking CPU" where all tasks run in parallel at a reduced speed.
Mechanism: It achieves this by tracking a task's virtual runtime (vruntime), which is its actual runtime weighted by its priority (nice value).
Formula: vruntime for high-priority (low nice) tasks accumulates slowly, while for low-priority (high nice) tasks it accumulates quickly.
Algorithm: CFS always picks the runnable task with the smallest vruntime to execute next.
Data Structure: It uses a red-black tree to efficiently store runnable tasks and find the one with the minimum vruntime.

CFS is designed for general-purpose workloads, balancing throughput and interactivity. However, some tasks, like in an automotive ECU or a high-frequency trading system, have strict, unyielding deadlines. For these, fairness is not the goal; meeting deadlines is.

In our next lesson, we will compare CFS with real-time scheduling policies (SCHED_FIFO, SCHED_RR) to understand how Linux handles these critical, time-sensitive applications.

Recommended resources