引用计数和着色法管理对象生命周期 - 讨论 - 高级语言虚拟机

[讨论] 引用计数和着色法管理对象生命周期

ljs_nogard 2011-10-13

我是做成一个叫 mpt r的智能指针的形式来实现引用计数染色法的。

既然是C++的智能指针，那就要有几个使用限制：

1. mptr 所指向的对象都必须由特定的内存池分配，否则无法保存一些额外信息
2. mptr 所管理的对象，如果要使用别的指针，那么 mptr 不负责这些指针所指对象的释放

还有一个是必要条件，但不算是限制的，就是 mptr 有能力判断自己是位于栈上还是堆上；
如果mptr是作为一个堆上的对象，那它有没有父对象，父对象在哪里，父对象的额外信息（例如颜色表），都可以很快地找出来。
这个怎么实现就不具体说了，很长，反正已经实现了。

接下来是一些算法所要保持的性质（都是必要条件）：

1. 如果一个对象具有某（几）种颜色，那么这个对象所包含的 mptr （子对象，subobject）所指向的对象，也必定具有这（几）种颜色；也可以简单说成 mptr 具有这几种颜色

2. 如果一个对象具有某一种颜色，那么它也一定知道，至多有多少个具有同样颜色这种颜色的对象指向它。

3. 如果一个对象，被若干个具有同一种颜色的 mptr 所指，若全部这些 mptr 已经宣告生命周期结束，或者已经褪去这种颜色，那么这个对象也同时褪去这种颜色

4. 在栈上的 mptr （根对象所在）一开始（即未被其他 mptr 赋值前）只能有一种颜色，并且是独一无二的颜色（新颜色）。

如何判断一个非根对象可回收（充分条件）：

1. 该对象褪去所有颜色
2. 该对象具有的所有颜色，其根对象已经消亡或者已转成其他颜色。（所以这里暗示的是，一个对象的引用计数，至少应该分为两部分，来自根对象的引用，来自非根对象的引用）

上面应该没有遗漏的了，有说得不清楚的地方欢迎提问。

正确性证明，在纸上写是很难的啦，所以我是打算用代码来做，省时省力。
而且某些极端的情况下，要保持上面的性质运算量还是蛮大的。

这个思路有很多种实现的算法，欢迎各位自己去实现，独立验证。

下面粘贴一个补充法则，和验证过程：
http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=21665972&ptid=3615619

如果 ABC 成环， DEF 成环，现在 C需要新指向一个新结点 K, 它不知道 K之后会怎么操作， K如何上色？

而后另一个新结点 M 指向B, 同样M怎么上色？

如果之后再将 K指向 D, K, DEF环怎么上色？

之后 E指向 M 形成一个新环，又是怎么上色？

--------------------------------------------------

首先告诉你我是怎样实现颜色传递的，规则如下：

1. 如果 x 和 y 的颜色表的交集为空，那么就将 x 颜色表的 key 作为一项加入 y 的颜色表中
2. 如果 x 和 y 的颜色表的交集非空，那么就将 x 和 y 的颜色表合并成一个，可以赋予一个新的颜色值，但要保持推算出原有颜色的能力。

以下是你的例子的过程：

1. ABC，具有颜色 1，然后C指向A，因为发现A和C拥有同一种颜色，那么 ABC三节点的颜色表合并成一个（就是说 ABC 三个颜色表的key 对应的 value 相同），怎么合并这个就比较复杂了……

2. DEF 成环，具有颜色 2，后面同理

3. C指向K，按规则1

4. 新节点M，应该是从根节点出发的，所以本身先具有颜色3，
M 指向 B, 应该是M将颜色传递给B，而不是M的颜色受影响。这样，ABC 的颜色表中要再增加一个M的颜色表的 key的项 (注意，不是value），因为M 和ABC没有共同的颜色（规则1）
此时可以归纳出 ABC 环具有颜色 1，3

5. K 再指向 D，同样不影响K 的颜色，但是 DEF 的颜色表中要增加一个 K 的颜色表key 的项。此时可以归纳出 DEF 环同时具有颜色 1 , 2, 3

6. E 指向 M，因为 M 已经具有颜色 3，E具有颜色 1,2,3，所以应该合并 M 和 E 的颜色表的key。这样，从ABC中也可以归纳出他们同时具有颜色1,2,3

所以，我之前说了，某些极端情况下，颜色表的归纳和合并，是需要很大量的运算的。
不过多数情况下，会比遍历对象好。

如果加以优化，应该代价会更小一些。

最后更新于（Nov 24）

ljsnogard_at_gmail_dot_com