linux - Linux 2.6 内部完全公平调度器

Question

我的问题是：在 CFS 中使用红黑树的目的是什么，为什么不能使用 AVL 树。？

score 2 · Accepted Answer

注意：我是从纯算法的角度回答这个问题（在实践中基本搜索树操作的性能），我不知道 Linux 开发人员是否有其他内部原因选择 RB 树（它可能让他们做某些事情 AVL树没有）。

一般来说，两者是可以互换的，就功能而言，它们也可以与基本的搜索树、treaps、splay树等互换。不同之处在于实际性能，因为所有平衡搜索树（AVL 和 RB 树都是平衡的）具有相同的理论性能。

根据两种数据结构（AVL、RB）的 wiki 页面，AVL 树在查询方面表现更好，而在插入和删除方面表现更差。如果您查看一个实现，这很容易注意到：平衡 AVL 树涉及更多，导致实践中的性能较慢。

所以我的猜测是，他们可以使用 AVL 树（除非他们利用结构属性 RB 树有而 AVL 树没有，这是不太可能的），但他们更关心插入和删除性能而不是查询性能，所以他们选择了RB代替。

还值得一提的是，C++、Java 和 .NET 中的许多内置数据结构在其实现中使用红黑树，这可能也是因为它们在所有操作中的性能相似。

score 1 · Accepted Answer

CFS Linux 调度程序实际上使用定制的 RB 树 ( linux/rbtree.h)。但这里的关键是，CFS 基本上想知道接下来要选择哪个任务。这是通过从树中选择最左边的节点来实现的（因为它将是具有较小切片时间的节点）。但是，为方便起见，CFS 使用的 RBT 也有指向此类节点的指针。

在这一点上，您可以说 AVL 树可以以相同的复杂性完成相同的任务。另一方面，在添加或删除任务条目时，您必须重新平衡并遍历 RBT。我知道，在这里，RBT 比 AVL 更适合这项工作。

score 0 · Accepted Answer

由于 RB 树是自平衡的，因此由于树的自平衡特性，树中的任何路径都不会是任何其他路径的两倍，因此，所有操作都是 O (log n)，因此插入和删除树中的任务可以快速高效地完成。

3 回答 3