« 上一篇下一篇 »

并行垃圾回收算法

我们必须控制启动跟踪过程的频率,这很重要跟踪步骤就像是一场赛跑。增变者创建必须扫描的新对象和新引用,而跟踪过程则试图扫描所有可达对象,并重新扫描同时产生的脏卡片。
下面给出一个并行、并发垃圾回收算法的大概描述,我们可以仔细看一下,:

1)扫描每个增变者线程的根集,将所有可以从根集中直接到达的对象设为待扫描状态。完成这一步的最简单的增量式做法是等待一个增变者线程调用内存管理器,如果那时它的根集还没有被扫描,就让它扫描自己的根集。如果所有其他跟踪工作都已经完成,而某个增变者线程还没有调用内存分配函数,那么必须暂停这个线程,扫描它的根集。

2)扫描处于待扫描状态的对象。为了支持并行计算,我们使用一个由固定大小的工作包(work packet )组成的工作队列。每个工作包保存了一些待扫描对象。当发现待扫描对象时,它们就被放置到工作包中。等待工作的线程将从队列中取出这些工作包,并跟踪其中的待扫描对象。这种策略允许在跟踪过程中把工作量平均分配给各个工作线程。如果系统用完了存储空间,使得我们无法找到创建这些工作包所需的空间,就直接为保存这些对象的卡片加上标记,使它们将在以后被扫描。后一种处理方法总是可行的,因为存放卡片标记的位数组已经预先分配好了。

3)扫描脏卡片中的对象。当工作队列中不再有待扫描对象,并且所有线程的根集都已经被扫描过之后,我们重新扫描这些卡片以寻找可达对象。只要增变者继续执行,脏卡片就会不断产生。因此,我们需要依照某种标准来停止跟踪过程。比如只允许卡片被再次扫描一次或固定的次数,或者当未完成扫描的卡片数量减少到某个阈值时停止跟踪。这么做的结果是使得并行和并发步骤通常会在完成全部跟踪工作之前就停止。剩下的工作将在下面介绍的最后一步中完成。

4)最后一步保证所有的可达对象都被标记为巳被访问的。随着所有增变者停止执行,使用系统中的所有处理器就可以快速找到所有线程的根集。因为大部分可达对象已经被跟踪确定,预计只有少量的对象会被放在待扫描状态中。所有的线程都参与了对其余可达对象的跟踪和对所有卡片的重新扫描。

我们必须控制启动跟踪过程的频率,这很重要。跟踪步骤就像是一场赛跑。增变者创建出必须被扫描的新对象和新引用,而跟踪过程则试图扫描所有可达对象,并重新扫描同时产生的脏卡片。在需要进行垃圾回收之前过分频繁地启动跟踪过程是没有必要的,因为这样做将会增加漂浮垃圾的数量。另一方面,我们又不能等到存储耗尽时才开始跟踪过程。因为这时增变者将不能继续运行,此时的情况就退化为使用全面停顿式回收器的情形。因此,算法必须适当地选择启动回收的时机和跟踪的频率。对前面的各轮垃圾回收中的对象增变速率的估算可以帮助我们在这方面做出决策。根据专用垃圾回收线程所做的工作量,可以动态调整跟踪频率。

« 上一篇下一篇 »