Chinaunix

标题: FreeBSD虚存系统splay树的基本原理 [打印本页]

作者: 雨丝风片 时间: 2006-03-15 14:24
标题: FreeBSD虚存系统splay树的基本原理

FreeBSD虚存系统splay树的基本原理

雨丝风片:chinaunix.net

在FreeBSD的虚拟内存系统中，一个虚拟地址空间中的不同区域是由很多的vm_map_entry结构体来描述的，这些vm_map_entry结构体同时按两种方式进行组织，一种是双向链表，一种是splay树。关于splay树的设计原理，请参见原始作者Daniel Dominic Sleator和Robert Endre Tarjan的论文【Self-Adjusting Binary Search Trees】。这里先给出我阅读后的一些笔记和简单的原理图示。由于FreeBSD虚拟内存系统中的splay树的节点是用来存储虚拟地址空间中一段区域的起始和终止地址等其它相关信息的，因此它在原有splay树的基础上进行了一些修改，以更快地满足内存区域匹配的要求。稍后将另写文章，结合FreeBSD6.0的源代码对此加以分析。

FreeBSD虚存系统的相关原理及图示请参见【The Design and Implementation of the FreeBSD Operating System】的第5章。

splay树在二叉查找树中引入了摊平复杂度和自调整的概念。

其它查找树的不足：
1、平衡树：对于一个有n个节点的平衡树，最坏情况下每次查找的时间不会超过O(log n)，但是，如果访问模式不均匀，平衡树的效率就会受到影响。此外，它们还需要额外的空间来存储平衡信息。
2、最优查找树：保证了最小的平均查找时间。但它需要假定查找概率是固定的和已知的，并且访问之间不能有相关性。它们的插入和删除开销都非常高。
3、倾斜查找树：结合了最优查找树的快速平均访问时间和平衡树的快速更新能力，但其结构上的限制更为复杂，和平衡树比起来也更难维护。
4、Finger查找树：可以在一个或多个临近的“手指”中进行快速访问，但需要在每个节点中存储额外的指针。

这些树的设计目标都是减少最坏情况下每次操作的时间，但是查找树的典型应用并不是只查一次就够了，经常是需要执行一系列的查找操作，因此我们应当主要关心这一系列的操作所花费的总体时间，而不只是每次操作单独花费的时间。对于此类应用，更好的目标就是降低操作的摊平时间，此处的摊平时间是指在一系列最坏情况的操作序列中的一次操作的平均时间。

获得摊平效率的一种方法就是使用“自调整”的数据结构。我们允许结构处于任何状态，但在每次操作期间都会应用一个简单的重构规则，以期提高未来操作的效率。其实在其它的数据结构中也有这种通过重构来获得摊平效率的例子，比如线性链表的前移和平衡树上的路径压缩。

和平衡的或是其它对结构有明确限制的数据结构比起来，自调整数据结构有以下几个优点：
1、从摊平角度而言，忽略常量因子，它们绝对不会比有明确限制的数据结构差，而且由于它们可以根据使用情况进行调整，在使用模式不均匀的情况下会更加有效。
2、由于无需存储平衡或者其它的限制信息，它们所需的空间更小。
3、它们的查找和更新算法概念简单，易于实现。

自调整结构有两个潜在的缺点：
1、它们需要更多的局部调整，尤其是在查找期间。（那些有明确限制的数据结构仅需在更新期间进行调整，查找期间则不用）
2、一系列查找操作中的某一个可能会耗时较长，这在实时应用程序中可能是个不足之处。

splay树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。

在二叉查找树中进行查找的方法可以归纳为“自顶向下，左小右大”。

假设我们想要对一个二叉查找树执行一系列的查找操作。为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。我们的目标就是设计一个简单的方法，在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方，因为对于我们的假设来说，这个条目很快就被再次查找的可能性极大。

之前存在两种重构方法：
1、单旋：在查找完位于节点x中的条目i之后，旋转链接x和其父节点的边。（除非x就是树根）
2、搬移至树根：在查找完位于节点x中的条目i之后，旋转链接x和其父节点的边，然后重复这个操作直至x成为树根。

splay树的重构方法和搬移至树根的方法相似，它也会沿着查找路径做自底向上的旋转，将被查找条目移至树根。但不同的是，它的旋转是成对进行的，顺序取决于查找路径的结构。为了在节点x处对树进行splay操作，我们需要重复下面的步骤，直至x成为树根为止：
1、第一种情况：如果x的父节点p(x)是树根，则旋转连接x和p(x)的边。（这种情况是最后一步）
2、第二种情况：如果p(x)不是树根，而且x和p(x)本身都是左孩子或者都是右孩子，，则先旋转连接p(x)和x的祖父节点g(x)的边，然后再旋转连接x和p(x)的边。
3、第三种情况：如果p(x)不是树根，而且x是左孩子，p(x)是右孩子，或者相反，则先旋转连接x和p(x)的边，再旋转连接x和新的p(x)的边。

