V1.3前-标记革除法
mark and sweep
GoV1.3之前的标记革除: mark and sweep
- 暂停程序业务逻辑
STW(stop the world)
, 分类出可达和不可达的对象,而后做上标记。 - 程序找出它所有可达的对象,并做上标记。
- 革除未标记的对象。(对象5,6不可达,被GC革除)
- 进行暂停,让程序持续跑。而后循环反复这个过程,直到process程序生命周期完结。
留神:mark and sweep算法在执行的时候,须要程序暂停!即 STW(stop the world)
,STW的过程中,CPU不执行用户代码,全副用于垃圾回收,这个过程的影响很大,所以STW也是一些回收机制最大的难题和心愿优化的点。所以在执行第三步的这段时间,程序会暂定进行任何工作,卡在那期待回收执行结束。
mark and sweep的毛病:
- STW,stop the world;让程序暂停,程序呈现卡顿 (重要);
- 标记须要扫描整个heap(堆);
- 革除数据会产生heap碎片。
V1.3 STW步骤提前
STW的步骤提前了一步,因为在Sweep革除的时候,能够不须要STW进行,因为这些对象曾经是不可达对象了,不会呈现回收写抵触等问题。
然而无论怎么优化,Go V1.3都面临这个一个重要问题,就是mark-and-sweep 算法会暂停整个程序 。
V1.5 三色标记法
- 每次新创建的对象,默认的色彩都是标记为“红色”
- 每次GC回收开始, 会从根节点开始遍历所有对象,把遍历到的对象从红色汇合放入“灰色”汇合
- 遍历灰色汇合,将灰色对象援用的对象从红色汇合放入灰色汇合,之后将此灰色对象放入彩色汇合
- 反复第三步, 直到灰色中无任何对象
- 回收所有的红色标记表的对象. 也就是回收垃圾
没有STW的三色标记法
在还没有扫描到对象2的时候,如果对象4指向对象3,同时对象2指针p移除,会导致对象3被误杀。
对象失落
- 条件1: 一个红色对象被彩色对象援用(红色被挂在彩色下)
- 条件2: 灰色对象与它之间的可达关系的红色对象受到毁坏(灰色同时丢了该红色)
当以上两个条件同时满足时,就会呈现对象失落景象!
强弱三色不变式
GC回收器满足上面两种状况之一时,即可保对象不失落。 这两种形式就是“强三色不变式”和“ 弱三色不变式”。
- 强三色不变式:不存在彩色对象援用到红色对象的指针。
- 弱三色不变式:所有被彩色对象援用的红色对象都处于灰色爱护状态。
插入屏障
具体操作
:在A对象援用B对象的时候,B对象被标记为灰色。(将B挂在A上游,B必须被标记为灰色)
满足
: 强三色不变式. (不存在彩色对象援用红色对象的状况了, 因为红色会强制变成灰色)
插入屏障机制,在栈空间的对象操作中不应用, 仅仅应用在堆空间对象的操作中。
解决流程:
- 程序创立,对象全副标记为红色,放入红色汇合中
- 遍历Root Set(只遍历一次),失去灰色节点
- 遍历灰色标记表,将可达对象标记为灰色,遍历后的灰色对象标记为彩色
- 此时对象4增加对象8(堆区:触发插入屏障),对象1增加对象9(不触发)
- 因为插入写屏障,对象8变为灰色,对象9仍为红色
- 持续循环上述流程进行三色标记,直到没有灰色节点
- 在筹备回收红色节点前,从新遍历扫描一次栈空间,此时加STW暂停爱护栈,避免外界烦扰(有新的红色被彩色增加)
- 在STW中,将占中的对象进行三色标记,直到没有灰色节点
- 进行STW
- 革除红色
有余:完结时须要STW来从新扫描,大概须要10~100ms
删除屏障
具体操作
: 被删除的对象,如果本身为灰色或者红色,那么被标记为灰色。
满足
: 弱三色不变式. (爱护灰色对象到红色对象的门路不会断)
解决流程:
- 程序创立,对象全副标记为红色,放入红色汇合中
- 遍历Root Set(只遍历一次),失去灰色节点
- 对象1删除对象5,触发删除写屏障,对象5标记为灰色
- 循环进行三色标记,直到没有灰色节点
- 革除红色
毛病:回收精度低,一个对象即便被删除了最初一个指向它的指针也仍旧能够活过这一轮,在下一轮GC中被清理掉。
V1.8 三色标记法+混合写屏障
混合写屏障
具体操作
:
1、GC开始将栈上的对象全副扫描并标记为彩色(之后不再进行第二次反复扫描,无需STW),
2、GC期间,任何在栈上创立的新对象,均为彩色。
3、被删除的对象标记为灰色。
4、被增加的对象标记为灰色。
满足
: 变形的弱三色不变式
典型场景
场景一: 对象被一个堆对象删除援用,成为栈对象的上游
//前提:堆对象4->对象7 = 对象7; //对象7 被 对象4援用栈对象1->对象7 = 堆对象7; //将堆对象7 挂在 栈对象1 上游堆对象4->对象7 = null; //对象4 删除援用 对象7
场景二: 对象被一个栈对象删除援用,成为另一个栈对象的上游
new 栈对象9;对象8->对象3 = 对象3; //将栈对象3 挂在 栈对象9 上游对象2->对象3 = null; //对象2 删除援用 对象3
场景三:对象被一个堆对象删除援用,成为另一个堆对象的上游
堆对象10->对象7 = 堆对象7; //将堆对象7 挂在 堆对象10 上游堆对象4->对象7 = null; //对象4 删除援用 对象7
场景四:对象从一个栈对象删除援用,成为另一个堆对象的上游
堆对象10->对象7 = 堆对象7; //将堆对象7 挂在 堆对象10 上游堆对象4->对象7 = null; //对象4 删除援用 对象7
Golang中的混合写屏障满足弱三色不变式
,联合了删除写屏障和插入写屏障的长处,只须要在开始时并发扫描各个goroutine的栈,使其变黑并始终放弃,这个过程不须要STW,而标记完结后,因为栈在扫描后始终是彩色的,也无需再进行re-scan操作了,缩小了STW的工夫。
总结
- GoV1.3- 一般标记革除法,整体过程须要启动STW,效率极低。
- GoV1.5- 三色标记法, 堆空间启动写屏障,栈空间不启动,全副扫描之后,须要从新扫描一次栈(须要STW),效率一般
- GoV1.8-三色标记法,混合写屏障机制, 栈空间不启动,堆空间启动。整个过程简直不须要STW,效率较高。
Reference
Golang涵养之路