“强-弱” 三色不变式

上篇讲到如果在三色标记法去掉STW环节之后，可能会产生对象失落景象，即一个非法援用的对象被gc给当作垃圾对象谬误回收掉了。

而为了防止这种状况的呈现须要毁坏这种景象造成的两个前提条件：

  • 条件1: 一个红色对象被彩色对象援用(红色被挂在彩色下)
  • 条件2: 灰色对象与它之间的可达关系的红色对象受到毁坏(灰色同时丢了该红色)

强三色不变式

如果咱们毁坏第一个条件，即强制性的不容许彩色对象援用红色对象，这样就不会呈现有红色对象被误删的状况，这个就叫做强三色不变式。

弱三色不变式

假如容许第一个条件，只毁坏第二个条件，即彩色对象能够援用红色对象，然而这个红色对象必须存在其余灰色对象对它的援用，或者可达它的链路上游存在灰色对象。这个就叫做弱三色不变式。

这样实则是彩色对象援用红色对象，红色对象处于一个危险被删除的状态，然而上游灰色对象的援用，能够爱护该红色对象，使其平安。

为了遵循上述的两个形式，GC算法演进到两种屏障形式，他们别离是“插入屏障”和“删除屏障”。

插入屏障（满足强三色不变式）

  • 具体操作:

在A对象援用B对象的时候，B对象被标记为灰色。(将B挂在A上游，B必须被标记为灰色)

  • 满足: 强三色不变式

不存在彩色对象援用红色对象的状况了， 因为红色会强制变成灰色

  • 实现伪代码：
A.增加上游对象(nil, B)   //A 之前没有上游， 新增加一个上游对象B， B被标记为灰色A.增加上游对象(C, B)     //A 将上游对象C 更换为B，  B被标记为灰色

这段伪码逻辑就是写屏障,. 咱们晓得,彩色对象的内存槽有两种地位, 栈和堆. 栈空间的特点是容量小,然而要求相应速度快,因为函数调用弹出频繁应用, 所以“插入屏障”机制,在栈空间的对象操作中不应用. 而仅仅应用在堆空间对象的操作中.

然而如果栈不增加,当全副三色标记扫描之后,栈上有可能仍然存在红色对象被援用的状况，所以要对栈从新进行三色标记扫描, 但这次为了对象不失落, 要对本次标记扫描启动STW暂停. 直到栈空间的三色标记完结.

删除屏障（满足弱三色不变式）

  • 具体操作

被删除的对象，如果本身为灰色或者红色，那么被标记为灰色。

  • 满足: 弱三色不变式

爱护灰色对象到红色对象的门路不会断

  • 实现伪代码：
A.增加上游对象(B, nil)   //A对象，删除B对象的援用。  B被A删除，被标记为灰(如果B之前为白)A.增加上游对象(B, C)         //A对象，更换上游B变成C。   B被A删除，被标记为灰(如果B之前为白)

这种形式的回收精度低，一个对象即便被删除了最初一个指向它的指针也仍旧能够活过这一轮，在下一轮GC中被清理掉。

混合写屏障（Go1.8引入）

插入写屏障和删除写屏障的短板：

  • 插入写屏障：完结时须要STW来从新扫描栈，标记栈上援用的红色对象的存活；
  • 删除写屏障：回收精度低，GC开始时STW扫描堆栈来记录初始快照，这个过程会爱护开始时刻的所有存活对象。

Go V1.8版本引入了混合写屏障机制（hybrid write barrier），防止了对栈re-scan的过程，极大的缩小了STW的工夫。联合了两者的长处。

混合写屏障规定

具体操作:

1、GC开始将栈上的对象全副扫描并标记为彩色(之后不再进行第二次反复扫描，无需STW)，

2、GC期间，任何在栈上创立的新对象，均为彩色。

3、被删除的对象标记为灰色。

4、被增加的对象标记为灰色。

满足: 变形的弱三色不变式

伪代码

增加上游对象(以后上游对象slot, 新上游对象ptr) {      //1         标记灰色(以后上游对象slot)    //只有以后上游对象被移走，就标记灰色            //2       标记灰色(新上游对象ptr)                //3      以后上游对象slot = 新上游对象ptr}

小结

  • GoV1.3- 一般标记革除法，整体过程须要启动STW，效率极低。
  • GoV1.5- 三色标记法， 堆空间启动写屏障，栈空间不启动，全副扫描之后，须要从新扫描一次栈(须要STW)，效率一般
  • GoV1.8-三色标记法，混合写屏障机制， 栈空间不启动，堆空间启动。整个过程简直不须要STW，效率较高。