目录
未来演进方向
历经之路
引用计数法
标记清除法
复制法
标记整理
分代式
三色标记法的诞生
三色标记法的基本概念
产生的问题
问题 1:浮动垃圾
问题 2:对象消失
遍历对象图不需要 STW 的解决方案
屏障机制
插入屏障(Dijkstra)- 灰色赋值器
删除屏障 (Yuasa)- 黑色赋值器
混合屏障
引用
未来演进方向
垃圾收集器是实现垃圾回收的具体实现,是GC技术的核心组件。垃圾收集器的演进方向主要包括以下几个方面:
-
低延迟:随着互联网和移动设备的普及,对于低延迟的要求越来越高。因此,垃圾收集器需要支持低延迟的回收,以减少GC对程序性能的影响。
-
高吞吐量:高吞吐量是指垃圾收集器需要在尽可能短的时间内回收尽可能多的垃圾。高吞吐量对于大规模数据处理和高性能计算等应用非常重要。
-
分代收集:分代收集是指将内存分为不同的代,每个代有不同的生命周期和回收策略。通过采用不同的回收策略和频率,可以提高GC效率和程序性能。
-
并发收集:并发收集是指在程序运行过程中,GC线程和应用线程可以同时执行,以减少GC对程序性能的影响。并发收集需要解决线程安全、一致性和可靠性等问题。
-
分区收集:分区收集是指将内存分为多个区域,每个区域有不同的分配和回收策略。通过采用不同的分区大小和回收策略,可以提高GC效率和程序性能。
-
压缩收集:压缩收集是指在回收内存时,将存活对象移动到一起,以减少内存碎片和提高内存利用率。压缩收集需要对程序中的引用进行调整,并且会对程序性能产生一定影响。
垃圾收集器的演进方向需要根据具体应用场景和需求进行选择和优化,以提高程序性能和用户体验。
历经之路
引用计数法
根据对象自身的引用计数来回收,当引用计数归零时进行回收,但是计数频繁更新会带来更多开销,且无法解决循环引用的问题。
- 优点:简单直接,回收速度快
- 缺点:需要额外的空间存放计数,无法处理循环引用的情况;
标记清除法
标记出所有不需要回收的对象,在标记完成后统一回收掉所有未被标记的对象。
- 优点:简单直接,速度快,适合可回收对象不多的场景
- 缺点:会造成不连续的内存空间(内存碎片),导致有大的对象创建的时候,明明内存中总内存是够的,但是空间不是连续的造成对象无法分配;
复制法
复制法将内存分为大小相同的两块,每次使用其中的一块,当这一块的内存使用完后,将还存活的对象复制到另一块去,然后再把使用的空间一次清理掉
- 优点:解决了内存碎片的问题,每次清除针对的都是整块内存,但是因为移动对象需要耗费时间,效率低于标记清除法;
- 缺点:有部分内存总是利用不到,资源浪费,移动存活对象比较耗时,并且如果存活对象较多的时候,需要担保机制确保复制区有足够的空间可完成复制;
标记整理
标记过程同标记清除法,结束后将存活对象压缩至一端,然后清除边界外的内容。
- 优点:解决了内存碎片的问题,也不像标记复制法那样需要担保机制,存活对象较多的场景也使适用;
- 缺点:性能低,因为在移动对象的时候不仅需要移动对象还要维护对象的引用地址,可能需要对内存经过几次扫描才能完成;
分代式
注意!这也是最重要的一种回收思想。eg. g1, c4, zgc, shenandah.
将对象根据存活时间的长短进行分类,存活时间小于某个值的为年轻代,存活时间大于某个值的为老年代,永远不会参与回收的对象为永久代。并根据分代假设(如果一个对象存活时间不长则倾向于被回收,如果一个对象已经存活很长时间则倾向于存活更长时间)对对象进行回收。
三色标记法的诞生
事实上,GC Roots 相比起整个 Java 堆中全部的对象毕竟还算是极少数,且在各种优化技巧(比如 OopMap)的加持下,它带来的停顿已经是非常短暂且相对固定的了,也就是说,“根节点枚举” 阶段的停顿时间不会随着堆容量的增长而增加。
当我们枚举完了所有的 GC Roots,就得进入第二阶段继续往下遍历对象图了,这一步骤同样需要 STW,并且停顿时间与 Java 堆容量直接成正比例关系:堆越大,存储的对象越多,对象图结构越复杂,要标记更多对象而产生的停顿时间自然就更长,这是理所当然的事情
也就是说,“从根节点开始遍历对象图” 阶段的停顿时间随着堆容量的增长而增加。
要知道包含“标记”阶段(也就是可达性分析)是所有追踪式垃圾收集算法的共同特征,如果这个阶段会随着堆变大而等比例增加停顿时间,其影响就会波及几乎所有的垃圾收集器。如果能够减少这部分停顿时间的话,那收益也将会是巨大的
想降低 STW 时间甚至是避免 STW,我们就要先搞清楚为什么必须在一个能保障一致性的快照上才能进行对象图的遍历?
需要注意的是,三色标记法只是辅助我们分析的工具,并不是某个垃圾收集器具体使用的算法!!!!!更不是降低 STW 时间 or 消除 STW 的方法,
具体解决方法下面还会介绍
在这里,三色标记法可以帮助我们搞清楚在可达性分析的第二阶段(也就是遍历对象图),如果用户线程和垃圾收集线程同时进行,会出现什么问题
三色标记法的基本概念
所谓三色标记法,就是把遍历对象图过程中遇到的对象,按照 “是否访问过” 这个条件标记成以下三种颜色:
-
白色:表示对象尚未被垃圾收集器访问过。显然在可达性分析刚刚开始的阶段,所有的对象都是白色的,若在分析结束的阶段,仍然是白色的对象,即代表不可达(可达性分析到不了的对象,就是死亡对象,需要被回收)
-
黑色:表示对象已经被垃圾收集器访问过,且这个对象的所有引用都已经扫描过。黑色的对象代表已经扫描过,它是安全存活的,如果有其他对象引用指向了黑色对象,无须重新扫描一遍。黑色对象不可能直接(不经过灰色对象)指向某个白色对象。
-
灰色:表示对象已经被垃圾收集器访问过,但这个对象上至少存在一个引用还没有被扫描过
执行步骤:
(1)起初所有的对象都是白色的;
(2)从根对象出发扫描所有可达对象,标记为灰色,放入待处理队列;
(3)从待处理队列中取出灰色对象,将其引用的对象标记为灰色并放入待处理队列中,自身标记为黑色;
(4)重复步骤(3),直到待处理队列为空,此时白色对象即为不可达的“垃圾”,回收白色对象;
根对象在垃圾回收的术语中又叫做根集合,它是垃圾回收器在标记过程时最先检查的对象,包括: (1)全局变量:程序在编译期就能确定的那些存在于程序整个生命周期的变量。
(2)执行栈:每个 goroutine 都包含自己的执行栈,这些执行栈上包含栈上的变量及指向分配的堆内存区块的指针。
(3)寄存器:寄存器的值可能表示一个指针,参与计算的这些指针可能指向某些赋值器分配的堆内存区块。
灰色可能不好理解,这里举个例子:A(GC roots) → B → C,如果 B 已经被扫描过,但是 B 的引用 C 还没有被扫描过,那么 B 就是灰色的,C 由于还没有被扫描,所以是白色的
所以对象图遍历的过程,其实就是由灰色从黑向白推进的过程,灰色是黑和白的分界线。
下面我们就用三色标记法来分析下,如果在对象图遍历这个阶段用户线程与收集器并发工作会出现什么问题
产生的问题
问题 1:浮动垃圾
所谓浮动垃圾,就是由于垃圾收集和用户线程是并行的,这个对象实际已经死亡了,已经没有其他人引用它了,但是被垃圾收集器错误地标记成了存活对象
举个例子,a 引用了 b,此时 b 被扫描为可达,但是用户线程随后又执行了 a.b = null,这个时候其实 b 已经是死亡的垃圾对象了,但是由于黑色对象不会被重新扫描,所以在垃圾收集里 b 依然作为存活对象被标记成黑色,因此就成了浮动垃圾。如下图所示:
浮动垃圾当然不是一件好事,但其实是可以容忍的,因为这只不过产生了一点逃过本次收集的浮动垃圾而已,反正还会有下一次垃圾收集,到时候就会被标记为垃圾被清理掉了
问题 2:对象消失
对象消失和浮动垃圾恰恰相反,对象消失是把原本存活的对象错误标记为已消亡,这就是非常致命的后果了,程序肯定会因此发生错误,下面表演示了这样的致命错误具体是如何产生的
如上图所示,b -> c 的引用被切断,但同时用户线程建立了一个新的从 a -> c 的引用,由于已经遍历到了 b,不可能再回去遍历 a(黑色对象不会被重新扫描),再遍历 c,所以这个 c 实际是存活的对象,但由于没有被垃圾收集器扫描到,被错误地标记成了白色。
总结下对象消失问题的两个条件:
- 插入了一条或多条从黑色对象到白色对象的新引用
- 删除了全部从灰色对象到该白色对象的直接或间接引用
Wilson 于 1994 年在理论上证明了,当且仅当以上两个条件同时满足时,才会产生 “对象消失” 的问题,即原本应该是黑色的对象被误标为白色
遍历对象图不需要 STW 的解决方案
如上所述,如果遍历对象图的过程不 STW 的话,第一个浮动垃圾的问题很好处理,但是第二个对象消失问题就很棘手了。
但是呢,遍历对象图的过程又实在太长,设计 JVM 的大佬们不得不想出一些办法来解决对象消失问题,使得在遍历对象图的过程中不用进行 STW(也就是用户线程和对象线程可以同时工作),从而提升可达性分析的效率
上面总结了对象消失问题的两个条件,所以说,如果我们想要解决并发扫描时的对象消失问题,只需破坏这两个条件的任意一个即可。由此分别产生了两种解决方案:
- 增量更新(Incremental Update):增量更新破坏的是第一个条件,当黑色对象插入新的指向白色对象的引用关系时(就是上图中的 a -> c 引用关系),就将这个新插入的引用记录下来,等并发扫描结束之后,再将这些记录过的引用关系中的黑色对象(a)为根,重新扫描一次。这可以简化理解为,黑色对象一旦新插入了指向白色对象的引用之后,它就变回灰色对象了。
- 原始快照(Snapshot At The Beginning,SATB):原始快照要破坏的是第二个条件,当灰色对象要删除指向白色对象的引用关系时(上图中的 b -> c 引用关系),就将这个要删除的引用记录下来,在并发扫描结束之后,再将这些记录过的引用关系中的灰色对象(b)为根,重新扫描一次。这也可以简化理解为,无论引用关系删除与否,都会按照刚刚开始扫描那一刻的对象图快照来进行搜索。
屏障机制
把回收器视为对象,把赋值器视为影响回收器这一对象的实际行为(即影响 GC 周期的长短),从而引入赋值器的颜色:
- 黑色赋值器:已经由回收器扫描过,不会再次对其进行扫描。
- 灰色赋值器:尚未被回收器扫描过或尽管已经扫描过,但仍需要重新扫描。
我们来看一下golang中屏障机制是什么做的?
插入屏障(Dijkstra)- 灰色赋值器
写入前,对指针所要指向的对象进行着色
// 灰色赋值器 Dijkstra 插入屏障
func DijkstraWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
shade(ptr) //先将新下游对象 ptr 标记为灰色
*slot = ptr
}
//说明:
添加下游对象(当前下游对象slot, 新下游对象ptr) {
//step 1
标记灰色(新下游对象ptr)
//step 2
当前下游对象slot = 新下游对象ptr
}
//场景:
A.添加下游对象(nil, B) //A 之前没有下游, 新添加一个下游对象B, B被标记为灰色
A.添加下游对象(C, B) //A 将下游对象C 更换为B, B被标记为灰色
避免条件1( 赋值器修改对象图,导致某一黑色对象引用白色对象;)因为在对象A 引用对象B 的时候,B 对象被标记为灰色 Dijkstra 插入屏障的好处在于可以立刻开始并发标记。
但存在两个缺点:
- 由于 Dijkstra 插入屏障的“保守”,在一次回收过程中可能会残留一部分对象没有回收成功,只有在下一个回收过程中才会被回收;
- 在标记阶段中,每次进行指针赋值操作时,都需要引入写屏障,这无疑会增加大量性能开销;为了避免造成性能问题,Go 团队在最终实现时,没有为所有栈上的指针写操作,启用写屏障,而是当发生栈上的写操作时,将栈标记为灰色,但此举产生了灰色赋值器,将会需要标记终止阶段 STW 时对这些栈进行重新扫描。
特点:在标记开始时无需STW,可直接开始,并发进行,但结束时需要STW来重新扫描栈
删除屏障 (Yuasa)- 黑色赋值器
写入前,对指针所在对象进行着色
// 黑色赋值器 Yuasa 屏障
func YuasaWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
shade(*slot) 先将*slot标记为灰色
*slot = ptr
}
//说明:
添加下游对象(当前下游对象slot, 新下游对象ptr) {
//step 1
if (当前下游对象slot是灰色 || 当前下游对象slot是白色) {
标记灰色(当前下游对象slot) //slot为被删除对象, 标记为灰色
}
//step 2
当前下游对象slot = 新下游对象ptr
}
//场景
A.添加下游对象(B, nil) //A对象,删除B对象的引用。B被A删除,被标记为灰(如果B之前为白)
A.添加下游对象(B, C) //A对象,更换下游B变成C。B被A删除,被标记为灰(如果B之前为白)
避免条件2(从灰色对象出发,到达白色对象的、未经访问过的路径被赋值器破坏),因为被删除对象,如果自身是灰色或者白色,则被标记为灰色
特点:标记结束不需要STW,但是回收精度低,GC 开始时STW 扫描堆栈记录初始快照,保护开始时刻的所有存活对象;且容易产生“冗余”扫描;
混合屏障
大大缩短了 STW 时间
- GC 开始将栈上的对象全部扫描并标记为黑色;
- GC 期间,任何在栈上创建的新对象,均为黑色;
- 被删除的堆对象标记为灰色;
- 被添加的堆对象标记为灰色;
// 混合写屏障
func HybridWritePointerSimple(slot *unsafe.Pointer, ptr unsafe.Pointer) {
shade(*slot)
shade(ptr)
*slot = ptr
}
场景一:对象被一个堆对象删除引用,成为栈对象的下游
由于屏障的作用,对象7不会被误删除;
场景二:对象被一个栈对象删除引用,成为栈对象的下游
场景三:对象被一个堆对象删除引用,成为堆对象的下游
场景四:对象被一个栈对象删除引用,成为另一个堆对象的下游
Golang 中的混合屏障结合了删除写屏障和插入写屏障的优点,只需要在开始时并发扫描各goroutine的栈,使其变黑并一直保持,标记结束后,因为栈空间在扫描后始终是黑色的,无需进行re-scan,减少了STW 的时间。
总结
- 你需要知道 垃圾收集器在追求并行高效回收过程中产生的问题是什么?
遍历对象图的过程又实在太长,设计 JVM 的大佬们不得不想出一些办法来解决对象消失问题,使得在遍历对象图的过程中不用进行 STW(也就是用户线程和对象线程可以同时工作),从而提升可达性分析的效率
- 又是如何解决的?
增量更新
增量更新破坏的是第一个条件,当黑色对象插入新的指向白色对象的引用关系时,就将这个新插入的引用记录下来,等并发扫描后再将这些记录过的引用关系中的黑色对象为根重新扫描一次,这样可以简化理解为黑色对象一旦插入新的指向白色对象它就变为灰色对象了
CMS就是基于增量更新来实现的
原始快照
原始快照破坏的是第二个条件,当灰色对象要删除指向白色对象的引用关系时,就要将这个要删除的引用记录下来,在并发扫描结束之后,再将这些记录过的引用关系中的灰色对象为根,重新扫描一次,可以简化理解为无论引用关系删除与否都会按照刚刚开始那一刻的对象图快照来进行搜索
引用
前沿实践:垃圾回收器是如何演进的?-阿里云开发者社区
GC 的认识 - 4. 三色标记法是什么? - 《Go 语言问题集(Go Questions)》 - 书栈网 · BookStack
Golang三色标记、混合写屏障GC模式图文全分析 - Go语言中文网 - Golang中文社区
JVM-三色标记法_有糖的口袋的博客-CSDN博客文章来源:https://www.toymoban.com/news/detail-534951.html
Javaer 面试必背系列!超高频八股之三色标记法文章来源地址https://www.toymoban.com/news/detail-534951.html
到了这里,关于GC回收器演进之路的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!