为什么CFS调度程序使用红黑树？

Question

CFS调度器根据最小虚拟时间选择下一个进程，为了有效地获取此值，它使用红黑树(rbtree)，使用rbtree可以在O(h)的时间内获得最小值，其中h是rbtree的高度。但是，使用min-heap我们可以仅在O(1)时间内获得最小虚拟时间进程。我想知道为什么CFS实现中没有考虑min-heap，以及在内核级别使用min-heap是否存在任何困难？

- noman pouigt

---

我不是算法专家，但似乎在o(1) peek之后，您应该执行heapify（它是o(log n)）以恢复堆属性。如果我错了，请提供您所说的实现的参考。 - Alex Hoppus

Answer 1

原因是: 堆(heap)基于数组实现，因此需要在内核空间中保留连续的内存。这是由于Linux中堆的实现方式所决定的。请参见文件 lib/prio_heap.c 和 include/linux/prio_heap.h，您将会注意到堆是使用heap_init和kmalloc分配的。一旦多编程空间变得巨大，维护成千上万个struct sched_entity就需要大量的连续空间(它运行在几个页面中)。从时间和性能角度来看，人们更喜欢堆，因为一旦选定最小的vruntime值，堆化操作可以在后台运行，但其空间需求成为瓶颈。

由于红黑树(rbtree)已经广泛应用，内核开发人员并没有考虑实现基于指针的堆，实际上也不需要。

- Vishal Sahu

---

谢谢。这是我找到的唯一一个能够解释红黑树相对于堆优势的说明。其他解释都说它们具有相同的时间复杂度。 - ospider

Answer 2

另一个有趣的点是，如果你有一个任务（进程或线程）从运行状态转换为阻塞状态（等待IO或网络资源），那么你需要将该任务从运行队列中删除，而复杂性如下：

• 对于红黑树，复杂度为O(log(n))
• 对于堆，复杂度为O(n)

堆的删除操作很慢，所以红黑树更好。

而当我们得到最小的虚拟运行时间时，堆操作实际上并不是O(1)，只有在引用根节点而不删除它时才是O(1)。但在CFS中，我们需要

• 删除它（需要O(log(n))的堆化）
• 更新虚拟运行时间，并将其重新插入到运行队列中，这也需要O(log(n))

- Tin Luu

---

真的。这可能是另一个可能的原因！ - Achint Sharma

删除堆节点的时间复杂度为O(log(n))，而不是O(n)。只需将要删除的节点与数组中的最后一个元素交换，删除该元素，然后对交换后的节点进行堆化即可。 - h4x3rotab

删除的问题在于“你如何找到节点？”在堆中，没有内部顺序，这意味着您需要遍历所有节点才能找到它。 - Tin Luu

Answer 3

另外需要补充一点，RBTree在基于virtualruntime更新实体时，会将tree.min值作为CFS调度缓存。这是指具有最小virtualruntime的进程，从而使得挑选下一个进程的结果为O(1)。 pick_next_entity() -> https://github.com/torvalds/linux/blob/9de1f9c8ca5100a02a2e271bdbde36202e251b4b/kernel/sched/fair.c#L4657

pick_next_entity() -> __pick_first_entity() https://github.com/torvalds/linux/blob/9de1f9c8ca5100a02a2e271bdbde36202e251b4b/kernel/sched/fair.c#L639

pick_next_entity() -> __pick_first_entity() -> (root)->rb_leftmost https://github.com/torvalds/linux/blob/3bc1bc0b59d04e997db25b84babf459ca1cd80b7/include/linux/rbtree.h#L106

调度程序可以尝试从树的root中访问缓存值。

- Hrishikesh