4、HotSpot回收算法细节.md

#### HotSpot算法细节

##### 发起内存回收

###### 安全点

安全点如何选取

* 数量：其选定的既不能太少以至于让收集器等待时间过长，也不能太过频繁以至于过分增大运行时的内存负荷。
* 位置：安全点位置的选取基本上是以“是否具有让程序长时间执行的特征”为标准进行选定的，因为每条指令执行的时间都非常短暂，程序不太可能因为指令流长度太长这样的原因而长时间执行。
  * “长时间执行”的最明显特征就是指令序列的复用，例如方法调用、循环跳转、异常跳转等都属于指令序列复用，所以只有具有这些功能的指令才会产生安全点。



实现方案

* 抢先式中断

  不需要线程的执行代码主动去配合，在垃圾收集发生时，系统首先把所有用户线程全部中断，如果发现有用户线程中断的地方不在安全点上，就恢复这条线程执行，让它一会再重新中断，直到跑到安全点上。现在几乎没有虚拟机实现采用抢先式中断来暂停线程响应GC事件。

* 主动式中断

  * 实现思想

    当垃圾收集需要中断线程的时候，不直接对线程操作，仅仅简单地设置一个标志位，各个线程执行过程时会不停地主动去轮询这个标志，一旦发现中断标志为真时就自己在最近的安全点上主动中断挂起。轮询标志的地方和安全点（即也是记录 OopMap 的指令，通常是上面所说的复用指令）是重合的，另外还要加上所有创建对象和其他需要在Java堆上分配内存的地方，这是为了检查是否即将要发生垃圾收集，避免没有足够内存分配新对象。

  * 保护陷阱

    由于轮询操作在代码中会频繁出现，这要求它必须足够高效。HotSpot使用内存保护陷阱的方式，把轮询操作精简至只有一条汇编指令的程度。

    下面的test指令就是HotSpot生成的轮询指令（可以看到是和紧挨着一个调用指令，并且记录了 OopMap），当需要暂停用户线程时，虚拟机把0x160100的内存页设置为不可读，那线程执行到test指令时就会产生一个自陷异常信号，然后在预先注册的异常处理器中挂起线程实现等待，这样仅通过一条汇编指令便完成安全点轮询和触发线程中断了。

    

