垃圾回收算法

垃圾回收算法的实现设计到大量的程序细节，并且每一个平台的虚拟机操作内存的方式都有不同，所以不需要去了解算法的具体实现。

复制算法

将可用内存按容量划分为大小相等的两块，每次只使用其中的一块。当这一块的内存用完了，就将还存活着的对象复制到另外一块上面，然后再把已使用过的内存空间一次清理掉。这样使得每次都是对整个半区进行内存回收，内存分配时也就不用考虑内存碎片等复杂情况，只要按顺序分配内存即可，实现简单，运行高效。

【Java面试题】阿里+头条+腾讯大厂Java笔试真题

只是这种算法的代价是将内存缩小为了原来的一半。但是要注意：内存移动是必须实打实的移动（复制），所以对应的引用（直接指针）需要调整。

复制回收算法适合于新生代，因为大部分对象朝生夕死，那么复制过去的对象比较少，效率自然就高，另外一半的一次性清理是很快的。

Appel式回收

一种更加优化的复制回收分代策略：具体做法是分配一块较大的 Eden 区和两块较小的 Survivor 空间（一般称作做From区和To区，也可以叫做S0和S1）

基于经验统计，新生代中的对象98%是“朝生夕死”的，所以并不需要按照 1:1 的比例来划分内存空间，而是将内存分为一块较大的 Eden 空间和两块较小的 Survivor 空间，每次使用 Eden和其中一块Survivor[1]。当回收时，将 Eden 和 Survivor 中还存活着的对象一次性地复制到另外一块 Survivor 空间上，最后清理掉 Eden 和刚才用过的 Survivor 空间。

HotSpot 虚拟机默认 Eden 和 Survivor 的大小比例是 8:1，也就是每次新生代中可用内存空间为整个新生代容量的 90%（80%+10%），只有10%的内存会被 “浪费”。当然，98%的对象可回收只是一般场景下的数据，我们没有办法保证每次回收都只有不多于10%的对象存活，当 Survivor 空间不够用时，需要依赖其他内存（这里指老年代）进行分配担保（Handle Promotion）

【Java面试题】阿里+头条+腾讯大厂Java笔试真题

标记清除

算法分为“标记”和“清除”两个阶段：首先扫描所有对象标记出需要回收的对象，在标记完成后扫描回收所有被标记的对象，所以需要扫描两遍。回收效率略低，如果大部分对象是朝生夕死，那么回收效率降低，因为需要大量标记对象和回收对象，对比复制回收效率要低。

它的主要问题，标记清除之后会产生大量不连续的内存碎片，空间碎片太多可能会导致以后在程序运行过程中需要分配较大对象时，无法找到足够的连续内存而不得不提前触发另一次垃圾回收动作。回收的时候如果需要回收的对象越多，需要做的标记和清除的工作越多，所以标记清除算法适用于老年代。

【Java面试题】阿里+头条+腾讯大厂Java笔试真题

标记整理

首先标记出所有需要回收的对象，在标记完成后，后续步骤不是直接对可回收对象进行清理，而是让所有存活的对象都向一端移动，然后直接清理掉端边界以外的内存。标记整理算法虽然没有内存碎片，但是效率偏低。

我们看到标记整理与标记清除算法的区别主要在于对象的移动。对象移动不单单会加重系统负担，同时需要全程暂停用户线程才能进行，同时所有引用对象的地方都需要更新（直接指针需要调整）。所以看到，老年代采用的标记整理算法与标记清除算法，各有优点，各有缺点。

【Java面试题】阿里+头条+腾讯大厂Java笔试真题

垃圾回收器

回收器名称回收对象和算法回收器类型Serial新生代，复制算法线程(串行)Parallel Scavenge新生代，复制算法并行的多线程回收器ParNew新生代，复制算法并行的多线程回收器Serial Old老年代，标记整理算法单线程(串行)Parallel Old老年代，标记整理算法并行的多线程回收器CMS老年代，标记清除算法并发的多线程回收器G1新生代，老年代；标记整理 + 化整为零并发的多线程回收器

【Java面试题】阿里+头条+腾讯大厂Java笔试真题

目前最常用的两种垃圾回收器，也不用多说，肯定是CMS和G1，一般面试官会问下CMS和G1的区别以及各自的特点，不太会深入问实现原理，毕竟Java面试可问的知识点实在太多了，都一个个深入问1个小时的面试时间根本不够。

串行的垃圾回收器就不说了，这里专门讲下并发的垃圾回收器

CMS（Concurrent Mark Sweep）回收器

