JVM-垃圾收集算法基础

目录

• 目录
• 前言
• 手动释放内存导致的问题
• 垃圾判定方法
• 哪些对象是垃圾？
  • 引用计数算法
  • 可达性分析法
• 垃圾收集算法
  • 标记-清除
    • 优点
    • 缺点
    • 优化
  • 标记-复制
    • 优点
    • 缺点
    • 优化
  • 标记-整理
    • 优点
    • 缺点
    • 优化
• 参考文档

---

目录

JVM-运行时数据区域
JVM-对象及其内存布局
JVM-垃圾收集算法基础

前言

上一篇文章对JVM的对象的内存布局以及对象创建逻辑等内容进行了梳理，本篇文章对常见的垃圾回收算法以及HotSpot垃圾回收器进行深入解析。

手动释放内存导致的问题

在托管代码出现之前，我们申请一片内存使用完后，需要手动释放内存。手动释放有以下几个问题。

1. 忘记释放

忘记释放内存，会导致内存溢出。程序长时间申请的内存一直不释放。最终可能导致进程内存占满。

1. 重复释放

忘记释放对程序本身的执行的正确性不会产生影响，另一种更严重的问题是重复释放。当已经释放过后，该地址被其他地方重新分配。此时又再次释放或使用了该内存，可能会导致无法预料的现象。

int* p = new int(5);
*p = 5;
delete p;
delete p;//此时p指向的地址可能被重新分配使用

1. 释放类型错误

创建的是数组，释放的不是数组。这种情况若创建的时基本类型，那么不会有什么问题，但是创建元素不是基本类型而是对象，由于new T[n]实际分配的内存空间是n*sizeof(T) + 4,额外的4个字节用于存放数组元素个数。在调用delete []时，前面4个字节记录的元素个数分别执行各个元素的析构函数，然后调用free (p-4)释放内存。

Tclass * p = new Tclass[20];
p[0] = 1;
delete p; //应该使用delete []

1. 内存释放错误

int a = 200;
int b = 500;
int *p = new int(a);
p = &b;  //(1)

delete p;
p = NULL;

在delete p时会有2个问题。

1. p原来指向的地址成了内存泄漏(new int产生的地址) ，因为没释放。
2. p原先指向的是堆内存, 后续操作已经指向局部变量（栈空间）对象地址了，而栈空间是无须进行delete的，因此delete 栈空间时会报错。

垃圾判定方法

由于手动释放内存可能导致各种问题，因此在C、C++等非托管语言中，程序员手动进行内存管理，需要非常小心。
为了避免上述手动内存管理造成的问题，因此出现了自动管理内存的GC算法。把内存管理交给计算机，避免了手动释放内存导致的问题。
自动内存管理做了2件事情：找出垃圾和回收垃圾，使得该内存可以重复使用。通常不需要再使用（不被引用）的对象被称为垃圾，发现和释放被垃圾占用的空间称为垃圾收集。

那么如何才能确定哪些对象是垃圾？目前主要有2种方法，引用计数法和可达性分析法。

哪些对象是垃圾？

引用计数算法

1960年，George E. Collins 在论文中发布了叫作引用计数的GC算法。引用计数法中引入了一个概念，那就是“计数器”。计数器表示的是对象引用了这个对象（被引用数）。计数器是无符号的整数，用于存储计数器的空间大小根据算法和实现而有所不同。每当有一个对象引用自己，就把自己的引用计数+1。每当一个对象不再引用自己，就把自己的引用计数-1，当引用计数为0时，则表示对象成为垃圾，内存就可以被回收。

假设一开始有ABC三个对象，其中A引用了B，A和C被根（比如栈帧中的局部变量表）引用。此时他们的计数都为1。

接下来A引用了C，B不再被A引用。此时B的引用计数归0，B的内存就被空闲链表所连接，下次B的内存可以被重新分配重复使用。而C的引用计数从1变为2。