在节点x处进行splay操作的时间是和查找x所需的时间成比例的。splay操作不单是把x搬移到了树根，而且还把查找路径上的每个节点的深度都大致减掉了一半。这种减半效应使得splay树更有效率，这是其它的简单的重构方法所不具备的特性。

splay树的更新操作：
access(i, t):如果i在树t中，则返回指向它的指针，否则返回空指针。
insert(i, t):将条目i插入树t中（假设其尚不存在）。
delete(i, t):从树t中删除条目i（假设其已经存在）。
join(t1, t2):将树t1和t2合并成一棵树，其中包含之前两棵树的所有条目，并返回合并之后的树。这个操作假设t1中的所有条目都小于t2中的条目，操作完成之后会销毁t1和t2。
split(i, t):构建并返回两棵树t1和t2，其中t1包含t中所有小于等于i的条目，t2包含t中所有大于i的条目。操作完成之后销毁t。

为了实现access(i, t)，我们可以从树t的根部向下查找i。如果查找操作遇到了一个含有i的节点x，我们就在x处进行splay操作，并返回指向x的指针，访问结束。如果遇到了空指针，表示i不在树中，我们就在最后一个非空节点处进行splay操作，然后返回空指针。如果树是空的，我们将忽略掉splay操作。

为了实现join(t1, t2)，我们首先访问t1中最大的条目i。访问结束之后，t1的根节点中包含的就是i，它的右孩子显然为空。我们把t2作为这个根节点的右子树并返回完成之后的新树即可实现join操作。

为了实现split(i, t)，我们首先执行access(i, t)，然后根据新的根节点中的值是大于还是小于等于i来切断这个根节点的左链接或右链接，并返回形成的两棵树。

为了实现insert(i, t)，我们首先执行split(i, t)，然后把t换成一个由新的包含有i的根节点组成的树，这个根节点的左右子树分别是split返回的树t1和t2。

为了实现delete(i, t)，我们首先执行access(i, t)，然后把t换成其左子树和右子树join之后的新树。

下面的实现insert和delete的方法有更好的摊平时间上限：
insert(i, t):查找i，把遇到的空指针替换成一个含有i的新节点，然后再在新节点处对树进行splay操作。
delete(i, t):查找含有i的节点，设此节点为x，其父节点为y。把x的左右子树合并之后替换掉x，然后再从y处进行splay操作。

下面根据作者给出的例程中的数据，画了一些简单的示意图，以期给出一个splay树的形象化说明。（由于FreeBSD根据自己的需要对算法进行了修改，因此这些图并不适于描述FreeBSD虚存系统中splay树的操作过程）

刚开始树中只有一个节点，键值为0。现在向树中添加键值为541的节点。（作者例程中的添加算法基本上可以归纳为上面给出的第二种insert算法，因此会先有一个根据新键值splay的过程，然后才是添加新键值并再次splay的操作）这里由于原先树中只有一个节点，因此插入之前的splay操作不会有任何效果。

插入键值为58的节点：

插入键值为599的节点：

插入键值为116的节点：

插入键值为657的节点：

[ 本帖最后由雨丝风片于 2006-3-15 21:28 编辑 ]

作者: congli 时间: 2006-03-15 14:43
看完了.
兄弟继续!

作者: 雨丝风片 时间: 2006-03-15 14:51

原帖由 congli 于 2006-3-15 14:43 发表
看完了.
兄弟继续!

不公平，偶花了两天时间看完论文等资料，你只花了两分钟，

现在相关代码已经看得差不多了，看完之后就把算法和代码分析写出来，

作者: congli 时间: 2006-03-15 14:56

原帖由 雨丝风片 于 2006-3-15 14:51 发表

不公平，偶花了两天时间看完论文等资料，你只花了两分钟，

现在相关代码已经看得差不多了，看完之后就把算法和代码分析写出来，

呵~是看完,但没看透.所以两天是没白花的!:wink:

作者: 雨丝风片 时间: 2006-03-15 15:03

原帖由 congli 于 2006-3-15 14:56 发表

呵~是看完,但没看透.所以两天是没白花的!:wink:

我也没透，

主要是我这个笔记写得太简单了，只能有一个概念上的了解。你可以去把原文搜下来看看，

事情的起因是由于前两天的一个话题，一直追溯到虚存系统中去了，然后又看代码，结果就碰到了所谓的splay树算法，冲冠一怒，先把它啃了再说，呵呵。等我把代码分析写出来，那才算是真透了～

作者: liangyi571 时间: 2006-03-15 19:20
不错。没看完，更没看懂，收藏，慢慢看。

作者: 雨丝风片 时间: 2006-03-15 21:21

原帖由 liangyi571 于 2006-3-15 19:20 发表
不错。没看完，更没看懂，收藏，慢慢看。

呵呵，是我写得太简略了。主要是想改变一下写作方式，要等把一切都理清楚然后再深入浅出地写出来，速度就太慢了，而且一个人去分析总比不上大家一起搞！所以先把笔记拿出来，附带上一些简单图示，然后再逐步贴出我的分析结果，这样大家如果感兴趣的话，就可以随时一起讨论，也好让我琢磨下面该写些什么，正所谓“开放的学习”，

