Completely Fair Scheduler

The Completely Fair Scheduler (CFS) was a process scheduler that was merged into the 2.6.23 (October 2007) release of the Linux kernel. It was the default scheduler of the tasks of the SCHED_NORMAL class (i.e., tasks that have no real-time execution constraints) and handled CPU resource allocation for executing processes, aiming to maximize overall CPU utilization while also maximizing interactive performance.

In contrast to the previous O(1) scheduler used in older Linux 2.6 kernels, which maintained and switched run queues of active and expired tasks, the CFS scheduler implementation is based on per-CPU run queues, whose nodes are time-ordered schedulable entities that are kept sorted by red–black trees. The CFS does away with the old notion of per-priorities fixed time-slices, and instead it aims at giving a fair share of CPU time to tasks (or, better, schedulable entities).

Starting from version 6.6 of the Linux kernel, it was replaced by the EEVDF scheduler.

Algorithm

A task (i.e., a synonym for thread) is the minimal entity that Linux can schedule. However, it can also manage groups of threads, whole multi-threaded processes, and even all the processes of a given user. This design leads to the concept of schedulable entities, where tasks are grouped and managed by the scheduler as a whole. For this design to work, each task_struct task descriptor embeds a field of type sched_entity that represents the set of entities the task belongs to.