顾名思义，这是并发的垃圾回收器，这种回收器是一种以获取最短的回收停顿时间为目的的垃圾收集器，目前很大一部分Java的互联网应用或者B/S系统的服务器上，由于这类应用尤其在意相应速度，希望系统停顿时间越短越好，这样用户体验也会更好，CMS就非常符合这类应用的需求。

从名字就可以看出，这种回收器是基于标记清除的算法实现，它的运作过程相对串行的垃圾回收器相对复杂点，分为以下4个步骤

初始标记：很短，仅仅只是标记下GC Root能直接关联的对象，速度极快。

并发标记：和用户应用同时进行，进行GC Root跟踪的过程，标记GC Root开始关联的所有对象，开始遍历整个可达分析的路径对象，这个时间比较长，所以并发。

重新标记：短暂，为了修正并发标记期间因用户程序继续运作而导致标记产生变动的那一部分对象的标记记录，这个阶段的停顿时间一般会比初始标记阶段稍长一些，但远比并发标记的时间短。

并发清除：由于整个过程中耗时最长的并发标记和并发清除过程收集器线程都可以与用户线程一起工作，所以，一般来说，CMS 的内存回收过程是与用户线程一起执行的。-XX:+UseConcMarkSweepGC ，表示新生代使用ParNew，老年代的用 CMS。

【Java面试题】阿里+头条+腾讯大厂Java笔试真题

CPU 敏感：CMS 对处理器资源敏感，毕竟采用了并发的收集、当处理核心数不足 4 个时，CMS 对用户的影响较大。

浮动垃圾：由于 CMS 并发清理阶段用户线程还在运行着，伴随程序运行自然就还会有新的垃圾不断产生，这一部分垃圾出现在标记过程之后，CMS无法在当次收集中处理掉它们，只好留待下一次GC时再清理掉。这一部分垃圾就称为“浮动垃圾”。由于浮动垃圾的存在，因此需要预留出一部分内存，意味着 CMS 收集不能像其它收集器那样等待老年代快满的时候再回收。在1.6的版本中老年代空间使用率阈值（92%）如果预留的内存不够存放浮动垃圾，就会出现 Concurrent Mode Failure，这时虚拟机将临时启用 Serial Old 来替代 CMS。

会产生空间碎片：标记 - 清除算法会导致产生不连续的空间碎片总体来说，CMS是JVM 推出了第一款并发垃圾收集器，所以还是非常有代表性。但是最大的问题是 CMS 采用了标记清除算法，所以会有内存碎片，当碎片较多时，给大对象的分配带来很大的麻烦，为了解决这个问题，CMS 提供一个参数：-XX:+UseCMSCompactAtFullCollection，一般是开启的，如果分配不了大对象，就进行内存碎片的整理过程。这个地方一般会使用 Serial Old ，因为 Serial Old 是一个单线程，所以如果内存空间很大、且对象较多时,CMS 发生这样情况会很卡。

总结：CMS 问题比较多，所以JDK没有一个版本默认垃圾回收器是CMS，只能手动指定。但是它毕竟是第一个并发垃圾回收器，对于了解并发垃圾回收具有一定意义，所以我们必须了解。为什么 CMS 采用标记-清除，在实现并发的垃圾回收时，如果采用标记整理算法，那么还涉及到对象的移动（对象的移动必定涉及到引用的变化，这个需要暂停业务线程来处理栈信息，这样使得并发收集的暂停时间更长），所以使用简单的标记-清除算法才可以降低 CMS的STW的时间。

该垃圾回收器适合回收堆空间几个 G至20G。

G1（Garbage First）

随着JVM内存的增大，STW的时间成为JVM 急迫解决的问题，但是如果按照传统的分代模型，总跳不出STW时间不可预测这点。

为了实现STW的时间可预测，首先要有一个思想上的改变。

G1将堆内存“化整为零”，将堆内存划分成多个大小相等独立区域（Region），每一个Region 都可以根据需要，扮演新生代的Eden空间、Survivor空间，或者老年代空间。

回收器能够对扮演不同角色的 Region 采用不同的策略去处理，这样无论是新创建的对象还是已经存活了一段时间、熬过多次收集的旧对象都能获取很好的收集效果。

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

开启参数 -XX:+UseG1GC分区大小 -XX:+G1HeapRegionSize一般建议逐渐增大该值，随着 size 增加，垃圾的存活时间更长，GC 间隔更长，但每次 GC 的时间也会更长。

最大GC暂停时间 -XX:MaxGCPauseMillis设置最大GC暂停时间的目标（单位毫秒），这是个软目标，JVM会尽最大可能实现它。

