垃圾回收 —— 判断对象已死


评论

知识框架：

  1. 判断对象已死 ~ 引用计数 / 可达性分析

    1. 可达性分析 ~ 遍历 / 根节点枚举 ~ OopMap ~ 安全点
    2. 安全点 ~ 如何选择 ~ 到达最近安全点 ~ 抢先式 / 主动式 ~ 安全区域
    3. 遍历引用链时间长 ~ 并发的可达性分析 ~ 三色标记 ~ 浮动垃圾 / 对象消失
    4. 对象消失 ~ 增量更新 / 原始快照
    5. 跨代引用 ~ 记忆集和卡表 ~ 写入屏障 ~ 条件更新

1 引用计数算法（Reference Counting）

虽然占用了一些额外的内存空间来进行计数，但是原理简单，判定效率也很高

但是有很多例外情况要考虑，必须要配合大量额外处理才能保证正确地工作，譬如单纯的引用计数就很难解决对象之间相互循环引用的问题，所以 Java 采用的并不是引用计数法

2 可达性分析算法

基本思路就是通过一系列称为 GC Roots 的根对象作为起始节点集，从这些节点开始，根据引用关系向下搜索，搜索过程所走过的路径称为 引用链（Reference Chain）

如果某个对象到 GC Roots 间没有任何引用链相连（即：不可达），则证明此对象是不可能再被使用的

可作为 GC Roots 的对象

  1. 在虚拟机栈（栈帧中的本地变量表）中引用的对象

    如各个线程被调用的方法堆栈中使用到的参数、局部变量、临时变量等

  2. 在方法区中类静态属性引用的对象

    如 Java 类的引用类型静态变量

  3. 在方法区中常量引用的对象

    如字符串常量池（String Table）里的引用

  4. 在本地方法栈中JNI（即 Native 方法）引用的对象

  5. Java 虚拟机内部的引用

    如基本数据类型对应的 Class 对象，一些常驻的异常对象（如 NullPointExcepiton、OutOfMemoryError）等，还有系统类加载器

  6. 所有被同步锁（synchronized 关键字）持有的对象

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

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

如只针对 Java 堆中某一块区域发起垃圾收集时（如只对新生代），必须考虑到内存区域是虚拟机自己的实现细节，不是孤立封闭的，所以某个区域里的对象完全有可能被位于堆中其他区域的对象所引用，这时候就需要将这些关联区域的对象也一并加入 GC Roots 集合中去，才能保证可达性分析的正确性

2.1 根节点枚举

迄今为止，所有收集器在根节点枚举这一步骤时都是必须暂停用户线程的，类似于 STW
这是因为：根节点枚举必须在一个能保障 一致性的快照 中才得以进行

一致性快照是指：整个枚举期间执行子系统看起来就像被 冻结 在某个时间点上，不会出现分析过程中，根节点集合的对象引用关系还在不断变化的情况，若这点不能满足的话，分析结果准确性也就无法保证

获取根节点的位置：

一共有两种方式，目前主流的都是采用 准确式垃圾收集

  1. 保守式垃圾收集：遍历方法区和栈区查找
  2. 准确式垃圾收集：使用 OopMap 记录根节点位置

OopMap 是什么？

oop（ordinary object pointer）普通对象指针，存放这些指针的 map 就称为 OopMap，用于 枚举 GC Roots，记录栈中引用数据类型的位置

OopMap 的设计思想为 用空间换时间，如果没有 OopMap 就必须每一次都对栈进行全量扫描，但栈中存储的并不都是对象的引用，全量扫描会导致耗时增加影响性能

而使用 OopMap 存储栈上的引用对象信息，就能实现每次枚举是只需要遍历每个栈的 OopMap（一个栈由多个栈桢组成，一个栈桢可能有多个 OopMap）

