垃圾收集算法

在前面的引用计数法和可达性算法一文中，我们讲了一个引用要被回收需要达到的条件以及怎么判断一个引用是否要被回收。了解了这些知识，就到了今天要讲的垃圾收集算法。

垃圾收集算法分为几种：标记-清除、复制、标记-整理和分代收集算法。每个收集算法都不是独立存在的，一个收集算法在另一个收集算法也有引用到，比如分代收集算法的新生代就是使用的复制算法。话不多说，下面就来说说这几种垃圾收集算法吧。

标记-清除算法

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

标记-清除算法的优点就是简单，只需要将需要回收的对象标记出来，到了回收的时候，直接回收就是了。但是缺点也很明显：

• 效率不高，标记和清除两个过程的效率都不高
• 会产生空间碎片。会产生大量的空间碎片，空间碎片太多可能会导致以后的程序运行过程中需要分配较大对象时，无法找到足球的连续内存而不得不出发另一个垃圾收集动作。

复制算法

为了解决标记-清除算法的缺点，出现了一个新的回收算法：复制算法。

回收算法主要的流程是：将可用的容量划分为大小相等的两块，每次只使用其中的一块。当这一块的内存用完了，就将还存活着的对象复制到另一块上面没然后在把已使用过的内存空间一次清理掉。

虽然这种收集算法能够解决内存碎片的问题，但是将内存缩为了原来的一半，代价有点高。这个算法也是后面要讲的分代收集算法的基础。

标记-整理算法

既然标记清除算法和复制算法有各种各样的缺点，那么中和一下这两个算法的优缺点，又有一个新的回收算法有闪亮登场了： 标记整理算法。

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

简单总结

在讲分代收集算法之前，我们先对上面讲到的几个算法作一个小总结。

标记清理和标记整理算法都是先对需要回收的对象进行标记，标记清理的后续操作是将标记的对象进行清除，而标记整理算法是将存活的对象都向一段移动，然后直接清理掉端边界以外的内存。复制算法是将内存划分为大小相等的两块，每次只使用其中一块，当启动一块使用完了，就换到另一块使用，把这一块清理掉。

标记清理算法的缺点很明显，很容易造成内存碎片，但贵在简单。复制算法的缺点也很明显，只使用其中一块内存，那就很浪费内存，但确是解决了内存碎片的问题。

上面的三个收集算法是下面要讲的这个垃圾收集算法基础。

分代收集算法

分代收集算法就是根据对象存活周期的不同将内存划分为几块，一般是把Java堆分为新生代和老年代。

在新生代中，每次垃圾收集时都发现有大批对象死去，只有少量存活，那就算用复制算法。只需要付出少量存活对象的复制成本就可以完成收集。而老年代中因为对象存活率高，没有额外空间对它进行分配担保，就必须使用“标记-清理”或者“标记-整理”算法来进行回收。

由于目前的商业虚拟机几乎都是使用分代收集算法，所以我们就重点讲讲分代收集算法。

分代收集算法的思想是，将Java堆中的内存区域分为年轻代和老年代（Tenured Gen），如果再细分的话，年轻代有区分为： Eden区和Survivor区 。Survivor区又可以细分为From区和To区。如果要用的图形的方式表现出来，就如同下面的图示。

内存分代

Eden 区, From space, To space。默认比例是8:1:1。

内存分配和回收策略

对象主要分配在新生代的Eden区上，如果启动了本地线程分配缓冲，将按线程有限的TLAB上分配。少数情况下也可能会直接分配在老年代中，分配规则并不是百分之百固定的，其细节取决于当前使用的哪一种垃圾收集器组合，还有虚拟机中与内存相关的参数的设置。

主要有下面几种普遍的分配策略

对象优先在Eden分配

大多数情况下，对象在新生代Eden区中分配。当Eden区没有足够空间进行分配时，虚拟机将发起一次MinorGC。

虚拟机提供了-XX:+PrintGCDetails这个收集器日志参数，告诉虚拟机在发生垃圾收集行为时打印内存回收日志，并且在进程退出的时候输出当前的内存各区域分配情况。

新生代主要使用的复制算法。

