February 4, 2012

Linux CFS Algorithm and Virtual Runtime

Since the 2.6.23 kernel, the Linux kernel process scheduler previously O(1) was replaced by CFS - a Completely Fair Scheduler. CFS uses a red-black tree as data-structure and unlike previous Unix process scheduler does not account a traditional time slice of process execution but accounts what is referred as the process virtual runtime, expressed in nanoseconds (as opposed to Hz or jiffies). The usage of a self-balanced tree as the red-black tree allows for a lookup of $$O(\log\ n)$$ time per the height of the tree, but more on this later. ... Read more