Why Completely Fair Scheduler(CFS) using Red-Black tree instead of Min-heap?

[Nicholas Mc Guire]

On Sat, Oct 17, 2015 at 11:55:29PM +0530, venu gangireddy wrote:
> Hi,
> 
> Currently, I am learning about CFS scheduler in linux, and I want to know
> reason about the data structure chooses in CFS implementation.
> 
> CFS scheduler picks next process based on minimum virtual time and to get
> this value efficiently its using Red-Black tree(rbtree), using rbtree we
> will get minimum O(h) here h is height of rbtree. But, using min-heap we
> can get min virtual time process in O(1) time only. I just want to know why

hmm... min heap insertion/deletion is O(log N) as you may have to swap up to
log N elements in the tree.

> min-heap is not consider in CFS implementation and is there any
> difficulties using min-heap in kernel level?
>
I don't think there is any fundamental obstacle to use min-heap
but the advantage is not clear to me - a rbtree is self-balancing so
search will stay O(log N) while in non-balanced trees it can
degenerate to O(n). If you always only need min/max then min-heap
could have an advantage - but if that is actually the
case in the scheduler I don't know. I suspect that the main reason
for rbtrees is simply that they have a constant cost for all of 
the operations which reduces strange corner-case behavior.

thx!
hofrat