1.标记-清除算法

标记-清除（Mark-and-Sweep）算法分为“标记（Mark）”和“清除（Sweep）”阶段：首先标记出所有不需要回收的对象，在标记完成后统一回收掉所有没有被标记的对象。

注：关于GC标记到底在哪儿？其实在上一章节中就已经分析过了，在对象头中存在一个markword字段，而GC标志位就存在其内部。

它是最基础的收集算法，后续的算法都是对其不足进行改进得到。这种垃圾收集算法会带来两个明显的问题：

内存碎片化问题：由于内存是连续的，所以在对象被删除之后，内存中会出现很多细小的可用内存碎片。如果我们需要的是一个比较大的空间，很有可能这些内存单元的大小过小无法进行分配。
分配速度慢：由于内存碎片的存在，需要维护一个空闲链表，极有可能发生每次需要遍历到链表的最后才能获得合适的内存空间。

image.png|425

关于具体是标记可回收对象还是不可回收对象，众说纷纭，两种说法其实都没问题，我个人更倾向于是前者。

如果按照前者的理解，整个标记-清除过程大致是这样的：

当一个对象被创建时，给一个标记位，假设为 0 (false)；
在标记阶段，我们将所有可达对象（或用户可以引用的对象）的标记位设置为 1 (true)；
扫描阶段清除的就是标记位为 0 (false)的对象。

2.复制算法

为了解决标记-清除算法的效率和内存碎片问题，复制（Copying）收集算法出现了。它可以将内存分为大小相同的两块，通常称为 from 区和 to 区，每次使用其中的一块。当这一块的内存使用完后，就将还存活的对象复制到另一块去，然后再把使用的空间一次清理掉。这样就使每次的内存回收都是对内存区间的一半进行回收。

image.png|550

虽然改进了标记-清除算法，但依然存在下面这些问题：

可用内存变小：可用内存缩小为原来的一半。
不适合老年代：如果存活对象数量比较大，复制性能会变得很差

复制算法的内存是1:1复制吗？

传统的复制算法是 1:1 复制

原理

在传统的复制算法中，将可用内存划分为两个大小相等的区域，通常称为 from 区和 to 区，这就是 1:1 的内存划分。当进行垃圾收集时，从 from 区（活动对象所在区）将存活的对象复制到 to 区，然后清空 from 区。下一次垃圾收集时，角色互换，原来的 to 区变为 from 区，原来的 from 区变为 to 区，如此反复。在新生代使用复制算法进行垃圾回收时，S0 和 S1 区就分别扮演着 from 区和 to 区的角色。

示例

假设可用内存为 100MB，按照 1:1 复制算法划分为两个 50MB 的区域（from 区和 to 区）。如果 from 区中有 20MB 的存活对象，在垃圾收集时，这 20MB 的存活对象会被复制到 to 区，然后 from 区被清空。

优化后的复制算法并非严格 1:1 复制

自适应大小分配

一些现代的垃圾收集器会根据实际情况对复制算法进行优化。例如，并不总是按照严格的 1:1 比例来划分内存区域。在某些情况下，根据对象的存活率等因素，可以动态调整 from 区和 to 区的大小。如果发现存活对象较少，可能会适当减小 to 区的大小；反之，如果存活对象较多，可能会增大 to 区的大小。

考虑对象年龄等因素

部分垃圾收集器（如分代收集器中的新生代收集器）在使用复制算法时，会结合对象的年龄信息。年轻代中的对象通常存活率较低，所以可以根据对象年龄动态分配内存，而不是简单的 1:1 复制。在新生代使用复制算法进行垃圾回收时，S0 和 S1 区就分别扮演着 from 区和 to 区的角色。例如，将年轻代划分为 Eden 区和两个 Survivor 区（Survivor0 和 Survivor1），Eden 区和 Survivor 区的大小比例可能是 8:1:1 或者其他比例，这里 Survivor 区之间的复制就不是简单的 1:1 复制，而是根据对象在年轻代中的存活情况来决定是否复制以及复制到哪个 Survivor 区

3.标记-整理算法

标记-整理（Mark-and-Compact）算法是根据老年代的特点提出的一种标记算法，标记过程仍然与“标记-清除”算法一样，但后续步骤不是直接对可回收对象回收，而是让所有存活的对象向一端移动，然后直接清理掉端边界以外的内存

image.png|450

由于多了整理这一步，因此效率也不高，适合老年代这种垃圾回收频率不是很高的场景