在引用计数法中，每个对象始终都知道自己的被引用数。当被引用数的值为0时，对象马上就会把自己作为空闲空间连接到空闲链表。也就是对象的内存空间可以被立即回收，垃圾回收效率非常高。但是引用计数法有个致命缺点，就是无法处理循环引用。
假设A和B对象存在循环引用，在方法执行的时候他们的引用计数都为2。

当方法执行完，栈帧弹出后，A和B对象的引用计数减为1，此时由于他们计数永远无法到0，因此他们的内存无法被释放。

引用计数法除了无法处理循环引用的问题外，还有几个其他的问题，比如每次指针更新都需要更新计数器，计数器需要占用空间等。为了解决引用计数法的一些缺点，衍生出许多其他的引用计数法，比如延迟引用计数法、Sticky引用计数法、Sticky引用计数法等，这里不做具体讨论。

由于引用计数法无法解决循环引用问题，因此Hotspot VM的堆区域的垃圾收集算法并没有采用引用计数法。而方法区中的运行时常量池（比如字符串表）因为不存在循环引用的问题，因此采用了引用计数法。

可达性分析法

当前主流的商用程序语言（Java、C#，上溯至前面提到的古老的Lisp）的内存管理系统，都是通过可达性分析（Reachability Analysis） 算法来判定对象是否存活的。这个算法的基本思路就是通过一系列称为GC Roots的根对象作为起始节点集，从这些节点开始，根据引用关系向下搜索，搜索过程所走过的路径称为“引用链”（Reference Chain），如果某个对象到GC Roots间没有任何引用链相连，或者用图论的话来说就是从GC Roots到这个对象不可达时，则证明此对象是不可能再被使用的。

在JVM中GC Roots包括以下几种：

1. 虚拟机栈引用的对象（实际是栈帧中的局部变量表引用的对象），如某方法的参数、局部变量等。
2. 方法区中静态变量引用的对象，如类中的静态引用类型变量。
3. 方法区中常量引用的对象，比如字符串表的引用。
4. 本地方法栈中JNI引用的对象。Java方法需要调用Native方法都需要通过JVM提供的JNI进行调用。
5. 以及其他JVM内部的引用，比如如klass对象，一些常驻的异常对象（比如NullPointExcepiton、OutOfMemoryError）等，系统类加载器，被同步锁（synchronized关键字）持有的对象，本地代码缓存等。

垃圾收集算法

通过引用计数法和可达性分析法，我们可以找出哪些是垃圾。找出垃圾，需要将垃圾清除。
前面说了引用计数法的垃圾清除非常简单，只要计数为0时，就可以将对象占用的内存空间加入到空闲链表中。内存就可以被回收利用。但是可达性分析法的垃圾清除并不容易。可达性分析并不是对象变为垃圾时就能立即回收。它需要一个查找的过程，通过查找整个堆空间或部分堆空间找出垃圾。然后才能对垃圾进行清除。19世纪60年代产生了几种垃圾收集算法，一直使用到现在。这些算法包括标记-清除、标记-复制和标记-整理。

标记-清除

最早出现的垃圾收集算法是 标记-清除（Mark-Sweep） 算法，Lisp之父和人工智能之父John McCarthy在1960年在其论文中首次提到了该GC算法。

标记-清除算法和名字一样，包含2个步骤：

• 标记阶段：遍历GC Roots标记所有存活对象。
• 清除阶段：遍历整个堆，回收所有没有被标记的对象，将垃圾对象的内存空间连接到空闲链表。

回收前内存

回收后内存

优点

1. 无需移动指针
   由于标记-清除算法只清除内存，而不压缩内存，因此对象地址不会发生改变，对象不移动时可以与其他GC算法相互组合使用。
2. 实现简单
   标记-清除只需要2个步骤，实现非常简单，与其他GC算法组合起来也就很简单了。
   在Hotspot虚拟机中，标记-清除算法通常用在老年代。比如CMS垃圾收集器的老年代就是使用标记-清除算法。

缺点

