前面我们了解了 Java7 与 Java8 的内存模型，接下里我们要学习 JVM 是如何回收对象所占用的内存的，本文先为你介绍三种常用的 GC 算法。

概述

常用的 GC 算法主要有三种：标记-清除算法、标记-整理算法、复制算法。还有一种分代收集算法，这种算法无非就是对内存的不同区域使用前面三种不同的算法。

这三种 GC 算法总体而言，都专注于干两件事情：

  • 标记所有存活的对象。在垃圾收集中有一个叫做 标记 (Marking) 的过程专门干这件事。
  • 清除所有死对象。这三种算法的区别就在于清理死对象的实现方式上。

标记可达对象 (Marking Reachable Objects)

现代 JVM 中所有的 GC 算法，第一步都是找出所有存活的对象，如图所示：

Java-GC-mark-and-sweep

GC Roots

前面 讲了 GC 中 根 (GC Roots) 的概念：

指的是指向对象指针的” 起点”。

可作为 GC Roots 的节点主要在全局性的引用（例如常量或类静态属性）与执行上下文（例如栈帧中的本地变量表）中，主要包括：

  • 在虚拟机栈（栈帧中的本地变量表）中应用的对象，譬如各个线程被调用的方法堆栈中使用到的参数、局部变量、临时变量。
  • 在方法区中类静态属性引用的对象，譬如 Java 类的应用类型静态变量。
  • 在方法区中常量的应用对象，譬如字符串常量池（StringTable）里的应用。
  • 在本地方法栈中 JNI（Native 方法）应用的对象。
  • Java 虚拟机内部引用，如基本数据类型对象的 Class 对象，一些常驻的异常对象（比如 NullPointException、OutOfMemoryError）等，还有系统类加载器。
  • 所有被同步锁（synchronized）持有的对象。
  • 反映 Java 虚拟机内部情况的 JMXBean、JVMTI 中注册的回调、本地代码缓存等。

GC 遍历 (traverses) 内存中整体的对象关系图 (object graph)，从 GC 根元素开始扫描，到直接引用以及间接引用 (通过对象的 属性域 )。所有 GC 访问到的对象都被 (marked) 为 存活对象 （上图中的蓝色标记）。而从 GC 根无法直接或间接访问到的对象称为 不可达的对象 (unreachable object) (上图中的灰色标记)，GC 会在接下来的阶段中清除掉这些不可达的对象。

在标记阶段，需要注意几点：

Stop The World(STW)

在标记阶段，需要暂停所有应用线程，以遍历所有对象的引用关系。因为这项分析工作必须在一个能确保一致性的快照中进行 —— 这里 “一致性” 的意思是指在整个分析期间整个执行系统看起来就像被冻结在某个时间点上，不可以出现分析过程中对象引用关系还在不断变化的情况，该点不满足的话分析结果准确性就无法得到保证。这种情景叫做 Stop The World pause (全线停顿)。

暂停的时间，与堆内存的大小，对象的总数没有直接关系，而是有存活对象（alive objects）的数量来决定。所以，增加堆内存的大小并不会直接影响标记阶段占用的时间。

OopMap

目前的主流 Java 虚拟机使用的都是准确式 GC（Exact VM），所以当执行系统停顿下来后，并不需要一个不漏地检查完所有执行上下文和全局的引用位置，虚拟机应当是有办法直接得知哪些地方存放着对象引用。在 HotSpot 的实现中，是使用一组称为 OopMap 的数据结构来达到这个目的的，在类加载完成的时候，HotSpot 就把对象内什么偏移量上是什么类型的数据计算出来，在 JIT 编译过程中，也会在特定的位置记录下栈和寄存器中哪些位置是引用。这样，GC 在扫描时就可以直接得知这些信息了。

OopMap 是一种用于记录位于 Java 栈上的对象引用的数据结构。 其主要目的是查找位于 Java 栈上的 GC Roots，当 Heap 中对象移动时，会去更新对应的对象引用信息。

oopMap.cpp 、 generateOopMap.cpp 、 oopMapCache.hpp

Safe Point

程序并非在所有的地方都能停顿下来开始 GC，只有达到安全点 (Safe Point) 才能暂定。如何在 GC 发生时，让所有线程都” 跑” 到安全点上再停顿下来，这里有两种方案：

抢先式中断（Preemptive Suspension）

不需要线程的执行代码主动配合，在 GC 发生时，首先把所有线程全部中断，如果发现有线程中断的地方不在安全点上，就恢复线程，让它” 跑” 到安全点上。（这种方式几乎没有虚拟机使用了）

主动式中断（Voluntary Suspension）

当 GC 需要中断线程的时候，不直接对线程操作，仅仅简单地设置一个标志，各个线程执行时主动去轮询这个标志，发现中断标志为真时就自己中断挂起。

