[编程基础]GC高级算法

在讨论完三大基础算法以后,我们现在来看看这基础算法的结合以后做成的高级算法。其中最具有代表性的就是:分代回收,增量回收,和并行回收,这三种。

1:分代回收

首先,我们来聊聊高级GC算法中最重要也是最常用的一种,即分代回收。由于GC和程序处理的本质是无关的,因此它所消耗的时间越短越好。分代回收的目的,正是为了在程序运行期间,将GC所消耗的时间尽量缩短。分代回收的基本思路,是利用来一般程序所具备的性质,即大部分对象都会在短时间内成为垃圾,而进过一定时间依然存活的对象往往拥有较长的寿命。如果寿命长的对象更容易存活下来,寿命短的对象则会被很快遗弃,那么如果对分配不久,诞生时间较短的“年轻”对象进行重点扫描,应该可以更有效的回收大部分垃圾。

在分代回收中,对象按照生成时间进行分代,刚诞生不久的年轻对象划分为新生代,而存活来较长时间的对象划分为老生代。根据具体实现方式的不同,可能还会划分更多的代。如果上述关于对象寿命的假说成立的话,那么只要对新生代对象进行扫描,就可以回收遗弃对象中很大一部分。像这种只扫描新生代对象的回收操作,被成为小回收。小回收中在扫描的时候如果遇到属于老生代的对象时,就不会对这个对象进行递归扫描了。这样一来,需要扫描的对象数量也会减少。然后把回收一次以后残留的对象划分到老生代中。

分代回收

上图中,任何地方都没有再被引用的对象F将会通过大回收进行回收。

上图(1)中的D被老生代E所引用,如果根据我们上面所有,如果在回收标记的时候,不对老生代中的对象进行递归引用标记操作的话,那D将不被任何对象引用,那将在一次GC中被回收掉。那这样的话,就就出现我们不期望的结果。所以我们需要做一次操作来,实现老生代对新生代的引用,这个操作一个记录,就是上图中的记录集,这个记录集就是对老生代对新生代引用变更的一个记录。在做小回收的时候,这个引用集将作为一个根来对待。

要让分代回收正确的工作,必须使记录集的内容保持更新。因此,在老生代到新生代的引用产生的瞬间,就必须对该引用进行记录,而负责执行这个操作的子程序,需要被嵌入到所有涉及对象更新操作的地方。这种检查程序需要对所有涉及修改对象内容的地方进行保护,因此被成为写屏障。

随着程序的不断运行,老生代区域中的“死亡”对象也在不断增加。为了避免这些“死亡”对象对内存的白白占用,所以需要有时候对所有的区域都进行一次扫描回收,这个操作叫做大回收或者完全回收。分代回收通过减少GC中扫描对象数量,达到减少GC带来平均中断时间的效果。不过由于还是要经历大回收的,所有最大中断时间并没有得到什么改善。

2:增量回收

在对实时性要求很高的程序中,比起缩短GC的平均中断时间,往往更重视缩短GC的最大中断时间。在这些实时性要求很高的程序中,必须能够对GC所产生的中断时间做出预测。在一般的GC算法中,做出这样的保证是不可能的,因为GC产生的中断时间与对象的数量和状态有关。因此,为了维持程序的实时性,不等到GC全部完成,而是将GC划分多个部分逐一执行。这种方式就叫做增量回收。在增量回收中,由于GC的过程是渐进的,在回收过程中程序本身也会继续运行,对象之间的引用关系也可能会发生变化。如果已经完成扫描和标记的对象被修改,对新的对象产生引用,这个新对象就不会被标记,这样明明还被引用的却会被回收。所以在增量回收中也采用了写屏障。当已经被标记的对象的引用发生变化时,通过写屏障会将新被引用的对象作为扫描的起点记录下来。由于增量回收的过程是分布渐进式的,可以将中断时间控制在一定长度之内。另一方面,由于中断操作需要消耗一定的时间,GC消耗的总时间会相应的增加。

3:并行回收

在现在的计算机中,一块芯片搭载多个cpu核心的多核处理器已经是一个司空见惯的东西了。那么在这种环境下,就需要利用多线程来充分发挥多CPU的性能,并行回收正是通过最大限度利用多CPU的处理能力来进行GC操作的一种方式。并行回收的基本原理是:是在原有的程序运行的同时进行GC操作,这一点和增量回收是相似的。因此也会遇到增量回收相同的问题。为了解决这个问题也需要写屏障来对当前的状态信息保持更新。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注