深入理解Java虚拟机——垃圾回收算法

1.前言

垃圾回收需要完成的三件事

首先我们需要明白垃圾回收需要完成的三件事：

• 哪些内存需要回收
  • 堆内存中的对象所使用的内存
  • 方法区中的废弃的常量以及不再使用的类型
• 什么时候回收
  • 当对象死亡
  • 方法区中某些内容（常量和类型）不再被使用
• 如何回收

明白了这三个步骤，对你后面的阅读，逻辑会更加清晰。

为什么要了解垃圾回收和内存分配？

当需要排查各种内存溢出、内存泄漏问题时，当垃圾收集成为系统达到更高并发量的瓶颈时，我们就必须对这些自动化的技术实施必要的监控和调节。

2.如何判断对象已死？

所谓死去，就意味着该对象不能再被任何途径使用。

2.1 引用计数算法

基本思路

引用计数法的基本思路是在对象中添加一个引用计数器，每当有一个地方引用它时，计数器值就加1；当有一个引用失效时，计数器值就减1；当任何时候，计数器的值为0，就意味着该对象不可能再被使用。

存在的问题

客观来说，引用计数法使用了极少空间进行计数，判定效率很高。

但是它存在很多难以解决的问题，举一个显而易见的例子：循环依赖就是一个很棘手的情况。

这里假设虚拟机使用引用计数算法判断对象是否已经死亡。比如说Java虚拟机的堆内存中，存在对象A和对象B，没有任何对象引用对象A和对象B，但是A引用了B，B也引用了A，这就造成了循环依赖，即使我们将A和B手动赋值为Null，但是实际上循环依赖仍然存在，这就导致了其无法被GC回收。

虽然引用计数算法简单高效，但是需要配合大量的额外处理才能保证正常工作，所以主流的Java虚拟机都没有采用该算法来管理内存。

2.2 可达性分析算法

基本思路

可达性分析算法的基本思路是通过一系列称为GC Roots的根对象作为起始节点集，从这些节点开始，根据引用关系向下搜索，搜索过程所走过的路径被称为引用链，如果某个对象到GC Roots间没有任何引用链相连，则证明该对象是不能再被使用的。

在这张图中，绿色的就是存活的对象，灰色的不与GC Roots相连，意味着不可达，也就是会被判断为可回收的对象。

哪些对象可以作为GC Roots的对象？

根据是否固定，我们可以将可以作为GC Roots的对象分为：

• 固定作为GC Roots的对象
• 不固定作为GC Roots的对象

固定可作为GC Roots的对象

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

不固定作为GC Roots的对象

除了固定GC Roots集合以外，根据对象所选用的垃圾收集器以及当前回收的内存区域不同，还可以有其他对象临时性的加入，共同构成GC Roots的集合。

譬如后文将会提到的分代收集和局部回收(Partial GC)，如果只针对Java堆中某一块区域发起垃圾收集时（如最典型的只针对新生代的垃圾收集），必须考虑到内存区域是虚拟机自己的实现细节（在用户视角里任何内存区域都是不 可见的），更不是孤立封闭的，所以某个区域里的对象完全有可能被位于堆中其他区域的对象所引用（跨代引用），这时候就需要将这些关联区域的对象也一并加入GC Roots集合中去，才能保证可达性分析的正确性。

HotSpot虚拟机：记忆集与卡表

打个比方来说如果是只针对新生代的垃圾收集，存在跨代引用，为了保证可达性分析的正确性，需要将关联区域的对象一并加入GC Roots集合中去。

为了解决对象跨代引用所带来的问题，垃圾收集器在新生代中建立了名为记忆集的数据结构，用于避免把整个老年代加进GC Roots的扫描范围。记忆集是一种用于记录从非收集区域指向收集区域的指针集合的抽象数据结构。

对于记忆集的实现有三种常见的方式：

