JVM虚拟机-垃圾回收算法

垃圾回收分为两个阶段：标记阶段和清除阶段。

在堆里存放着几乎所有的Java对象实例，在GC执行垃圾回收之前，首先需要区分出内存中哪些是存活对象，哪些是已经死亡的对象。只有被标记为己经死亡的对象，GC才会在执行垃圾回收时，释放掉其所占用的内存空间，这个过程称为垃圾标记阶段。

当成功区分出内存中存活对象和死亡对象后，GC接下来的任务就是执行垃圾回收，释放掉无用对象所占用的内存空间，这个过程称之为清除阶段。

标记阶段

当一个对象已经不再被任何的存活对象继续引用时，便可判定为已经死亡。

判断对象存活一般有两种方式：

• 引用计数算法
• 可达性分析算法

引用计数算法

引用计数算法（Reference Counting）：对每个对象保存一个整型的引用计数器属性，用于记录对象被引用的情况。

例如：一个对象A，只要有任何一个对象引用了A，则A的引用计数器就加1；当引用失效时，引用计数器就减1。只要对象A的引用计数器的值为0，即表示对象A不可能再被使用，可进行回收。

优点：实现简单，垃圾对象便于辨识；判定效率高，回收没有延迟性。

缺点：需要单独的字段存储计数器，增加了存储空间的开销。每次赋值都需要更新计数器，伴随着加法和减法操作，增加了时间开销。且无法处理循环引用的情况（致命），这也导致在Java的垃圾回收器中没有使用这类算法。

循环引用

当p的指针断开的时候，内部的引用形成一个循环，这就是循环引用，从而造成内存泄漏。

代码演示：测试Java是否采用了引用计数算法，及循环引用

/**
 * 引用计数算法测试
 *
 * @author: 陌溪
 * @create: 2020-07-12-10:26
 */
public class RefCountGC {
    // 这个成员属性的唯一作用就是占用一点内存
    private byte[] bigSize = new byte[5*1024*1024];
    // 引用
    Object reference = null;

    public static void main(String[] args) {
        RefCountGC obj1 = new RefCountGC();
        RefCountGC obj2 = new RefCountGC();
        obj1.reference = obj2;
        obj2.reference = obj1;
        //触发循环引用，引用计数法将无法进行回收对象
        obj1 = null;
        obj2 = null;
        // 显示的执行垃圾收集行为，判断obj1 和 obj2是否被回收？
        System.gc();
    }
}

运行结果

[GC (System.gc()) [PSYoungGen: 15490K->808K(76288K)] 15490K->816K(251392K), 0.0061980 secs] [Times: user=0.00 sys=0.00, real=0.36 secs] 
[Full GC (System.gc()) [PSYoungGen: 808K->0K(76288K)] [ParOldGen: 8K->672K(175104K)] 816K->672K(251392K), [Metaspace: 3479K->3479K(1056768K)], 0.0045983 secs] [Times: user=0.00 sys=0.00, real=0.00 secs] 
Heap
 PSYoungGen      total 76288K, used 655K [0x000000076b500000, 0x0000000770a00000, 0x00000007c0000000)
  eden space 65536K, 1% used [0x000000076b500000,0x000000076b5a3ee8,0x000000076f500000)
  from space 10752K, 0% used [0x000000076f500000,0x000000076f500000,0x000000076ff80000)
  to   space 10752K, 0% used [0x000000076ff80000,0x000000076ff80000,0x0000000770a00000)
 ParOldGen       total 175104K, used 672K [0x00000006c1e00000, 0x00000006cc900000, 0x000000076b500000)
  object space 175104K, 0% used [0x00000006c1e00000,0x00000006c1ea8070,0x00000006cc900000)
 Metaspace       used 3486K, capacity 4496K, committed 4864K, reserved 1056768K
  class space    used 385K, capacity 388K, committed 512K, reserved 1048576K

上述进行了GC收集的行为，将上述的新生代中的两个对象都进行回收了

PSYoungGen: 15490K->808K(76288K)] 15490K->816K(251392K)