OopMap 存储了两种对象的引用：

  1. 栈里和寄存器内的引用

    在即时编译中，在特定的位置记录下栈里和寄存器里哪些位置是引用

  2. 对象内的引用

    类加载动作完成时，HotSpot 就会计算出对象内什么偏移量上是什么类型的数据

OopMap 可以理解为是商场的商品清单，清单上记录着每一种商品的所在位置和数量，通过清单可以直接到对应的货架上找到商品

如果没有这份清单，需要寻找一件商品的时候，就只能从头开始，按顺序翻找每一个货架上的商品，直到找到对应的商品

2.2 安全点

主要用于保证节点枚举时，所有的 OopMap 都是当前 最新的（即对象的引用关系都正确）

随时变化的 OopMap

在程序执行的过程中，指令可能 随时都会改变 对象之间的引用关系

如果要保证任何时刻 OopMap 都是最新的（进行根节点枚举时 需要），就意味着对于每一条指令的执行，都生成（或更新）对应的 OopMap，那么将会占用大量的内存空间，这会大大增加 GC 的空间成本以至于无法忍受

所以针对这个问题，就引入了安全点的概念，详细如下：

  1. **机制：**只有在安全点才会生成（或更新）OopMap
  2. **原理：**只要所有线程都在安全点上，那此时的 OopMap 就是最新的了
  3. **优势：**不需要每一条指令都更新 OopMap 了，节省时间
  4. **要求：**并非在任何时刻都能停顿下来 进行垃圾收集，而是需要保证所有线程都到达安全点，才能以最新的 OopMap 进行所需的根节点枚举了

安全点的选择：

由于收集器需要等待所有线程都到达安全点才能开始，这就要求安全点的设置：

  1. 既不能太少以至于让收集器等待时间过长
  2. 也不能太过频繁以至于过分增大运行时的内存负荷

**安全点选择标准：**是否具有让程序长时间执行的特征

由此可以考虑在以下地方设置安全点：方法调用、循环跳转、异常跳转等

这些都属于指令序列复用，会有长时间执行的特征，所以只有具有这些功能的指令才会产生安全点

在垃圾回收时，如何使线程到达最近的安全点？这就对应了两种中断线程的方法：

  1. 抢先式中断（Preemptive Suspension）

    不需要线程的执行代码主动去配合

    在垃圾收集发生时，JVM 会中断所有用户线程，如果发现有用户线程中断的地方不在安全点上，就恢复这条线程执行，让它一会再重新中断，直到跑到安全点

    现在几乎没有虚拟机实现采用抢先式中断来暂停线程响应 GC 事件

  2. 主动式中断（Voluntary Suspension）

    JVM 需要阻塞用户线程的时候，首先做一个标志，每个用户线程会主动轮询这个标志位，一旦发现标志位为真则在自己最近的安全点上主动中断挂起

HotSpot 中的实现：主动式中断

采用的是 内存保护陷阱 的方式，当需要暂停用户线程式，就会把一个内存页设置为不可读，而执行到这个轮询指令时会读取这个内存页，这是如果不可读就会产生一个自陷异常信号，然后在预先注册的异常处理器中挂起线程实现等待

这样仅通过一条汇编指令便完成安全点轮询和触发线程中断了

2.3 安全区域（Safe Region）

在实际情况中，可能出现线程无法响应虚拟机的中断请求，不能再走到安全的地方去中断挂起自己。这种情况发生在：程序没有分配到处理机时间从而无法执行

这是就引入了 安全区域，这个区域保证了里边的 引用关系不会发生改变，因此在区域内的任何地方开始进行垃圾收集都是安全的，安全区域可以看作安全点的拉伸版

安全区域的执行机制：

  1. 线程开始执行到安全区域中时，会进行一次标记

    当这段时间里虚拟机要发起垃圾收集时，就不必去管这些已声明自己在安全区域内的线程了

  2. 线程要离开安全区域时，要检查是否已完成根节点枚举

    如果已完成，则继续执行
    如果未完成，则需要一致等待，直到收到可以离开安全区域的信号位置

