【JVM】从可达性分析，到JVM垃圾回收算法，再到垃圾收集器

《深入理解Java虚拟机》[1]中，有下面这么一段话：

在JVM的各个区域中，如虚拟机栈中，栈帧随着方法的进入和退出而有条不紊的执行者出栈和入栈操作。每一个栈帧中分配多少内存基本上是在类结构确定下来时就已知的（尽管在运行期会由即时编译器进行一些优化，但在基于概念模型的讨论里，大体上可以认为是编译器可知的），因此这几个区域的内存分配和回收都具有确定性，在这几个区域内就不需要考虑如何回收的问题，当方法结束或者线程结束时，内存自然就跟随着回收了。
而Java堆和方法区这两个区域则有着很显著的不确定性：一个接口的多个实现类的内存可能会不一样，一个方法所执行的不同条件分支所需要的内存也可能不一样，只有处于运行期间，我们才能知道程序究竟会创建哪些对象，创建多少个对象，这部分内存分配和回收是动态的。垃圾收集器所关注的正式这部分内存该如何管理，本文后续讨论的“内存”分配与回收也仅仅特指这一部分内存。

简单的说，就是线程私有区域的内存好回收，因为其分配多少内存、其中有多少对象、多大对象，因为是属于单个线程私有的内存区域，都是容易确定的；而如Java堆和方法区，因为属于线程公有的内存区域，则具有显著的不确定性，因此需要对于这部分区域设计垃圾收集器。

比如，我们该怎么确定一个对象已死呢？

一，如何判断对象已死

1，引用计数算法

引用计数算法（Reference Counting），在对象中添加一个引用计数器，每当有一个地方引用它，计数器值就加一；当引用失效时，计数器值就减一；任何时刻计数器为零的对象就是不可能再被使用的。

这种算法原理简单，判定效率高，有一些比著名的应用案例，如Python语言、微软COM(Component Object Model)技术等。但是，在Java领域，至少主流的Java虚拟机里没有选用引用计数法来管理内存，主要原因是，这个看似简单的算法有很多例外情况要考虑，必须要配合大量额外处理才能保证正确的工作，譬如单纯的引用计数就很难解决对象之间相互循环引用的问题。

2，可达性分析算法

当前主流的商用程序语言（Java、C#）的内存管理系统，都是通过可达性分析（Reachability Analysis）算法来判定对象是否存活的。这个算法的基本思路就是通过一系列成为“GC Roots”的根对象作为起始节点集，从这些节点开始根据引用关系向下搜索，搜索过程所走过的路径称为“引用链（Reference Chain）”，如果某个对象到GC Roots间没有任何引用链相连，或者用图论的话来说就是从GC Roots到这个对象不可达时，则证明此对象是不可能再被使用的。

在Java技术体系里面，固定可作为GC Roots的对象包括很多种，如虚拟机栈的栈帧的本地变量表中引用的对象，如字符串常量池中引用的对象等等。

另外，在JDK1.2之后，为了更清楚的描述对象的引用状态，对引用的概念进行了扩充，将引用分为强引用(Strongly Reference)、软引用（Soft Reference）、弱引用（Weak Reference）和虚引用（Phantom Reference）四种，这4种的引用强度逐渐减弱。其中我们最常使用的如"Object o = new Object()"是强引用，其他的引用必须使用对应的类来实现如软引用（SoftReference类）、弱引用（WeakReference类）、虚引用（PhantomReference类），JVM在对待这些引用会有不同的回收时机。

二，分代收集理论

一部分虚拟机是遵循“分代收集”（Generational Collection）的理论进行设计的。它建立在两个分代假说之上：

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

因此在应用分代收集理论的商用Java虚拟机中，设计者一般会至少把Java堆划分为新生代（Young Generation）和老年代（Old Generation）两个区域。

三，JVM垃圾回收算法

垃圾回收算法这里介绍三种，分别是标记-清除（Mark-Sweep）算法、标记-复制（Semispace Copying）算法、标记-整理（Mark-Compact）算法。

其中，标记-清除（Mark-Sweep）算法首先标记出所有需要回收的对象，在标记完成后，统一回收掉所有被标记的对象，也可以反过来，标记存活的对象，统一回收未被标记的对象。其缺点是容易产生内存碎片，标记-清除需要两次扫描所有对象。

标记-复制（Semispace-Copying）算法解决了标记-清除算法为了解决标记-清除算法效率低的问题，1969年Fenichel提出了一种称为“半区复制”（Semispace-Copying）的垃圾收集算法，它将可用内存按容量划分为大小大小相等的凉快，每次只使用其中的一块。显而易见，这种复制回收算法的缺点是将可用内存缩小为了原来的一半，空间浪费严重。