【Java面试题】阿里+头条+腾讯大厂Java笔试真题

运行过程如下：

初始标记:仅仅只是标记一下GC Roots能直接关联到的对象，并且修改 TAMS 指针的值，让下一阶段用户线程并发运行时，能正确地在可用的 Region 中分配新对象。这个阶段需要停顿线程，但耗时很短，而且是借用进行Minor GC的时候同步完成的，所以G1收集器在这个阶段实际并没有额外的停顿。要达到GC与用户线程并发运行，必须要解决回收过程中新对象的分配，所以G1为每一个Region 区域设计了两个名为TAMS（Top at Mark Start）的指针，从 Region 区域划出一部分空间用于记录并发回收过程中的新对象。这样的对象认为它们是存活的，不纳入垃圾回收范围。

并发标记：从GC Root开始对堆中对象进行可达性分析，递归扫描整个堆里的对象图，找出要回收的对象，这阶段耗时较长，但可与用户程序并发执行。当对象图扫描完成以后，并发时有引用变动的对象，这些对象会漏标，漏标的对象会被一个叫做SATB(snapshot at the beginning)算法来解决。

最终标记：对用户线程做另一个短暂的暂停，用于处理并发阶段结后仍遗留下来的最后那少量的 SATB 记录(漏标对象)。

筛选回收：负责更新Region的统计数据，对各个Region的回收价值和成本进行排序，根据用户所期望的停顿时间来制定回收计划，可以自由选择任意多个Region构成回收集，然后把决定回收的那一部分 Region 的存活对象复制到空的Region中，再清理掉整个旧 Region 的全部空间。这里的操作涉及存活对象的移动，是必须暂停用户线程，由多条收集器线程并行完成的。

总结：并行与并发：G1 能充分利用多 CPU、多核环境下的硬件优势，使用多个 CPU（CPU 或者 CPU 核心）来缩短 Stop-The-World 停顿的时间，部分其他收集器原本需要停顿 Java 线程执行的 GC 动作，G1 收集器仍然可以通过并发的方式让 Java 程序继续执行。

分代收集：与其他收集器一样，分代概念在 G1 中依然得以保留。虽然 G1 可以不需要其他收集器配合就能独立管理整个 GC 堆，但它能够采用不同的方式去处理新创建的对象和已经存活了一段时间、熬过多次 GC 的旧对象以获取更好的收集效果。

空间整合：与 CMS 的“标记—清理”算法不同，G1 从整体来看是基于“标记—整理”算法实现的收集器，从局部（两个 Region 之间）上来看是基于“复制”算法实现的，但无论如何，这两种算法都意味着 G1 运作期间不会产生内存空间碎片，收集后能提供规整的可用内存。这种特性有利于程序长时间运行，分配大对象时不会因为无法找到连续内存空间而提前触发下一次 GC。

追求停顿时间：-XX:MaxGCPauseMillis 指定目标的最大停顿时间，G1 尝试调整新生代和老年代的比例，堆大小，晋升年龄来达到这个目标时间。

并发标记

三色标记算法

说到并发标记，就不能不提下并发标记中的三色标记算法，它是一种描述追踪式回收器的有效的办法，利用它可以推演回收器的正确性。

在三色标记法之前有一个算法叫 Mark-And-Sweep（标记清除）。这个算法会设置一个标志位来记录对象是否被使用。最开始所有的标记位都是0，如果发现对象是可达的就会置为1，一步步下去就会呈现一个类似树状的结果。等标记的步骤完成后，会将未被标记的对象统一清理，再次把所有的标记位设置成0方便下次清理。

这个算法最大的问题是 GC 执行期间需要把整个程序完全暂停，不能异步进行 GC 操作。因为在不同阶段标记清扫法的标志位0和1有不同的含义，那么新增的对象无论标记为什么都有可能意外删除这个对象。对实时性要求高的系统来说，这种需要长时间挂起的标记清扫法是不可接受的。所以就需要一个算法来解决 GC 运行时程序长时间挂起的问题，那就三色标记法。三色标记最大的好处是可以异步执行，从而可以以中断时间极少的代价或者完全没有中断来进行整个GC。

我们将对象分为三种类型：

黑色：根对象，或者该对象与它的子对象都被扫描过。

灰色：对本身被扫描，但是还没扫描完该对象的子对象。

白色：未被扫描对象，如果扫描完所有对象之后，最终为白色的为不可达对象，既垃圾对象。

【Java面试题】阿里+头条+腾讯大厂Java笔试真题