大对象直接进入老年代

所谓大对象是指，需要大量连续内存空间的Java对象。最典型的大对象就是那种很长的字符串以及数组。

虚拟机提供了一个-XX:PretenureSizeThreshold参数，令大于这个设置值的对象直接在老年代分配。这样做的目的是米边Eden区及两个Survivor区之间发生大量的内存复制（新生代采用复制算法收集内存）。

长久存活的对象将进入老年代

虚拟机为了识别哪些对象应该放在年轻代，哪些对象应该放在老年代。为了做到这一点，虚拟机给每个对象定义了一个对象年龄（Age）计数器。如果对象在Eden出生并经过第一次MinorGC后仍然存活，并且能被Survivor容纳的话，将被移动到Survivor空间中，并且对象年龄设为1。对象在Survivor区中每经历一次Minor GC，年龄就增加1，当它的年龄增加到一定程度（默认15），就将被晋升到老年代中。对象晋升老年代的年龄阈值，可以通过参数-XX:MaxTenuringThreshold设置。

老年代主要使用标记清除算法。

动态对象年龄判定

为了能更好适应不同程序的内存状况，虚拟机并不是永远地要求对象的年龄必须达到了MaxTenuringThreshold才能晋升老年代，如果在Survivor空间中相同年龄所有对象大小的总和大于Survivor空间一半，年龄大于或等于该年龄对象就可以直接进入老年代，无须等到MaxTenuringThreshold中要求的年龄。

MinorGC和FullGC

新生代GC（MinorGC）：指发生在新生代的垃圾收集动作，因为Java对象大多都具备朝生夕灭的特性，所以MinorGC非常频繁，一般回收速度也比较快。

