« 上一篇下一篇 »

增量式可达性分析

如果我们让增变者和一个算法,那样的基本跟踪算法交替执行,那么一些可达对象可能会被错认为是不可达的。问题的根源在于增变者的动作可能会违反这个算法的一个关键不变式,即一个已扫描对象中的引用只能指向已扫描或待扫描的对象,这些引用不可以指向未被访问对象。考虑下面的场景:

1)垃圾回收器发现对象o1可达并扫描o1中的指针,因而将o1置于已扫描状态。

2)增变者将一个指向未被访问(但可达)的对象0的引用存放到已扫描对象ol中。它从当前处于未被访问或待扫描状态的对象o2中将一个指向o的引用拷贝到ol中。

3)增变者失去了对象o2中指向o的引用。它可能已经在扫描o2中指向o的引用之前就覆写了这个指针;也可能o2已经变得不可达,因此一直没有进人待扫描状态,因此它内部的指针没有被扫描过。

现在,o可以通过对象ol到达,但是垃圾回收器可能既没有看到o1中指向o的引用,也没有看到o2中指向o的引用。

要得到一个更加准确且正确的增量式跟踪方法,关键在于我们必须注意所有将一个指向当前未被访问对象的引用从一个尚未扫描的对象中拷贝到巳扫描对象中的动作。为了截获可能有问题的引用传递,算法可以在跟踪过程中按照下列方式修改增变者的动作:

*写关卡。截获把一个指向未被访问的对象o的引用写人一个已扫描对象o1的运算。在这种情况下,将o作为可达对象并将其放人待扫描集合。另一种方法是将被写对象o1放回到待扫描集合中,使得我们可以再次扫描它。

*读关卡。截获对未被访问或待扫描对象中的引用的读运算。只要增变者从一个处于未被访问或待扫描状态中的对象读取一个指向对象o的引用时,就将o设为可达的,并将其放人待扫描对象的集合。

*传递关卡。截获在未被访问或待扫描对象中原引用丢失的情况。只要增变者覆写一个未被访问或待扫描对象中的引用时,保存即将被覆写的引用并将其设为可达的,然后将这个引用本身放人待扫描集合。

上述几种做法都不能找到最小的可达对象集合。如果跟踪过程确定一个对象是可达的,那么这个对象就一直被认为是可达的。即使在跟踪过程结束之前所有指向它的引用都被覆写,它仍然被认为是可达的。也就是说,找到的可达对象集合介于(R U Vew) - Lost与(R U Vew;)之间。

上面给出的可选算法中写关卡方法是最有效的。读关卡方法的代价较高,因为一般来说读运算要比写运算多得多。转换关卡没有什么竞争力,因为很多对象“英年早逝”,这种方法会保留很多的不可达对象。

« 上一篇下一篇 »