【Java虚拟机探究】6.GC算法与种类(上)

之前讲解了JVM的一些常用配置参数，在里面提到了堆的一些区域，分为新生代和老年代，GC是专门对堆内存进行清理的。本篇我们来探讨GC针对堆内存的垃圾回收的算法与种类。

一、GC的概念

GC就是“Garbage Collection”垃圾收集的意思，这个“垃圾”指的就是Java系统在运行过程中产生的一些已经无用的“对象”，而这些“对象”是占据着一定空间的，如果这些对象不被及时释放掉，最终会导致内存被耗尽，即内存溢出。所以这些无用的对象，就需要在一定的时间范围内被及时的回收掉，以确保整个系统有足够的内存可以使用。

而在C/C++中通常需要程序员自己去申请和释放内存空间，因此没有一个主动的GC垃圾回收的概念，而在Java中已经将内存的回收和垃圾的释放操作，交由JVM的GC来自动处理，减少了程序员开发程序的工作量，也减少了因没有释放内存而导致的内存溢出问题。

GC垃圾回收机制，就是在JVM中有一个专门用于垃圾回收的线程，不停的在监听内存的使用情况，随时将无用的内存进行释放，所以GC的主要目的就是防止内存的泄露。

而GC垃圾回收的概念本身不是由Java提出的，事实上，早在1960年的时候，就已经开发出来了GC算法的思想来管理程序的内存，Java只是借鉴了这种优秀的概念，来处理自己语言的内存管理问题。

在Java中，GC的主要处理的对象就是堆空间和永久区，GC会将在堆空间和永久区的一些已经没有用的、无效的对象和空间释放。

二、GC算法

那么GC是如何进行垃圾回收的？它是依靠一些回收算法来对内存进行回收操作的。目前垃圾回收的常用算法有四种，分别是“引用计数法”、“标记清除”、“标记压缩”、“复制算法”。

1.引用计数法

“引用计数法”通过引用计数，来标记一个对象是不是应该回收。该算法是一个比较古老的算法，早在微软的时代，就已经有“COM”技术使用该算法，而现在我们在“ActionScript3”以及“Python”语言中也可以看到该算法的身影。

所谓的“引用计数”为每个对象都标记一个使用数量，只要有一个人使用这个对象，就会在这个对象的引用数量上加1，有N个人使用，就在这个对象的引用数量上加N，一旦有人释放了这个对象，就将这个引用的数量减1。当一个对象的引用数量为0时，就意味着没有人再使用这个对象了，那么这个对象就可以进行空间的释放了。这就是引用计数法的基本思想。

下面是一个对象引用的引用图：

其中根对象可能会有若干的引用对象，而引用对象可能也会有引用...只要能引用到的对象，就认为是“可达”的有效对象。

而当一个引用对象一旦消失，该对象就变成“不可达”。原本该对象的引用标记为1，被释放后，引用标记变为0，此时该对象就会被回收：

但是引用计数法会有两个比较麻烦的问题：

(1)引用和去引用伴随加法和减法，影响性能

因为每个对象一旦引用数量为0时，就要被清除，所以要不停的计算和检查每一个对象的引用数量，当被引用和被断开引用时，也要不停的进行加和减的操作，十分耗费程序性能。

(2)很难处理循环引用

当出现了引用指向是一个“环”的状态后，就会发生一系列问题。如下面的引用图：

在该图中有一个根对象，根对象引用了一个对象，而被引用的这个对象又被另外一个对象引用，所以此时它的引用标记为2。

当根对象断开对被引用对象的引用时，被引用对象它的引用实例就变为了1，而根据引用计数法的规则，当前引用对象计数为1的时候是不会被清除的，因此这3个“环状”引用的对象，对于根对象来说，都是不可达的引用对象，而在“环状”引用中的三个对象的引用计数都是1，都不会被清除，此时从单纯的引用计数算法来看，是无法处理这种垃圾数据的：

这种情况就是“垃圾对象循环引用”的现象，它会导致垃圾对象的引用标记始终都不为0，及时这些对象对于根对象是不可达的有效对象，但是也不会得到有效的释放。

2.标记清除法

标记清除法是现代垃圾回收算法的思想基础。标记清除法将垃圾回收分为两个阶段：标记阶段和清除阶段。一种可行的实现是，在标记阶段，首先通过根节点，标记所有从根节点开始的可达对象，因此，未被标记的对象就是未被引用的垃圾对象，然后，在清除阶段，清除所有未被标记的对象。

下图就是一个标记清除的空间处理方式：

在该图中，空白区域表示“空闲空间”，黑色代表“垃圾对象”，浅灰色代表“存活对象”。根节点下的箭头表示“引用”，从根节点下箭头一路指向的，都是根节点的可达对象，这些对象是不应该被回收的；而所有黑色不可达的，为垃圾对象；一旦标记阶段做了标记之后，在清除阶段，只需要简单的将未标记的对象(或标记为垃圾的对象)清除即可，此时整个回收算法就计算完毕。

标记清除算法与引用计数法比较而言，引用计数法中不可达的对象，但出现循环引用的时候，计数为1是不会被清理的；而标记清除算法，只计算对象可达还是不可达，只要不可达，就会被标记为垃圾对象清除，不管它是不是有循环引用，这样就避免了“垃圾对象循环引用”的现象。

3.标记压缩法

标记压缩算法适合用于存活对象较多的场合，如老年代。它在标记清除算法的基础上做了一些优化。和标记清除算法一样，标记压缩算法也首先需要从根节点开始，对所有可达对象做一次标记。但之后，它并不简单的清理未标记的对象，而是将所有的存活对象压缩到内存的一端，之后，清理边界外所有的空间。