[ 本帖最后由雨丝风片于 2006-3-15 21:22 编辑 ]

作者: gvim 时间: 2006-03-15 21:54
我看了，我还没有深入到这里去，先学习下。
是以start addr作为关键字段的吧？可是我没有看出来 freebsd在vm中的的splay tree和普通的splay tree 算法有什么不一样呢？

作者: 雨丝风片 时间: 2006-03-16 08:46

原帖由 gvim 于 2006-3-15 21:54 发表
是以start addr作为关键字段的吧？

嗯！

原帖由 gvim 于 2006-3-15 21:54 发表
可是我没有看出来 freebsd在vm中的的splay tree和普通的splay tree 算法有什么不一样呢？

那是因为我只是画出来，还没写出来嘛，

splay树从FreeBSD5.0开始引入VM系统，FreeBSD5.3的时候对算法进行了优化，也就是添加了vm_map_entry结构体里面的adj_free和max_free两个字段，为了对这两个字段进行计算，其算法就有一些小小的变化。但万变不离其宗，其根本流程和原始splay树仍然是一致的，只是操作过程中树的形态看上去不太一样而已。

作者: congli 时间: 2006-03-16 08:49

那是因为我只是画出来，还没写出来嘛，

兄弟你也挺搞的,看到这句差点把口中的牛奶喷出来啦.哈~

作者: 雨丝风片 时间: 2006-03-16 08:54

原帖由 congli 于 2006-3-16 08:49 发表

兄弟你也挺搞的,看到这句差点把口中的牛奶喷出来啦.哈~

呵呵！

不是我故意卖关子，有些东西虽然在总体算法上通了，但还没想好以什么形式表述出来。表述好了，大家就可以排除无关因素，直取本质。

作者: gvim 时间: 2006-03-16 09:40

原帖由 雨丝风片 于 2006-3-16 08:54 发表

呵呵！

不是我故意卖关子，有些东西虽然在总体算法上通了，但还没想好以什么形式表述出来。表述好了，大家就可以排除无关因素，直取本质。

呵呵。期待你提取的本质和我提取的本质有什么不同，然后我就可以站在你这个前人的肩膀上做文章。

作者: congli 时间: 2006-03-16 09:44

原帖由 gvim 于 2006-3-16 09:40 发表

呵呵。期待你提取的本质和我提取的本质有什么不同，然后我就可以站在你这个前人的肩膀上做文章。

什么时候把你的本质也拿出来,让我可以站在你们两个前人的肩膀上再做文章.

作者: gvim 时间: 2006-03-16 09:46

原帖由 congli 于 2006-3-16 09:44 发表

什么时候把你的本质也拿出来,让我可以站在你们两个前人的肩膀上再做文章.

我不会保留的，呵呵。你可以随便踩我

作者: congli 时间: 2006-03-16 09:51

原帖由 gvim 于 2006-3-16 09:46 发表

我不会保留的，呵呵。你可以随便踩我

哇哈哈!那我就不客气啦!

作者: 雨丝风片 时间: 2006-03-16 09:56

原帖由 gvim 于 2006-3-16 09:40 发表
呵呵。期待你提取的本质和我提取的本质有什么不同，然后我就可以站在你这个前人的肩膀上做文章。

有什么东西赶快亮出来吧，把此贴变成讨论贴～

作者: 雨丝风片 时间: 2006-03-16 09:57

原帖由 gvim 于 2006-3-16 09:46 发表
我不会保留的，呵呵。你可以随便踩我

想起了石榴姐～:em11:

作者: gvim 时间: 2006-03-16 09:59

原帖由 雨丝风片 于 2006-3-16 09:56 发表

有什么东西赶快亮出来吧，把此贴变成讨论贴～

我还没有深入到代码层去检验，所以还不敢拿出来，太"干"了也不好看，是吧

作者: 雨丝风片 时间: 2006-03-16 10:09

原帖由 gvim 于 2006-3-16 09:59 发表

我还没有深入到代码层去检验，所以还不敢拿出来，太"干"了也不好看，是吧

看多少说多少嘛，

为了计算前面提到两个size，FreeBSD要对splay树进行正反两次遍历，有点像上下拉两次拉链。先分后合这一点是和原始splay树一致的，但在第一次遍历时要对树进行倒置，第二次再“正”过来。

作者: yuzlei 时间: 2006-03-23 23:45
找到了一个splay tree的java applet demo，非常直观
http://www.ibr.cs.tu-bs.de/cours ... ayTree-Example.html

作者: 雨丝风片 时间: 2006-03-24 08:31

原帖由 yuzlei 于 2006-3-23 23:45 发表
找到了一个splay tree的java applet demo，非常直观
http://www.ibr.cs.tu-bs.de/cours ... ayTree-Example.html

不错！用这种方式学算法太好玩了，以后可以把BSD的源代码分析也做成这种动画！

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)