如果使用引用计数算法，那么这两个对象将会无法回收（开启了循环引用）。而现在两个对象被回收了，说明Java使用的不是引用计数算法来进行标记的。

• Python中使用了引用计数，是如何解决循环引用：使用弱引用weakref，weakref的Python的标准库

可达性分析算法

可达性分析算法：也可以称为 根搜索算法、追踪性垃圾收集（Tracing Garbage Collection）。

可达性分析算法优点：实现简单、执行高效，且有效地解决在引用计数算法中循环引用的问题，防止了内存泄漏的发生。

可达性分析算法实现思路：

以根对象集合（GCRoots，一组必须活跃的引用，特征：它们只会引⽤其他对象，⽽不会被其他对象引⽤）为起始点，按照从上至下的方式搜索被根对象集合所连接的目标对象是否可达。内存中的存活对象都会被根对象集合直接或间接连接着，使用可达性分析算法搜索所走过的路径称为引用链（Reference Chain）。当目标对象没有任何引用链相连，则是不可达的，就意味着该对象己经死亡，可以标记为垃圾对象。反之，只有能够被根对象集合直接或者间接连接的对象才是存活对象。

GC Roots角色

充当GC Roots的角色：

• 虚拟机栈中引用的对象 。如：各个线程被调用的方法中使用到的参数、局部变量等。
• 本地方法栈内JNI（通常说的本地方法）引用的对象方法区中类静态属性引用的对象。如：Java类的引用类型静态变量
• 方法区中常量引用的对象。如：字符串常量池（string Table）里的引用
• 所有被同步锁synchronized持有的对象
• Java虚拟机内部的引用。

• 基本数据类型对应的Class对象，一些常驻的异常对象（如：NullPointerException、OutOfMemoryError），系统类加载器。

• 反映java虚拟机内部情况的JMXBean、JVMTI中注册的回调、本地代码缓存等。

充当GCRoots角色总结：

总结一句话就是，除去堆空间外，其他的一些结构可以作为GC Roots进行可达性分析。如 虚拟机栈、本地方法栈、方法区、字符串常量池 等地方对堆空间进行引用的

除了这些固定的GC Roots集合以外，根据用户所选用的垃圾收集器以及当前回收的内存区域不同，还可以有其他对象“临时性”地加入，共同构成完整GC Roots集合。比如：分代收集和局部回收（PartialGC）。

如果只针对Java堆中的某一块区域进行垃圾回收（比如：典型的只针对新生代），必须考虑到内存区域是虚拟机自己的实现细节，更不是孤立封闭的，这个区域的对象完全有可能被其他区域的对象所引用，这时候就需要一并将关联的区域对象也加入GCRoots集合中去考虑，才能保证可达性分析的准确性。

小技巧

由于Root采用栈方式存放变量和指针，所以如果一个指针，它保存了堆内存里面的对象，但是自己又不存放在堆内存里面，那它就是一个Root。

注意：

如果要使用可达性分析算法来判断内存是否可回收，那么分析工作必须在一个能保障一致性的快照中进行。这点不满足的话分析结果的准确性就无法保证。这也是导致GC进行时必须“Stop The World”的一个重要原因。即使是号称（几乎）不会发生停顿的CMS收集器中，枚举根节点时也是必须要停顿的。

实战：MAT与JProfiler的GC Roots溯源

清除阶段

特长生

目前在JVM中比较常见的三种垃圾收集算法：

• 标记-清除算法（Mark-Sweep）
• 复制算法（copying）
• 标记-压缩算法（Mark-Compact）

标记-清除算法

标记-清除算法（Mark-Sweep）是一种非常基础和常见的垃圾收集算法，该算法被J.McCarthy等人在1960年提出并并应用于Lisp语言。

执行过程

当堆中的有效内存空间（available memory）被耗尽的时候，就会停止整个程序（也被称为stop the world），然后进行两项工作：标记和清除

• 标记：Collector从引用根节点开始遍历，标记所有被引用的对象（即：不会成为垃圾）。一般是在对象的Header中记录为可达对象。
• 清除：Collector对堆内存从头到尾进行线性的遍历，如果发现某个对象在其Header中没有标记为可达对象，则进行回收

内存分配策略

