CFS performance improvement using Binomial Heap

Process scheduling algorithm plays a crucial role in operating system performance and so does the data-structure used for its implementation. A scheduler is designed to ensure the distribution of resources among the tasks is fair along with maximization of CPU utilization. The Completely Fair Scheduler (CFS), the default scheduler of Linux (since kernel version 2.6.23), ensures equal opportunity among tasks. In this paper we discuss the CFS and propose an improved performance implementation using Binomial Heap as a replacement for Red-Black Tree. Preliminary results with simulation on C are very promising and show about 3 times improvement for insert operations.