雷锋教你阿里面试题(HotSpot的算法实现)

HotSpot算法实现

我们今天说一下hotspot的算法实现，我先将回顾一下我们几个知识点.如何判断对象已经可回收了,即不可能再被任何途径使用这些对象.

1.引用计数器

给一个对象添加一个引用计数器,每当有一个地方引用他,计数器就加一，当引用失效，计数器就减一,任何时刻计数器为0的对象就是不可能被使用的.客观的说，引用计数器的实现简单，判定效率也很高，是一个很不错的算法,但是至少主流的java虚拟机没有选用引用计数器，主要的原因是他很难解决对象之间的互相引用问题.

2.可达性分析

他的思想通过一系列成为“GC Roots”的队形作为起始点,从这些节点开始往下搜索，搜索所走的路径成为”引用链“当对象到GC Roots没有任何引用链，证明此对象是不可用对象，可以判定他死刑.

如上图，obj5,obj6,obj7，虽然互相关联，但是和GC Roots是不可达的，可以认为他们是可回收对象.接下来我们说一下HotSpot的算法实现.

枚举根节点

从可达性分析从GC Roots节点找引用链这个操作为例，先说一下那些可以作为GC Roots节点.

1.虚拟栈(栈帧中的本地变量表)中引用的对象

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

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

4.本地方法栈(一般叫Native方法)中引用的对象

但是现在很多应用仅仅在方法区就有数百兆。如果要逐个检查里面的引用(我的理解就是检查栈内存里面所有的数据类型，但是里面只有一部分是引用类型)，势必消耗很多时间。另外，可达性分析对执行时间的敏感还体现在GC停顿上，因为必须确保一致性的快照中进行，这里的“一致性”的意思就是在分析节点时，整个系统看起来就想被冻结在某个时间点上，不可以出现分析期间，对象的引用还在不断的变化，这对可达性分析的结果就无法保证.因此导致GC进行时必须进行停顿所有的java执行线程(stop the word)

基于上面原因，虚拟机当然就自己方法解决

1. 解决检查引用消耗的问题 由于目前主流的虚拟机使用都是准确式GC,所以当执行系统停顿后，并不需要一个不漏的的检查完所有的引用位置，HotSpot使用一个叫Oopmap的数据结构来达到这个目的，在类加载完成时候，HotSpot就把对象内什么偏移量上是什么类型的数据计算出来，在JIT编译过程中，也会在特定位置记录下栈和寄存器中在哪些位置是引用，这样GC扫描的时候直接就知道了那些地方有引用信息.有了OopMap的协助下，HotSpot可以快速的完成GC Roots枚举.

安全点

那是不是每一条指令生成OopMap呢，显然不是这样的，不然GC的空间成本将会变得很高。

实际上，HotSpot也的确没有为每一条指令生成OopMap,他只是在特定位置生成，这些位置成为安全点(Safepoint),即程序执行时，并非在所有地方都停顿开始GC,由于安全点既不能太少，以至于让GC等待时间过长，也不能过于频繁导致过分增大运行时的负荷，所以安全点的选定，基本就是以程序“是否具有让程序长时间执行的特征”为标准选定的，因为每条指令执行时间都非常短暂，程序不太可能因为指令流长度太长这个原因为过长的时间运行（开始看到这不是很明白，其实就是这句话的意思是说:如果一个方法调用要花费很长时间，你不可能让GC等待方法调用完成后，再去进入安全点，这样就会导致GC要等好长时间，所以安全点的选定，就应该判断程序是否将要执行很长时间，如果是，就把安全点放到他们之后，如循环尾部，方法调用后，方法临返回前，抛异常的位置).

对与安全点，另一个问题就是如何所有线程都走到最近安全点上在停顿下来，有两种方案

1.抢先式中断

不需要线程配合，当GC发生的时候，中断所有的线程，如果发现有线程没有在安全点，就让他回复运行，让他到运行到安全点

2.主动式中断

不直接对线程操作，仅仅简单的设置一个标志，各个线程执行，主动轮训这个标志，如果为真，就中断自己挂起，这个标志位置和安全点重合。

安全区域

到这里还没有完呢，那如果有的线程不运行，如果他的状态是sleep或者block，线程是无法响应中断请求的，也就无法进入安全点,也就没有办法进行GC,因此就需要安全域(Safe Region)解决.

Safe Region 是指在一段代码片段中，引用关系不会发生变化。在这个区域内的任意地方开始 GC 都是安全的。

线程在进入 Safe Region 的时候先标记自己已进入了 Safe Region，等到被唤醒时准备离开 Safe Region 时，先检查能否离开，如果 GC 完成了，那么线程可以离开，否则它必须等待直到收到安全离开的信号为止.