What is the Completely Fair Scheduler (CFS)?
Learn how the Linux Completely Fair Scheduler works — vruntime, the red-black tree, and nice values — with an interview question answered.
Expected Interview Answer
The Completely Fair Scheduler (CFS) is the default Linux process scheduler that tracks each runnable task’s virtual runtime and always picks the task with the least accumulated virtual runtime to run next, approximating an ideal system where every task gets a perfectly equal, continuous share of the CPU.
CFS maintains runnable tasks in a red-black tree keyed by virtual runtime (vruntime), a measure of how much CPU time a task has consumed, weighted by its nice value so higher-priority tasks accumulate vruntime more slowly. The scheduler always dispatches the leftmost node in the tree, meaning the task with the smallest vruntime so far — the one that has, proportionally, received the least CPU time. As that task runs, its vruntime increases, and once it exceeds another task’s vruntime, that other task becomes the new leftmost node and gets scheduled next, which naturally interleaves tasks in proportion to their weight without needing fixed time quanta or discrete priority queues. Nice values (from -20 to 19) scale the weight applied to vruntime accumulation, so a higher-priority task’s vruntime grows more slowly relative to a lower-priority one’s, giving it a proportionally larger CPU share, and CFS uses an adaptive scheduling latency target combined with a minimum granularity to decide how often it re-evaluates rather than a fixed time-slice per task.
- Approximates perfectly fair, proportional CPU sharing in O(log n) via a red-black tree
- No fixed time quantum — scheduling decisions scale with the number of runnable tasks
- Nice values smoothly scale CPU share instead of using rigid priority queues
- Default scheduler for normal (non-real-time) tasks in the Linux kernel
AI Mentor Explanation
CFS is like a nets facility that tracks each batter’s total minutes of practice so far and always calls up whichever batter has had the least practice time relative to their assigned weighting. A batter who has barely practiced gets called next, and as soon as they start batting their tallied minutes rise until someone else has a lower tally, at which point that batter is called instead. A senior batter with a higher weighting accumulates tracked minutes more slowly per minute actually spent, so they end up getting a proportionally larger share of net time over the session, all without anyone assigning fixed turn lengths.
Step-by-Step Explanation
Step 1
Track vruntime
Each runnable task accumulates virtual runtime, weighted by its nice value, as it consumes CPU time.
Step 2
Maintain the tree
Runnable tasks are kept in a red-black tree ordered by vruntime, so the smallest-vruntime task is always the leftmost node.
Step 3
Pick the leftmost task
The scheduler dispatches the leftmost (least-vruntime) task, giving it CPU time next.
Step 4
Re-evaluate
As the running task’s vruntime grows past another task’s, that other task becomes leftmost and is scheduled in, bounded by the scheduling latency target and minimum granularity.
What Interviewer Expects
- Understanding of vruntime as the core fairness metric
- Knowledge that CFS uses a red-black tree keyed by vruntime, not fixed queues
- Explanation of how nice values scale vruntime accumulation to change CPU share
- Awareness that CFS is the default Linux scheduler for normal (non-real-time) tasks
Common Mistakes
- Confusing CFS with round robin (CFS has no fixed time quantum per task)
- Thinking nice values map to fixed priority queues rather than vruntime weighting
- Forgetting that CFS picks the leftmost (smallest vruntime) node, not a random or FIFO choice
- Not knowing CFS is specific to normal Linux scheduling, separate from real-time scheduling classes
Best Answer (HR Friendly)
“The Completely Fair Scheduler is the default Linux scheduler, and its core idea is tracking how much CPU time each task has effectively received so far, then always running whichever task has received the least. It uses an efficient tree structure to always find that task quickly, and it lets you weight tasks so some get proportionally more CPU without needing rigid, fixed time slices.”
Code Example
struct task {
long vruntime; /* weighted accumulated CPU time */
int weight; /* derived from the task’s nice value */
struct task *left, *right; /* conceptual red-black tree links */
};
void update_vruntime(struct task *t, long time_ran) {
/* higher weight (higher priority) accumulates vruntime more slowly */
t->vruntime += (time_ran * NICE_0_WEIGHT) / t->weight;
}
struct task *pick_next(struct task *tree_root) {
struct task *node = tree_root;
while (node->left != NULL) {
node = node->left; /* leftmost node has the smallest vruntime */
}
return node;
}Follow-up Questions
- How does a nice value affect a task’s vruntime accumulation rate?
- Why does CFS use a red-black tree instead of a simple sorted list?
- What is scheduling latency and minimum granularity in CFS?
- How does CFS differ from Linux’s real-time scheduling classes like SCHED_FIFO?
MCQ Practice
1. What does CFS use to decide which task runs next?
CFS always dispatches the runnable task with the least vruntime so far, approximating perfectly fair proportional CPU sharing.
2. What data structure does CFS use to track runnable tasks?
CFS keeps runnable tasks in a red-black tree ordered by vruntime, letting it find the least-vruntime task in O(log n).
3. How does a lower nice value (higher priority) affect a task in CFS?
A higher-priority (lower nice value) task’s vruntime accumulates more slowly relative to CPU time consumed, so it ends up with a proportionally larger CPU share.
Flash Cards
What is CFS? — The default Linux scheduler for normal tasks, which always runs the runnable task with the smallest accumulated vruntime.
What data structure backs CFS? — A red-black tree keyed by vruntime, giving O(log n) selection of the next task.
How do nice values affect CFS? — They scale how fast a task’s vruntime grows, changing its proportional CPU share.
Does CFS use fixed time quanta? — No — it uses an adaptive scheduling latency target and minimum granularity instead of per-task fixed slices.