既然可达性分析判定一个对象是否应该回收取决于根节点是否可达,那么根节点的选取就变得尤为重要。在 Java 中,根节点(GC Roots)可以为如下几种:
其实可以看到,所谓 GC Roots 更像是活跃对象集合,哪些对象是存活的,就可以作为 GC Roots。
它们分别是:
对于类型的回收,需要判断一个类型是否属于不再使用的类,条件会比较苛刻:
在使用了大量的动态代理,反射,CGLib 的地方,类型回收就显得比较重要。
收集器根据这两个假说把 Java 堆划分成了不同区域,根据对象的年龄(指对象熬过垃圾回收的次数)划分出了两个主要的区域:新生代和老年代。
新生代关注的更多是如何保留少量存活,使用弱分代假说;而老年代则可以使用更低的频率来回收,使用强分代假说。新生代回收之后剩下的对象会逐步晋升代老年代。
因为跨代引用假说的存在,所以可以把老年代划分出不同区域,这样在进行 Minor GC 时,仅仅把这些区域内的老年代加入到 GC Roots,以它们为根节点进行扫描。
这个算法足够简单,但是它有两个缺点:
为了解决标记清除算法的执行效率不稳定问题,引入了标记-复制算法。
此算法会把堆分为两个区域,其中一个保留,另一个存放对象;每次垃圾回收就把需要存活的对象复制到另一半内存,然后清空整个内存半区,这样这一半就完全空闲,而且所有的存活对象都会整齐地排列在另一半中。下次同样这样操作。
这种算法的缺点显而易见:每次只有一半内存得以使用,未免有点太浪费空间了。
为了解决这个问题,可以把内存划分比例换一下,因为统计发现,绝大多数新生代对象撑不过第一轮垃圾回收。
目前有一种更好的解决方案:把内存划分成两个较小的 Survivor(以下简称 S)和一个较大的 Eden(以下简称 E)。每次只使用一个 S 和一个 E 来分配内存。垃圾回收时,把这个 E 和 S 上的存活对象移动到另一个 S 上,然后清空 E 和刚刚那个 S。
凡事总有个例外,如果 S 不够容纳一次 GC 之后的存活对象,就需要老年代的部分区域来存放。这部分实现的安全性由 JVM 担保。
由此可见这个算法主要用于新生代的 GC。
这个算法如果用在老年代上的话,估计不是很理想,因为老年代存活对象太多了。而且这个算法在移动对象时,必须暂停用户程序,就像 JOJO 里 Dio 喊出:The World!全世界冻结一样。然后搬运它需要搬运的对象。
是否移动对象有弊有利。移动的好处在于内存空间整齐,方便新空间的申请,且加大系统吞吐量;弊端就是会因为移动对象而产生过多的停顿。
还有一种中和式,就是在内存碎片多到无法容忍时进行整理,CMS 便是这样的原理。
因为在类加载时会确定对象偏移量多少的位置上,数据是什么类型,加上即时编译时,也会记录栈和寄存器里哪些保存的是引用类型,所以最终可以直接得到所有引用的位置。然后把它们加入到 OOPMap,进而选出根节点。
JIT 记录 OOPMap 具体过程:一个线程意味着一个栈,一个栈由多个栈帧组成,一个栈帧对应着一个方法,一个方法里面可能有多个安全点(见下面)。 GC 发生时,程序首先运行到最近的一个安全点停下来,然后更新自己的 OOPMap ,记下栈上哪些位置代表着引用。枚举根节点时,递归遍历每个栈帧的 OOPMap,通过栈中记录的被引用对象的内存地址,即可找到所有的 GC Roots。
OOPMap 还可用作准确式 GC(以下内容为转载)。
与保守式 GC 相对的就是准确式 GC,何为准确式 GC?就是我们准确的知道,某个位置上面是否是指针,对于 Java 来说,就是知道对于某个位置上的数据是什么类型的,这样就可以判断出所有的位置上的数据是不是指向 GC 堆的引用,包括栈和寄存器里的数据。
网上看了下说是实现这种要求的方法有好几种,但是在 java 中实现的方式是:从我外部记录下类型信息,存成映射表,在 HotSpot 中把这种映射表称之为 OOPMap,不同的虚拟机名称可能不一样。
实现这种功能,需要虚拟机的解释器和 JIT 编译器支持,由他们来生成 OOPMap。生成这样的映射表一般有两种方式:
安全点的选择基本遵循“是否具有让程序长时间执行的特征”来选择的,比如循环,异常抛出,方法调用等。只有具有这些特征的指令才会被放置安全点。说白了就是如果一段代码会长时间执行(比如循环,或者方法调用),那么我们不能等到这段代码执行完再添加安全点,只能把安全点插入到这段代码内部,以此防止它长时间执行影响 GC;比如插入在循环块内最后的位置,方法返回的位置(相当于在方法与方法之间插入)。
另一个问题是,怎么让程序在安全点停下来?有两个方案,抢占式中断和主动式中断。前者基本不再使用,来看看后者。
主动式中断比较简单,在安全点前面添加一个 test 汇编指令,当希望线程停下时,就通过 JVM 把 test 后面的地址设置为不可读,这样就可以触发线程产生自陷异常,被预先注册好的处理程序挂起。
在这里可以看出,所谓的枚举 GC Roots 时发动 The World 能力是通过让线程发生中断来实现的。
线程中断的位置是离它最近的安全点,所以 GC 开始枚举时必须等待所有线程全部跑到最近的安全点才行(此时忽略那些非运行的线程)。因为安全点有很多,所以当 JVM 发动能力后,很快啊!所有还在运行的线程基本马上立刻就停了。
然后更新 OOPMap,进行枚举 GC Roots。
安全区域具体过程:
记忆集一般有这三种:
其中,卡精度是使用最多的,它有点像分页,把内存划分成固定大小的区域,然后总内存大小/每个内存区域大小=卡表长度
如果这块内存区域含有跨代指针,则卡表对应元素为 1,否则为 0。
首先,写屏障会对引用赋值代码进行 AOP 切入,使用的是环形通知(Around)。赋值代码之前的部分是写前屏障,而之后的成为写后屏障。
在应用了写屏障技术后,JVM 就会为赋值指令生成相应的更新卡表指令。
但是还有一个问题,称为伪共享问题(缓存系统中是以缓存行(CacheLine)为单位存储的,当多线程修改互相独立的变量时,如果这些变量共享同一个缓存行,就会无意中影响彼此的性能,这就是伪共享),这个问题在此不再描述。一种简单的解决方案是:不采用无条件的写屏障,而是使用判断-更新操作来进行,每次更新卡表之前,首先检查卡表的值,如果是 0,则更新为 1,否则不变。
暂停用户程序的原因是为了保证标记时不会发生引用关系变化,既然是为了标记这段时间引用关系不变,那么可以生成快照,然后在快照上进行。
但是有什么办法可以在生成快照时也不会暂停用户程序或者不会被运行时的用户程序影响快照呢?
引入了三色标记原理。
首先定义定义三个标记色:
如果无法保证快照一致性,那么在标记时会出现两种情况:
第一种抛弃不说,因为这体现出来的仅仅是回收不及时(下次就会回收)罢了,但是第二种需要格外注意。
对于第二种情况产生的原因,有两个:
为了解决误删问题,就需要破坏这两个条件。于是引入增量更新和原始快照。
增量更新:当有黑色对象向白色对象添加引用时,就记录,然后在扫描完成后,以刚刚那些黑色对象为根,再进行一次扫描。
原始快照:当有灰色对象想删除对白色对象的引用时,就记录下来,扫描结束,以灰色对象为根,再来一次扫描。
一句话:增量更新就是你想增加存活对象我就给你记录然后增加;原始快照就是你想删除可能存活的对象我就记录,不给你删,想删吗?等下次 GC 吧!
不论是增量更新还是原始快照,对它们(增量更新或原始快照记录的变化)进行处理依旧需要暂停用户程序,但是因为它们量比较少,所以产生的停顿时间可以暂时忽略。
这是在并发条件下的分析,如果回收器不是并发的,而是直接发动时停能力,那就直接扫描标记,也不存在上述问题。
对了,引用关系的删除和添加的记录操作是通过写屏障实现的。
标记完了,具体的回收行为取决于具体的回收器。
它的实现略微有点复杂,但是它刚好体现了前面讨论的并发的可达性分析原理。整体分为四个步骤:
A. 🔧初始标记。仅仅标记一下 GC Roots 能直接关联到的对象。
B. 🔨并发标记。与用户线程一起执行,遍历整个对象图,同时记录这期间用户程序作出的更改。
C. ⛏重新标记。修正并发标记期间用户程序产生的修改,就是把并发期间标记为不可达的但因为引用关系变化而又可达的对象,重新标记为可达。这一步需要暂停用户程序。但是因为数量少,所以并不会花费很多时间。
D. 🛠并发清除。回收对象,由于不需要移动对象,所以也是可以于用户程序并行执行的。
但是它也有三个明显的缺点:
一、🙅🏻对处理器资源很敏感。
二、🙅🏼无法处理浮动垃圾(因为标记是并发的,所以标记过程可能还有垃圾产生,这只能留到下一次回收),导致内存空间被垃圾占用,如果不幸的话,甚至可能导致在并发标记阶段预留的堆大小不够用户程序使用。这样就会触发“并发失败”;此时将会冻结用户线程,使用 SerialOld 进行老年代垃圾收集。
三、🙅标记-清除算法会导致空间碎片,此时不得不进行一个 Full GC(整堆和方法区收集)。这样会导致空间整理时产生更长的停顿。
关于浮动垃圾,其产生是因为重新标记只会处理并发标记阶段被记录的变化中从不可达->可达的对象,反之不会处理,所以才会产生浮动垃圾;要么就是并发标记的记录不会记录可达->不可达的变化。总之,要么是没记录新的垃圾,要么是记录了但是没处理新的垃圾。
以上仅为本人理解,为防误导请读者自行谷歌。
G1 为了更好地回收,取消了传统的新生代和老年代的概念,回收的范围扩大到了整个堆。最后通过特殊的算法判定哪个区域回收收益最大,组成回收集进行回收。
在 Region 中有一类特殊的 Humongous 区域,专门用来存放大对象。大对象可以跨区存储,即使用连续的 Region 来存储。G1 的大多数行为都把 Humongous 当初老年代来处理。
G1 还把 Region 当成最小回收单位,每次优先回收价值最大的 Region。
看一下 G1 的内存布局:
对于 Region 的跨引用问题,G1 的解决方案是进行跨区域记录且使用更加复杂的记忆集,具体表现为:谁指向我和我指向谁;是一个双向的映射集。
G1 还使用原始快照(SATB)算法来保证并发标记过程中的引用变化,同时为了保证收集过程中的新对象分配,设置了两个 TAMS 指针,指针上的区域 G1 默认是标记过的,所以新的对象可以分配在指针之上来确保存活。
还有一些其他的问题,可以参考G1的原理实现
现在来看看 G1 的实际工作过程:
A. 📪初始标记。仅仅标记一下 GC Roots 能直接关联到的对象,并设置新的 TAMS 指针的值。此阶段可以借助 Minor GC 同步完成,所以耗时几乎忽略不计。
B. 📫并发标记。扫描并标记整个对象图,并使用 SATB 进行记录此过程中的引用变化。
C. 📬最终标记。暂停用户程序,处理 SATB 记录。
D. 📭筛选回收。重新更新 Region 统计数据并排序,或通过用户自定的策略选定 Region(s)构成回收集,然后把存活 Region 复制到空的 Region(自动整理内存空间)并清空旧的区域,这个移动对象的过程需要暂停用户程序。
用户可以选择停顿时间是 G1 的一个很重要的特性。可以在停顿时间和吞吐量之间取得一个实际的平衡。
同时为了实现原始快照搜索,G1 还使用了写前屏障,不过由于 G1 的写屏障更复杂,所以使用的是异步实现。
和 G1 一样,Shenandoah 支持 Region,支持 Humongous 和回收价值最大的,但是 Shenandoah 支持回收阶段与用户线程并发,默认不使用分代收集,使用连接矩阵而不是记忆集。
连接矩阵很简单,就是一个 M*N 的表格,如果 i 和 j 存在引用关系,那么 i-j 就被打上标记。
来看看 Shenandoah 的工作原理:
所谓引用指针。就是给对象头添加一个指针,正常下这个指针指向自己,此方式有点像前面提到的句柄定位。更新对象引用时,仅仅需要更改这一处即可。让每次访问旧对象时,自动转发到新对象位置,这样只要旧对象还在,就会访问到新的对象。
但是转发指针必然存在并发问题,比如收集器线程设置指针,而用户线程访问,还有就是对于对象的写入,只能写入到新对象上。对于并发问题,可以使用 CAS+失败重试解决。
对于转发指针的设置,是在并发回收阶段处理的,然后在最终引用更新更新引用(指针)的值。
要覆盖全部对象访问操作,Shenandoah 必须使用读,写屏障去拦截。
对于读写屏障,尤其是读屏障,性能代价是很大的,因为系统中读操作更多。可以改成基于引用访问屏障来解决,也就是仅拦截引用类型的读写操作,而忽略普通类型。
ZGC 是一款基于 Region 内存布局,不设分代(暂时)。使用了读屏障,染色指针和多重内存映射技术来实现可并发的标记-整理算法,以低延迟为目标的一款垃圾收集器。
ZGC 的 Region 分为三个区域:
ZGC 的另一个标志性技术是染色指针。之前的三色标记法,看起来是标记对象,实则可以是标记引用,什么意思呢?
“让所有指向对象的指针失效可以达到标记对象为不存活的效果。”
一个对象的存活与否,取决于是否有引用指向它,所以如果可以通过设置引用(地址指针)某些 bit 位来指明引用的状态,也是一样的标记作用。如果指向这个对象的所有指针都被标记为不可用,那么这个对象就是需要回收的。
此时三色标记成了一开始让每个指针的标记位都为不可达,遍历一遍引用图,把可达的引用标记位设为可达,最后还是不可达的引用指向的对象(指向这个对象的所有引用都不可达)就是需要回收的。
而染色指针就是把记录指针是否可用的机制放在了指针构成上。为什么可以这样?因为目前 Linux 支持的最大虚拟地址空间为 47 位,也就是 128TB,和最大物理地址空间 46 位,也就是 64TB。而在 64 位机中,Linux 保留了高 18 位,如果我们可以缩减堆地址的话,那就会有部分高位怎么也用不到。
所以 ZGC 最高支持 4TB 堆和 64 位机,这样第 43-46 位就可为我们所用(实际上目前 ZGC 支持到了 16TB,这个是后话)。
把 4 位分成:保留位-Remapped 位-Mark1 位-Mark0 位这四种便可以实现把引用状态信息保存在指针中。
染色指针有三大优势:
但是有一个问题,Java 作为一个进程,直接修改内存指针,OS 是否支持?事实上,因为虚拟地址到物理地址的映射关系,加上 ZGC 使用了空间换时间,使得这个问题得以解决。所谓空间换时间,只是把三(如果算上原本的地址就是四个)个地址映射到了同一个物理地址空间。
首先,OS 在做虚拟->物理空间映射时,把地址后 m 位提出来,把前 64-m 位当成页表索引,找到 n,再把 n+m 拼接到一起(不是加到一起),作为物理地址,n 的范围,m 的值由 OS 和实际内存大小决定。
所以可以知道,如果后 m 位一致,那么多个虚拟地址会映射到同一个物理地址的。详见。所以 ZGC 利用这一点,把四个标志位不同的虚拟地址提前申请了,让它们都映射到同一个物理地址,解决了 OS 不支持的问题。
如果把 4 位标示位看成内存分段符,算上原本的,四位标识位,有 0000,0001,0010,0100 四种,所以它们在后 42 位相同的情况下,有 0+4TB,4+4TB,8+4TB,16+4TB 的内存空间起始间隔。
现在来看看实际的工作流程:
还有一个问题,就是 ZGC 取消了新生代,所以在对象生命周期很短的场景下,可能回收的不会那么及时。
同时还有一个优点,在支持 NUMA 的处理器上,会优先在当前线程所在的 CPU 核心本地缓存上分配,以保证高效的内存访问。
领取专属 10元无门槛券
私享最新 技术干货