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