From mboxrd@z Thu Jan 1 00:00:00 1970 From: der.herr@hofr.at (Nicholas Mc Guire) Date: Sun, 18 Oct 2015 06:55:19 +0000 Subject: Why Completely Fair Scheduler(CFS) using Red-Black tree instead of Min-heap? In-Reply-To: References: Message-ID: <20151018065519.GC27232@osadl.at> To: kernelnewbies@lists.kernelnewbies.org List-Id: kernelnewbies.lists.kernelnewbies.org 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