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 a process goes to sleep (say, waiting on an I/O to complete, or for a network packet to arrive), it is removed from the tree and kept track of elsewhere.

Example

Let’s look at an example to make this more clear. Assume there are ten jobs, and that they ...