• 如果内存规整

• 采用指针碰撞的方式进行内存分配

• 如果内存不规整

• 空闲地址列表分配

空闲地址列表分配

在清除阶段程序会遍历整个堆，对有标记的对象(不是垃圾)把标记清除掉等待下次GC，对于没有标记的对象（垃圾）则会将垃圾对象地址放到一个单向的空闲列表free_list里面（并没有清空内存），而当新建对象需要分配内存时，从free_list里面找到合适大小的地址所在的内存空间进行覆盖。

合适大小空间的选择策略

新建对象分配内存时假设需要大小为size，则需要对空闲列表free_list进行一次单向遍历找出大于等于size的块。对于如何找到合适的块有以下三种分配策略:

• First-fit：找到大于等于size的块立即返回
• Best-fit：遍历整个空闲列表，返回大于等于size的最小分块
• Worst-fit：遍历整个空闲列表，找到最大的分块，然后切成两部分，一部分size大小，并将该部分返回。

这三种策略里面Worst-fit的空间利用率看起来是最合理，但实际上切分之后会造成很多的小块，形成内存碎片，所以不推荐使用。对于First-fit和Best-fit来说，考虑到分配的速度和效率First-fit是更为明智的选择。

缺点

• 标记清除算法的效率不算高
• 在进行GC的时候，需要停止整个应用程序，用户体验较差
• 这种方式清理出来的空闲内存是不连续的，产生内碎片，需要维护一个空闲列表

复制算法

为了解决标记-清除算法在垃圾收集效率方面的缺陷，M.L.Minsky于1963年发表了著名的论文，“使用双存储区的Lisp语言垃圾收集器CA LISP Garbage Collector Algorithm Using Serial Secondary Storage”。M.L.Minsky在该论文中描述的算法被人们称为复制（Copying）算法，它也被M.L.Minsky本人成功地引入到了Lisp语言的一个实现版本中。

执行过程

将活着的内存空间分为两块，每次只使用其中一块，在垃圾回收时将正在使用的内存中的存活对象复制到未被使用的内存块中，之后清除正在使用的内存块中的所有对象，交换两个内存的角色，最后完成垃圾回收。（堆空间新生代S0/S1设计思路）

优缺点

优点

• 没有标记和清除过程，实现简单，运行高效
• 复制过去以后保证空间的连续性，不会出现“碎片”问题。

缺点

• 此算法的缺点也是很明显的，就是需要两倍的内存空间。
• 对于G1这种分拆成为大量region的GC，复制而不是移动，意味着GC需要维护region之间对象引用关系，内存或是时间都是不小的开销

适用场景

存活对象少，来及对象多的场景下复制算法的性价比较高。

如果系统中的垃圾对象很多，复制算法的效率会很低。如：在新生代，对常规应用的垃圾回收，一次通常可以回收70% - 99% 的内存空间，使用复制算法回收性价比很高。而老年代大量的对象存活，复制的对象会有很多，效率会很低。所以现在的商业虚拟机都是用这种收集算法回收新生代（S0/S1设计）。

标记-压缩算法

复制算法对新生代性价比很高，而对于老年代则不是很友好，因此需要一种适合类似于老年代存活对象多的场景的算法。

标记-清除算法，尚可应用在老年代中，但该算法执行效率低下，且在执行完内存回收后还会产生内存碎片，所以JVM的设计者在此基础之上进行改进。标记-压缩（Mark-Compact）算法由此诞生。

1970年前后，G.L.Steele、C.J.Chene和D.s.Wise等研究者发布标记-压缩算法。在许多现代的垃圾收集器中，人们都使用了标记-压缩算法或其改进版本。

执行过程

依然分为两项工作：标记和压缩

标记：标记-清除算法一样，从根节点开始标记所有被引用对象

压缩：将所有的存活对象压缩到内存的一端，按顺序排放。之后，清理边界外所有的空间。

优缺点

优点

• 消除了标记-清除算法当中，内存区域分散的缺点，需要给新对象分配内存时，JVM只需要持有一个内存的起始地址即可（而标记-清除算法需要维护一张空闲列表，维护空闲列表明显成本高了很多）。
• 消除了复制算法当中，内存双倍的高额开销。