![在这里插入图片描述](https://img-blog.csdnimg.cn/20201026143938613.png#pic_center)






###### 安全区域

问题

* 使用安全点的设计似乎已经完美解决如何停顿用户线程，让虚拟机进入垃圾回收状态的问题了，但实际情况却并不一定。安全点机制保证了程序执行时，在不太长的时间内就会遇到可进入垃圾收集过程的安全点。但是，程序“不执行”的时候呢？
  * 所谓的程序不执行就是没有分配处理器时间，典型的场景便是用户线程处于Sleep状态或者Blocked状态，这时候线程无法响应虚拟机的中断请求，不能再走到安全的地方去中断挂起自己，虚拟机也显然不可能持续等待线程重新被激活分配处理器时间。



解决

* 对于这种情况，就必须引入安全区域（Safe Region）来解决。安全区域是指能够确保在某一段代码片段之中，引用关系不会发生变化，因此，在这个区域中任意地方开始垃圾收集都是安全的。我们也可以把安全区域看作被扩展拉伸了的安全点。
* 当用户线程执行到安全区域里面的代码时，首先会标识自己已经进入了安全区域，那样当这段时间里虚拟机要发起垃圾收集时就不必去管这些已声明自己在安全区域内的线程了。当线程要离开安全区域时，它要检查虚拟机是否已经完成了根节点枚举（或者垃圾收集过程中其他需要暂停用户线程的阶段），如果完成了，那线程就当作没事发生过，继续执行；否则它就必须一直等待，直到收到可以离开安全区域的信号为止。





##### 加速内存标记

###### 根节点枚举

问题

* GC Roots 查找的目标很明确，其主要在全局性的引用（例如常量或类静态属性）与执行上下文（例如栈帧中的本地变量表）中，但查找过程要做到高效并非一件容易的事情，现在Java应用越做越庞大，光是方法区的大小就常有数百上千兆，里面的类、常量等更是恒河沙数，若要逐个检查所有的类、常量或者引用，找到可以作为起源的引用（即 GC Roots），肯定得消耗不少时间。 



解决（OopMap，实际上是汇编指令中的记录，该记录里包含了该操作涉及的对象指针）

* 目前主流Java虚拟机使用的都是准确式垃圾收集，所以当用户线程停顿下来之后，其实并不需要一个不漏地检查完所有执行上下文和全局的引用位置，虚拟机应当是有办法直接得到哪些地方存放着对象引用的。在HotSpot的解决方案里，是使用一组称为OopMap的数据结构来达到这个目的。

  * 在即时编译过程中，也会在特定的位置记录下栈里和寄存器里哪些位置是引用。由此可以知道执行这一指令使用了哪些对象，那么根据对象指针就可以找到该对象，而该对象就是GC Roots。
  * 一旦类加载动作完成的时候，HotSpot就会把对象内什么偏移量上是什么类型的数据计算出来，因为除了引用类型还有基本数据类型，那么当这一对象成为 GC Roots 后，就可以快速找到其引用的对象，然后就可以接着按图的方式往下遍历。




* OopMap 示例

  反编译 String::hashCode() 方法的本地代码

  ![](https://img-blog.csdnimg.cn/20201026143955512.png#pic_center)


  



注意点

* 枚举过程"Stop The world"：迄今为止，所有收集器在根节点枚举这一步骤时都是必须暂停用户线程的（即 “Stop The World”，整个枚举期间执行子系统被冻结在某个时间点上）。不过可达性分析算法耗时最长的查找引用链的过程已经可以做到与用户线程一起并发。 
* 只在安全点记录 OopMap：在OopMap的协助下，HotSpot可以快速准确地完成GC Roots枚举，但一个很现实的问题随之而来：如果为每一条指令都生成对应的OopMap，那将会需要大量的额外存储空间，这样垃圾收集伴随而来的空间成本就会变得无法忍受。因此 HotSpot 没有为每条指令都生成OopMap，只是在安全点记录 OopMap。





###### 并发的可达性分析

问题

主流编程语言的垃圾收集器基本上都是依靠可达性分析算法来判定对象是否存活的，可达性分析算法理论上要求全过程都基于一个能保障一致性的快照中才能够进行分析，这意味着必须全程冻结用户线程的运行。

* 在根节点枚举这个步骤中，由于GC Roots相比起整个Java堆中全部的对象毕竟还算是极少数，且在各种优化技巧（如OopMap）的加持下，它带来的停顿已经是非常短暂且相对固定（不随堆容量而增长）的了。
* 可从GC Roots再继续往下遍历对象图，这一步骤的停顿时间就必定会与Java堆容量直接成正比例关系了：堆越大，存储的对象越多，对象图结构越复杂，要标记更多对象而产生的停顿时间自然就更长。





三色标记算法

* 种类

  * 白色：表示对象尚未被垃圾收集器访问过。显然在可达性分析刚刚开始的阶段，所有的对象都是白色的，若在分析结束的阶段，仍然是白色的对象，即代表不可达。
  * 灰色：表示对象已经被垃圾收集器访问过，但这个对象上至少存在一个引用还没有被扫描过。 
  * 黑色：表示对象已经被垃圾收集器访问过，且这个对象的所有引用都已经扫描过。黑色的对象代表已经扫描过，它是安全存活的，如果有其他对象引用指向了黑色对象，无须重新扫描一遍。黑色对象不可能直接（不经过灰色对象）指向某个白色对象。

* 目的：

  * 回收白色的，因为是不可达的，保留黑色的，即存活的。
  * 遍历结束的话是不存在灰色的，如果某个对象可达的话，其会是一个 白 -> 灰 -> 黑，或者 白 -> 黑 的推进过程。

* 过程

  ![](https://img-blog.csdnimg.cn/20201026144014883.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70#pic_center)






用户线程与收集器是并发标记问题

* 一种是把原本消亡的对象错误标记为存活，这不是好事，但其实是可以容忍的，只不过产生了一点逃过本次收集的浮动垃圾而已

* 另一种是把原本存活的对象错误标记为已消亡，这就是非常致命的后果了，程序肯定会因此发生错误

  ![在这里插入图片描述](https://img-blog.csdnimg.cn/20201026144037312.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70#pic_center)
















* 再补充一点应用时的问题，即并发失败，因为并发阶段应用还在执行，那么就会不断产生垃圾，所以如果回收速度比不上对象产生的速度，那么就会并发失败，从而必须 stop word，触发更耗时的 full gc





“对象消失”的问题解决（下面针对的是并发遍历标记阶段之后，进行最终标记阶段的策略，对于完成这一步最终标记之后，不会再对新增加的节点进行颜色标记，即要等到下一轮垃圾回收时才标记新增的这一部分）

* 当且仅当以下两个条件同时满足时，会产生“对象消失”的问题，即原本应该是黑色的对象被误标为白色

  * 赋值器插入了一条或多条从黑色对象到白色对象的新引用；
    * 说明一下：这个条件也适用于并发标记阶段 有节点新增的情况
  * 赋值器删除了全部从灰色对象到该白色对象的直接或间接引用
    * 说明一下：这个条件不适用于并发标记阶段有节点新增，因为是完全可能存在黑色节点直接指向白色节点，但该白色节点之前没连接灰色节点
    * 解释一下，为什么并发阶段不新增节点，那么如果让黑色节点指向白色节点时，该白色节点一定被灰色节点指向：因为按照 gc 线程单遍历的情况下，即正常情况下不可能出现黑色直接连接白色，所以必定是 黑 -> 灰 -> 白。现在有用户线程并发了，那么可以被调整的白色节点，一定也满足有灰色节点的指向的，因为如果没有灰色节点直接或者间接引用，那么说明已经完全没有 gc root 指向它了，那么怎么可能还有办法引用到该白色节点，并让其被黑色节点引用呢？

* 要解决并发扫描时的对象消失问题，只需破坏这两个条件的任意一个即可

  * 增量更新

    增量更新要破坏的是第一个条件，当黑色对象插入新的指向白色对象的引用关系时，就将这个新插入的引用记录下来，等并发扫描结束之后，再将这些记录过的引用关系中的黑色对象为根，重新扫描一次。这可以简化理解为，黑色对象一旦新插入了指向白色对象的引用之后，它就变回灰色对象了。

    * CMS 最终标记 Stop the world 时使用该算法，该方法在并发阶段可以给图新增节点，在最终标记阶段之后新增的垃圾称为浮动垃圾

  * 原始快照

    原始快照要破坏的是第二个条件，当灰色对象要删除指向白色对象的引用关系时，就将这个要删除的引用记录下来，在并发扫描结束之后，再将这些记录过的引用关系中的灰色对象为根，重新扫描一次。这也可以简化理解为，无论引用关系删除与否，都会按照刚刚开始扫描那一刻的对象图快照来进行搜索。

    * G1 最终标记 Stop the world 时使用该算法，因为这个方法是针对灰色节点直接或间接引用被破坏，所以并发标记阶段不可以再给图产生新的节点，所以采用了两个名为TAMS（Top at Mark Start）的指针，把 Region 在整个垃圾回收阶段（包括根节点枚举 -> 并发标记 -> 最终标记 -> 筛选回收 四个阶段）产生的新对象都放在这两个地址的中间，即默认它们是存活的。
    * G1 使用这种算法的原因肯定也是为了垃圾回收时间更短，因为如果并发标记阶段不断新增节点，那么最终标记阶段耗时肯定会变长，所以如果不去处理并发标记阶段新增的对象，那么肯定可以降低最终标记 stop world 的时间，符合 g1 低延时与可控的特点



##### 加速内存扫描

###### 记忆集与卡表

问题

* 存在对象跨代引用所带来的问题，难道要把整个老年代加进GC Roots扫描范围吗？
  * 因此垃圾收集器在新生代中建立了名为记忆集（Remembered Set）的数据结构。



记录集精度

* 最简单的实现可以用非收集区域中所有含跨代引用的 对象数组 来实现这个数据结构

  * 但记录全部含跨代引用对象的实现方案，无论是空间占用还是维护成本都相当高昂。
* 在垃圾收集的场景中，收集器只需要通过记忆集判断出**某一块非收集区域**是否存在有指向了收集区域的指针就可以了，并不需要了解这些跨代指针的全部细节。那设计者在实现记忆集的时候，便可以选择更为粗犷的记录粒度来节省记忆集的存储和维护成本，
  * 字长精度：每个记录精确到一个机器字长（就是处理器的寻址位数，如常见的32位或64位，这个精度决定了机器访问物理内存地址的指针长度），该字包含跨代指针。
  * 对象精度：每个记录精确到一个对象，该对象里有字段含有跨代指针（上面说的最简单的对象数组就是这种精度）。
  * 卡精度：每个记录精确到一块内存区域，该区域内有对象含有跨代指针。



实现

* 使用第三种“卡精度”，即一种称为“卡表”（Card Table）的方式去实现记忆集  ，这也是目前最常用的一种记忆集实现形式。

* 卡表最简单的形式可以只是一个字节数组 ，而HotSpot虚拟机确实也是这样做的。以下这行代码是HotSpot默认的卡表标记逻辑 ：

  ```c++
  CARD_TABLE [this address >> 9] = 0;
  ```

  * 字节数组CARD_TABLE的每一个元素都对应着其标识的内存区域中一块特定大小的内存块的起始地址，这个内存块被称作“卡页”（Card Page）
  * 一般来说，卡页大小都是以2的N次幂的字节数，通过上面代码可以看出HotSpot中使用的卡页是2的9次幂，即512字节（地址右移9位，相当于用地址除以512，然后就得到该地址在 CARD_TABLE 中的索引，那么和 CARD_TABLE 下个索引之间，其实际地址起始位置就相差 512 字节 ）

  * 一个卡页的内存中通常包含不止一个对象，只要卡页内有一个（或更多）对象的字段存在着跨代指针，那就将对应卡表的数组元素的值标识为1，称为这个元素变脏（Dirty），没有则标识为0。在垃圾收集发生时，只要筛选出卡表中变脏的元素，就能轻易得出哪些卡页内存块中包含跨代指针，把它们加入GC Roots中一并扫描。





###### 写屏障

问题

* 卡表元素如何维护的问题，其变脏之后，如何维护卡表？在有其他分代区域中对象引用了本区域对象时，其对应的卡表元素就应该变脏，但问题是如何变脏，即如何在对象赋值的那一刻去更新维护卡表呢？
  * 假如是解释执行的字节码，那相对好处理，虚拟机负责每条字节码指令的执行，有充分的介入空间；
  * 但在编译执行的场景中呢？经过即时编译后的代码已经是纯粹的机器指令流了，这就必须找到一个在机器码层面的手段，把维护卡表的动作放到每一个赋值操作之中。



实现

* 在HotSpot虚拟机里是通过写屏障（Write Barrier）技术维护卡表状态的。

  * 这里提到的“写屏障”，以及在低延迟收集器中会提到的“读屏障”与解决并发乱序执行问题中的“内存屏障”  区分开来，避免混淆。

* 写屏障可以看作在虚拟机层面对“引用类型字段赋值”这个动作的AOP切面 ，在引用对象赋值时会产生一个环形（Around）通知，供程序执行额外的动作，也就是说赋值的前后都在写屏障的覆盖范畴内。

  * 在赋值前的部分的写屏障叫作写前屏障（Pre-Write Barrier），在赋值后的则叫作写后屏障（Post-Write Barrier）。

  ```c++
  /**
   * 写后屏障更新卡表
   */
  void oop_field_store(oop* field, oop new_value) {
  	// 引用字段赋值操作
  	*field = new_value;
  	// 写后屏障，在这里完成卡表状态更新
  	post_write_barrier(field, new_value);
  }
  ```

  



伪共享

* 伪共享是处理并发底层细节时一种经常需要考虑的问题，现代中央处理器的缓存系统中是以缓存行（Cache Line）为单位存储的，当多线程修改互相独立的变量时，如果这些变量恰好共享同一个缓存行，就会彼此影响（由MESI协议，写回、无效化、然后重新同步）而导致性能降低，这就是伪共享问题。

  * 假设处理器的缓存行大小为64字节，由于一个卡表元素占1个字节，64个卡表元素将共享同一个缓存行。这64个卡表元素对应的卡页总的内存为32KB（64×512字节），也就是说如果不同线程更新的对象正好处于这32KB的内存区域内，就会导致更新卡表时正好写入同一个缓存行而影响性能。

* 为了避免伪共享问题，一种简单的解决方案是不采用无条件的写屏障，而是先检查卡表标记，只有当该卡表元素未被标记过时才将其标记为变脏，即将卡表更新的逻辑变为以下代码所示：

  ```c++
  if (CARD_TABLE [this address >> 9] != 0)
  	CARD_TABLE [this address >> 9] = 0;
  ```

* 在JDK 7之后，HotSpot虚拟机增加了一个新的参数-XX：+UseCondCardMark，用来决定是否开启卡表更新的条件判断。开启会增加一次额外判断的开销，但能够避免伪共享问题，两者各有性能损耗，是否打开要根据应用实际运行情况来进行测试权衡。