Enhancing CFS Scheduler Performance through Binomial Heap Integration

This paper proposes an enhancement to the Completely Fair Scheduler (CFS) in Linux by replacing the Red-Black Tree (RBT) with a Binomial Heap to improve scheduling efficiency. While CFS provides fair CPU time allocation, its reliance on RBT can lead to inefficiencies as the number of tasks grows, particularly in insertion and extraction operations. The Binomial Heap, with its constant time complexity for insertion operation makes it a suitable alternative. Performance evaluations demonstrate that this modification decreases the time required for insertion by up to 50% and for extraction up to 12%. In this paper, this modification is implemented and evaluated demonstrating that the Binomial Heap improves system performance in managing tasks within CFS.