IBM公司曾有一项专门研究对新生代“朝生夕灭的特点做了更量化的诠释——新生代中的对象有98%熬不过第一轮收集。因此并不需要按照1:1的比例来划分新生代的内存空间。

1989年，Andrew Appel针对具备“朝生夕灭”特点的对象，提出了一种更优化的半区复制分代策略，现在称为“Appel式回收”。如HotSpot虚拟机的Serial、ParNew等收集器均采用了这种策略来设计新生代的内存布局。Appel式回收的具体做法是把新生代分为一块较大的Eden空间和两块较小的Survivor空间，每次分配内存只使用Eden和其中一块Survivor空间。发生垃圾收集时，将Eden和Survivor中仍然存活的对象一次性的复制到另外一块Survivor空间上，然后直接清理掉Eden和已用过的那块Survivor空间。HotSpot虚拟机默认Eden和Survivor的大小比例是8:1，也即每次新生代中可用内存空间为整个新生代容量的90%（Eden的80%加上一个Survivor的10%），只有一个Survivor空间，即10%的新生代是会被浪费的。

当然，没有任何人可以百分百保证每次回收都只有不多于10%的对象存活，因此Appel式回收有一个充当罕见情况的逃生门的安全设计，当Survivor空间不足以容纳一次MinorGC之后存活的对象时，就需要依赖其他内存区域（实际上大多就是老年代）进行分配担保（Handle Promotion）。

标记-复制算法在对象存活率较高的时候就要进行较多的复制操作，效率将会降低。更关键的是，如果不想浪费50%的空间，就需要有额外的空间进行分配担保，以应对被使用的内存中所有对象都100%存活的极端情况，所以在老年代一般都不能直接使用这种算法。

针对老年代对象的存亡特征，1974年Edward Lueders提出了另外一种有针对性的“标记-整理”（Mark-Compact）算法，其中的标记过程仍然与“标记-清除”算法一样，但后续步骤不是直接对可回收对象进行清理，而是让所有存活的对象都向内存空间一端移动，然后直接清理掉边界以外的内存。这种算法的优点是没有碎片，缺点是效率偏低，两遍扫描所有对象，需要调整指针。

四，垃圾收集器

Serial收集器，这个收集器是最古老最基础的收集器，Serial基于复制算法、应用于年轻代，Serial Old是Serial的老年代版本，基于标记-整理算法、应用于老年代。这个收集器是一个单线程工作的收集器，它的单线程的意义并不仅仅是说它只会使用一个是处理器或一个手机县城去完成垃圾收集工作，更重要的是强调在它进行垃圾收集时，必须暂停其他所有工作线程。这种垃圾收集器在内存较小如几十兆乃至一二百兆的年轻代中都可以很好的工作，相比其他收集器，这种收集器简单高效，垃圾收集的停顿时间可以控制在十几、几十毫秒，只要不是频繁发生GC，这点停顿时间【注1】对于许多用户来说是完全可以接受的。

Serial Old，正如前文所说，Serial收集器的老年代版本，基于标记-整理算法工作在老年代。Serial和Serial Old收集器组合，Serial Old也可以和Parallel Scavenge组合。Serial Old的另外一个作用就是老年代CMS收集器发生失败时的后备方案，当然，相比CMS工作内存之大，Serial Old单线程的工作效率是十分感人的。

ParNew，实际上是Serial收集器的多线程版本，除了在垃圾回收时同时使用多线程进行垃圾回收之外，其余的行为包括Serial收集器可用的所有控制参数、手机算法等和Serial完全一致。ParNew工作在年轻代，可以配合CMS进行工作。

Parallel Scavenge，同样是基于标记-复制算法实现的收集器【注2】，也是能够并行收集的多线程收集器。Parallel Scavenge收集器的特点是它的关注点与其他收集器不同，CMS等收集器的关注点是尽可能的缩短用户县城的停顿时间，而Parallel Scavenge收集器的目标则是达到一个可控制的吞吐量（Throughput）【注3】。Parallel Scavenge收集器提供了两个参数用于精确控制吞吐量，分别是控制最大垃圾收集停顿时间的-XX:MaxGCPauseMillis和直接设置吞吐量大小的-XX:GCTimeRatio参数的。

