满嘴都是糖果

对象死亡判断算法

引用记数法

在对象中添加一个引用计数器， 每当有一个地方引用它时， 计数器值就加一； 当引用失效时， 计数器值就减一； 任何时刻计数器为零的对象就是不可能再被使用的。

尽管原理简单，判断效率高，但是有很多情况是欠缺考虑的，比如两个废弃对象之间互相引用，虽然两个对象不会再使用，但是引用计数器不会为0，但是它们实质上是应该被清理的。

可达性分析

这个算法的基本思路就是通过一系列称为“GC Roots”的根对象作为起始节点集， 从这些节点开始， 根据引用关系向下搜索， 搜索过 程所走过的路径称为“引用链”（Reference Chain） ， 如果某个对象到GC Roots间没有任何引用链相连，或者用图论的话来说就是从GC Roots到这个对象不可达时， 则证明此对象是不可能再被使用的。

在Java技术体系里面， 固定可作为GC Roots的对象包括以下几种：

• 在虚拟机栈（栈帧中的本地变量表） 中引用的对象， 譬如各个线程被调用的方法堆栈中使用到的参数、 局部变量、 临时变量等。
• 在方法区中类静态属性引用的对象， 譬如Java类的引用类型静态变量
• 在方法区中常量引用的对象， 譬如字符串常量池（String Table） 里的引用
• 在本地方法栈中JNI（即通常所说的Native方法） 引用的对象
• Java虚拟机内部的引用， 如基本数据类型对应的Class对象， 一些常驻的异常对象（比如NullPointExcepiton、 OutOfMemoryError） 等， 还有系统类加载器。
• 所有被同步锁（synchronized关键字） 持有的对象。
• 反映Java虚拟机内部情况的JMXBean、 JVMTI中注册的回调、 本地代码缓存等。

引用

Java对引用的概念进行了扩充， 将引用分为强引用（Strongly Re-ference） 、 软引用（Soft Reference） 、 弱引用（Weak Reference） 和虚引用（Phantom Reference） 4种， 这4种引用强度依次逐渐减弱。

• 强引用是最传统的“引用”的定义， 是指在程序代码之中普遍存在的引用赋值， 即类似“Object obj=new Object()”这种引用关系。 无论任何情况下， 只要强引用关系还存在， 垃圾收集器就永远不会回收掉被引用的对象。
• 软引用是用来描述一些还有用， 但非必须的对象。 只被软引用关联着的对象， 在系统将要发生内存溢出异常前， 会把这些对象列进回收范围之中进行第二次回收， 如果这次回收还没有足够的内存，才会抛出内存溢出异常。 在JDK 1.2版之后提供了SoftReference类来实现软引用。
• 弱引用也是用来描述那些非必须对象， 但是它的强度比软引用更弱一些， 被弱引用关联的对象只能生存到下一次垃圾收集发生为止。 当垃圾收集器开始工作， 无论当前内存是否足够， 都会回收掉只被弱引用关联的对象。 在JDK 1.2版之后提供了WeakReference类来实现弱引用。
• 虚引用也称为“幽灵引用”或者“幻影引用”， 它是最弱的一种引用关系。 一个对象是否有虚引用的存在， 完全不会对其生存时间构成影响， 也无法通过虚引用来取得一个对象实例。 为一个对象设置虚引用关联的唯一目的只是为了能在这个对象被收集器回收时收到一个系统通知。 在JDK 1.2版之后提供了PhantomReference类来实现虚引用。

垃圾收集算法

标记-清除算法

算法分为“标记”和“清除”两个阶段： 首先标记出所有需要回收的对象， 在标记完成后， 统一回收掉所有被标记的对象， 也可以反过来， 标记存活的对象， 统一回收所有未被标记的对象。

它的主要缺点有两个：

• 第一个是执行效率不稳定， 如果Java堆中包含大量对象， 而且其中大部分是需要被回收的， 这时必须进行大量标记和清除的动作， 导致标记和清除两个过程的执行效率都随对象数量增长而降低；
• 第二个是内存空间的碎片化问题， 标记、 清除之后会产生大量不连续的内存碎片

标记-复制算法