• 字长精度:每个记录精确到一个机器字长(就是处理器的寻址位数，如常见的32位或64位，这个精度决定了机器访问物理内存地址的指针长度)，该字包含跨代指针。
• 对象精度:每个记录精确到一个对象，该对象里有字段含有跨代指针。
• 卡精度:每个记录精确到一块内存区域，该区域内有对象含有跨代指针。

第三种卡精度所指的是用一种称为卡表(Card Table)的方式去实现记忆集，这也是目前最常用的一种记忆集实现形式。卡表就是记忆集的一种具体实现，它定义了记忆集的记录精度、与堆内存的映射关系等。

在HotSpot虚拟机中，使用卡表实现记忆集，对于卡表的实现仅仅使用了一个字节数组。

字节数组种的每一个元素都对应着其标识内存区域种一块特定大小的内存块，这个内存块被称为卡页。

一个卡页的内存中通常包含不止一个对象，只要卡页内有一个(或更多)对象的字段存在着跨代指针，那就将对应卡表的数组元素的值标识为1，称为这个元素变脏(Dirty)，没有则标识为0。在垃圾收集发生时，只要筛选出卡表中变脏的元素，就能轻易得出哪些卡页内存块中包含跨代指针，把它 们加入GC Roots中一并扫描。

2.3 finalize()方法

宣告一个对象死亡，至少需要进行两次标记过程。

• 如果对象进行可达性分析后发现没有与GC Roots相连接的引用链，那么它将会被第一次标记，随后进行一次筛选，筛选条件是此对象是否有必要执行finalize方法。
  • 假如对象没有覆盖finalize方法或者finalize方法已经执行过，则被视为没有必要执行。在第二次标记时会被列入“即将回收”集合。
  • 假如对象覆盖了finalize方法，则会将该对象放入一个名为F-Queue的队列中，并且稍后由一条虚拟机自动建立的低调度优先级的Finalizer线程去执行他们的finalize方法。如果在该对象的finalize方法中成功将该对象与引用链上任意一个对象建立关联，那么第二次标记就会将它移出“即将回收”集合。

2.4 回收方法区

方法区的垃圾收集主要回收两部分的内容：废弃的常量和不再使用的类型。

判断常量是否废弃

如果有一个字符串已经进入了方法区中的常量池中，但是已经没有任何对象引用这个字符串变量，如果这个时候发生垃圾回收，并且垃圾收集器判断确实有必要就会将该字符串清出字符串常量池中。

判断类是否废弃

相对于判断常量是否废弃，类的废弃判断要复杂一些。判断一个类为“不再使用的类”需要同时满足三个条件：

1. 该类的所有实例都已经被回收，也就是Java堆中不存在该类及其任何派生子类的实例
2. 加载该类的类加载器已经被回收，这个条件除非是精心设计的可替换类加载器的场景（JSP的重加载），否则一般很难达成
3. 该类对应的Class对象没有在任何地方被引用，无法在任何地方通过反射访问该类的方法

即使一个类被判断为“不再使用的类”，也需要Java虚拟机允许对其进行回收。并不像对象一样，没有引用了自然就会回收。

3. 垃圾收集算法

分代收集理论

当前商业虚拟机的垃圾收集器大多数都遵循了“分代收集”的理论进行设计，分代收集建立在两个分代假说上：

• （1）弱分代假说：绝大多数对象都是朝生夕灭的
• （2）强分代假说：熬过越多次垃圾收集过程的对象就越是难以消亡

这两个分代假说共同奠定了多款常用的垃圾收集器的一致的设计原则：收集器应该将Java堆划分出不同的区域，然后将回收对象依据其年龄（年龄即对象熬过垃圾收集过程的次数）分配到不同的区域之中存储。

在将Java堆内存划分为不同的区域之后，垃圾收集器才可以每次只回收其中某一个或者某些部分的区域（Minor GC、Major GC、Full GC）。进而演化出与对象存亡特征相匹配的垃圾收集算法。

垃圾收集行为根据区域具体可以如下划分：

