hangscer

GC算法概述

2017/02/13

引用计数法

对于一个对象A,只要有任何一个对象引用了A,则A的计数器就加1。引用失效则减1。如果对象A的引用计数器为0,则A就不能再使用。

存在两个非常严重的问题:

  • 无法处理循环引用的问题
  • 引用计数器在每次因引用产生和消除的时候,需要伴随加法操作和减法操作,性能下降。

标记清除法(Mark-Sweep)

Mark-Sweep是现代垃圾回收算法的思想基础,该算法分为两个阶段:

  • 标记阶段
  • 清除阶段

一种可行的实现是,首先通过根节点,标记所有可达对象,因此,未被标记的是垃圾对象。然后,清除所有未被标记的对象。该算法最大问题是空间碎片化严重。

如图所示,使用标记清除法对一块连续的内存空间进行空间。从根节点开始(这里显示了2个根节点),所有的有引用关系的对象均被标记为存活对象(箭头引用)。从根节点起,不可达的对象均为垃圾对象。在标记操作完成后,系统回收所有不可达对象。

那么可达性分析中的GC root究竟是什么呢?

虚拟机栈中引用的对象
方法区中静态属性引用的对象
方法区中常量引用的对象
本地方法栈中JNI引用的对象

复制算法(Copying)

算法核心思想是:将原来的内存空间分为两块,每次只使用其中一块,在垃圾回收时,将正在使用的内存中的存活对象复制到未使用的内存块中去。之后,清除正在使用内存块中的所有对象,交换两者角色,完成垃圾回收。

优点是无空间碎片,效率高。缺点是将系统内存折半。因此,单纯的cpoying算法难以让人接受。

如图,A、B两块内存空间,A在进行垃圾回收时,将存活对象复制到B区域,B中空间在复制后保持连续。复制完成后,清空A,并将空间B设置为当前使用空间。

在Java的新生代串行垃圾回收器中,使用了复制回收算法的思想。新生代分为eden空间、from空间和to空间。其中from和to空间可以视为复制的两块大小相同、地位相等、且可以互换角色的空间块。from和to空间也被称为survivor空间,即幸存者空间,用于存放未被回收的对象。

标记压缩算法(Mark-Compact)

复制算法的高效性是建立在存活对象少、垃圾对象多的前提下的。这种情况在新生代经常发生,但是在老年代,更常见的情况是大部分对象都是存活对象。如果依然使用复制算法,由于存活对象较多,复制的成本将很高。

标记压缩算法是一种老年代的回收算法。它在标记清除算法的基础上做了优化。通标记清除算法,首先从根节点开始,对所有可达对象做一次标记。但之后,它并不是只是简单的清理未标记的对象,而是把所有存活的对象压缩到内存的一端。它不是直接清理可回收对象,而是将存活对象都向一端移动,然后清理掉端边界以外的内存。

通过根节点标记所有可达对象后,沿虚线进行对象移动,将所有的可达对象都移动到一端,并保持它们的引用关系。

分代算法(Generational Collecting)

前文讲的复制、标记清除、标记压缩等垃圾回收算法。在所有这些算法中,并没有一种算法可以完全代替其他算法,它们都有自己独特的优势和优点。

复制算法:适用于存活对象很少,回收对象多。
标记压缩算法:适用于存活对象多,回收对象少。

分代算法基于这样思想,它将内存区间根据对象的特点分为几块,针对使用不同的算法。

一般的,java把所有新建的对象都放入新生代的内存区域。新生代的特点就是对象朝生夕灭,大约90%的新建对象会被很快回收,因此,新生代比较适合复制算法。当一个对象经过几次回收后依然存活,对象就会被放入老年代的内存空间。在老年代中,几乎所有对象都是经过几次垃圾回收后依然得以存活。因此,可以认为这些对象在一段时间内,甚至在应用程序的整个生命周期中,将是常驻内存的。
more:

  1. 对于新生代采用Coping算法,因为新生代每次垃圾回收都要回收大量对象,也就是说需要复杂的很少。但是为什么新生代被分为EdenFromTo区域呢?
  2. 老年代的特点是每次回收少量对象,采用标记压缩算法。

工作流程简述:
现在假定EdenFromToOld空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//分配一个又一个对象
分配在Eden区
//不好!,Eden区满了,只能GC(新生代GC:Minor GC)
把Eden区的存活对象copy到From区,然后清空Eden区(To区本来是空的)
//分配了一个又一个的对象
分配在Eden区
//不好!,Eden区又满了,只能GC(新生代GC:Minor GC)
把Eden区和From区的存活对象copy到To区,然后清空Eden区和From区
//分配一个又一个的对象
分配在Eden区
//不好!Eden区满了,只能GC(新生代GC:Minor GC)
把Eden区和To区的存活对象copy到From区,然后清空Eden区和To区
//......
//有的对象来来回回在From和To区待了比如15次左右,就被分配到Old区
//有的对象太大,直接分配在Old区
//有的存活对象,From或To容不下,也被放在Old区
//....
//在某次Minor GC中Old区也满了,这是一次大GC(老年代GC:Major GC)
//....

在极端情况下,老年代的存活率可以达到100%,如果依然使用复制算法回收老年代,将需要复制大量对象,可对老年代使用标记压缩清除的算法。

通常,新生代回收的频率很高,每次耗时都很短,而老年代的频率很低,但是很耗时。为了支持高频率的新生代回收,jvm可能使用一种叫做卡表(Card Table)的数据结构。卡表是一个比特位集合,每一个比特位用来表示老年代的某一区域中的对象是否持有新生代对象的引用。这样在新生代GC时,可以不完全扫描所有老年代对象,来确定一个对象的引用关系。而可以先扫描卡表,只有当卡表的标记位为1时,才需要扫描给定区域的老年代对象。标记位为0时,这个老年代对象一定不引用新生代的对象。

在新生代GC时,只需要扫描卡表位上位1所在的老年代空间,大大加快了新生代的回收速度。

STOP THE WORLD

因为垃圾回收的时候,需要整个的引用状态保持不变,否则判定是判定垃圾,等我稍后回收的时候它又被引用了,这就全乱套了。所以,GC的时候,其他所有的程序执行处于暂停状态,卡住了。
幸运的是,这个卡顿是非常短(尤其是新生代),对程序的影响微乎其微.