jvm 垃圾收集算法详解

垃圾收集算法

分代收集理论

垃圾收集器的理论基础，它建立在两个分代假说之上：

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

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

如果一个区域中大多数对象都是朝生夕灭，难以熬过垃圾收集过程的话，那么把它们集中放在一起，每次回收时只关注如何保留少量存活而不是去标记那些大量将要被回收的对象，就能以较低代价回收到大量的空间；
如果剩下的都是难以消亡的对象，那把它们集中放在一块，虚拟机便可以使用较低的频率来回收这个区域，这就同时兼顾了垃圾收集的时间开销和内存的空间有效利用。

Java堆划分为新生代（Young Generation）和老年代（Old Generation）两个区域。在新生代中，每次垃圾收集时都发现有大批对象死去，而每次回收后存活的少量对象，将会逐步晋升到老年代中存放

标记-清除算法：

基础算法，后面两个算法基于此算法改进

算法分为“标记”和“清除”两个阶段：首先标记出所有需要回收的对象，在标记完成后，统一回收掉所有被标记的对象，也可以反过来，标记存活的对象，统一回收所有未被标记的对象。标记过程就是对象是否属于垃圾的判定过程。该算法两个

缺点：

执行效率不稳定
内存碎片化

标记-复制算法：

将内存分成两块区域，每次只使用其中一块，垃圾回收时，将不可回收的对象复制到另一块区域，然后一次性清除可回收的对象。

优点：

当一次性面对大量可回收对象，只需要复制少量存活对象，然后直接清除另一区域的垃圾对象。并且没有内存碎片。

缺点：

需要浪费一半的存储空间。
如果可回收对象比较少，就要复制大量存活对象到另一个区域，效率降低。不适合对象存活周期较长的场景。

新生代中的对象有98%熬不过第一轮收集。因此并不需要按照1∶1的比例来划分新生代的内存空间。

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之后存活的对象时，就需要依赖其他内存区域（实际上大多就是老年代）进行分配担保。

标记-整理算法：

1.标记阶段，将所有存活的对象进行标记。Java中使用可达性分析算法，从GC Root开始通过引用链遍历出所有存活对象。

2.整理阶段，将存活对象移动到堆的一端。清理掉存活对象的内存空间。

优点：

内存使用效率高，整个堆内存都可以使用，不会像复制算法只能使用半个堆内存
不会发生碎片化，在整理阶段可以将对象往内存的一侧进行移动，剩下的空间都是可以分配对象的有效空间

缺点：

整理阶段的效率不高，整理算法有很多种，比如Lisp2整理算法需要对整个堆中的对象搜索3次，整体性能不佳。可以通过Two-Finger、表格算法、ImmixGC等高效的整理算法优化此阶段的性能

为什么标记-复制适用于新生代，标记-整理适用于老年代？

新生代需要被清理的对象多，复制只需要复制少量存活对象

老年代存活的对象多，不能使用Eden Survivor那套，不然内存就不够了，当然标记-整理也是一项很负重的操作，但如果不整理，就需要额外使用页表等方式标记哪些空间可用来解决空间碎片化问题，这也会导致额外负担，所以从整个程序的吞吐量考虑，标记-整理是较好的选择

当然老年代也可以先标记-清除，等内存空间碎片化到一定程度时，进行一次标记整理

三色标记法：

可达性分析算法中，标记过程需要stop the world，保证全局获得一致性快照，这个操作可否与用户线程并发？

先来看三色标记法：把遍历对象图过程中遇到的对象，按照“是否访问过”这个条件标记成以下三种颜色：

