CFS 调度程序根据最小虚拟时间选择下一个进程，并使用红黑树(rbtree)有效地获取该值，使用 rbtree 我们将获得最小 O(h)，其中 h 是 rbtree 的高度。但是，使用 min-heap 我们只能在 O(1) 时间内获得最小虚拟时间进程。我只是想知道为什么在CFS实现中不考虑min-heap以及在内核级别使用min-heap有什么困难吗？
最佳答案
原因是:堆是基于数组的，因此需要内核空间中的连续内存。这是因为 Linux 中堆的实现方式。请参阅文件lib/prio_heap.c和include/linux/prio_heap.h你会注意到堆是 kmalloc使用heap_init 。一旦多道编程空间变得巨大，需要维护数千个struct sched_entity需要大量连续空间(它在多个页面中运行)。从时间和性能的角度来看，人们更喜欢堆，因为 hepify 操作可以在后台运行一分钟 vruntime已被选中，但空间要求造成了瓶颈。
如rbtree很容易获得，内核开发人员没有想到实现基于指针的堆，事实上也不需要。
关于linux-kernel - 为什么CFS调度器使用红黑树？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33191110/