Safe Region

当线程处于 Sleep 状态或者 Blocked 状态，这时线程无法响应 JVM 的中断请求，也就无法” 跑” 到安全的地方去中断挂起，JVM 也不可能等到线程重新被分配 CPU 时间。这就需要安全区域来解决。

安全区域（Safe Region）是指在一段代码片段之中，引用关系不会发生变化。在这个区域中的任意地方开始 GC 都是安全的。

在线程执行到 Safe Region 中的代码时，首先标识自己已经进入了 Safe Region，那样，当在这段时间里 JVM 要发起 GC 时，就不用管标识自己为 Safe Region 状态的线程了。在线程要离开 Safe Region 时，它要检查系统是否已经完成了根节点枚举（或者是整个 GC 过程），如果完成了，那线程就继续执行，否则它就必须等待直到收到可以安全离开 Safe Region 的信号为止。

删除不可达对象 (Removing Unused Objects)

各种 GC 算法在删除不可达对象时略有不同，但总体可分为三类：清除 (sweeping)、整理 (compacting) 和复制 (copying)。

Sweep (清除)

Mark-Sweep(标记 - 清除) 算法是最基础的收集算法。在标记阶段完成之后，所有不可达的对象占用的空间都会被回收，用于下一次新对象的分配。

GC-sweep

优点

  • 算法简单，实现容易

缺点

  • 碎片化（fragmentation）。在 GC 标记 - 清除算法的使用过程中会逐渐产生被细化的分块，不久后就会导致无数的 小分块散布在堆的各处。如果发生碎片化，那么即使堆中分块的总大小够用，也会因为一个个的分块都太小而不能执行分配。
  • 需要使用空闲链表 (free­list)，来记录所有的空闲区域，以及每个区域的大小。维护空闲表增加了对象分配时的开销。
  • 分配速度低下。GC 标记 - 清除算法中分块不是连续的，因此每次分配都必须遍历空闲链表，找到足够大的分块。最糟的情况就是每次进行分配都得把空闲链表遍历到最后。

Copy (复制)

为了解决效率问题，一种称为 “复制”（Copying）的收集算法出现了，它将可用内存按容量划分为大小相等的两块，每次只使用其中的一块。当这一块的内存用完了，就将还存活着的对象复制到另外一块上面，然后再把已使用过的内存空间一次清理掉。这样使得每次都是对整个半区进行内存回收，内存分配时也就不用考虑内存碎片等复杂情况，只要移动堆顶指针，按顺序分配内存即可，实现简单，运行高效。

GC-mark-and-copy-in-Java

优点

优秀的吞吐量

GC 标记 - 清除算法消耗的吞吐量是搜索活动对象（标记阶段）所花费的时间和搜索整体堆（清除阶段）所花费的时间之和。

而 GC 复制算法只搜索并复制活动对象，所以跟一般的 GC 标记 - 清除算 法相比，它能在较短时间内完成 GC。也就是说，其吞吐量优秀。

尤其是堆越大，差距越明显。GC 标记 - 清除算法在清除阶段所花费的时间会不断增加， 但 GC 复制算法就不会产生这种消耗。毕竟它消耗的时间是与活动对象的数量成比例的。

可实现高速分配

GC 复制算法不使用空闲链表。这是因为分块是一个连续的内存空间。因此，只要这个分块大小不小于所申请的大小，那么移动 $free 指针就可以进行分配了。不像 GC 标记 - 清除算法那样每次分配内存空间时，都要遍历空闲链表，而且每次都要遍历到最后一个分块。

不会发生碎片化

GC 复制算法每次回收垃圾对象是，都是对整个一半的空间进行回收，不像 GC 标记 - 清除算法那样，会留下碎片化的内存空间。

缺点

堆使用效率低下

GC 复制算法把堆二等分，通常只能利用其中的一半来安排对象。也就是说，只有一半堆能被使用。相比其他能使用整个堆的 GC 算法而言，可以说这是 GC 复制算法的一个重大的缺陷。

Compact (整理)

标记 - 清除 -­ 整理算法 (Mark-­Sweep­-Compact)。标记过程仍然与 “标记 - 清除” 算法一样，但后续步骤不是直接对可回收对象进行清理，而是让所有存活的对象都向一端移动，然后直接清理掉端边界以外的内存。

03_03_GC-mark-sweep-compact

优点

标记 - 清除 -­ 整理算法 (Mark­Sweep­Compact)，将所有被标记的对象 (存活对象)，迁移到内存空间的起始处，消除了标记 ­ 清除算法的缺点。

缺点

GC 暂停时间会增加。因为需要将所有对象复制到另一个地方，然后修改指向这些对象的引用。

参考资料