把新生代分为一块较大的Eden空间和两块较小的Survivor空间， 每次分配内存只使用Eden和其中一块Survivor。 发生垃圾搜集时， 将Eden和Survivor中仍然存活的对象一次性复制到另外一块Survivor空间上， 然后直接清理掉Eden和已用过的那块Survivor空间。 HotSpot虚拟机默认Eden和Survivor的大小比例是8∶ 1， 也即每次新生代中可用内存空间为整个新生代容量的90%（Eden的80%加上一个Survivor的10%） ， 只有一个Survivor空间， 即10%的新生代是会被“浪费”的。 当Survivor空间不足以容纳一次Minor GC之后存活的对象时， 就需要依赖其他内存区域（实际上大多就是老年代） 进行分配担保（Handle Promotion） 。

标记-整理算法

标记-复制算法在对象存活率较高时就要进行较多的复制操作， 效率将会降低。 更关键的是， 如果不想浪费50%的空间， 就需要有额外的空间进行分配担保， 以应对被使用的内存中所有对象都100%存活的极端情况， 所以在老年代一般不能直接选用这种算法。

标记-整理算法让所有存活的对象都向内存空间一端移动， 然后直接清理掉边界以外的内存。但是，在老年代这种每次回收都有大量对象存活区域， 移动存活对象并更新所有引用这些对象的地方将会是一种极为负重的操作。

还有一种“和稀泥式”解决方案可以不在内存分配和访问上增加太大额外负担， 做法是让虚拟机平时多数时间都采用标记-清除算法， 暂时容忍内存碎片的存在， 直到内存空间的碎片化程度已经大到影响对象分配时， 再采用标记-整理算法收集一次， 以获得规整的内存空间。

HotSpot算法实现细节

根节点枚举

所有收集器在根节点枚举这一步骤时都是必须暂停用户线程的，因此会遇到Stop The Word问题。根节点枚举必须在一个能保证一致性的快照中进行，确保分析结果的准确性。

HotSpot使用一种称之为OopMap的数据结构，它的作用是在类加载动作完成后，记录对象中某一偏移量上存在的类型是什么，以便虚拟机知道哪里存放着对象引用，这将比完全检查完所有执行上下文和全局的引用位置的时间开销要小很多。

安全点

在OopMap的协助下， HotSpot可以快速准确地完成GC Roots枚举，但是如果为每一条指令都生成对应的OopMap， 那将会需要大量的额外存储空间，空间成本很高。HotSpot只会在一些特定的称之为安全点的位置，记录OopMap信息。

这决定了用户程序执行时并非在代码指令流的任意位置都能够停顿下来开始垃圾收集， 而是强制要求必须执行到达安全点后才能够暂停。 主动式中断的思想是当垃圾收集需要中断线程的时候， 不直接对线程操作， 仅仅简单地设置一个标志位， 各个线程执行过程时会不停地主动去轮询这个标志， 一旦发现中断标志为真时就自己在最近的安全点上主动中断挂起。

但若是用户线程目前处于sleep状态或者是Blacked状态，无法获取CPU资源走到安全点的位置将自己挂起，这引入了安全区域来解决。

安全区域是指能够确保在某一段代码片段之中， 引用关系不会发生变化， 因此， 在这个区域中任意地方开始垃圾收集都是安全的。 我们也可以把安全区域看作被扩展拉伸了的安全点。

当用户线程执行到安全区域里面的代码时， 首先会标识自己已经进入了安全区域， 那样当这段时间里虚拟机要发起垃圾收集时就不必去管这些已声明自己在安全区域内的线程了。 当线程要离开安全区域时， 它要检查虚拟机是否已经完成了根节点枚举（或者垃圾收集过程中其他需要暂停用户线程的阶段） ， 如果完成了， 那线程就当作没事发生过， 继续执行； 否则它就必须一直等待， 直到收到可以离开安全区域的信号为止。

记忆集和卡表

垃圾收集器在新生代中建立了名为记忆集（Remembered Set） 的数据结构， 用以避免把整个老年代加进GC Roots扫描范围。

记忆集是一种用于记录从非收集区域指向收集区域的指针集合的抽象数据结构。 如果我们不考虑效率和成本的话， 最简单的实现可以用非收集区域中所有含跨代引用的对象数组来实现这个数据结构

记忆集实现的粒度有三种选择：

