前言

深入浅出Java虚拟机(三)——初识JVM的垃圾回收机制 中我们了解了可达性分析算法,今天我们来具体认识一下可达性分析算法的一些细节的内容,看看具体是如何实现的。

并发可达性分析

当前主流编程语言的垃圾收集器基本上都是依靠可达性分析算法来判定对象是否存活的, 可达性分析算法理论上 要求全过程都基于一个能保障一致性的快照中才能够进行分析。

垃圾回收器的工作流程大体如下:

  1. 标记出哪些对象是存活的,哪些是垃圾(可回收);
  2. 进行回收(清除/复制/整理),如果有移动过对象(复制/整理),还需要更新引用。

三色标记

三色标记(Tri-color Marking)作为工具来辅助推导, 把遍历对象图过程中遇到的对象, 按照“是否访问过”这个条件标记成以下三种颜色: 要找出存活对象,根据可达性分析,从GC Roots开始进行遍历访问,可达的则为存活对象。

我们把遍历对象图过程中遇到的对象,按“是否访问过”这个条件标记成以下三种颜色:

白色:尚未访问过。

黑色:本对象已访问过,而且本对象引用到的其他对象也全部访问过了**。**

灰色:本对象已访问过,但是本对象引用到的其他对象尚未全部访问完。全部访问后,会转换为黑色。

假设现在有白、灰、黑三个集合(表示当前对象的颜色),其遍历访问过程为:

  1. 初始时,所有对象都在 【白色集合】中;

  2. 将GC Roots 直接引用到的对象 挪到 【灰色集合】中;

  3. 从灰色集合中获取对象: 3.1. 将本对象引用到的其他对象全部挪到【灰色集合】中; 3.2. 将本对象挪到 【黑色集合】里面。

  4. 重复步骤3,直至【灰色集合】为空时结束。

  5. 结束后,仍在【白色集合】的对象即为GC Roots 不可达,可以进行回收。

    注:如果标记结束后对象仍为白色,意味着已经找不到该对象在哪了,不可能会再被重新引用。

当Stop The World (以下简称 STW)时,对象间的引用 是不会发生变化的,可以轻松完成标记。 而当需要支持并发标记时,即标记期间应用线程还在继续跑,对象间的引用可能发生变化多标漏标的情况就有可能发生。

下面我们来看一下多标(也就是浮动垃圾)和漏标的问题。

浮动垃圾

看下图:

假设已经遍历到E(变为灰色了),此时应用执行了ObjD.fieldE=null,也就是将对象D中对E的引用置为null。

此刻之后,对象E/F/G是“应该”被回收的。然而因为E已经变为灰色了,其仍会被当作存活对象继续遍历下去。最终 的结果是:这部分对象仍会被标记为存活,即本轮GC不会回收这部分内存。 这部分本应该回收但是没有回收到的内存,被称之为“浮动垃圾”。浮动垃圾并不会影响应用程序的正确性,只是 需要等到下一轮垃圾回收中才被清除。

漏标

假设GC线程已经遍历到E(变为灰色了),此时应用线程先执行了:

var G = objE.fieldG;

objE.fieldG = null; // 灰色E 断开引用 白色G

objD.fieldG = G; // 黑色D 引用 白色G

此时切回GC线程继续跑,因为E已经没有对G的引用了,所以不会将G放到灰色集合;尽管因为D重新引用了G,但 因为D已经是黑色了,不会再重新做遍历处理。 最终导致的结果是:G会一直停留在白色集合中,最后被当作垃圾 进行清除。这直接影响到了应用程序的正确性,是不可接受的。 不难分析,漏标只有同时满足以下两个条件时才会发生:

条件一:灰色对象断开了白色对象的引用;即灰色对象原来成员变量的引用 发生了变化。

条件二:黑色对象重新引用了该白色对象;即黑色对象成员变量增加了新的引用。

从代码的角度来看:

var G = objE.fieldG; // 1.读

objE.fieldG = null; // 2.写

objD.fieldG = G; // 3.写

  1. 读取 对象E的成员变量fieldG的引用值,即对象G;
  2. 对象E 往其成员变量fieldG,写入 null值。
  3. 对象D 往其成员变量fieldG,写入 对象G ;

我们只要在上面这三步中的任意一步中做一些“手脚”,将对象G记录起来,然后作为灰色对象再进行遍历即可。比 如放到一个特定的集合,等初始的GC Roots遍历完(并发标记),该集合的对象 遍历即可(重新标记)。

重新标记是需要STW的,因为应用程序一直在跑的话,该集合可能会一直增加新的对象,导致永远都跑不完。当然,并发标记期间也可以将该集合中的大部分先跑了,从而缩短重新标记STW的时间,这个是优化问题了。

总结

我们认识了三色标记法来实现并发可达性分析算法,并对出现的“浮动垃圾”和“漏标”的问题进行了介绍。