垃圾回收算法基础

翻译原文 => plumbr Java GC handbook

前文参见：

Java垃圾回收手册(一)：初识垃圾回收
Java垃圾回收手册(二)：Java中的垃圾回收

在深入GC算法的实现细节之前，我们最好先来了解下相关术语及背后的基本原理。不同回收器的实现细节各有不同，但总的来说基本所有的回收器都会关注如下两个方面：

• 找出所有的存活对象
• 清理掉所有的其它对象——也就是那些被认为是废弃或无用的对象。

首先，所有回收器都会通过一个标记过程来对存活对象进行统计。

标记可达对象

JVM中用到的所有现代GC算法在回收前都会先找出所有仍存活的对象。下图中所展示的JVM中的内存布局可以用来很好地阐释这一概念：

Java-GC-mark-and-sweep.png

首先，垃圾回收器将某些特殊的对象定义为GC根对象。所谓的GC根对象包括：

• 当前执行方法中的所有本地变量及入参
• 活跃线程
• 已加载类中的静态变量
• JNI引用

接下来，垃圾回收器会对内存中的整个对象图进行遍历，它先从GC根对象开始，然后是根对象引用的其它对象，比如实例变量。回收器将访问到的所有对象都标记为存活。

存活对象在上图中被标记为蓝色。当标记阶段完成了之后，所有的存活对象都已经被标记完了。其它的那些（上图中灰色的那些）也就是GC根对象不可达的对象，也就是说你的应用不会再用到它们了。这些就是垃圾对象，回收器将会在接下来的阶段中清除它们。

关于标记阶段有几个关键点是值得注意的：

• 开始进行标记前，需要先暂停应用线程，否则如果对象图一直在变化的话是无法真正去遍历它的。暂停应用线程以便JVM可以尽情地进行整理记录的程序位置点又被称之为安全点（Safe Point），这会触发一次Stop The World(STW)暂停。触发安全点的原因有许多，但最常见的应该就是垃圾回收了。
• 暂停时间的长短并不取决于堆内对象的多少也不是堆的大小，而是存活对象的多少。因此，调高堆的大小并不会影响到标记阶段的时间长短。

当标记阶段完成后，GC开始进入下一阶段，删除不可达对象。

删除无用对象

不同的GC算法在删除无用对象上的做法会有所不同，不过大致上可以为分三类：清除（Sweeping)，整理/压缩(Compacting)以及拷贝(Copying)。下面的几节将会详细介绍下这几种算法的不同。

清除

从概念上来讲，标记-清除算法使用的方法是最简单的，只需要忽略这些对象便可以了。也就是说当标记阶段完成之后，未被访问到的对象所在的空间都会被认为是空闲的，可以用来创建新的对象。

这种方法需要使用一个空闲列表来记录所有的空闲区域以及大小。对空闲列表的管理会增加分配对象时的工作量。这种方法还有一个缺陷就是——虽然空闲区域的大小是足够的，但却可能没有一个单一区域能够满足这次分配所需的大小，因此本次分配还是会失败（在Java中就是一次OutOfMemoryError）。

GC-sweep.png

整理

标记-清除-整理算法修复了标记-清除算法的短板——它将所有标记的也就是存活的对象都移动到内存区域的开始位置。这种方法的缺点就是GC暂停的时间会增长，因为你需要将所有的对象都拷贝到一个新的地方，还得更新它们的引用地址。相对于标记-清除算法，它的优点也是显而易见的——经过整理之后，新对象的分配只需要通过指针碰撞便能完成（pointer bumping），相当简单。使用这种方法空闲区域的位置是始终可知的，也不会再有碎片的问题了。

GC-mark-sweep-compact.png

复制

标记-复制算法与标记-整理算法非常类似，它们都会将所有存活对象重新进行分配。区别在于重新分配的目标地址不同，复制算法是为存活对象分配了另外的内存区域作为它们的新家。标记复制算法的优点在于标记阶段和复制阶段可以同时进行。它的缺点是需要一块能容纳下所有存活对象的额外的内存空间。

GC-mark-and-copy-in-Java.png