2.4 并发的可达性分析（三色标记，Tri-color Marking）

根节点数量比较少枚举耗时非常短暂且相对固定（不随堆容量而增长）
但通过根节点往下去遍历对象图，会导致停顿时间与 Java 堆容量直接成正比例关系（对象多、图复杂），用户线程停顿时间九出现卡顿的情况

由此就需要有一种能和用户线程并发进行的垃圾清理机制，该机制采用的是三色标记

  1. 白色：

    指对象尚未被垃圾收集器访问过，在刚开始时所有对象都是白色
    标记完成后，如果对象还为白色，则说明该对象从根节点不可达是垃圾，可以删除

  2. 黑色：

    指对象已经被垃圾收集器访问过，且该对象的所有引用已经扫描过，不是垃圾

    如果还有其他对象指向黑色对象，那就不需要再遍历一次了，因为黑色对象不可能直接指向白色对象

    即：下一个根节点又遍历到该对象，就不需要对该对象的所有引用进行扫描了

  3. 灰色：

    指对象已经被垃圾收集器访问过，但至少还存在一个引用没有扫描过

思考：这些颜色是在哪里进行标记的呢？

以前学习的时候没有注意过这个问题，现在复习到染色指针时，就想到了三色标记是怎么实现的

其实在《深入理解Java虚拟机》（第三版）中已经有提到过了（当时没细看），就是在介绍 ZGC 染色指针时带出的（P114 页最上方），原文如下：

HotSpot虚拟机的几种收集器有不同的标记实现方案，有的把标记直接记录在对象头上（如Serial收集器），有的把标记记录在与对象相互独立的数据结构上（如G1、Shenandoah使用了一种相当于堆内存的1/64大小的，称为BitMap的结构来记录标记信息），而ZGC的染色指针是最直接的、最纯粹的，它直接把标记信息记在引用对象的指针上，这时，与其说可达性分析是遍历对象图来标记对象，还不如说是遍历“引用图”来标记“引用”了

由此可以知道，三色标记可以在 对象头、独立数据结构 和 引用 上进行标记

问题 1：浮动垃圾

是指在并发标记阶段中，原本可达的对象变成不可达，但垃圾收集器没有发现，而导致垃圾无法在本次垃圾回收中清理掉

如某对象在并发标记阶段被标记为可达的，但在后续并发标记中，该对象的所有引用都被断开了，使得它变成了一个垃圾。但对于已经标记的对象垃圾收集器并不会再扫描一遍，所以就使得这个垃圾被误标记成不是垃圾而无法在本轮进行处理，需要等到下一次垃圾回收才能清理掉

为什么 CMS 有重新标记阶段，却还是产生浮动垃圾？

CMS 重新标记的作用是：查找由于 CMS 收集器完成并发标记后，应用程序线程对对象中的引用进行更新而导致并发 跟踪遗漏 的对象，即把并发标记没标记上的对象重新标记一下

所以 CMS 的重新标记阶段，只是为了解决 对象消失 的问题，因为这个问题是严重的会导致程序出现致命错误

为什么 CMS 不解决浮动垃圾的问题？

因为浮动垃圾是可以容忍的（不是致命错误），所以在 CMS 垃圾收集器中并没有对浮动垃圾进行处理，而是留到下一次垃圾收集

如果要解决，就必须对所有的可达结点重新扫描一遍，这样会使前边的两个操作作废了，效率很低

问题 2：对象消失

是指并发标记阶段中，原本不可达的对象变成可达的，但垃圾收集器没有发现，而导致需要用到的对象可能被清理掉，从而会有严重的错误

同时满足以下两个条件就会发生对象消失错误：

  1. 赋值器插入了一条或多条从黑色对象到白色对象的新引用
  2. 赋值器删除了全部从灰色对象到该白色对象的直接或间接引用

总的来说就是该白色对象再需要被使用后，却永远无法被扫描到了