缺点

• 效率低于复制算法
• 移动对象的同时，如果对象被其他对象引用，则还需要调整引用的地址
• 移动过程中，需要全程暂停用户应用程序。即：Stop the World

标-清、复制、标-压对比

没有最好的算法，只有最合适的算法

算法名称

标记-清除算法

复制算法

标记-压缩算法

速率

中等

最快

最慢

空间开销

少（有内存碎片）

通常需要活对象的2倍空间（无内存碎片）

少（无内存碎片）

移动对象

否

是

是

全能王

标记清除、复制、标记压缩，三种算法都具有自己独特的优势和特点，相互不可替代，没有一种算法可以完全替代。全能王因此应运而生：分代收集算法。

分代收集算法

分代收集算法基于不同生命周期的对象可以采取不同的收集方式。一般是把Java堆分为新生代和老年代，这样就可以根据各个年代的特点使用不同的回收算法，以提高垃圾回收的效率。

目前几乎所有的虚拟机GC都采用分代收集算法执行垃圾回收。在HotSpot中，基于分代的概念，GC所使用的内存回收算法必须结合年轻代和老年代各自的特点。

• 年轻代（Young Gen）

年轻代特点：区域相对老年代较小，对象生命周期短、存活率低，回收频繁。这种情况复制算法的回收整理，速度是最快的。复制算法的效率只和当前存活对象大小有关，因此很适用于年轻代的回收。而复制算法内存利用率不高的问题，通过HotSpot中的两个survivor的设计得到缓解。

• 老年代（Tenured Gen）

老年代特点：区域较大，对象生命周期长、存活率高，回收不及年轻代频繁。这种情况存在大量存活率高的对象，复制算法明显变得不合适。一般采用标记-清除或者标记-清除与标记-压缩的混合实现。

• 标记的开销与存活对象的数量成正比。
• 清除的开销与所管理区域的大小成正相关。
• 压缩的开销与存活对象的数据成正比。

以HotSpot中的CMS回收器为例，CMS是基于标记-清除算法实现的，对于对象的回收效率很高。而对于碎片问题，CMS采用基于标记-压缩算法的Serial old回收器作为补偿措施：当内存回收不佳（碎片导致的Concurrent Mode Failure时），将采用serial old执行Major GC以达到对老年代内存的整理。

SWT优化

上述现有的算法，在垃圾回收过程中，应用软件将处于一种Stop the World（STW）的状态。在STW状态下，应用程序所有的线程都会挂起，暂停一切正常的工作，等待垃圾回收的完成。如果垃圾回收时间过长，应用程序会被挂起很久，将严重影响用户体验或者系统的稳定性。

• 一次性将所有的垃圾进行处理，会造成系统长时间的停顿 —> 增量收集算法
• 堆空间大，进行垃圾处理，会造成系统长时间的停顿 —> 分区算法

增量收集算法

增量收集（Incremental Collecting）算法让垃圾收集线程和应用程序线程交替执行。每次，垃圾收集线程只收集一小片区域的内存空间，接着切换到应用程序线程。依次反复，直到垃圾收集完成。

总体而言，增量收集算法的基础仍是传统的标记-清除和复制算法。增量收集算法通过对线程间冲突的妥善处理，允许垃圾收集线程以分阶段的方式完成标记、清理或复制工作。

优缺点

优点

能减少系统的停顿时间

缺点线程切换和上下文转换的时间消耗，会使得垃圾回收的总体成本上升，造成系统吞吐量的下降·

分区算法

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

分区算法将整个堆空间划分成连续的不同小区间。每一个小区间都独立使用，独立回收。这种算法的好处是可以控制一次回收多少个小区间。

对象的终止机制

对象的finalize()方法

Java语言提供了对象终止（finalization）机制来允许开发人员提供对象被销毁之前的自定义处理逻辑。当垃圾回收器发现没有引用指向一个对象，准备垃圾回收此对象之前，总会先调用这个对象的finalize()方法。