1. 内存碎片

   可以发现标记-清除有个严重的问题就是会造成内存碎片。当清理阶段时，会将垃圾对象空间插入到空闲链表中，若多个回收区域内存是连续的，还会将他们合并成一个空间。另外由于标记-清除算法会出现内存碎片，还会导致分配对象的效率降低。

2. 对象分配速度慢

   当分配对象的时候，需要则遍历每个空闲链表的节点。通常使用空闲链表有三种分配方式：First-fit、Best-fit和Worst-fit。

   • First-fit: First-fit优先找到第一块大于或等于需要分配内存大小的空闲块。如果空闲块大于所需分配的内存时将其分割为2块。
   • Best-fit: Best-fit会遍历整个空闲链表，尽可能找到最适合的内存块，它会找到大于或等于需要分配内存大小的最小分块。
   • Worst-fit: Worst-fit会找出空闲链表中最大的分块，将其分割成mutator申请的大小和分割后剩余的大小，目的是将分割后剩余的分块最大化。但因为Worst-fit很容易生成大量小的分块，一般不推荐使用。

3. 与写时复制技术不兼容
   标记-清除 算法除了会产生内存碎片以外，还无法和写时复制技术一起使用。由于 标记-清除 算法需要修改对象头部的标记用于记录对象是否存活，因此，发生GC时，存活的对象头部的标记就会被修改，从而导致出现内存复制。

4. 吞吐量与堆大小相关

   标记-清除 算法在清除阶段需要遍历整个堆，找到没有标记的对象进行清除。因此随着堆增大，GC效率就会降低。

优化

为了解决 标记-清除 算法由于内存碎片导致对象分配速度慢的问题，衍生出一些优秀的算法。

1. 多个空闲链表：将不同大小的空闲块分组，提高内存分配速度。
2. BiBOP（Big Bag Of Pages）法：把堆分割成固定大小的块，让每个块只能配置同样大小的对象。分配指定大小的对象，直接找到对应的块进行分配。
3. 位图标记：将对象标记从对象头提取出，放在一个单独的位图表格种，使得标记-清除算法与写时复制技术兼容。
4. 延迟清除法：由于清除算法需要遍历整个堆，因此将清除步骤延迟到创建对象的步骤处理，降低最大暂停时间。清除算法会记录上一次清除的位置，当创建对象的时候，会从上一次清除的位置继续向后清除，因此不会遍历整个堆。

标记-复制

标记-清除 算法高效的同时带来了内存碎片的问题，而引用计数法又无法回收循环引用的对象。
1963年，也有“人工智能之父”之称的Marvin L. Minsky在论文中发布了复制算法。
1969年，Fenichel提出了一种称为“半区复制”（Semispace Copying）的垃圾收集算法，它将可用内存按容量划分为大小相等的两块。一块称为From空间，另一块称为To空间。将From空间的内容复制到To空间，然后把From空间进行清理。

标记-复制算法包含3个步骤：

• 划分区域：将内存分为2块等大的区域。
• 复制：将存活的对象从From区域复制到To区域。
• 清除：将From区域进行整体清除。
• 互换：将From区域和To区域互换。原来的To区域变为新的From区域，原来的From区域变为新的To区域。

回收前内存

回收后内存

优点

1. 无碎片化

   从上面的过程可以发现，标记-复制 算法处理完后，内存就处于规整状态。就不会发生实际可用内存足够，但是却没有足够的内存块分配大对象的情况。

2. 对象分配速度快

   由于标记-复制算法不会产生碎片，因此分配对象的逻辑就非常简单快速。在JVM-对象及其内存布局也提到了，当内存规整时，可以使用 指针碰撞 的方式快速的分配对象。而无需遍历空闲链表。

3. GC吞吐量高

   标记-复制 算法使用深度优先搜索的方式遍历每个GC Roots对象。先将根对象和根对象的所有引用的子对象复制到To区域，再处理下一个根对象。在清理时直接清理整个From区域，无需遍历整个堆。因此 标记-复制 算法的效率与堆大小无关，只与存活对象（被GC根引用的对象）数量相关。

