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

I decided to write this article as to give a short intro, which I hope would help one another to dive into understanding but more tweaking the I/O scheduler for better computing performance. So what is the I/O scheduler… Talking about the I/O scheduler requires to immediately address the issue of I/O process execution on a system. Each action made by an application whether in a simple read/write manner, memory allocation in a nutshell creates an I/O request to the filesystem/virtual memory, which in return transmit the requests to the scheduler, who handles it back to the low-level device drivers… ... Read more