垃圾回收的概念与算法（第四章）

《实战Java虚拟机：JVM故障诊断与性能优化 (第2版)》

第4章 垃圾回收的概念与算法

目标：

1. 了解什么是垃圾回收
2. 学习几种常用的垃圾回收算法
3. 掌握可触及性的概念
4. 理解 Stop-The-World（STW）

4.1. 认识垃圾回收 - 内存管理清洁工

垃圾回收（Garbage Collection，简称 GC），GC 中的垃圾，特指存在于内存中的、不会再被使用的对象，如果大量不会被使用的对象一直占着空间，在需要内存空间时有可能导致内存溢出。
垃圾回收并不是 JVM 独创的，早在 20 世纪 60 年代，垃圾回收就已经被 Lisp 语言所使用。现在，除了 Java，C#、Python 等语言都运用了垃圾回收的思想。

4.2. 常用的垃圾回收算法 - 清洁工具大 PK

常用的垃圾回收算法包括：引用计数法、标记清除法、复制算法、标记压缩法、分代算法和分区算法。

4.2.1. 引用计数法（Reference Counting）

1.最经典、最古老的一种垃圾收集算法。
2.实现：对于一个对象 A，只要任何一个对象引用了 A，则 A 的引用计数器就加 1，当引用失效时，引用计数器就减 1。只要对象 A 的引用计数器的值为 0，则对象 A 就不可能再被使用。
3.引用计数器的实现：为每个对象配备一个整型的计数器即可。
4.问题：非常严重的两个问题：
（1） 无法处理循环引用。因此，在 Java 的垃圾回收器中没有使用这种算法。
（2） 引用计算器要求在每次引用产生和消除的时候，伴随一个加法操作和一个减法操作，对系统性能会有一定的影响。

（1）一个简单的循环引用问题描述如下：有对象 A 和对象 B，对象 A 中含有对对象 B 的引用， 对象 B 中含有对象 A 的引用。此时，对象 A 和对象 B 的引用计数器都不为 0。但是，在系统中却不存在任何第 3 个对象引用了对象 A 或对象 B。也就是说，对象 A 和对象 B 是应该被回收的垃圾对象，但由于垃圾对象间相互引用，使垃圾回收器无法识别，引起了内存泄漏。

4.2.2. 标记清除法（Mark-Sweep）

1.标记清除法是现代垃圾回收算法的思想基础；
2.标记清除法将垃圾回收分为两个阶段：标记阶段和清除阶段；
3.实现：在标记阶段，首先通过根节点标记所有从根节点开始的可达对象。因此，未被标记的对象就是未被引用的垃圾对象。然后，在清除阶段，清除所有未被标记的对象。
4.问题：可能产生空间碎片；
5.注意：标记清除法先通过根节点标记所有的可达对象，然后清除所有的不可达对象，完成垃圾回收。

如图 4.2 所示，使用标记清除法对一块连续的内存空间进行回收。从根节点开始（这里显示了 2 个根节点），所有的有引用关系的对象均被标记为存活对象（箭头表示引用）。从根节点起，不可达对象均为垃圾对象。在标记操作完成后，系统回收所有不可达对象的空间。
如图 4.2 所示，回收后的空间是不连续的。在对象的堆空间分配过程中，尤其是大对象的内存分配，不连续内存空间的工作效率要低于连续空间。因此，这也是该算法的最大缺点。

4.2.3. 复制算法（Copying）

1.核心思想：将原有的内存空间分为两块，每次只使用其中一块，在进行垃圾回收时，将正在使用的内存中的存活对象复制到未使用的内存块中，之后清除正在使用的内存块中的所有对象，交换两个内存的角色，完成垃圾回收；
2.优点：
（1）效率高：如果系统中的垃圾对象很多，复制算法需要复制的存活对象数量就会相对很少；
（2）没有碎片：对象是在垃圾回收过程中统一被复制到新的内存空间中的，可确保回收后的内存没有碎片；
3.缺点：复制算法的代价是将系统内存折半；
4.新生代：存放年轻对象的堆空间。年轻对象指刚刚创建的或者经历垃圾回收次数不多的对象；
5.老年代：存放老年对象的堆空间。老年对象指经历多次垃圾回收后依然存活的对象；
6.注意：复制算法比较适合新生代，因为在新生代垃圾对象通常会多于存活对象，复制算法的效果会比较好；

如图 4.3 所示，A、B 两块相同的内存空间，A 在进行垃圾回收时，将存活对象复制到 B 中，B 在复制后保持连续。复制完成后，情况 A，并将空间 B 设置为当前使用空间。

在 Java 的新生代串行垃圾回收器中，使用了复制算法的思想。新生代分为 eden 区、from 区和 to 区 3 个部分。其中 from 区和 to 区可以视为用于复制的两块大小相同、地位相等且可进行角色互换的空间。from 区和 to 区也称为 survivor 区，即幸存者空间，用于存放未被回收的对象。

