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 _______________________________________________ Kernelnewbies mailing list Kernelnewbies@xxxxxxxxxxxxxxxxx http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
