Completely Fair Scheduler

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).

Each per-CPU run-queue of type cfs_rq sorts sched_entity structures in a time-ordered fashion into a red-black tree (or 'rbtree' in Linux lingo), where the leftmost node is occupied by the entity that has received the least slice of execution time (which is saved in the vruntime field of the entity).

The complexity of the algorithm that inserts nodes into the cfs_rq runqueue of the CFS scheduler is O(log N), where N is the total number of entities.

[4] CFS is an implementation of a well-studied, classic scheduling algorithm called weighted fair queuing.

CFS is the first implementation of a fair queuing process scheduler widely used in a general-purpose operating system.

Developed by Mike Galbraith using ideas suggested by Linus Torvalds, the patch implements a feature called auto-grouping that significantly boosts interactive desktop performance.