在进行垃圾回收时，eden 区的存活对象会被复制到未使用的 survivor 区（假设是 to 区），正在使用的 survivor 区（假设是 from ）的年轻对象也会被复制到 to 区（大对象或者老年对象会直接进入老年代，如果 to 区已满，则对象也会直接进入老年代）。此时，eden 区和 from 区的剩余对象就是垃圾对象，可以直接清空，to 区则存放此次回收后的存活对象。这种改进的复制算法，既保证了空间的连续性，又避免了大量的内存空间浪费，如图 4.4 所示，显示了复制算法的实际回收过程。当所有存活对象都复制到 survivor 区（图中为 to）后，简单地清空 eden 区和备用的 survivor 区（图中为 from）即可。

4.2.4. 标记压缩法（Mark-Compact）

复制算法的高效性是建立在存活对象少、垃圾对象多的前提下的。这种情况在新生代经常发生，但是在老年代，更常见的情况是大部分对象都是存活对象。如果依然使用复制算法，由于存活对象较多，复制的成本将很高。因此，基于老年代垃圾回收的特性，需要使用其他算法。

1.老年代的回收算法，是在标记清除法的基础上做了一些优化；
2.实现：首先需要从根节点开始，对所有可达对象做一次标记。之后，将所有的存活对象压缩到内存的一端。然后，清理边界外所有的空间。
3.优点：
（1）避免了碎片的产生；
（2）不需要两块相同的内存空间，性价比较高；
4.最终效果等同于标记清除法执行完后再进行一次内存碎片整理，因此，也可以称为标记清除压缩法；

如图 4.5 所示，在通过根节点标记出所有的可达对象后，沿虚线进行对象移动，将所有的可达对象都移动到一端，并保持它们之间的引用关系，最后清理边界外的空间，即可完成垃圾回收工作。

4.2.5. 分代算法（Generational Collecting）

在前面介绍的算法中，没有一种算法可以完全替代其他算法，它们都有自己的优势和特点。根据垃圾回收对象的特性，使用合适的算法，才是明智的选择。

1.分代算法将内存区间根据对象的特点分成几块，根据每块内存区间的特点使用不同的回收算法，以提高垃圾回收的效率；
2.新生代比较适合使用复制算法：新生代的特点是朝生夕灭；

一般来说，JVM 会将所有的新建对象都放入称为新生代的内存区域，新生代的特点是对象朝生夕灭，大约 90% 的新建对象会被很快回收，因此新生代比较适合使用复制算法。当一个对象经过几次回收后依然存活，对象就会被放入称为老年代的内存空间。在老年代中，几乎所有的对象都是经过几次垃圾回收依然得以存活的。因此，可以认为这些对象在一段时期内，甚至在应用程序的整个生命周期中，将是常驻内存的。

3.老年代使用标记压缩法或标记清除法：

在极端情况下，老年代对象的存活率可以达到 100%。如果依然使用复制算法回收老年代，将需要复制大量对象。再加上老年代的回收性价比也低于新生代，因此这种做法是不可取的。根据分代的思想，可以对老年代的回收使用与新生代不同的标记压缩法或标记清除法，以提高垃圾回收效率。如图4.6所示，显示了这种分代回收的思想。

4.新生代回收的频率很高，但是每次回收的耗时很短；老年代回收的频率比较低，但是会消耗更多的时间；

为了支持高频率的新生代回收，虚拟机可能使用一种叫作卡表（Card Table）的数据结构。卡表为一个比特位集合，每一个比特位可以用来表示老年代的某一区域中的所有对象是否持有新生代对象的引用。这样在新生代GC时，可以不用花大量时间扫描所有的老年代对象来确定每一个对象的引用关 系，可以先扫描卡表，只有当卡表的标记位为 1 时，才需要扫描给定区域的老年代对象， 而卡表位为0的老年代对象，一定不含有新生代对象的引用。如图 4.7 所示，卡表中每一位 表示老年代 4KB 的空间，卡表记录为 0 的老年代区域没有任何对象指向新生代，只有卡表 位为1的区域才有对象包含新生代引用，因此，在新生代GC时只需要扫描卡表位为1的老 年代空间。使用这种方式，可以大大加快新生代的回收速度。

4.2.6. 分区算法（Region）

1.分区算法将整个堆空间划分成连续的不同小区间，每一个小区间都独立使用，独立回收；
2.优点：可以控制一次回收小区间的数量；

一般来说，在相同条件下，堆空间越大，一次 GC 所需要的时间就越长，从而产生的停顿也越长。为了更好地控制 GC 产生的停顿时间，将一 块大的内存区域分割成多个小块，根据目标停顿时间，每次合理地回收若干个小区间，而不是回收整个堆空间，从而减少一次GC所产生的停顿。

4.3. 判断可触及性 - 谁才是真正的垃圾