对象的finalize() 方法允许在子类中被重写，只会被调用一次，用于在对象被回收时进行资源释放。通常在这个方法中进行一些资源释放和清理的工作。如关闭文件、套接字和数据库连接等。

注意：

永远不要主动调用某个对象的finalize（）方法，应该交给垃圾回收机制调用。原因包括下面三点：

1. 在finalize（）时可能会导致对象复活。
2. finalize（）方法的执行时间是没有保障的，它完全由GC线程决定，极端情况下，若不发生GC，则finalize（）方法将没有执行机会。 因为优先级比较低，即使主动调用该方法，也不会因此就直接进行回收。
3. 一个糟糕的finalize（）会严重影响GC的性能。

虚拟机对象的三种状态

生存or死亡：由finalize（）分割

当所有的根节点都无法访问到某个对象，说明对象己经不再使用了。一般来说，此对象需要被回收。但事实上，也并非是“非死不可”的，这时候它们暂时处于“缓刑”阶段。一个无法触及的对象有可能在某一个条件下“复活”自己，如果这样，那么对它的回收就是不合理的，为此，定义虚拟机中的对象可能的三种状态。如下：

• 可触及的：从根节点开始，可以到达这个对象。
• 可复活的：对象的所有引用都被释放，但是对象有可能在finalize（）中复活。
• 不可触及的：对象的finalize（）被调用，并且没有复活，则进入不可触及状态。不可触及的对象可以被回收。

具体过程

判定一个对象A是否可回收，至少要经历两次标记过程：

1. 当对象A到GC Roots没有引用链，进行第一次标记。
2. 进行筛选，判断此对象是否有必要执行finalize（）方法

1. 如果对象A没有重写finalize（）方法，或者finalize（）方法已经被虚拟机调用过，则虚拟机视为“没有必要执行”，对象A被判定为不可触及的，可以被回收，结束操作。
2. 如果对象A重写了finalize（）方法，且还未执行过，那么对象A会被插入到F-Queue队列中，由一个虚拟机自动创建的、低优先级的Finalizer线程触发其finalize（）方法执行。之后GC对F-Queue队列中的对象进行第二次标记。

1. 如果对象A在finalize（）方法中与引用链上的任何一个对象建立了联系，那么在第二次标记时，对象A会被移出“即将回收”集合。之后，当对象A会再次出现没有引用存在的情况。在这个情况下，finalize方法不会被再次调用，对象会直接变成不可触及的状态，也就是说，一个对象的finalize方法只会被调用一次。
2. 如果对象A在finalize（）方法中没有任何引用，对象A被判定为不可触及的，可以被回收，结束操作。

图示Finalizer线程

代码演示

重写 finalize()方法，使对象重新复活

/**
 * 测试Object类中finalize()方法
 * 对象复活场景
 */
public class CanReliveObj {
    // 类变量，属于GC Roots的一部分
    public static CanReliveObj canReliveObj;

    @Override
    protected void finalize() throws Throwable {
        super.finalize();
        System.out.println("调用当前类重写的finalize()方法");
        canReliveObj = this;
    }

    public static void main(String[] args) throws InterruptedException {
        canReliveObj = new CanReliveObj();
        canReliveObj = null;
        System.gc();
        System.out.println("-----------------第一次gc操作------------");
        // 因为Finalizer线程的优先级比较低，暂停2秒，以等待它
        Thread.sleep(2000);
        if (canReliveObj == null) {
            System.out.println("obj is dead");
        } else {
            System.out.println("obj is still alive");
        }

        System.out.println("-----------------第二次gc操作------------");
        canReliveObj = null;
        System.gc();
        // 下面代码和上面代码是一样的，但是 canReliveObj却自救失败了
        Thread.sleep(2000);
        if (canReliveObj == null) {
            System.out.println("obj is dead");
        } else {
            System.out.println("obj is still alive");
        }

    }
}

运行结果：在进行第一次清除的时候，我们会执行finalize方法，然后 对象 进行了一次自救操作，但是因为finalize()方法只会被调用一次，因此第二次该对象将会被垃圾清除。

-----------------第一次gc操作------------
调用当前类重写的finalize()方法
obj is still alive
-----------------第二次gc操作------------
obj is dead