由于和吞吐量密切相关，Parallel Scavenge收集器也经常被称作“吞吐量优先收集器”。PS还有一个参数，-XX:+UseAdaptiveSizePolicy，这是一个开关参数，打开之后，就不需要人工指定新生代的大小（-Xmn），Eden与Survivor区的比例（-XX:SurvivorRatio），晋升老年代对象大小（-XX:PretenureSizeThreshold）等细节参数了，虚拟机会根据当前系统的运行情况收集性能监控信息，动态调整这些参数以提供最合适的停顿时间或者最大吞吐量，这种调节方式被称为垃圾收集的自适应的调节策略（GC Ergonomics）。

Parallel Old，是Parallel Scavenge的老年代版本。直到JDK6才开始提供。可以和Parallel Scavenge配合，即PS+PO。

CMS（Concurrent Mark Sweep）收集器是一种以获取最短回收停顿时间为目标的收集器。目前很大一部分的Java应用集中在互联网网站或者基于浏览器的BS系统的服务端上，这类应用通常都会比较关注服务的响应速度，希望系统停顿时间尽可能短，以给用户带来更好的交互体验。CMS收集器就非常符合这类应用的需求。

CMS回收流程如下：

在这里插入图片描述
CMS只有初始标记和重新标记阶段是需要STW的。其中，初始标记会标记一下能直接关联到GC Roots的对象，速度很快；并发标记阶段是从GC Roots的直接关联对象开始遍历整个对象图的过程，这个过程比较耗时但是不需要STW；重新标记阶段是为了修正并发标记阶段，因用户程序继续运作而导致标记产生变动的那一部分对象的标记记录，这个阶段的STW时间要比初始标记阶段要长一些，但远比并发标记阶段时间短；最后的并发清除阶段，清理删除掉标记阶段判断已死亡的对象，由于不需要移动存活对象，所以这个阶段也是可以和用户线程同时并发的。

CMS是一款划时代的垃圾收集器，是第一个真正能够并发收集垃圾的收集器，其优点正如其名：并发收集、低停顿。但是CMS存在严重的问题：

第一，CMS并发阶段虽然不会导致用户线程停顿，但是会导致吞吐量降低。

第二，CMS无法处理浮动垃圾（Floating Garbage），有可能会出现"Concurrent Mode Failure"，进而导致领一次完全STW的Full GC，即降级为使用Serial Old这种单线程垃圾收集器来回收可能达到上G的内存空间。

所谓浮动垃圾，就是在CMS并发标记和清理阶段，用户线程还是在继续运行的，程序在运行自然会不断有垃圾产生，但这一部分对象是出现在标记阶段之后的，因此CMS无法处理它们，只能留待下一次垃圾收集时再处理掉。这一部分垃圾就称为浮动垃圾。同样也是由于在垃圾收集阶段用户线程还需要持续运行，那就还需要预留足够内存空间提供给用户线程使用，因此CMS收集器不能像其他收集器那样等待老年代完全被填满了再进行收集，必须预留一部分空间供并发收集时的程序运作使用。

JDK5的默认设置，CMS收集器当老年代使用了68%的空间后就会被激活，这是个偏保守的设置。如果在实际应用中老年代增长并不是太快，可以适当跳高参数-XX:CMSInitiatingOccu-pancyFraction的值来提高CMS的触发百分比，降低内存回收频率，获取更好性能。到了JDK6时，CMS收集器的启动阈值已经默认提升到92%。但这又会面临另外一种风险，就是会出现一次并发失败（Concurrent Mode Failure），这时候虚拟机将不得不启动后备预案：停止用户线程的执行，使用Serial Old来重新进行老年代的垃圾收集，但是这样时间就太长了。所以参数-XX:CMSInitiatingOccupancyFraction设置的太高容易并发失败，反而降低性能，需要根据实际情况权衡后来设置。

第三，CMS全名Concurrent Mark Sweep，可以看出它用的是标记清除算法，会存在空间碎片问题。当碎片过多时，将会给大对象的分配带来问题，此时即使空间仍然存在很多剩余，但是无法找到足够的连续空间来分配给当前对象，于是触发Full GC。

垃圾收集器的组合如下：

连线的表示可以组合成一对，另外G1是逻辑上分代的，至于之后的ZGC等已经不按照分代算法进行设计了。
在这里插入图片描述

Garbage First（G1），是垃圾收集器技术发展史上的里程碑式的成果，开创了收集器面向局部收集的设计思路和基于Region的内存布局形式。在JDK8 Update40的时候，这个版本以后的G1收集器被Oracle官方称为“全功能的垃圾收集器”，从JDK9开始，G1取代PS+PO称为服务端模式的默认垃圾收集器，CMS被沦落为被声明为不推荐使用。

