Reason why CFS scheduler using red black tree?

Question

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?

Answer 1

The reason is: Heaps are array based and hence require contiguous memory in kernel space. This is because the way heaps are implemented in Linux. See the files lib/prio_heap.c and include/linux/prio_heap.h and you'll note that heap is kmalloc'd using heap_init. Once the multi-programming space becomes huge, maintaining thousands of struct sched_entity requires lot of contiguous space (it runs in several pages). From time and performance point of view, one would prefer heap as hepify operation can run in background once min vruntime is picked but it's space requirement which makes bottleneck.

As rbtree is readily available, kernel developers didn't think of implementing pointer based heap, in fact one doesn't need.