4.3.1. 对象的复活 - finalize() 函数

1.可触及性包含以下 3 种状态：

• 可触及的：从根节点开始，可以到达这个对象；
• 可复活的：对象的所有引用都被释放，但是对象有可能在 finalize() 函数中复活；
• 不可触及的（可被回收）：对象的 finalize() 函数被调用，并且没有复活，就会进入不可触及状态，不可触及的对象不可能被复活，因为 finalize() 函数只会被调用一次；

垃圾回收的基本思想是考查每一个对象的可触及性，即从根节点开始是否可以访问这个对象，如果可以，则说明当前对象正在被使用，如果从所有的根节点开始都无法访问到某个对象，说明该对象已经不再使用了，一般来说，该对象需要被回收。但事实上，一个无法触及的对象有可能在某个条件下使自己“复活”，如果是这样的情况，那么对它的回收就是不合理的，为此，需要给出一个对象可触及性状态的定义，并规定在什么状态下才可以安全地回收对象。

2.finalize() 函数是一个非常糟糕的模式，不推荐使用 finalize() 函数释放资源；
（1）因为 finalize() 函数有可能发生引用外泄，在无意中复活对象；
（2）由于 finalize() 函数是被系统调用的，调用时间是不明确的，因此不是一个好的资源释放方案，推荐在 try-catch-finally 语句中进行资源的释放。

4.3.2. 引用和可触及性的强度

1.Java 中提供了 4 个级别的引用：强引用、软引用、弱引用和虚引用。

除强引用外，其他 3 种引用均可以在 java.lang.ref 包中找到。如图 4.9 所示，显示了这 3 种引用类型对应的类，开发人员可以在应用程序中直接使用它们。其中 FinalReference 为“最终”引用，它用以实现对象的 finalize() 函数。

2.强引用就是程序中一般使用的引用类型，强引用的对象是可触及的，不会被回收。软引用、弱引用和虚引用的对象是软可触及、弱可触及和虚可触及的，在一定条件下都是可以被回收的。
3.强引用的特点：
（1）强引用可以直接访问目标对象；
（2）强引用所指向的对象在任何时候都不会被系统回收，JVM 宁愿抛出 OOM 异常，也不会回收强引用所指向的对象；
（3）强引用可能导致内存泄漏；

4.3.3. 软引用 - 可被回收的引用

1.软引用是比强引用弱一点的引用类型。如果一个对象只持有软引用，那么当堆空间不足时，就会被回收。软引用使用 java.lang.ref.SoftReference 类实现。GC 未必会回收软引用的对象，但是当内存资源紧张时，软引用就会被回收，软引用对象不会引起内存溢出。

4.3.4. 弱引用 - 发现即回收

1.弱引用是一种比软引用弱的引用类型。在系统 GC 时，只要发现弱引用，不管系统堆空间情况如何，都会将对象进行回收。但是，由于垃圾回收器的线程通常优先级很低，并不一定能很快地发现持有弱引用的对象。在这种情况下，弱引用对象可以存在较长时间。一旦一个弱引用对象被垃圾回收器回收，便会加入一个注册的引用队列（这一点和软引用很像）。弱引用使用 java.lang.ref.WeakReference 类实现。
2.注意：软引用、弱引用都非常适合保持那些可有可无的缓存数据。如果这么做，当系统内存不足时，这些缓存数据会被回收，不会导致内存溢出。而当内存资源充足时，这些缓存数据又可以存在相当长的时间，从而起到让系统加速的作用。

4.3.5. 虚引用 - 对象回收跟踪

1.虚引用是所有引用类型中最弱的一个。一个持有虚引用的对象，和没有引用几乎是一样的，随时都可能被垃圾回收器回收。当试图通过虚引用的 get() 方法取得强引用时，总会失败。并且，虚引用必须和引用队列一起使用，它的作用在于跟踪垃圾回收过程；
2.当垃圾回收器准备回收一个对象时，如果发现它还有虚引用，就会在回收对象后，将这个虚引用加入引用队列，以通知应用程序对象的回收情况。
3.由于虚引用可以跟踪对象的回收时间，所以也可以将一些资源释放操作放在虚引用中执行和记录。

4.4. 垃圾回收时的停顿 - Stop-The-World

垃圾回收器的任务是识别和回收垃圾对象，以进行内存清理。为了让垃圾回收器可以正常且高效地执行，在大部分情况下，会要求系统进入一个停顿的状态。停顿的目的是终止所有应用线程的执行，只有这样系统中才不会有新的垃圾产生，同时停顿保证了系统状态在某一个瞬间的一致性，也有益于垃圾回收器更好地标记垃圾对象。因此，在垃圾回收时，都会产生应用程序的停顿。停顿产生时，整个应用程序会被卡死，没有任何响应，因 此这个停顿也叫作“Stop-The-World”（STW）。