Completely Fair Scheduler (CFS): How vruntime Lets Long-Running Processes Compete with Newer Ones
Introduction
Imagine your Linux system running dozens of processes simultaneously: a video renderer chugging away in the background, a web browser loading a page, a terminal session compiling code, and a music player streaming your favorite playlist. How does the operating system (OS) decide which process gets CPU time next? The answer lies in the process scheduler—a critical component that ensures fair and efficient distribution of CPU resources.
For decades, Linux relied on schedulers like the O(1) scheduler, which used fixed priority levels and runqueues to manage processes. However, these designs often struggled with fairness: long-running CPU-bound processes (e.g., video renderers) could hog CPU time, while newer or interactive processes (e.g., web browsers) might starve or feel unresponsive.
Enter the Completely Fair Scheduler (CFS), introduced in Linux kernel 2.6.23 (2007). CFS revolutionized process scheduling by prioritizing "fairness"—ensuring each process gets a proportional share of CPU time. At the heart of CFS is a clever concept called vruntime (virtual runtime), which dynamically tracks how much CPU time each process has used (adjusted for priority). This allows CFS to balance long-running processes with newer ones, ensuring no task is starved and responsiveness is maintained.
Note: As of Linux kernel 6.6 (October 2023), CFS has been replaced by the EEVDF (Earliest Eligible Virtual Deadline First) scheduler as the default scheduler for normal tasks. However, understanding CFS remains valuable because EEVDF builds on similar virtual-runtime concepts, and CFS concepts are still widely referenced in Linux documentation and educational materials.
In this blog, we’ll dive deep into CFS, explore how vruntime works, and see why it’s the secret to fair competition between old and new processes.