四、垃圾收集算法

在前一章我们讲了两种判断对象死亡的方法：引用计数和可达性分析，本章我们来介绍下四种垃圾收集算法，这些内容都是为我们后一章讲解jvm垃圾收集器做铺垫。

一、收集算法

1、标记清除（Mark-Sweep）

这是最基础的垃圾回收算法，之所以说它是最基础的是因为它最容易实现，思想也是最简单的。标记-清除算法分为两个阶段：标记阶段和清除阶段。标记阶段的任务是标记出所有需要被回收的对象，清除阶段就是回收被标记的对象所占用的空间。具体过程如下图所示：

这种算法的两个缺陷：
效率问题 (如果需要标记的对象太多，效率不高)
空间问题（标记清除后会产生大量不连续的碎片）

2、复制算法(Copying)

为了解决Mark-Sweep算法的缺陷，Copying算法就被提了出来。它将可用内存按容量划分为大小相等的两块，每次只使用其中的一块。当这一块的内存用完了，就将还存活着的对象复制到另外一块上面，然后再把已使用的内存空间一次清理掉，这样一来就不容易出现内存碎片的问题。具体过程如下图所示：

这种算法虽然实现简单，运行高效且不容易产生内存碎片，但是却对内存空间的使用做出了高昂的代价，因为能够使用的内存缩减到原来的一半。
很显然，Copying算法的效率跟存活对象的数目多少有很大的关系，如果存活对象很多，那么Copying算法的效率将会大大降低。

3、标记整理（Mark-Compact）

为了解决Copying算法的缺陷，充分利用内存空间，提出了Mark-Compact算法。该算法标记阶段和Mark-Sweep一样，但是在完成标记之后，它不是直接清理可回收对象，而是将存活对象都向一端移动，然后清理掉端边界以外的内存。具体过程如下图所示：

4、分代收集(Generational Collection)

分代收集算法是目前大部分JVM的垃圾收集器采用的算法。它的核心思想是根据对象存活的生命周期将内存划分为若干个不同的区域。一般情况下将堆区划分为老年代（Tenured Generation）和新生代（Young Generation），老年代的特点是每次垃圾收集时只有少量对象需要被回收，而新生代的特点是每次垃圾回收时都有大量的对象需要被回收，那么就可以根据不同代的特点采取最适合的收集算法。
目前大部分垃圾收集器对于新生代都采取Copying算法，因为新生代中每次垃圾回收都要回收大部分对象，也就是说需要复制的操作次数较少，但是实际中并不是按照1：1的比例来划分新生代的空间的，一般来说是将新生代划分为一块较大的Eden空间和两块较小的Survivor空间，每次使用Eden空间和其中的一块Survivor空间，当进行回收时，将Eden和Survivor中还存活的对象复制到另一块Survivor空间中，然后清理掉Eden和刚才使用过的Survivor空间。
而由于老年代的特点是每次回收都只回收少量对象，一般使用的是Mark-Compact算法。

二、标记算法底层实现：三色标记

定义

三色标记算法是一种垃圾回收的标记算法。它可以让JVM不发生或仅短时间发生STW(Stop The World)，从而达到清除JVM内存垃圾的目的。JVM中的CMS、G1垃圾回收器 所使用垃圾回收算法即为三色标记法。

事先约定

:::info 白色：对象未被标记（需要被清除的垃圾）
灰色：对象被标记了，但是该对象下的属性未被完全标记。（需要在该对象中寻找垃圾）
黑色：代表该对象以及该对象下的属性全部被标记过了。（程序需要用到的对象，不应该被回收） :::

三色标记遍历过程

:::info 1.初始时，全部对象都是白色的
2.GC Roots直接引用的对象变成灰色
3.从灰色集合中获取元素：
3.1 将本对象直接引用的对象标记为灰色
3.2 将本对象标记为黑色
4.重复步骤3，直到灰色的对象集合变为空
5.结束后，仍然被标记为白色的对象就是不可达对象，视为垃圾对象。 :::

三色标记存在问题以及解决方案

:::info 多标产生浮动垃圾：并发标记的过程中，若一个已经被标记成黑色或者灰色的对象，突然变成了垃圾，由于不会再对黑色标记过的对象重新扫描,所以不会被发现，那么这个对象不是白色的但是不会被清除，重新标记也不能从GC Root中去找到，所以成为了浮动垃圾，「浮动垃圾对系统的影响不大，留给下一次GC进行处理即可」。
对象漏标问题：并发标记的过程中，一个业务线程将一个未被扫描过的白色对象断开引用成为垃圾（删除引用），同时黑色对象引用了该对象（增加引用）（这两部可以不分先后顺序）；因为黑色对象的含义为其属性都已经被标记过了，重新标记也不会从黑色对象中去找，导致该对象被程序所需要，却又要被GC回收，此问题会导致系统出现问题，而CMS与G1，两种回收器在使用三色标记法时，都采取了一些措施来应对这些问题，「CMS对增加引用环节进行处理（Increment Update），G1则对删除引用环节进行处理(SATB)。」 ::: :::info 解决方案：
CMS：写屏障 + 增量更新
G1：写屏障 + 原始快照 :::