老年代GC（Major GC/Full GC)：指发生在老年代的GC，出现了Major GC，经常会伴随至少一次的MinorGC(但非绝对的，在Parallel Scavenge收集器的手机策略里就有直接进行Major GC的策略选择过程）。Major GC的速度一般会比MinorGC慢10倍以上。

需要注意的是，MinorGC是发生在新生代，FullGC是发生在老年代

在面试的时候，有一个知识点，就是什么时候会发生MinorGC？什么时候发生FullGC？这里我们也来说说吧。

MinorGC和FullGC的触发条件

什么时候触发MinorGC？

1. Eden区没有足够的内存空间的时候，会触发MinorGC。即申请一个对象时，发现Eden区不够用，则触发一次MinorGC。MinorGC时，会把存活的对象复制到To space区域，如果To space区域不够，则利用担保机制进入老年代区域。

什么时候触发FullGC？

1. 调用System.gc时，系统建议执行Full GC，但是不必然执行。
2. 老年代空间不足
3. 方法区空间不足
4. 通过Minor GC后进入老年代的平均大小大于老年代的可用内存。GMS GC时出现promotion failed（在进行minorGC时，Survivor space放不下，分配担保时担保失败，对象只能放入老年代，然而此时老年代也放不下）,oncurrent mode failure（在进行GMS GC过程中同时有对象要放入老年代中，而此时老年代空间不足）。
5. 由Eden区、From Space区向To Space区复制时，对象大小大于To Space可用内存，则把该对象转存到老年代，且老年代的可用内存小于该对象大小

简单总结

在说下面几个知识点之前，先来对分代收集算法做一个简单总结。

分代收集算法是根据对象的存活周期将内存空间分为了不同的空间，比如说年轻代和老年代。年轻代还可以细分为Eden区和Survivor区，Survivor区在细分又可以分为From区和To区。分代收集算法定义了一定的内存分配和回收策略：对象优先在Eden分配、大对象直接进入老年代以及长久存活的对象将进入老年代。这三个策略可以说是见名知意，这里不多做赘述。后面会讲一个空间分配担保，这个知识点也详细解释了这三个策略的原因。

然后就是MinorGC和FullGC，Minor GC发生在年轻代，Full GC 发生在老年代，这两个GC 有不同的触发条件，这里也不做赘述。

上面说到了分代收集算法的内存分配和回收策略，下面来讲讲这几个策略的具体原因。

空间分配担保

在发生MinorGC 之前，虚拟机会先检查老年代最大可用的连续空间是否大于新生代所有对象总空间，如果这个条件成立，那么MinorGC可以确保是安全的，如果不成立，则虚拟机会查看HandlePromotionFailure设置值是否允许担保失败，如果允许，那么会继续检查老年代最大可用的连续空间是否大于历次晋升到老年代对象的平均大小，如果大于，则尝试着进行一次MinorGC，尽管这次MinorGC是有风险的：如果小于，或者HandlePromotionFailure设置不允许冒险，那么这时也要改为进行一次FullGC。

下面解释一下“冒险”是冒了什么风险，前面提到过，新生代使用复制收集算法，但是为了内存利用率，只使用起一个Survivor空间来作为轮换备份，因此当出现大量对象在MinorGC后仍然存活的情况（最极端的情况就是内存回收或新生代的所有所有对象都存活），就需要老年代进行分配担保吗，把Survivor无法容纳的对象直接进入老年代。与生活中的贷款担保类似，老年代要进行这样的担保，前提是老年代本身还有容纳这些对象的剩余空间，一共有多少对象会活下来在实际完成内存回收之前是无法明确知道的，所以只好取之前每一次回收晋升到老年代对象容量的平均大小值作为经验值，与老年代的剩余空间进行比较，决定是否进行FullGC来让老年代腾出更多空间。

取平均值进行比较仍然是一种动态概率的手段，也就是说，如果某次MinorGC存活后的对象突增，远远高于平均值的话，依然会导致担保失败（Handle Promotion Failure）。

HotSpot的算法实现

这里主要讲HotSpot虚拟机对于上面的收集算法的实现。

枚举根节点

可作为GC Roots的节点主要在全局性的引用与执行上下文中，现在很多应用仅仅方法区就有数百兆，如果要逐个检查这里面的引用，那必然会消耗很多时间。

另外，可达性分析对执行时间的敏感还体现在GC停顿上，因为这项分析工作必须在一个能确保一致性的快照中进行-这里“一致性”的意思是指整个分析期间真个执行系统看起来就像被冻结在某个时间点上，不可能出现分析过程中对象引用关系还在不断变化的情况，该点不满足的话分析结果准确性就无法得到保证。这点导致GC进行时必须停顿所有Java执行线程（Sun将这件事情成为“Stop-The-World”）的其中一个重要原因，即使是在号称（几乎）不会发生停顿的CMS收集器中，枚举根节点时也是必须要停顿的。

Java虚拟机通过一组称为OopMap的数据结构来达到记录那些地方存放对象引用的目的，在类加载完成的时候，HotSpot就把对象内什么偏移量上是什么类型的数据计算出来，在JIT编译过程中，也会在特定的位置记录下栈和寄存器中那些位置是引用，这样，GC在扫描时就可以直接得知是什么信息了。

安全点

在OopMap的协助下，HotSpot可以快速且准确地完成GC Roots枚举。但是如果引用引用关系变化，OopMap的也会相应变化，这样会造成很多空间浪费。

实际上，HotSpot没有为每条指令都生成OopMap，只是在特定的位置记录了这些信息，这些位置被称为安全点（safepoint），即程序执行时并非在所有的地方都停下来开始GC，只有在到达安全点时才能暂停。

安全点的选定不能太少导致GC等待时间太长，也不能太频繁导致过分增大运行时的负荷。

对于安全点，还需要考虑如何在GC发生时让所有线程都跑到最近的安全点上在停顿下来。这里有两种方案：

• 抢先式中断 ：不需要线程的执行代码主动去配合，在GC发生时，首先把所有线程全部中断，如果发现有线程中断的地方不在安全点上，就恢复线程，让它跑到安全点上。
• 主动式中断：思想是当GC需要中断线程的时候，不直接对线程操作，仅仅简单地设置一个标志，各个线程执行时主动去轮询这个标志，发现中断标志为真时就自己中断挂起，轮询标志的地方和安全点是重合的。

分代收集算法

分代收集算法就是根据对象存活周期的不同将内存划分为几块，一般是把Java堆分为新生代和老年代。

在新生代中，每次垃圾收集时都发现有大批对象死去，只有少量存活，那就算用复制算法。只需要付出少量存活对象的复制成本就可以完成收集。而老年代中因为对象存活率高，没有额外空间对它进行分配担保，就必须使用“标记-清理”或者“标记-整理”算法来进行回收。

由于目前的商业虚拟机几乎都是使用分代收集算法，所以我们就重点讲讲分代收集算法。

分代收集算法的思想是，将Java堆中的内存区域分为年轻代和老年代（Tenured Gen），如果再细分的话，年轻代有区分为： Eden区和Survivor区 。Survivor区又可以细分为From区和To区。如果要用的图形的方式表现出来，就如同下面的图示。

内存分代

我们来说说年轻代

年轻代

我可以从上图中可以看到，年轻代分为三个区域：Eden区和两个Survivor区。

当年轻代中的 Eden 区分配满的时候，就会触发年轻代的 GC （Minor GC），具体过程如下：

• 在 Eden 区执行了第一次 GC 之后，存活的对象会被移动到其中一个 Survivor 分区（form）
• Eden 区再次GC，这是会采用复制算法，将 Eden 和 from 区一起清理掉。存活的对象会被复制到 to 区；接下来，只需要清空 from 区就可以了。

这个过程中，总会有一个Survivor分区是空置的。Eden 区, From space, To space。默认比例是8:1:1。也就是说只有 10% 的的空间被浪费了。

我们可以通过参数： -XX:SurvivorRatio参数进行配置这个比例。

内存分配和回收策略

对象主要分配在新生代的Eden区上，如果启动了本地线程分配缓冲，将按线程有限的TLAB上分配。少数情况下也可能会直接分配在老年代中，分配规则并不是百分之百固定的，其细节取决于当前使用的哪一种垃圾收集器组合，还有虚拟机中与内存相关的参数的设置。

TLAB 的全称是：ThreadLocal Allocation Buffer，JVM 默认给每个线程开辟一个 buffer 区域，用来加速对象分配，这个 buffer 就放在 Eden 区中。

对象的分配优先在 TLAB 上，但是 TLAB 通常都很小，所以对象相对比较大的时候，会在 Eden 去的共享区域进行分配。

这个道理和 Java 语言中的 ThreadLocal 类似，避免了对公共区的操作，以及一些锁竞争。

主要有下面几种普遍的分配策略

对象优先在Eden分配

大多数情况下，对象在新生代Eden区中分配。当Eden区没有足够空间进行分配时，虚拟机将发起一次MinorGC。

虚拟机提供了-XX:+PrintGCDetails这个收集器日志参数，告诉虚拟机在发生垃圾收集行为时打印内存回收日志，并且在进程退出的时候输出当前的内存各区域分配情况。

新生代主要使用的复制算法。

老年代

老年代一直使用标记-清除 、标记-整理算法，因为老年代的对象存活率一般是比较高的，空间比较大，拷贝起来并不划算，还不如采用就地收集的方式。

那么对象是如何“提升”到老年的？

提升

如果对象达到一定年龄，会通过“提升”进入老年代。

虚拟机为了识别哪些对象应该放在年轻代，哪些对象应该放在老年代。为了做到这一点，虚拟机给每个对象定义了一个对象年龄（Age）计数器。如果对象在Eden出生并经过第一次MinorGC后仍然存活，并且能被Survivor容纳的话，将被移动到Survivor空间中，并且对象年龄设为1。对象在Survivor区中每经历一次Minor GC，年龄就增加1，当它的年龄增加到一定程度（默认15），就将被晋升到老年代中。

对象晋升老年代的年龄阈值，可以通过参数-XX:MaxTenuringThreshold设置。

大对象直接进入老年代

所谓大对象是指，需要大量连续内存空间的Java对象。最典型的大对象就是那种很长的字符串以及数组。

虚拟机提供了一个-XX:PretenureSizeThreshold参数，令大于这个设置值的对象直接在老年代分配。这样做的目的是米边Eden区及两个Survivor区之间发生大量的内存复制（新生代采用复制算法收集内存）。

分配担保

每次存活的对象，都会放入其中一个幸存区，这个区域默认的比例是10%。但是我们无法保证每次存活的对象都小于 10%，就需要依靠其他内存（指老年代）进行分配担保。这个时候，对象也会直接在老年代上分配。

至于分配担保，我们下面还会细讲。

动态对象年龄判定

为了能更好适应不同程序的内存状况，虚拟机并不是永远地要求对象的年龄必须达到了MaxTenuringThreshold才能晋升老年代，如果在Survivor空间中相同年龄所有对象大小的总和大于Survivor空间一半，年龄大于或等于该年龄对象就可以直接进入老年代，无须等到MaxTenuringThreshold中要求的年龄。

卡片标记 （card marking）

对象的引用关系是一个巨大的网状，有的对象可能在 Eden 区，有的可能在老年代，那么这种跨代的引用是如何处理的呢？由于 MInor GC 是单独发生的，如果一个老年代的对象引用了它，如何确保能够让年轻代的对象存货呢？

对于是否的判断，我们通常都会用到 Bitmap（位图）和 布隆过滤器来加快搜索的速度。

JVM 的老年代是被分成了 众多的 卡页（card page）的。

卡表（card Table） 就是用于标记卡页状态的一个集合，每个卡表项对应一个卡页。

如果年轻代有对象分配，而且老年代有对象指向这个新对象，那么这个老年代对象所对应内存的卡页，就会标识为 dirty，卡表只需要非常小的存储空间就可以保留这些状态，垃圾回收时，就可以先读这个表，进行快速判断。

我们看完了上面，下面来一张图来总结一下垃圾回收。

IMG_0025

MinorGC和FullGC

新生代GC（MinorGC）：指发生在新生代的垃圾收集动作，因为Java对象大多都具备朝生夕灭的特性，所以MinorGC非常频繁，一般回收速度也比较快。

老年代GC（Major GC/Full GC)：指发生在老年代的GC，出现了Major GC，经常会伴随至少一次的MinorGC(但非绝对的，在Parallel Scavenge收集器的手机策略里就有直接进行Major GC的策略选择过程）。Major GC的速度一般会比MinorGC慢10倍以上。

需要注意的是，MinorGC是发生在新生代，FullGC是发生在老年代

在面试的时候，有一个知识点，就是什么时候会发生MinorGC？什么时候发生FullGC？这里我们也来说说吧。

MinorGC和FullGC的触发条件

什么时候触发MinorGC？

1. Eden区没有足够的内存空间的时候，会触发MinorGC。即申请一个对象时，发现Eden区不够用，则触发一次MinorGC。MinorGC时，会把存活的对象复制到To space区域，如果To space区域不够，则利用担保机制进入老年代区域。

什么时候触发FullGC？

1. 调用System.gc时，系统建议执行Full GC，但是不必然执行。
2. 老年代空间不足
3. 方法区空间不足
4. 通过Minor GC后进入老年代的平均大小大于老年代的可用内存。GMS GC时出现promotion failed（在进行minorGC时，Survivor space放不下，分配担保时担保失败，对象只能放入老年代，然而此时老年代也放不下）,oncurrent mode failure（在进行GMS GC过程中同时有对象要放入老年代中，而此时老年代空间不足）。
5. 由Eden区、From Space区向To Space区复制时，对象大小大于To Space可用内存，则把该对象转存到老年代，且老年代的可用内存小于该对象大小

简单总结

在说下面几个知识点之前，先来对分代收集算法做一个简单总结。

分代收集算法是根据对象的存活周期将内存空间分为了不同的空间，比如说年轻代和老年代。年轻代还可以细分为Eden区和Survivor区，Survivor区在细分又可以分为From区和To区。分代收集算法定义了一定的内存分配和回收策略：对象优先在Eden分配、大对象直接进入老年代以及长久存活的对象将进入老年代。这三个策略可以说是见名知意，这里不多做赘述。后面会讲一个空间分配担保，这个知识点也详细解释了这三个策略的原因。

然后就是MinorGC和FullGC，Minor GC发生在年轻代，Full GC 发生在老年代，这两个GC 有不同的触发条件，这里也不做赘述。

上面说到了分代收集算法的内存分配和回收策略，下面来讲讲这几个策略的具体原因。

空间分配担保

在发生MinorGC 之前，虚拟机会先检查老年代最大可用的连续空间是否大于新生代所有对象总空间，如果这个条件成立，那么MinorGC可以确保是安全的，如果不成立，则虚拟机会查看HandlePromotionFailure设置值是否允许担保失败，如果允许，那么会继续检查老年代最大可用的连续空间是否大于历次晋升到老年代对象的平均大小，如果大于，则尝试着进行一次MinorGC，尽管这次MinorGC是有风险的：如果小于，或者HandlePromotionFailure设置不允许冒险，那么这时也要改为进行一次FullGC。

下面解释一下“冒险”是冒了什么风险，前面提到过，新生代使用复制收集算法，但是为了内存利用率，只使用起一个Survivor空间来作为轮换备份，因此当出现大量对象在MinorGC后仍然存活的情况（最极端的情况就是内存回收或新生代的所有所有对象都存活），就需要老年代进行分配担保吗，把Survivor无法容纳的对象直接进入老年代。与生活中的贷款担保类似，老年代要进行这样的担保，前提是老年代本身还有容纳这些对象的剩余空间，一共有多少对象会活下来在实际完成内存回收之前是无法明确知道的，所以只好取之前每一次回收晋升到老年代对象容量的平均大小值作为经验值，与老年代的剩余空间进行比较，决定是否进行FullGC来让老年代腾出更多空间。

取平均值进行比较仍然是一种动态概率的手段，也就是说，如果某次MinorGC存活后的对象突增，远远高于平均值的话，依然会导致担保失败（Handle Promotion Failure）。

HotSpot的算法实现

这里主要讲HotSpot虚拟机对于上面的收集算法的实现。

枚举根节点

可作为GC Roots的节点主要在全局性的引用与执行上下文中，现在很多应用仅仅方法区就有数百兆，如果要逐个检查这里面的引用，那必然会消耗很多时间。

另外，可达性分析对执行时间的敏感还体现在GC停顿上，因为这项分析工作必须在一个能确保一致性的快照中进行-这里“一致性”的意思是指整个分析期间真个执行系统看起来就像被冻结在某个时间点上，不可能出现分析过程中对象引用关系还在不断变化的情况，该点不满足的话分析结果准确性就无法得到保证。这点导致GC进行时必须停顿所有Java执行线程（Sun将这件事情成为“Stop-The-World”）的其中一个重要原因，即使是在号称（几乎）不会发生停顿的CMS收集器中，枚举根节点时也是必须要停顿的。

Java虚拟机通过一组称为OopMap的数据结构来达到记录那些地方存放对象引用的目的，在类加载完成的时候，HotSpot就把对象内什么偏移量上是什么类型的数据计算出来，在JIT编译过程中，也会在特定的位置记录下栈和寄存器中那些位置是引用，这样，GC在扫描时就可以直接得知是什么信息了。

安全点

在OopMap的协助下，HotSpot可以快速且准确地完成GC Roots枚举。但是如果引用引用关系变化，OopMap的也会相应变化，这样会造成很多空间浪费。

实际上，HotSpot没有为每条指令都生成OopMap，只是在特定的位置记录了这些信息，这些位置被称为安全点（safepoint），即程序执行时并非在所有的地方都停下来开始GC，只有在到达安全点时才能暂停。

安全点的选定不能太少导致GC等待时间太长，也不能太频繁导致过分增大运行时的负荷。

对于安全点，还需要考虑如何在GC发生时让所有线程都跑到最近的安全点上在停顿下来。这里有两种方案：

• 抢先式中断 ：不需要线程的执行代码主动去配合，在GC发生时，首先把所有线程全部中断，如果发现有线程中断的地方不在安全点上，就恢复线程，让它跑到安全点上。
• 主动式中断：思想是当GC需要中断线程的时候，不直接对线程操作，仅仅简单地设置一个标志，各个线程执行时主动去轮询这个标志，发现中断标志为真时就自己中断挂起，轮询标志的地方和安全点是重合的。