白色：表示对象尚未被垃圾收集器访问过。显然在可达性分析刚刚开始的阶段，所有的对象都是白色的，若在分析结束的阶段，仍然是白色的对象，即代表不可达，需要被回收
黑色：表示对象已经被垃圾收集器访问过，且所有引用了这个对象的对象都已经扫描过。黑色的对象代表已经扫描过，它是安全存活的，不用被回收，如果有其他对象引用指向了黑色对象，无须重新扫描一遍。黑色对象不可能直接（不经过灰色对象）指向某个白色对象。
灰色：表示对象已经被垃圾收集器访问过，但这个对象上至少存在一个引用还没有被扫描过。是个中间态，当扫描完成后，不会出现这个颜色，整个图非黑即白

可达性分析算法其实就是从GC Roots出发，将图（对象直接的引用关系图）波浪式地由白色转为黑色，其中灰色是黑白之间的过渡色。

这个标记法在用户线程和收集器并发工作下可能存在问题：

是把原本消亡的对象错误标记为存活，这不是好事，但其实是可以容忍的，只不过产生了一点逃过本次收集的浮动垃圾而已，下次收集清理掉就好。
把原本存活的对象错误标记为已消亡，这就是非常致命的后果了，程序肯定会因此发生错误

在三色标记法中，当垃圾收集器（GC）与用户线程（Mutator）并发运行时，若同时满足以下两个条件，会导致对象消失问题（即存活对象被错误回收）：

条件一：赋值器插入黑色→白色的新引用

场景：用户线程在标记过程中，为某个已扫描完成的黑色对象（如对象C）新增了一个指向白色对象（如对象B）的引用。
问题：由于黑色对象已被标记为“安全存活”，其引用的对象本应在后续扫描中被处理。但若此时对象B未被及时标记为灰色，GC可能误认为B不可达（仍为白色），从而错误回收它。

条件二：赋值器删除所有灰色→白色的引用

场景：用户线程在标记过程中，删除了所有从灰色对象（如对象A）到白色对象（如对象B）的引用。
问题：灰色对象B原本依赖灰色对象A的引用存活，但A删除对B的引用后，若B未被其他对象引用，GC可能认为B不可达（仍为白色），从而错误回收它。

为何同时满足两个条件会导致对象消失？

初始状态：灰色对象A引用白色对象B（B存活）。
条件二触发：用户线程删除A→B的引用（B失去唯一存活路径）。
条件一触发：用户线程新增C→B的引用（C是已扫描的黑色对象）。
GC视角：
- B在条件二后变为“无引用”，被标记为白色（待回收）。
- C的新引用未被GC及时感知，B未被重新标记为灰色。
- 最终B被错误回收，但C仍持有对B的引用，导致程序错误。

解决方案：破坏任一条件

1. 破坏条件一：禁止黑色→白色的新引用

方法：在插入黑色→白色引用时，强制将白色对象标记为灰色（如通过写屏障）。
效果：新引用的白色对象会被重新扫描，确保其存活性被正确识别。

2. 破坏条件二：禁止删除所有灰色→白色的引用

方法：在删除灰色→白色引用时，记录被删除的白色对象（如通过写屏障）。
效果：即使所有灰色引用被删除，被记录的白色对象仍会被重新标记为灰色，避免被错误回收。

//别人的文档

当标记与用户线程并发时，可能造成以上问题，为了使标记与用户线程并发，减少STW的时间，就需要解决上述问题，由此分别产生了两种解决方案：增量更新和原始快照

增量更新要破坏的是第一个条件，当黑色对象插入新的指向白色对象的引用关系时，就将这个新插入的引用记录下来，等并发扫描结束之后，再将这些记录过的引用关系中的黑色对象为根，重新扫描一次。这可以简化理解为，黑色对象一旦新插入了指向白色对象的引用之后，它就变回灰色对象了。即出现了新的引用关系就记录下来，然后重新扫描
原始快照要破坏的是第二个条件，当灰色对象要删除指向白色对象的引用关系时，就将这个要删除的引用记录下来，在并发扫描结束之后，再以这些白色对象为根，重新扫描一次。这也可以简化理解为，无论引用关系删除与否，都会按照刚刚开始扫描那一刻的对象图快照来进行搜索。（当B删除了N引用之后，B->N 的关系仍然被记录，这个动作通过一个写屏障来实现（可以理解为一个aop）。扫描结束之后再以B为根（被记录的灰色对象为根）重新扫描一次，此时的扫描的B->N的引用已经被重新记录了，即使他实际已经被删除但在这次扫描中它仍然存在。但是这可能导致N在本次垃圾回收时应该被回收，却逃过了这次，不过没关系，下次gc它逃不了）

