目录

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。
JVM-垃圾收集算法基础-LMLPHP

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

JVM-垃圾收集算法基础-LMLPHP

在引用计数法中,每个对象始终都知道自己的被引用数。当被引用数的值为0时,对象马上就会把自己作为空闲空间连接到空闲链表。也就是对象的内存空间可以被立即回收,垃圾回收效率非常高。但是引用计数法有个致命缺点,就是无法处理循环引用
假设A和B对象存在循环引用,在方法执行的时候他们的引用计数都为2。
JVM-垃圾收集算法基础-LMLPHP
当方法执行完,栈帧弹出后,A和B对象的引用计数减为1,此时由于他们计数永远无法到0,因此他们的内存无法被释放。

JVM-垃圾收集算法基础-LMLPHP

引用计数法除了无法处理循环引用的问题外,还有几个其他的问题,比如每次指针更新都需要更新计数器,计数器需要占用空间等。为了解决引用计数法的一些缺点,衍生出许多其他的引用计数法,比如延迟引用计数法、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标记所有存活对象。
  • 清除阶段:遍历整个堆,回收所有没有被标记的对象,将垃圾对象的内存空间连接到空闲链表。

JVM-垃圾收集算法基础-LMLPHP

回收前内存
JVM-垃圾收集算法基础-LMLPHP

回收后内存
JVM-垃圾收集算法基础-LMLPHP

优点

  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区域。

JVM-垃圾收集算法基础-LMLPHP

回收前内存
JVM-垃圾收集算法基础-LMLPHP

回收后内存
JVM-垃圾收集算法基础-LMLPHP

优点

  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个步骤
    • 查找新地址
    • 更新指针
    • 移动对象。

JVM-垃圾收集算法基础-LMLPHP

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

回收前内存
JVM-垃圾收集算法基础-LMLPHP

回收后内存
JVM-垃圾收集算法基础-LMLPHP

优点

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

06-05 22:27