Linux CFS: Scheduling by Virtual Runtime
How Linux shares CPU fairly with virtual runtime: always run the task that has had the least. A simulation gives equal tasks 34, 33 and 33 ms, and nice values shift the split to 69%, 23% and 8%.
The Linux Completely Fair Scheduler always runs the runnable task with the smallest virtual runtime, which grows as a task runs, scaled by 1024 divided by its weight. Interviewers expect the data structure: tasks sit in a red-black tree ordered by vruntime, and the leftmost node runs next. Lower nice values mean larger weight and a larger CPU share.
The Completely Fair Scheduler gives each runnable task a virtual runtime that grows as it runs, scaled by weight, and always runs the task with the smallest value. Equal-priority tasks end up with equal shares, and a lower nice value earns a larger share. Newer kernels replace CFS with EEVDF, which keeps the same fairness idea.
- Under CFS, a task's vruntime grows by t x (1024 / weight) while it runs, and the runnable task with the smallest vruntime is scheduled next.
- In the Linux weight table, nice 0 has weight 1024, nice 5 has weight 335 and nice -5 has weight 3121.
- CFS keeps runnable tasks in a red-black tree ordered by vruntime; the leftmost node is found in O(1) with a cached pointer, and reinsertion costs O(log n).
- A 100 ms CFS simulation gave three nice-0 tasks 34, 33 and 33 ms, and tasks at nice 0, 5 and -5 got 23%, 8% and 69% of the CPU.
- CFS does not starve low-priority tasks: the nice 5 task in the simulation still ran 8% of the time, unlike strict priority scheduling.
- Since Linux 6.6 the default fair scheduler is EEVDF, which keeps virtual-time fairness but picks among eligible tasks by earliest virtual deadline.
01The idea: an ideal fair CPU
Classic schedulers use time slices and priority queues. CFS, which Linux used from 2007, starts from a different picture: an ideal processor that runs all N tasks at the same moment, each at 1/N speed. A real CPU cannot do that, so CFS approximates it by tracking how far each task is behind its fair share and always running the one that is furthest behind.
There are no fixed time slices to tune. A task runs until it is no longer the most deserving one or until a minimum granularity passes, whichever the scheduler decides.
02Virtual runtime
Every task has a vruntime. While a task runs for a time t, its vruntime increases by t x (1024 / weight). Weight comes from the nice value: nice 0 has weight 1024, nice 5 has 335, nice -5 has 3121 (values from the kernel's weight table). A heavy task's vruntime grows more slowly, so it stays the smallest for longer and gets more CPU.
The runnable tasks sit in a red-black tree ordered by vruntime. The scheduler picks the leftmost node, the smallest vruntime. Finding it is O(1) with a cached pointer, and inserting a task back is O(log n).
03A simulation with equal tasks
import heapq
W = {-5: 3121, 0: 1024, 5: 335} # nice -> weight
def cfs(tasks, total_ms=100):
ran = {n: 0 for n in tasks}
h = [(0.0, n) for n in tasks]
heapq.heapify(h)
for _ in range(total_ms):
v, n = heapq.heappop(h) # smallest vruntime runs
ran[n] += 1
heapq.heappush(h, (v + 1024 / W[tasks[n]], n))
return ran
print(cfs({'A': 0, 'B': 0, 'C': 0}))The result is {'A': 34, 'B': 33, 'C': 33}. Each task ran about a third of the time, and the extra millisecond went to A on a tie. The heap plays the role of the red-black tree. This is a toy: it uses 1 ms ticks, ignores sleeping tasks and multiple cores, and has none of the kernel's minimum-granularity rules.
04Nice values change the share
print(cfs({'A': 0, 'B': 5, 'C': -5}))The output is {'A': 23, 'B': 8, 'C': 69}. The weights are 1024, 335 and 3121, summing to 4480, so the expected shares are 22.9%, 7.5% and 69.7%, which the simulation matches. Even the lowest-priority task, nice 5, still ran 8% of the time. CFS does not starve it; it just gives it a smaller share. That is an important difference from strict priority scheduling, where a low-priority task can wait forever.
05Sleeping tasks and latency
A task that sleeps (waiting for a keypress or network packet) stops accumulating vruntime. If it kept its old tiny value it would, on waking, monopolise the CPU while it caught up. So on wakeup its vruntime is raised to no lower than the queue's minimum vruntime minus a small bonus (a task that slept only briefly keeps its own value). Interactive tasks that mostly sleep therefore get to run soon after waking, which makes them feel responsive, without letting them cheat the system.
The bonus gives a gentle advantage to tasks that use little CPU, which is the right trade for editors, shells and other interactive programs.
06Beyond a single queue, and EEVDF
Linux keeps a separate run queue per CPU and periodically balances load between them, taking cache warmth into account. Control groups let CFS divide the CPU fairly between groups, such as containers, and then between tasks within each group, so one container with many threads cannot crowd out another.
Since Linux 6.6 the default fair scheduler is EEVDF (earliest eligible virtual deadline first), which keeps the virtual-time fairness model but picks among eligible tasks by the earliest deadline. This gives better control over latency than CFS's heuristics. The fairness principle in this article carries over.
07Common interview questions
Q: What does CFS pick to run next?
A: The runnable task with the smallest virtual runtime.
Q: What data structure does it use?
A: A red-black tree ordered by vruntime, with the leftmost node as the next task.
Q: How do nice values work?
A: They map to weights. Higher weight means vruntime grows more slowly, so the task gets a larger CPU share.
Q: Does CFS starve low-priority tasks?
A: No. They get a smaller but nonzero share.
Q: What happens to vruntime when a task sleeps and wakes?
A: It is reset near the queue minimum so it cannot hog the CPU to catch up.
Q: How does this differ from round robin?
A: Round robin gives fixed slices in turn. CFS tracks accumulated runtime and weights, so it gives proportional shares.