• Partical GC：不完整收集整个Java堆的垃圾收集
  • Minor GC：指目标只是新生代的垃圾收集
  • Major GC：指目标只是老年代的垃圾收集（目前只有CMS收集器会有单独收集老年代的行为）
  • Mixed GC ：指目标是收集整个新生代和老年代的垃圾收集（目前只有G1收集器有这种行为）
• Full GC：收集整个Java堆和方法区的垃圾收集

除了前两个分代假说外，还存在第三条假说：

• （3）跨代引用假说：跨代引用相对于同代引用来说仅占极少数。

该假说的隐含之意就是：存在互相引用关系的两个对象，是应该倾向同时生存或者同时消亡的。

这也就意味着我们不必为了少量的跨代引用区扫描整个老年代，也不必专门浪费空间记录每一个对象是否存在及存在哪些跨代引用。我们只需要在新生代建立一个全局数据结构，该结构将老年代划分为若干块，标识出哪一块内存会存在跨代引用。发生MinorGC的时候，只有被标识的”老年代块“才会被加入到GC Roots进行扫描。

3.1 标记-清除算法

标记清除算法分为标记和清除两个阶段：首先标记出所有需要回收的对象，标记完成后，统一回收掉所有被标记的对象。

标记清除算法主要存在两个缺点：

• 执行效率不稳定
• 容易导致大量内存空间碎片

3.2 标记-复制算法

标记复制算法常被称为复制算法，它将可用内存按容量划分为大小相等的两块，每次只使用其中的一块。当这一块的内存用完了，就将还存活着的对象复制到另外一块上面，然后再把已使用过的内存空间一次清理掉。该算法适用于大多数对象都是可回收的情况，如果大部分对象都存活，则意味着要进行大量的复制操作（将存活的对象赋值到另一块内存中），会带来额外开销。

标记复制算法的优点在于实现简单，运行高效，但是同样缺点也很明显，这样会缩小可用内存空间。

但事实上，根据研究98%的对象都活不过第一轮收集，所以并不需要完全按照1:1分配内存。HotSpot虚拟机中的新生代垃圾收集器均采用了Appel式回收来设计新生代内存布局。

Appel式回收的具体做法是把新生代分为一块较大的Eden空间和两块较小的 Survivor空间，每次分配内存只使用Eden和其中一块Survivor。发生垃圾收集时，将Eden和Survivor中仍然存活的对象一次性复制到另外一块Survivor空间上，然后直接清理掉Eden和已用过的那块Survivor空间。HotSpot虚拟机默认Eden和Survivor的大小比例是8∶1，也即每次新生代中可用内存空间为整个新 生代容量的90%（Eden的80%加上一个Survivor的10%），只有一个Survivor空间，即10%的新生代是会 被“浪费”的。当然，98%的对象可被回收仅仅是“普通场景”下测得的数据，任何人都没有办法百分百 保证每次回收都只有不多于10%的对象存活，因此Appel式回收还有一个充当罕见情况的“逃生门”的安 全设计，当Survivor空间不足以容纳一次Minor GC之后存活的对象时，就需要依赖其他内存区域（实际上大多就是老年代）进行分配担保（Handle Promotion）。

所谓分配担保就是：如果另外一块 Survivor空间没有足够空间存放上一次新生代收集下来的存活对象，这些对象便将通过分配担保机制直 接进入老年代，这对虚拟机来说就是安全的。

3.3 标记-整理算法

标记整理算法的标记过程同标记清除算法一样。而后续步骤不是直接对可回收对象进行回收，而是让所有存活对象向一段移动，然后直接清理掉边界以外的内存。

标记整理算法相对于标记清除算法的本质差异在于，前者是一种移动式的回收算法，后者是非移动式的。

是否移动回收后的存活对象是一项优缺点并存的风险决策：

1. 如果移动存活对象，意味着全程必须暂停用户应用程序才能进行，也就是发生STOP THE WORLD
2. 如果不移动存活对象，空间碎片化问题就只能依赖更为复杂的内存分配器和内存访问器来解决
   整理算法相对于标记清除算法的本质差异在于，前者是一种移动式的回收算法，后者是非移动式的。