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

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

[venu gangireddy]

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
min-heap is not consider in CFS implementation and is there any
difficulties using min-heap in kernel level?

Thanks in advance.

-- 

*Regards,*
*Venugopal Reddy.*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.kernelnewbies.org/pipermail/kernelnewbies/attachments/20151017/ed7f3ade/attachment.html 

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

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

[anish singh]

On Sat, Oct 17, 2015 at 11:25 AM, venu gangireddy <venu.gangireddy@gmail.com
> 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.
>
> Nice.

> 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
> min-heap is not consider in CFS implementation and is there any
> difficulties using min-heap in kernel level?
>

I am not an expert in algorithms, but it seems that after o(1) peek you
should perform heapify (which is o(log n)) to restore heap property. So
give the reference to the implementation you talking about if I am wrong.

>
>
> Thanks in advance.
>
> --
>
> *Regards,*
> *Venugopal Reddy.*
>
> _______________________________________________
> Kernelnewbies mailing list
> Kernelnewbies at kernelnewbies.org
> http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.kernelnewbies.org/pipermail/kernelnewbies/attachments/20151018/1696f7c1/attachment.html