CFS调度器使用红黑树的原因？

Question

CFS 调度程序根据最小虚拟时间选择下一个进程，并使用红黑树（rbtree）有效地获得该值，使用 rbtree 我们将获得最小 O（h），这里 h 是 rbtree 的高度。但是，使用最小堆我们只能在 O(1) 时间内获得最小虚拟时间进程。我只想知道为什么在 CFS 实现中不考虑 min-heap，在内核级别使用 min-heap 有什么困难吗？

Answer 1

原因是：堆是基于数组的，因此需要内核空间中的连续内存。这是因为堆在 Linux 中的实现方式。查看文件lib/prio_heap.c，include/linux/prio_heap.h您会注意到堆正在kmalloc使用heap_init. 一旦多道程序空间变得巨大，维护数千个struct sched_entity需要大量连续空间（它在几页中运行）。从时间和性能的角度来看，人们更喜欢堆，因为一旦选择 min 后 hepify 操作可以在后台运行，vruntime但它的空间要求会造成瓶颈。

正如rbtree现成的那样，内核开发人员没有考虑实现基于指针的堆，实际上不需要。