对象标记算法

对象回收前，需要标记其"死活"，常用的对象标记算法主要包括引用计数算法和可达性分析算法。

引用

• 强引用 (Strongly Reference)

只要强引用还存在，垃圾收集器就永远不会回收掉被引用的对象；

• 软引用 (Soft Reference)

内存溢出时，进行回收，这次回收还没有足够的内存，才会抛出内存溢出异常；

• 弱引用 (Weak Reference)

只能生存到下一次垃圾收集发生为止。

• 虚引用 (Phantom Reference)

只是被回收时收到1个通知。

引用计数算法

在对象中添加一个引用计数器，每当有1个地方引用它时，计数器值就+1；当引用失效时，计数器值就-1；任何时刻计数器为0的对象就是不可能再使用的。

很难解决对象循环引用的问题。

可达性分析算法

基本思路就是通过一系列 "GC Roots" 的根对象作为初始节点集，从这些节点开始，根据引用关系向下搜索，搜索过程走过的路径称为"引用链" (Reference Chain)，如果某个对象到 GC Roots 间没有任何引用链相连，或者用图论的话来讲就是从 GC Roots到这个对象不可达时，则证明该对象时不可能再被使用的。

垃圾收集算法

标记清除(Mark-Sweep)算法

1960 年由 Lisp 之父 John McCarthy 所提出。

算法分为"标记"和"清除"2个阶段:

• 首先标记出所有需要回收的对象；
• 标记完成后，统一回收掉所有被标记的对象。

主要缺点:

• 必须进行大量标记和清除的动作，导致标记和清除两个过程的执行效率均随对象数量增长而降低；
• 内存碎片化问题，标记、清除之后会产生大量不连续的内存碎片，空间碎片太多可能会导致当以后在程序运行过程中需要分配较大对象时无法找到足够的连续内存而不得不提前触发另一次垃圾回收动作。

标记复制(Mark-Copy)算法

1969 年 Fenichel 提出一种称为"半区复制" (Semispace Copying) 的垃圾回收算法。

该算法将内存按照容量会分为2个大小相等的两块，每次只使用其中的一块，当这一块的内存用完了，就将还存活着的对象复制到另外一块上面，然后再将已使用过的内存空间一次清理掉。

缺点:

• 如果内存中多数对象都是存活的，该算法会产生大量内存复制的开销；
• 可用内存被缩小为原来的一半，空间比较浪费。

考虑掉新生代的内存对象有98%熬不过第一轮收集，相当于多数对象均是可回收的，那上述算法需要复制的仅是占少数的存活对象，而且后续分配内存时不用考虑有空间碎片的复杂情况，所以标记复制算法主要用于新生代垃圾收集器。

由于半区复制对内存空间浪费太过严重，所以在1989年，Andrew Appel 针对"朝生夕灭"特点的对象，提出了一种更优化的半区复制分代策略，现在称为 Appel 式回收。

Appel 式回收的具体做法是把新生代分为一块较大的 Eden 空间和两块较小的 Survivor 空间，每次分配内存只使用 Eden 和其中一块 Survivor。发生垃圾收集时，将 Eden 和 Survivor 中仍然存活的对象一次性复制到另外一块 Survivor 空间上。然后直接清理掉 Eden 和已用过的那块 Survivor 空间。

HotSpot 虚拟机默认 Eden 和 Surivor 的大小比例为 8:1:1。当然，任何人都没有办法百分百保证每次回收都只有不多于10%的对象存活，因此，Appel 还有一个充当罕见情况"逃生门"的安全设计，当 Survivor 空间不足以容纳一次 Minor GC 之后存活的对象时，就需要依赖其他内存区域(实际上大多都是老年代)进行内存分配担保(Handle Promotion)。

标记整理(Mark-Compact)算法

标记复制算法在对象存活率较高时就要进行较多的复制操作，效率就会降低，故不适用于老年代的垃圾收集。

针对老年代对象的存亡特征，1974年 Edward Lueders 提出了另外一种有针对性的标记整理算法。

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

标记清除算法和标记整理算法的本质差异在于前者是一种非移动式的回收算法，而后者是移动式的。

是否移动回收后的存活对象是一项优缺点并存的风险决策:

• 如果移动对象，当存活对象较多时，该操作将极为笨重，而且对象移动操作必须全程暂停用户应用程序才能进行，即"Stop The World"，而这会增加应用程序的延迟；
• 如果不移动对象，弥散于堆中的存活对象导致的内存碎片化问题只能依赖更为复杂的内存分配器和内存访问器来解决。内存的访问是用户程序最频繁的操作，假如在这个环节增加额外的负担，势必直接影响应用程序的吞吐量。

综上，移动对象则内存回收的时候更复杂，不移动对象则内存分配的时候更复杂。不移动对象停顿时间更短，但因内存分配和访问相比垃圾收集频率要高得多，总吞吐仍然是下降的。

所以，关注吞吐量的收集器一般采用标记整理算法，而关注延迟的收集器一般采用标记清除算法。

经典垃圾收集器

Serial 收集器

单线程新生代收集器，基于标记复制算法。

ParNew 收集器

新生代收集器，实质上是 Serial 收集器的多线程并行版本，基于标记复制算法。

Parallel Scavenge 收集器

新生代多线程收集器，基于标记复制算法，目标是达到一个可控制的吞吐量 (Throughput)。

吞吐量 = 运行用户代码时间 / (运行用户代码对象 + 运行垃圾收集时间)。

Parallel Scavenge收集器提供了以下2个参数来精准控制吞吐量:

• -XX:MaxGCPauseMillis

单位为毫秒，收集器将尽量保证内存回收花费的时间不超过用户设定值。

