JVM-垃圾收集算法基础

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

1. 忘记释放

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

2. 重复释放

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

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

部分编译器会阻止重复释放的问题，良好的编码是在delete后将指针置空。

3. 释放类型错误

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

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

4. 内存释放错误

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虚拟机》