作为CMS收集器的替代者和继承人，设计者们希望作出一款能够建立“停顿时间模型”（Pause Prediction Model）的收集器，停顿时间模型的意思是能够支持指定在一个长度为M毫秒的时间片段内，消耗在垃圾收集上的时间大概率不超过N毫秒这样的目标。

那么具体要怎么做才能实现这个目标呢？首先要有一个思想上的转变，在G1收集器出现之前的所有，包括CMS在内，垃圾收集的目标范围要么是整个新生代（Minor GC），要么是整个老年代（Major GC）（只有ParNew+CMS中的CMS才能单独进行MajorGC，Serial+Serial、PS+PO都无法单独进行Major GC，它们老年代GC等于Full GC），要么就是整个Java堆（Full GC）。而G1跳出了这个樊笼，它可以面向堆内存任何部分来组成回收集（Collection Set，一般简称CSet）进行回收，衡量标准不再是它属于哪个分代，而是哪块内存的垃圾数量最多，回收收益最大，这就是G1收集器deMixed GC模式。

G1开创的基于Region的堆内存布局是它能够实现这个目标的关键。虽然G1也仍是遵循分代收集理论设计的，但其堆内存的布局与其他收集器有非常明显的差异：G1不在坚持固定大小以及固定数量的分代区域划分，而是把连续的Java堆划分为多个大小相等的独立区域（Region），每一个Region都可以根据需要，扮演新生代的Eden空间、Survivor空间，或者老年代空间，收集器能够扮演不同角色的Region采用不同的策略去处理，这样无论是新创建的对象还是已经存货了一段时间、熬过多次收集的旧对象都能获取很好的收集效果。

Region中还有一类特殊的Humongous区域，专门用来存储大对象。G1认为只要超过了一个Region容量一半的对象即可判定为大对象。每个Region的大小可以通过参数-XX:G1HeapRegionSize设定，取值范围1MB~32MB，而且应为2的N次幂。而对于那些超过了整个Region容量的超级大对象，将会被存放在N个连续的Humongous Region之中，G1的大多数行为都把Humongous Region作为老年代的一部分进行看待。

虽然G1仍然保留新生代和老年代的概念，但新生代和老年代不再是固定的了，它们都是一系列区域（不需要连续）的动态集合。G1收集器之所以能建立可预测的停顿时间模型，是因为它将Region作为单次回收的最小单元，即每次收集到的内存空间都是Region大小的整数倍，这样可以有计划的避免在整个Java堆中进行全区域的垃圾收集。更具体的处理思路是让G1收集器去跟踪各个Region里面的垃圾堆积的“价值”大小，价值即回收所获得的空间大小以及回收所需时间的经验值，然后在后台维护一个优先级列表，每次根据用户设定允许的收集停顿时间（参数-XX:MaxGCPauseMillis指定，默认值200毫秒），优先处理回收价值收益最大的那些Region，这也是Garbage First名字的由来。使用Region划分内存空间，以及具有优先级的区域回收方式，保证了G1收集器在优先的时间内获取尽可能高的收集效率。

G1会根据设定的预期响应时间（-XX:MaxGCPauseMillis），自动调整新老年代比例，一般为5%~60%。所以一般不建议使用G1时手工设置Y区大小。

CMS和G1在标记上有一些共同点，也有一些区别。CMS和G1都采用了三色标记算法，即

白色：未标记对象
灰色：自身被标记，成员变量未标记
黑色：自身和成员变量都已标记

三色标记算法的漏洞就是会产生漏标。

假设我们使用的是CMS，在remark过程中，黑色A指向了白色D，并且灰色B指向白色A的引用删除掉，如果不对黑色A重新扫描，则会漏标。会把白色D对象当做没有新引用指向从而回收掉。

如下图所示。

在这里插入图片描述

即，漏标是指本来是可达的对象，在重新标记的过程中（如CMS的remark），由于指针的变动，导致对象没有被标记上，被当做不可达的垃圾回收掉了。

从引用增加和引用删除的角度来看上述例子，产生漏标有两个可能的因素：

1，标记进行时增加了一个黑到白的引用，如果不重新对黑色进行处理，则会漏标2，标记进行时删除了灰对象到白对象的引用，那么这个白对象有可能被漏标

如何解决这个三色标记的漏标问题？只要解决上述的两个条件之一即可。如此，CMS和G1的并发标记算法如下：

1， incremental update – 增量更新，关注引用的增加，
把黑色重新标记为灰色，下次重新扫描属性，CMS使用
2，SATB（Snapshot At The Beginning） – 关注引用的删除
当B->D消失时，要把这个引用推到GC的堆栈，保证D还能被GC扫描到
G1使用