• 字长精度： 每个记录精确到一个机器字长（就是处理器的寻址位数， 如常见的32位或64位， 这个精度决定了机器访问物理内存地址的指针长度） ， 该字包含跨代指针
• 对象精度： 每个记录精确到一个对象， 该对象里有字段含有跨代指针
• 卡精度： 每个记录精确到一块内存区域， 该区域内有对象含有跨代指针

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

卡表最简单的形式可以只是一个字节数组， 而HotSpot虚拟机确实也是这样做的。

一般来说， 卡页大小都是以2的N次幂的字节数， 通过上面代码可以看出HotSpot中使用的卡页是2的9次幂， 即512字节（地址右移9位， 相当于用地址除以512） 。 只要卡页内有一个（或更多） 对象的字段存在着跨代指针， 那就将对应卡表的数组元素的值标识为1， 称为这个元素变脏（Dirty） ， 没有则标识为0。 在垃圾收集发生时， 只要筛选出卡表中变脏的元素， 就能轻易得出哪些卡页内存块中包含跨代指针， 把它们加入GC Roots中一并扫描。

写屏障

写屏障是为了实现如何将卡表中元素变脏的，具体实现就是利用AOP切面技术在引用对象赋值时会产生一个环形（Around） 通知， 供程序执行额外的动作， 也就是说赋值的前后都在写屏障的覆盖范畴内。 在赋值前的部分的写屏障叫作写前屏障（Pre-Write Barrier） ， 在赋值后的则叫作写后屏障（Post-Write Barrier） 。

除了写屏障的开销外， 卡表在高并发场景下还面临着“伪共享”（False Sharing） 问题。 伪共享是处理并发底层细节时一种经常需要考虑的问题， 现代中央处理器的缓存系统中是以缓存行（Cache Line）为单位存储的， 当多线程修改互相独立的变量时， 如果这些变量恰好共享同一个缓存行， 就会彼此影响（写回、 无效化或者同步） 而导致性能降低， 这就是伪共享问题。

假设处理器的缓存行大小为64字节， 由于一个卡表元素占1个字节， 64个卡表元素将共享同一个缓存行。 这64个卡表元素对应的卡页总的内存为32KB（64×512字节） ， 也就是说如果不同线程更新的对象正好处于这32KB的内存区域内， 就会导致更新卡表时正好写入同一个缓存行而影响性能。 为了避免伪共享问题， 一种简单的解决方案是不采用无条件的写屏障， 而是先检查卡表标记， 只有当该卡表元素未被标记过时才将其标记为变脏

在JDK 7之后， HotSpot虚拟机增加了一个新的参数-XX： +UseCondCardMark， 用来决定是否开启卡表更新的条件判断。 开启会增加一次额外判断的开销， 但能够避免伪共享问题。

并发的可达性分析

们引入三色标记（Tri-color Marking）作为工具来辅助推导， 把遍历对象图过程中遇到的对象， 按照“是否访问过”这个条件标记成以下三种颜色：

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

如果用户线程与收集器是并发工作呢？ 收集器在对象图上标记颜色， 同时用户线程在修改引用关系——即修改对象图的结构， 这样可能出现两种后果。 一种是把原本消亡的对象错误标记为存活，这不是好事， 但其实是可以容忍的， 只不过产生了一点逃过本次收集的浮动垃圾而已， 下次收集清理掉就好。 另一种是把原本存活的对象错误标记为已消亡， 这就是非常致命的后果了， 程序肯定会因此发生错误

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

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

因此， 我们要解决并发扫描时的对象消失问题， 只需破坏这两个条件的任意一个即可。 由此分别产生了两种解决方案： 增量更新（Incremental Update） 和原始快照（Snapshot At The Beginning，SATB） 。

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

原始快照要破坏的是第二个条件， 当灰色对象要删除指向白色对象的引用关系时， 就将这个要删除的引用记录下来， 在并发扫描结束之后， 再将这些记录过的引用关系中的灰色对象为根， 重新扫描一次。 这也可以简化理解为， 无论引用关系删除与否， 都会按照刚刚开始扫描那一刻的对象图快照来进行搜索 ，这样原本并没有被黑色节点连接的节点，也就是应该被删除的节点也会染上黑色，在这轮GC中不会被清除，成为浮动垃圾，但是它会在下一次GC中被清除。

This site is open source. Improve this page.