码恋
ALL YOUR SMILES, ALL MY LIFE.
JVM 系列之垃圾回收算法
一、概述
在 JVM 中，内存运行时数据区被分为 Java 虚拟机堆、方法区、程序计数器、Java 虚拟机栈、本地方法栈。
其中程序计数器、Java 虚拟机栈、本地方法栈为线程私有，栈中的栈帧随着方法的进入和退出执行着入栈和出栈操作，每个栈帧中需要分配多大的内存在程序编译完成后就基本可以确定，随着线程生命周期的结束，占用的内存就随之被回收了。
而堆和方法区就不一样了，程序在运行时，会执行到不同的分支，这时我们才能知道要创建什么样的对象，创建多少个，也就是说需要分配多大的内存需要在运行时才能确定，这部分的内存是动态的分配和回收的。JVM 就是主要针对这部分内存做垃圾回收。
二、如何确定对象已经死亡
堆中存放着 JVM 中的大多数对象，在回收这些对象前，重要的步骤之一是首先判断哪些对象存活，哪些对象是在死亡状态，这些在死亡状态的对象已经无用，需要被回收释放其占用的内存。
1. 引用计数法
我们知道正在被使用的对象是不能被回收的，判断对象是否死亡比较容易想到的方法是，在对象头中维护对象被其他对象引用的计数器，如果被引用的数量为 0 ，则认为对象已经死亡，可以被回收了。
引用计数法实现原理简单，判定对象存活只需查看对象的引用计数器，执行效率很高，但是在大多数的 Java 垃圾回收器中并没有使用这种算法来判断对象的存活情况。
主要原因是，这个看起来简单的算法需要考虑很多例外的情况，需要做大量额外的处理来保证其正常工作，它很难解决对象之间的循环引用问题，比如 A 对象的成员变量引用了 B 对象，而 B 对象的成员变量又引用了 A 。如此，两个对象的引用计数一直不为 0 ，导致对象无法回收。但是对程序来讲，这两个对象已经无用了，是垃圾对象。
2. 可达性分析法
如下图所示，定义一些称之为 GC Roots 的集合，如果一个对象存在从 GC Roots 到该对象的引用路径，则认为该对象是存活的。反之，就认为这个对象不会再被使用了。这个引用路径称之为引用链，从 GC Roots 搜寻到一个对象的引用链的过程，就是可达性分析法。
❀ 在 Java 中可以作为 GC Roots 的对象：
a) 虚拟机栈中引用的对象（栈帧中的本地变量表）；
b) 方法区中类静态属性引用的对象；
c) 方法区中常量引用的对象；
d) 本地方法栈中 Native 方法引用的对象；
e) Java 虚拟机内部引用的对象，如基本类型对应的 Class 对象；
f) 所有被同步锁（synchronized 关键字）锁定的对象；
g) 反映 Java 虚拟机内部情况的 JMXBean 、本地代码缓存等；
除了上述这些固定的 GC Roots 集合以外， 根据用户选择的垃圾回收器和内存回收区域的不同，还有一些对象可以临时性的加入，共同构成 GC Roots 集合。
3. Java 中的引用类型
无论是引用计数法还是可达性分析法，都离不开“引用”。按照引用强度的大小，分为强引用、软引用、弱引用、虚引用。
- 强引用，即
Object obj = new Object这种赋值的方式。只要这种引用方式存在，对象就不会被回收。 - 软引用，用来描述一些还有用，但是非必须的对象。只被软引用关联的对象，在内存溢出前，会将这些对象加入回收列表进行二次回收，如果回收之后还没有足够的内存，才会排除内存溢出异常。可以使用 SoftReference 创建一个软引用。
- 弱引用，也用来描述一些非必须的对象，它比弱引用更弱一些，只被弱引用关联的对象，只能生存到发生下一次垃圾回收为止，无论内存是否足够，都会对这些对象进行回收。可以使用 WeakReference 创建弱引用。
- 虚引用，只被虚引用关联的对象，不会对对象的生命周期造成任何影响，也无法通过虚引用来获得一个对象实例，它的唯一作用就是对象在被垃圾回收时收到一个系统通知。可以使用 PhantomReference 创建一个虚引用。
4. finalize() 方法
在可达性分析中，一个对象被判定为不可达后，并不代表这个对象就死亡了，一个对象最多会经历两次标记，在进行 GC Roots 可达性分析时，发现对象没有引用链会对对象进行第一次标记，并加入筛选列表进行第二次筛选，判断对象是否有必要执行 finalize() 方法。如果一个对象没有继承 finalize() 方法或 finalize() 方法已经被虚拟机调用过，则认为没有必要执行了。
由此，对象其实可以在 finalize() 中通过赋值引用的方式来拯救自己，并不是不可达了就死亡了。
三、垃圾回收算法
1. 分代收集理论
分代收集理论建立在两个假说之上：
- 弱分代假说：绝大多数对象都是朝生夕死的。
- 强分代假说：熬过多次垃圾回收的对象就越难以消亡。
基于此我们可以将这两类对象分别存储在不同的内存区域，在做垃圾回收时，绝大多数对象是是朝生夕死的（年轻代），只需要标记存活的对象而不是大量消亡的对象，就能以较低的代价清理出大量的内存空间；同时把熬过多次垃圾回收的对象放入另一个区域（老年代），就能以较低的频率对这个区域做垃圾回收。这样既能节省垃圾回收的时间开销，又能有效的利用内存空间。
将 Java 堆划分不同的区域后，每次垃圾回收只需要关注一块或多个区域了。但是有一个很明显的问题：不同区域的对象是存在着跨代引用的。
为了解决这一问题，就有了第三条假说：
- 跨代引用假说：存在跨带引用的对象数量相对同代引用来说是极少的。
其实这条假说是基于上面两条的一个推论：存在互相引用的两个对象，因该是趋向于同时生存或者消亡的。假设对象 A, B 是存在跨带引用的，随着 B 进入老年代越来越难以消亡，A，B 存在着引用，A 也同时难以消亡，随之进入老年代，这时就不存在跨带引用了。
因为不必为了相对极少的跨带引用对象去扫描整个老年代，也不必花费额外的内存空间记录哪些兑现存在着跨带引用。只需在年轻代维护一块内存空间（记忆集）记录老年代那个内存区域存在着跨带引用，发生 Young GC （指对年轻代进行垃圾回收，与之对应的有 Minor GC / Young GC、Major GC / Old GC、Full GC 等）时，将其加入 GC Roots 扫描即可。在运行时，虽然增加了维护记忆集的变化的开销，但是相比扫描这个老年代而言，还是很划算的。
2. 标记-清除算法
标记-清除算法即先标记处待回收的垃圾对象，然后回收其内存区域。
这种算法存在两个缺点：一是这回收过程中需要大量标记，清除动作。随着堆中对象数量的增长，执行效率越来越低；二是会产生内存碎片，导致在分配大对象时有可能没有连续的内存，提前触发再一次垃圾回收。
3. 标记-复制算法
标记-复制算法即先将堆划分为两个区域，新建对象时只使用其中一个区域分配内存，发生 GC 时先标记存活的对象，然后将存活的对象复制到另一块空间中，然后再清空之前的空间。
对象存活的数量较多时，需要做大量的复制操作，将会产生大量的空间复制开销。但是在对象存活数量较少时，只需复制少量的对象，然后一次性清理之前使用的空间。在复制时只需按照顺序分配另一块的内存即可，不会产生内存碎片问题，算法简单高效，标记-复制算法特别适合对于年轻代的垃圾回收。
这种算法最大的缺点显而易见：分配对象时只使用了一半空间，有很严重的空间浪费。
针对这个问题，其实可以通过调整前后两块内存空间的占比来优化，具体的做法是：在 JVM 中，将堆的空间主要分为两部分，年轻代和老年代，同时对于年轻代又划分为 Eden 区域、From 区域和 To 区域。
新建的对象被分配到 Eden Space 中，当 Eden 区域空间满时，就触发一次 Young GC，已经不被使用的做回收处理，而仍然被使用的则被复制到 From 区域。经过这个过程，整个Eden区域就是空闲的，如果有新的对象，就 Eden 区域中创建。如果Eden区域的内存再次被用完，就再一次触发了 Young GC ，这时就将 Eden 区域和 From 区域中还在使用的对象复制到 To 区域。下一次 Young GC 则是将 Eden 区域和 To 区域中还在使用的对象全部复制到 From 区域。
如此，经过多次 Young GC 后，会存在某些对象在 From 区域和 To 区域进行多次复制，如果超过某个阈值对象仍然没有释放，则将这些对象复制到 Old Generation。如果Old Generation 区域也用完之后，就会触发 Full GC ，全量回收会对系统的性能造成非常大的影响，所以可以根据各应用的特点和对象的生命周期来设置一个合理的年轻代与老年代的大小值，尽量减少 Full GC。
在 HotSpot 虚拟机中，默认 Eden 和 Survivor（指其中的一块） 的大小比例是 8 ：1，即只浪费了 10 % 的空间。当 Survivor 的空间无法存储仍在存活的对象时，会有类似逃生门的机制，直接进入老年代空间。
4. 标记-整理算法
标记-复制算法在对象存活率较高时，就要随之进行更多的复制操作，效率也随之降低。同时如果不想浪费一半的内存空间，就要提供上述的逃生门机制，需要有其他内存空间托底。因此这种算法并不适合对老年代进行回收。
标记-整理算法通常用来回收老年代，它的过程是这样的：在发生老年代回收时，首先标记存活的对象，然后将存活对象向内存的一端移动，最后清理掉边界以外的内存区域。
四、Hotspot 的算法实现
上面综述了对象存活的判定方法和垃圾回收算法，不同的虚拟机的对于具体的实现会有所差异，这里我们结合 HotSpot 虚拟机来具体看下。
1. 根节点枚举
在做可达性分析时，首先要列举出 GC Roots 集合，然后再从这些根节点出发，做遍历。在文章的上面列举了可以作为 GC Roots 的对象，其中固定可以做为根节点的对象主要存在全局性的引用（常量、静态变量等）和执行上下文（栈帧中的本地变量表）中。虽然目标明确，但是现代 Java 应用的对象数量实在是太多了，要做到高效的查找，从这里出发肯定需要消耗不少的时间。
在虚拟机中，其实不需要一个一个的检查完所有的全局引用位置和执行上下文，而是使用了特殊的数据结构来存储这个根节点，HotSpot 使用了 OopMap 来实现。
OopMap 存储了 Java 对象的内存布局和状态信息，包括对象引用的位置信息，因此它可以被用来识别活动对象。在根节点枚举的过程中，垃圾收集器会查看 OopMap 来判断特定字节码位置上哪些寄存器或栈帧槽位包含对象引用，这些引用是根集中的对象或活动对象。如果一个寄存器或槽位包含对象引用，那么垃圾收集器将递归遍历该引用指向的对象以及该对象引用的其他对象，并将它们标记为活动对象。
2. 安全点
直到现在，所有的垃圾收集器在根节点枚举时都要暂停用户的线程，称其为 “Stop The World”。这时因为，在分析的过程中，如果根节点集合的引用关系还在不断地变化之中的话，那么分析的准确性就无法得到保障。
那么就需要找到一些在程序运行时可以进行根节点枚举的点，这些点叫做安全点。
安全点的选择基本上是以“是否具有让程序长时间执行的特征”为标准进行选定的。
能否让程序长时间执行的明显特征就是指令复用，如方法调用、循环跳转等，在这些指令才会产生安全点，并生成对应的 OopMap 。
在安全点上，根节点集合的引用关系不会发生变化，这时就可以暂停用户的线程，在这里开始垃圾收集。那么如何让程序的线程都跑到最近的安全点呢？
这里有抢占式中断和主动式中断两种方式：
- 抢占式中断
抢占式中断不需要线程的执行代码主动配合，在发生垃圾收集时，系统首先中断用户的所有线程，如果发现有线程不在安全点上，则回复该线程的执行，直到到达最近的安全点再重新中断。 - 主动式中断
主动式中断是当发生垃圾回收时，不直接中断线程，而是设置一个标志位，其他线程不断轮训这个标志位，一旦发现中断标志为真时，就在最近的安全点上主动挂起线程。
3. 安全区
当程序执行时，线程可以在不长的时间中走到最近的安全点，但是当线程处于 sleep 或 block 状态时，就无法主动走到安全点了，虚拟机也不可能一直等待线程被重新激活分配 CPU 时间。对于这个问题，引入了安全区域来解决。
安全区域与安全点相似，能够在一段代码片段中，保证引用关系不会发生变化，因此在这个区域内发生垃圾回收就是安全的。
具体实现是，当线程执行到安全区域的代码片段时，会标识自己已经进入了安全区域，这样虚拟机就不需要管已经在安全区域的线程了。另一方面，如果线程在重新获得 CPU 时间片时，先判断是否在垃圾回收需要暂停用户线程的阶段，如果在就继续等待，直到收到可以离开安全区域的信号为止，否则就照常执行。
4. 记忆集与卡表
上面在说分代回收的时候，提到了记忆集，用来解决对象跨带引用的问题。记忆集是用来标识从非回收区域指向被回收区域的一组指针的抽象数据结构。
如何实现记忆集，比较容易想到的方式是维护一个 map ，存储存在跨代引用的对象。但是这种方式，占用的内存很多，同时随着对象引用的变化，维护成本也相当高昂。
在虚拟机实现的时候，可以采用更粗略的范围存储来减少内存开销和维护成本，而不是直接存储对象：
- 粗略记忆集（Coarse-Grain Remembered Set）：它记录了所有老年代对象中引用年轻代的位置。这种记忆集的精度较低，需要扫描的对象较多，但是它比较简单，容易实现和维护。
- 细粒度记忆集（Fine-Grain Remembered Set）：它记录了每个老年代对象中所有引用年轻代的位置。这种记忆集的精度较高，可以避免扫描一些不必要的对象，从而提高垃圾收集的效率。但是它需要消耗更多的空间，并且维护成本也比较高。
- 基于卡表的记忆集（Card Table Remembered Set）：它使用了一个类似于分区的概念，将老年代对象划分为多个固定大小的区域，每个区域称为一张卡片（Card）。在垃圾收集时，只需要扫描与年轻代交界的卡片，从而避免扫描所有老年代对象，提高了垃圾收集的效率。此外，基于卡表的记忆集的维护成本相对较低。
HotSpot 采用卡表来实现，卡表的实现是一个字节数组：
CARD_TABLE [this address >> 9] = 1;
字节数组每一个元素都对应着其标识的内存区域的一小块，这个内存块被称为卡页。卡页的大小通常是 2 的 N 次幂字节，HotSpot 的卡页大小是 2 的 9 次幂，即 512 字节。一个卡页中通常存在不止一个对象，如果这些对象中有一个存在跨代引用的话，就把对应的数组元素的值置为 1，称这个元素变脏。在垃圾收集时，只需要找出卡表中变脏的页，就能找出哪些对象存在跨带指针，并将其加入 GC Roots 中。
5. 写屏障
前面说了记忆集的实现，缩减了 GC Roots 枚举范围的问题。那么卡表是如何维护的呢？
当一个老年代对象中的引用发生变化时，需要更新卡表中的信息。具体来说，如果一个引用从老年代对象中指向了一个年轻代对象，那么这个老年代对象所在的卡片就需要被标记为“脏”（Dirty）。类似地，如果一个引用从一个年轻代对象指向了一个老年代对象，那么这个年轻代对象所在的卡片也需要被标记为“脏”。
Java HotSpot 虚拟机中使用了写屏障（Write Barrier）来维护卡表。写屏障是一种在 Java 程序中插入的特殊代码，它能够拦截 Java 程序中所有的写操作，并将修改过的对象标记为“脏”。具体来说，当一个对象的引用被修改时，写屏障会检查该引用指向的对象是否在老年代中，如果是，则会将该对象所在的卡片标记为“脏”。
需要注意的是，写屏障会带来一定的性能开销，因为它会拦截所有的写操作，包括一些不涉及垃圾收集的操作。因此，在某些情况下，可以通过关闭写屏障来提高Java程序的执行效率，但这也会降低垃圾收集的效率。
五、结语
至此为止，我们就了解了 JVM 的垃圾回收算法及其实现。