下图就是一个标记压缩的空间处理方式：

在该图中，空白区域表示“空闲空间”，黑色代表“垃圾对象”，浅灰色代表“存活对象”，而斜线代表“移动”。标记压缩算法首先标记出了对象是否存活，然后开始移动存活对象，而不是立即去清除未标记的对象。如图中所示，在标记完存活对象之后，会按照箭头的方向将存活对象压缩至内存的一端，移动完毕之后，将存活对象存储边界(存活对象所在空间的行尾)以外的空间全部清除。以上就是标记压缩基本的思路。

与标记清除相比，标记压缩在GC后已用空间是连续占据了总空间的前端，可用空间是连续的。而标记清除算法，将已用空间（生存对象占据）和可用空间（回收了可清除对象的空间）相互交错，形成了可用空间“碎片”，这种间断的空间状态，继续给新对象分配空间，寻址可用空间效率较低，而且还会有无法利用的空间（碎片太小，无法分配），相比标记压缩法，在GC结束后会产生连续的可用空间，提高给新对象分配空间和空间的利用率。

标记压缩的得失

标记压缩方法的优势并不体现在GC时期，相反在GC时的耗时会比标记清除方法高，因为为了保证空间连续，多了搬运对象的过程，这个应该是耗时的操作。用GC时的时间消耗换来的是更多更高效使用的可用空间。这种交换到底值得不值得是要根据不同的场景进行权衡的。这样的矛盾也是不同的垃圾收集器（GC思想的实现）适合不同分代不同场景的表现。标记压缩算法的应用场景是老年代，说老年代执行GC效率低，可用对象重排整理是主要原因。

4.复制算法

与标记清除算法相比，复制算法是一种相对高效的回收方法。它不适用于存活对象较多的场合，如老年代。

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

下图就是一个复制算法的空间处理方式：

在该图中，空白区域表示“空闲空间”，黑色代表“垃圾对象”，浅灰色代表“存活对象”。这里将空间分割成了大小相同的两块，每次只使用一块(如1G的空间，每次只使用512M)。每次会将所有可用的存活对象，复制到另外一个空间去(根据箭头所示)，复制完毕后，就会将第一块空间的所有对象，全部清除。以后的存储和清除就会反复交换空间。

复制算法的很大的一个缺点就是，浪费了很大一部分空间(至少浪费了一半的空间)。因此我们整合“标记清理”的思想，要达到让空间不做过多的浪费。下面就是对复制算法的一些拓展：

在上图中，将空间分为四块，第四块“老年代、大对象”为“担保空间”，不在复制算法的处理范围内。上面的三块，分别是一块大的空间，和两块大小一样的小的空间。其中大的空间主要用来产生对象，而下面两个小的，是复制算法处理的核心空间，可以称为“复制空间”。

在垃圾回收进行的时候，首先大对象直接进入“担保空间”(老年代)：

因为大对象不太好塞到“复制空间”去，因为“复制空间”本身会很小(因为“复制空间”越大，浪费的空间越大)，大对象可能会放不进去，而就算放进去，"复制空间”中的小对象可能会被排挤到“老年代”中去，是不合理的。

而在“复制空间”中每一次复制后，未被清除的对象年龄都会加1，当这个对象到达一定的年龄阶段的时候，该对象就是一个“老年对象”(即好几次回收都没有被回收掉的，即长期有效的对象)，此时该“老年对象”会被放置到老年代：

除了“大对象”和“老年对象”外，剩余的对象就会被做复制。那块大的空间中，小的、年轻的对象在回收的时候，就会被统一的放置在左侧空闲的空间中，而右侧的空间中的小的、年轻的对象也会被直接复制到左侧的空闲空间中去：

然后根据复制算法的机制，就会清空另外的两个空间：

我们可以看到回收完成之后的效果。

对于上面的几个空间，在Java的堆空间中，最上面的大空间就是eden伊甸区域，新new对象都会放在那个区域，而下面两个小空间都属于survivor存活区，一开始存放从eden区转移过来的对象的那个空间属于survivor的from类型空间，空白的待复制的空间属于survivor的to类型空间。而最下面的老年代和持久带所在区域为年老区(Tenured)，老年对象被放置在老年代（Old Generation），大对象放置(静态文件，如今Java类、方法)的区域是持久代（Permanent Generation）：

三、分代思想

可以看到，复制算法相对于前面的几种算法，对空间的划分是比较科学的，这使得垃圾回收的效率变高，而这个所谓的空间的划分，其实就是所谓的“分代思想”。

分代思想的核心就是，依据对象的存活周期进行分类，短命对象归为新生代，长命对象归为老年代。

在GC的过程中，通过分代，我们可以根据不同代的特点，选取合适的收集算法：

(1)少量对象存活，适合复制算法

(2)大量对象存活，适合标记清理或者标记压缩

四、GC算法总结整理

我们上面讲解了“引用计数法”、“标记清除法”、“标记压缩法”以及“复制算法”这几种垃圾回收的算法，那么Java中的GC使用了什么算法呢？

在Java中，是没有采用“引用计数法”的，原因就是因为单纯的“引用计数法”无法处理“循环引用”的问题。

而“标记清除”和“标记压缩”是Java在老年代被明确使用的。

而“复制算法”是Java在新生代被明确使用的算法。

如下图：

思考：所有的算法都需要能够识别一个垃圾对象，因此需要给出一个可触及性的定义。有关什么是可触及性，下一篇我会继续为大家总结。