4. 与缓存兼容

   标记-复制 算法会将引用相关的对象按续排放，可以充分利用缓存实现高速访问。

缺点

1. 内存利用率低

   由于 标记-复制 算法将区域分为两半，只有一半可以使用，因此会造成内存的浪费。相当于使用空间换时间，且空间的成本相对较高。

2. 对象移动

   标记-复制算法每次都会移动对象，因此与一些要求对象不移动的GC算法不兼容。

3. 递归调用

   普通的 标记-复制 算法会递归调用子对象重复 标记-复制 操作，就会存在执行新的方法而创建栈帧，增加额外的资源消耗。不过在1970年出现了迭代式的 标记-复制 算法，解决了这个问题。

优化

1. 1970年，C. J. Cheney研究出了迭代式标记-复制GC算法，优化了传统递归调用导致的资源占用问题。
2. 1991年，Paul R. Wilson、Michael S. Lam和Thomas G. Moher提出的近似深度优先搜索法，解决了迭代式标记-复制GC算法由于广度优先搜索策略造成无法重复使用缓存的问题。
3. 另外还出现了多空间复制算法，优化了堆使用率。传统的复制算法只能利用一半的堆空间。而多空间复制算法采用组合算法方式进行垃圾收集，该算法将堆分为10份，其中2份使用复制算法，另外8份采用标记-清除算法。
4. 在JVM中，采用的是1989年Andrew Appel针对具备“朝生夕灭”特点的对象，研究出的半区复制分代策略，现在称为“Appel式回收”。它仅仅使用整个堆中的一小块使用标记-复制算法，从而提高内存使用率。

标记-整理

标记-复制 算法解决了 标记-清除 算法内存碎片的问题，但是也同时带来另一个问题，就是内存使用率低的问题。1974年Edward Lueders提出了另外一种有针对性的 标记-整理（Mark-Compact） 算法(也可以叫标记-压缩算法)。

标记-整理 算法包含2个步骤：

• 标记阶段：标记所有可回收的对象。
• 整理阶段：分为3个步骤
  • 查找新地址
  • 更新指针
  • 移动对象。

标记-整理 算法解决了 标记-复制 算法的空间占用问题，但是由于整理阶段需要遍历多次堆，因此性能相比其他两种GC算法，也会差很多。可以发现每种垃圾回收算法都有自己的优点和缺点。并不存在一个完美的算法能够同时兼顾空间和时间。

回收前内存

回收后内存

优点

1. 堆利用率高
   能够使用全部的堆内存。不像 标记-清除 和 标记-复制 算法只能使用部分堆内存。
2. 不会产生内存碎片
   由于 标记-整理 会整理堆，使其变为规整。因此不会产生内存碎片，另外对象的分配速度也很快。

缺点

由于整理阶段，需要多次遍历整个堆。因此GC性能较差，甚至可能长时间出现停顿（STW）现象。

优化

1. Robert A. Saunders研究出来的名为Two-Finger的压缩算法，只需要搜索两次堆，比传统的算法少一次堆的搜索，但是该算法要求所有对象大小必须一致，且不会按对象原来的顺序进行压缩（无法使用CPU高速缓存）。
2. B. K. Haddon和W. M. Waite于1967年研究出来的表格算法，该算法比较复杂，但是解决了Two-Finger会导致对象顺序改变的问题，可以通过缓存提高访问速度。
3. Stephen M. Blackburn和Kathryn S. McKinley于2008年研究出来的ImmixGC算法，将标记-清除算法和压缩组合使用。由于存在标记-清除算法，因此存在内存碎片的情况。另外该算法堆内存分块处理，在极端情况可能会导致一个块只能存一个对象导致内存使用率不高，另外该算法在压缩的时候也不会顾及对象原始顺序。

参考文档

1. 《垃圾回收算法与实现》
2. 《深入理解Java虚拟机》

---