垃圾收集停顿时间缩短是以牺牲吞吐量和新生代空间为代价换取的:系统把新生代调得小一些，收集300M新生代肯定比收集500M快，但也直接导致垃圾收集发生的更频繁，原来10秒收集一次，每次停顿100毫秒，现在变成5秒收集一次，每次停顿70毫秒。停顿时间确实在下降，但吞吐量也降下来了。

• -XX:GCTimeRatio

为大于0小于100的整数，为用户代码时间和垃圾收集时间的比值。

假设该参数设置为19，则允许的最大垃圾收集时间占总时间的5%(1/(1+19))。

默认值为99，即允许最大1%的垃圾收集时间。

Parallel Scavenge 还有另外一个参数: -XX:+UseAdaptiveSizePolicy，该参数激活后，虚拟机会根据当前系统的运行情况收集性能监控信息，动态调整新生代大小 (-Xmn)、Eden 和 Survivor 区的比例 (-XX:SurvivorRatio)、晋升老年代对象大小 (-XX:PretenureSizeThreshold)等参数，以提供最合适的停顿时间或者最大吞吐量。该种调节方式称为垃圾收集的自适应调节策略 (GC Ergonomics)，也是 Parallel Scavenge 收集器区别于 ParNew 收集器的重要特征。

Serial Old 收集器

单线程老年代收集器，基于标记整理算法实现。

主要有2种用途:

• JDK 5 以及之前版本中与 Parallel Scavenge 收集器搭配使用；
• 当 CMS 收集器发生 Concurrent Mode Failure 时使用。

Parallel Old

多线程老年代收集器，基于标记复制算法实现，是 Parallel Scavenge 收集器的老年代版本。

在注重吞吐量或者处理器资源较为稀缺的场合，均可以优先考虑 Parallel Scavenge(PS) 和 Parallel Old(Par) 组合(JDK9 之前服务端的默认垃圾回收器组合)。

CMS(Concurrent Mark Sweep) 收集器

CMS 收集器是一种获取最短回收停顿时间为目标的老年代收集器，基于标记清除算法实现。

CMS 垃圾收集过程分为以下4个步骤:

• 初始标记 (CMS initial mark)，单线程，需要 Stop The World
• 并发标记 (CMS concurrent mark)，与用户线程并发，不需要 Stop The World
• 重新标记 (CMS remark)，多线程，需要 Stop The World
• 并发清除 (CMS concurrent sweep)，与用户线程并发，不需要 Stop The World

CMS 的优点是并发收集、低停顿，缺点为:

• 对处理器资源比较敏感

在并发标记和并发清除阶段，虽然不会导致用户线程停顿，但却会因为占用部分线程而导致应用程序变慢，降低总吞吐量。

• 可能出现 "Concurrent Mode Failure"

在 CMS 的并发标记和并发清理阶段，由于用户线程还在运行，程序在运行自然就还会伴随有新的垃圾对象不断产生，但该部分垃圾是在对象标记之后，CMS 无法在当次收集中处理掉它们，只好留待下一次垃圾收集时再清理掉，该部分垃圾称之为"浮动垃圾"。

同时，由于垃圾收集阶段用户线程还需持续运行，还需要预留足够的内存空间提供给用户线程使用，JDK5 默认配置下，CMS 收集器当老年代使用68%的空间后就会被激活，该参数为偏保守的配置，如果在实际应用中老年代增长的不太快，可以适当调高参数 -XX:CMSInitiatingOccupancyFraction 的值来提高 CMS 的触发百分比，降低内存回收频率，获取更高的性能。到 JDK6，CMS 收集器的启动阈值默认提升到了92%，但容易造成 CMS 运行期间，预留的内存大小无法满足用户线程分配新对象，引起 "Concurrent Mode Failure"。此时，冻结用户线程，临时启用 Serial Old 收集器来重新进行老年代的垃圾收集，但这样停顿时间就变长了。所以 -XX:CMSInitiatingOccupancyFraction 设置得太高将会很容易导致大量并发失败产生，性能反而降低。

• 标记清除算法会导致内存碎片问题

G1(Garbage First) 收集器

开创了收集器面向局部收集的设计思路和基于 Region 的内存布局形式。

在 G1 收集器出现之前的所有其他收集器，包括 CMS 在内，垃圾收集的目标范围要么是整个新生代 (Minor GC)，要么就是整个老年代 (Major GC)，再要么就是整个 Java 堆 (Full GC)。

G1 跳出了上述樊笼，可以面向对内内存任何部分来组成回收集 (Collection Set) 进行回收，衡量标准不再是它属于哪个分代，而是哪块内存中存放的垃圾数量最多，回收收益最大，这就是 G1 收集器的 Mixed GC 模式。

G1 把连续的 Java 堆划分为多个大小相等的独立区域 (Region)，每个 Region 均可以根据需要，扮演新生代的 Eden 空间、Survivor 空间或者老年代空间。收集器能够对扮演不同角色 Region 采用不同的策略去处理。

从 G1 开始，最先进的垃圾收集器的设计导向均不约而同地变为追求能够应付应用的内存分配速率 (Allocation Rate)，而不追求一次把整个 Java 堆全部清理干净。这样，应用在分配，同时收集器在收集，只要收集的速度能够跟得上对象分配的速度，那一切就能运作得很完美。

G1 从整体开看是基于标记整理算法实现的收集器，但从局部(两个 Region 之间)上看又是基于标记复制算法实现。无论如何，这两种算法都意味着 G1 运行期间不会产生内存空间碎片，垃圾收集完成之后能够提供规整的可用内存。

G1 的内存占用和额外执行负载较高，在大内存应用上(6GB-8GB 以上)才会发挥其优势。