Completely Fair Scheduling (CFS)
This is what Linux uses for its scheduler.
Resources
The Completely Fair Scheduler (CFS) is the default process scheduler in the Linux kernel, designed to efficiently manage how CPU time is allocated among processes.
CFS operates on the principle of “fairness,” where each process gets a fair share of the CPU based on its weight, which is derived from its priority.
Unlike traditional schedulers that rely on fixed time slices, CFS uses a virtual runtime system to ensure that every process gets a proportional amount of CPU time.
Processes with lower virtual runtimes are prioritized, meaning the scheduler will choose the process that has been executed the least relative to others.
- CFS maintains a red-black tree data structure to organize the processes, enabling efficient insertion, deletion, and selection of tasks with logarithmic complexity.
The central goal of CFS is to ensure that no process starves for CPU time, and it achieves this by trying to approximate an ideal, “fair” multitasking system where all runnable processes get an equal share of CPU resources over time. Processes that use more CPU are given lower priority, while processes that use less CPU are given higher priority in subsequent scheduling decisions. This dynamic behavior helps balance system responsiveness and throughput, making CFS well-suited for modern multitasking systems where a mix of interactive and batch processes needs to be handled smoothly.