这两个条件破坏掉其中一个就可以了，所以分别产生了两种解决方案：

  1. 增量更新（Incremental Update）：CMS 采用

    增量更新要破坏的是第一个条件

    当黑色对象插入新的指向白色对象的引用关系时，就将这个 新插入的引用记录下来，再并发扫描结束之后，再将这些记录过的引用关系中的黑色对象为根，重新扫描一次

    即：黑色对象一旦新插入了指向白色对象的引用之后，它就变回灰色对象了（会再扫描一次）

    但在实际的操作中，通常是进行重新标记，有两种方式可以实现：
    如果黑色对象对白色对象新增了引用，那么
    ① 将白色对象标记为灰色 ② 将黑色对象标记为灰色

  2. 原始快照（Snapshot At The Beginning，SATB）：G1 采用

    原始快照要破坏的是第二个条件

    当灰色对象要删除指向白色对象的引用关系时，就将这个 要删除的引用记录下来，在并发扫描结束之后，再将这些记录过的引用关系中的灰色对象为根，重新扫描一次

    即：无论引用关系删除与否，都会按照刚刚开始扫描那一刻的对象图快照来进行搜索

无论是对引用关系记录的插入还是删除，虚拟机的记录操作都是通过 写屏障 实现的
CMS 就是基于增量更新来做并发标记的，而 G1、Shenandoah 则是用原始快照来实现

2.5. 跨代引用问题

现代的垃圾回收器基本上都使用分代垃圾收集，这是一种部分回收，在进行垃圾回收时，会出现只回收一部分区域的情况（比如只回收新生代）

这就出现一个问题，如果一个对象在新生代中没有其他新生代对象的引用，那么按照可达性分析算法该对象会被视为垃圾，但如果此时该对象又是被老年代对象引用的，不是垃圾，就会导致对象被错误回收了造成错误！

解决的方法有很简单的，就是扫描整个老年代，把其中跨代引用的新生代先进行标记了，这样就避免了错误回收的情况，但代价却很大需要扫描整个老年代

2.5.1. 记忆集（Remembered Set）与卡表（Card Table）

所以，记忆集（Remembered Set）出现了
它是一个抽象概念，标识用来记录从非收集器指向收集区的集合

记忆集可以按照不同精度来实现：

  1. 地址（字长）：精确到某个地址是否包含了跨代指针
  2. 对象：记录某个对象是否含有跨代指针
  3. 内存区域：只记录某个内存区域内的对象是否含有跨代指针

前两种实现精度太高，会导致记忆集的大小过大，所以现在普遍的实现是按内存区域来的，每一块内存区域城为 “卡”，卡的值标识区域内是有对象含有跨代指针（可以用 0 和 1 标识）。内存会被划分成多个区域，对应有多个卡片，所以这种实现方式被称为 “卡表”（Card Table）

在 HotSpot 中，卡表就是一个字节数组，每个下标对应一个卡片指向一片内存区域，值为 1 表示区域内至少有一个对象含有跨代指针，那就把这些对象加入 GC Root 中进行扫描。这样就实现了只需遍历一部分的老年代对象就解决跨代引用问题了

2.5.2. 写屏障

那卡表是如何维护的呢，在 HotSpot 中是通过 **写屏障（Write Barrier）**来实现的

写屏障分为写前和写后，在记录卡表时采用的是写后屏障，一旦收集器在屏障中修改了对象引用，无论是新生代还是老年代都会更新卡表，有额外的开销但是很小

同时卡表的更新还需要写入到其他线程的缓存行中，如果卡表本身就在该缓存行中，就会导致重复的写入而降低效率。JDK7 后 HotSpot 提供的做法是采用于表标记，在每次更新时需要额外判断卡表是否被标记了，只有未被标记才进行写入，虽然减少了写入损耗但是每一次都增加了一次判断的消耗，需要根据实际情况来决定是否开启这个功能（-XX:+UseCondCardMark）

IceClean星之所在，心之所向

云上的一只小澈