How is CFS efficient?

Explore how the Completely Fair Scheduler (CFS) achieves efficiency by using red-black trees to manage running processes, ensuring logarithmic time operations. Understand how CFS prevents starvation when jobs wake from sleep and why efficient data structures matter for modern, high-load systems.

We'll cover the following...

- Using red-black trees
  - Example
- Dealing with I/O and sleeping processes
- Other CFS fun

Using red-black trees

One major focus of CFS is efficiency. For a scheduler, there are many facets of efficiency, but one of them is as simple as this: when the scheduler has to find the next job to run, it should do so as quickly as possible. Simple data structures like lists don’t scale: modern systems sometimes are composed of 1000s of processes, and thus searching through a long-list every so many milliseconds is wasteful.

CFS addresses this by keeping processes in a red-black tree“Symmetric binary B-Trees: Data Structure And Maintenance Algorithms” by Rudolf Bayer. Acta Informatica, Volume 1, Number 4, December 1972. A cool balanced tree introduced before you were born (most likely). One of many balanced trees out there; study your algorithms book for more alternatives!. A red-black tree is one of many types of balanced trees; in contrast to a simple binary tree (which can degenerate to list-like performance under worst-case insertion patterns), balanced trees do a little extra work to maintain low depths, and thus ensure that operations are logarithmic (and not linear) in time.

CFS does not keep all processes in this structure; rather, only running (or runnable) processes are kept therein. If ...