原始快照相对于增量更新更快，但是可能产生更多的浮动垃圾

增量更新和原始快照这两种解决方案都有实际应用，譬如，CMS是基于增量更新来做并发标记的，G1、Shenandoah则是用原始快照来实现。

分代垃圾回收算法

分代垃圾回收将整个内存区域划分为年轻代和老年代：分代回收时，创建出来的对象，首先会被放入Eden伊甸园区。随着对象在Eden区越来越多，如果Eden区满，新创建的对象已经无法放入，就会触发年轻代的GC，称为Minor GC或者Young GC。Minor GC会把需要eden中和From需要回收的对象回收，把没有回收的对象放入To区。接下来，S0会变成To区，S1变成From区。当eden区满时再往里放入对象，依然会发生Minor GC。

注意：每次Minor GC中都会为对象记录他的年龄，初始值为0，每次GC完加1。如果Minor GC后对象的年龄达到阈值（最大15，默认值和垃圾回收器有关），对象就会被晋升至老年代。当老年代中空间不足，无法放入新的对象时，先尝试minor gc如果还是不足，就会触发Full GC，Full GC会对整个堆进行垃圾回收。如果Full GC依然无法回收掉老年代的对象，那么当对象继续放入老年代时，就会抛出Out Of Memory异常。

程序中大部分对象都是朝生夕死，在年轻代创建并且回收，只有少量对象会长期存活进入老年代。

分代垃圾回收的优点有：

1、可以通过调整年轻代和老年代的比例来适应不同类型的应用程序，提高内存的利用率和性能。

2、新生代和老年代使用不同的垃圾回收算法，新生代一般选择复制算法效率高、不会产生内存碎片，老年代可以选择标记-清除和标记-整理算法，由程序员来选择灵活度较高。

3、分代的设计中允许只回收新生代（minor gc），如果能满足对象分配的要求就不需要对整个堆进行回收(full gc),STW（Stop The World）由垃圾回收引起的停顿时间就会减少。

新生代Minor GC流程：

当Eden区满时，触发Minor GC
标记算法找到所有存活下来的对象
检查老年代最大可用的连续空间是否大于新生代所有存活下来的对象的空间，如果大于，则发起Minor GC。
如果小于，则看 HandlePromotionFailure 有没有设置，如果没有设置，就发起 Full GC。
如果设置了HandlePromotionFailure，则看老年代最大可用的连续空间是否大于历次晋升到老年代对象的平均大小，如果小于，就发起 Full GC。
如果大于，发起 Minor GC。Minor GC 后，看 Survivor 空间是否足够存放存活对象，如果不够，就放入老年代，如果够放，就直接存放 Survivor 空间。如果老年代都不够放存活对象，担保失败（Handle Promotion Failure），发起 Full GC。

HandlePromotionFailure（是否允许进行晋升担保）的作用，当设置为 true 时（默认值），JVM 会尝试继续 Minor GC，即使老年代空间不足以容纳所有需要晋升的对象。JVM 会尝试清理更多的老年代空间或者采用其他措施来应对空间不足的情况。避免因为老年代空间不足而过早触发 Full GC（全堆回收）。Full GC 通常比 Minor GC 更耗时，会导致更长时间的停顿。但该参数在JDK7开始彻底被弃用，相当于该参数变为false，这可能导致Full GC频繁发生，但JVM也开始动态调整新生代、老年代的空间大小配置，尽量减少Full GC的发生，且如果老年代空间不足，会提前执行部分清理或混合GC。