可以看得出来，CMS的并发标记算法增量更新需要扫描黑色对象的所有白色成员变量，而G1的SATB，只需要将堆栈中的对象弹出，精准的判断每一个对象即可。

在判断对象是否可达时，有一种比较尴尬的情况，就是跨代引用。如果某个年轻代对象被老年代对象引用，是否意味着JVM在YGC时必须将老年代也纳入扫描范围，而且每次查找某个对象是否有引用时，都要去老年代扫描一遍呢？记忆集解决了这个问题。卡表是记忆集的一种实现。即记录了每一个从老年代到年轻代的引用，堆中存在唯一一个卡表，这样每次判断对象引用是否存在老年代引用，只需要去卡表中查一下就好了。如CMS就是使用卡表记录跨代引用的。

G1的Region结构是一种更小巧的内存单元（从1M，2M…32M不等，必须是2的n次幂，可以由-XX:G1HeapRegionSize指定），每一个Region都有可能是年轻代（Eden、Survivor），也可能是老年代（Old），跨代引用更加频繁。因此G1采用了一种名为RSet（也是一种记忆集的实现）的结构，记录了其他Region中的对象到本Region的引用，存储在每个Region中，其中记录了该Region中每一个跨Region引用的对象。这种基于分而治之的思想的实现，使得G1可以更快速的查找跨Region引用的对象，垃圾收集器不需要扫描整个堆找到谁引用了当前分区中的对象，
只需要扫描RSet即可。

由于RSet 的存在，那么每次给对象赋引用的时候，就得做一些额
外的操作，指的是在RSet中做一些额外的记录，在GC中被称为写屏障。

需要注意的是，这个写屏障不等于内存屏障。

G1的GC存在3种，或者说3个阶段。

1，YGC，即对年轻代的Region进行GC。

2，MixedGC，当内存占用超过XX:InitiatingHeapOccupacyPercent指定的百分比（默认45%）时，会采用类似CMS的回收算法对整个堆进行回收。

3，Full GC，当老年代空间不足（没办法分配Region给老年代了）或者显示调用System.gc()时，触发Full GC。在Java10以前是串行Full GC，Java10以后是并行Full GC。

MixedGC的过程如下，和CMS区别不大，最后的筛选回收变成了需要STW。

在这里插入图片描述

Shenandoah和ZGC，是两款实验状态下的垃圾收集器（这句话是深入理解Java虚拟机中的，有点过时了。实际上Shenandoah在JDK12中以实验特性首次引入，JDK15成为生产特性。ZGC在JDK11中以实验性质引入，JDK15中成为生产特性），被官方命名为低延迟2垃圾收集器（Low-Latency Garbage Collector），其几乎整个工作过程都是并发的，只有初始标记、最终标记这些阶段有短暂的停顿，这部分停顿的时间基本上是固定的，与堆的容量、堆中对象的数量没有任何正比关系。

如Shenandoah，最初由Redhat公司研发，后加入OpenJDK，成为OpenJDK12的新特性之一，但是一直没有加入OraclJDK。这款垃圾收集器的目标是将垃圾收集的停顿时间控制在10毫秒以内的垃圾收集器，这意味着相比CMS和G1，Shenandoah不仅要并发的进行垃圾标记，还要并发的进城对象清理后的整理动作。

如ZGC（Z Garbage Collector）是在OpenJDK11中新加入的带有实验性质的低延迟垃圾收集器。

Shenandoah和ZGC都没有按照分代年龄来进行设计。

注1：
停顿时间（Stop The World, STW），垃圾收集期间，所有用户线程都要停止工作等待垃圾回收结束。这段时间称为STW。部分收集器只能并行，即垃圾收集时间等同于STW的时间如Serial、ParNew。部分收集器可以并发，如CMS、G1，STW时间小于其垃圾收集时间。

注2：
基本上实现上就分代的收集器或者说只工作在年轻代或者老年代的收集器，如Serial、Serial Old、CMS、ParNew、PS、PO，工作在年轻代的算法都是复制（Copying）算法，更准确的说是appel回收；工作在老年代的都是标记整理（Mark-Compact）算法。

注3：
吞吐量：用户代码时间 /（用户代码执行时间 + 垃圾回收时间）
响应时间：STW越短，响应时间越好
吞吐量优先，如科学计算、数据挖掘，用PS+PO
响应时间优先，如网站、GUI、API，用G1（JDK1.8）

注4：
卡表，为解决对象跨代引用所带来的问题，垃圾收集器在新生代中建立了名为记忆集（Remembered Set）的数据结构，用以避免把整个老年代加进GC Roots扫描范围。G1的RSet也是记忆集（Remembered Set）的一种实现。