4.分代收集算法

当前虚拟机的垃圾收集都采用分代收集算法，这种算法没有什么新的思想，只是根据对象存活周期的不同将内存分为几块。一般将 Java 堆分为新生代和老年代，这样我们就可以根据各个年代的特点选择合适的垃圾收集算法。

比如在新生代中，每次收集都会有大量对象死去，所以可以选择”标记-复制“算法，只需要付出少量对象的复制成本就可以完成每次垃圾收集。而老年代的对象存活几率是比较高的，而且没有额外的空间对它进行分配担保，所以我们必须选择“标记-清除”或“标记-整理”算法进行垃圾收集。

如上三种GC算法则是JVM虚拟机的基础GC算法，综合对比来看：

收集速度：复制算法 > 标记-清除算法 > 标记-整理算法
内存整齐度：复制算法 = 标记-整理算法 > 标记-清除算法
内存利用率：标记-整理算法 > 标记-清除算法 > 复制算法

在GC算法中，速度快的需要用空间来换，空间利用率高且整齐度高的，则需要牺牲时间来换取，所以相对而言，在绝大部分算法中，时间与空间不可兼得。

在上述三种算法中，复制算法和标-整算法都是基于标-清算法进行优化的，所以在现代的高性能JVM中绝大多数虚拟机都采用复制或标-整算法进行垃圾收集工作。

STW

在前面介绍GC算法时曾提到过，在发生GC时会停下所有的用户线程，从而导致Java程序出现全局停顿的无响应情况，而这种情况则被称为STW（Stop The World）世界暂停。在发生STW之后，所有的Java代码会停止运行，不过native代码是可以继续执行的，但也不能和JVM交互。一般发生STW都是由于GC引起的，但在某几种少数情况下，也会导致STW出现，如线程Dump、死锁检查、堆日志Dump等

一、GC发生时为什么需要STW？

GC发生时为什么都必须要STW呢？这主要有两个原因，一个是尽量为了避免浮动垃圾产生，第二个则是为了确保一致性。

1、避免产生浮动垃圾

如果在GC发生时不停下用户线程，那么会导致这么一种情况出现，就是刚刚标记完成一块区域中的对象，但转眼用户线程又在该区域中产生了新的“垃圾”。举个例子：

好比你生日聚会，聚会搞得屋子很乱，所以有人需要过来打扫卫生，但保洁人员刚扫完这边，那边又被搞乱了，又跑过去扫完那边之后，这边又被搞乱了，最终导致房间永远无法打扫干净。为了避免在打扫过程中产生“浮动垃圾”，就只能选择让所有聚会人员全部停止活动，这样才能确保最终屋子能够打扫干净。

同时，如果在GC发生时不做全局停顿，带来的后果则是：会给GC线程造成很大的负担，GC算法的实现难度也会增加，因为GC机制很难去准确判断哪些是垃圾。

2、确保内存一致性

在GC发生时，可达性分析算法的工作必须要在一个能够确保一致性的内存快照中进行。也就是指：在整个分析期间，JVM看起来就像被冻结在某个时间点上，不可以出现分析过程中对象引用关系还在不断变化的情况，该点不满足的话分析结果的准确性无法得到保证。这也是GC进行时，必须停止所有用户线程的其中一个重要原因。

二、STW会带来什么问题？

不过STW也会带来一些问题，比如导致客户端长时间无响应、HA（高可用）系统中的主从切换脑裂、上游系统宕机等。

1、客户端长时间无响应问题

因为STW发生时，会停止所有用户线程，所以对于客户端发送过来的网络请求并没有线程处理，最终导致客户端那边一直“转圈等待”，STW不结束，则客户端会一直处于无响应状态。

2、HA系统中的主从切换脑裂问题

同时如果你的系统做了主备、主从、多活等HA方案，那么如果主机触发GC发生STW，最终造成主机长时间停顿，而备机会监测到主机没有工作，于是备机开始尝试将流量切换到自身来处理，从备机变为了主机。
但旧主不工作只是暂时的，因为GC的原因导致暂停一段时间，而当GC完成后，旧主会依旧开始工作，最终造成了整个HA系统中出现了双主情况，形成了脑裂问题，最终影响生产环境。

3、上游系统宕机问题

如果你的系统是以多机器部署的工程项目，那么如果当某个工程所在的机器发送GC出现STW时，那么上游系统过来的请求则不会处理，如果STW时间一长，最终很有可能导致上游机器扛不住流量而出现宕机。