三色标记法基本原理

1. 从程序根节点开始扫描，扫描到的标记为灰色。

2. 广度优先的原则，从灰色标记表中，遍历所有灰色节点的下一级，将其标记为灰色。上一轮灰色表中的全部放入黑色表。

3. 依次循环上一步。

4. 最终白色节点说明没有被访问，需要回收。

这时候我们思考

但是扫描和回收的动作，可以与程序并行吗？

如果有并行面临的问题A：某个白色节点被黑色引用，同时被灰色断开，则永远不会被扫描到，从而错误地被回收。

因此，STW（stop the world，在做垃圾回收的时候，程序彻底停止等待）能保证不出现这个情况。但是 STW 会占用程序的时间。

那我们想办法如何避免上面出现的问题A。

首先我们分析下 A 这种情况出现的两个条件

1、白色被灰色引用，并抛弃
2、黑色引用白色

如何破坏这个两个条件呢？

黑色节点不允许引用白色节点

屏障机制

强-弱 三色不变式

• 强版：
  直接破环条件2，黑色不允许引用白色，引用则报错

• 弱版：
  黑色可以引用白色，但是白色的上游必须有灰色（保证能被扫到），这个其实是破环的1和2不同时存在。

根据这个分析，GC 算法引入了屏障机制。

插入屏障

当黑色节点引用的白色节点，直接置为灰色。

1
2
3
4
5
6
7

添加下游对象(当前下游对象slot, 新下游对象ptr) {   
  //1
  标记灰色(新下游对象ptr)   
  
  //2
  当前下游对象slot = 新下游对象ptr
}

License

Adopting CC BY-NC-SA 4.0 License Agreement

Share