三色标记法
在前面的双色标记法中，我们可以看到一个对象可以分为白色和黑色。现在引入一个灰色的概念，标记那些已经被扫描到但是所引用的对象没有被扫描完的对象。
三色法分为两步，
新创建的对象标记为白色，并加入白色集合
#第一步为标记阶段
移动root节点引用的对象到灰色集合
当灰色集合不为空，
选取一个灰色节点，标记为黑色，从灰色集合移动到黑色集合
遍历这个节点所引用的白色节点，从白色集合移动到灰色集合
#第二阶段为清除阶段
剩下的白色节点为可以清理的节点
#算法中节点只能从白色移动到灰色，在从灰色移动到黑色。
白色，黄色以及蓝色分别代表了gc中的白色，灰色以及黑色,
步骤1.所有节点都是在白色集合
步骤2.A,F移动到灰色集合
步骤3.A,F移动到黑色结合；B,C,D移动到灰色集合
步骤4.B,C,D移动到黑色结合
步骤5.清除白色集合里的节点
标记阶段不变量
1.root集合都是灰色或者黑色
2.黑色节点不能引用白色节点
3.灰色节点定义为介于黑色和白色的节点
4.标记阶段的过程就是通过遍历灰色集合然后把他们变成黑色
5.灰色集合为空的时候标记阶段就结束了。
增量式垃圾收集器，标记阶段往往运行用户程序的时候，往往会引入新的对象。所以新对象的处理就是个麻烦，会打破不变量，所以引入屏障来恢复不变量。
屏障
站在垃圾收集器的角度，运行的程序就是个麻烦，因为在收集过程中，会不断破坏不变量“黑色节点不能引用白色节点”，比如t.x = {}，t已经被标记成黑色了，这个时候重新让他引用白色的x。
有两种方法来处理这种情况。
1.递进的方式，让新创建的白色节点直接变成灰色。
2.后退的方式，让黑色节点重新退回为灰色。
为了避免ping-pong，所以把黑色节点不是加入“灰色集合”而是加入“在次灰色集合”。这个灰色集合的遍历会以原子操作的方式进行。
还有栈永远设置成灰色，避免屏障操作当有变量写入栈上时。
不论的后退的方式还是栈永远设置成灰色都是处于性能的考虑，避免ping-pong.对于会经常增加引用的节点设置灰色后，不要在设置黑色是最好的选择，因为如果变成黑色了，很快又变成灰色了。
- 后退的例子，把表从黑色集合移动到“在次灰色集合”
for i=1,N do a[i] = <exp> end - 前进的例子,把元表从“白色集合“移动到“灰色结合”
setmetatable(obj,mt)
Atomic步骤
- 标记阶段的结束都会调用atomic step。
- 这一步遍历“再次灰色集合”和栈
- 清理弱表
- 区分开了需要会被回收的集合，需要重新复活的集合。
#三色法增量式gc
移动root节点引用的对象到灰色集合
goto:标记过程
标记过程:
while 灰色节点集合不为空
获取灰色集合的节点
添加节点到黑色集合
获取节点的相邻节点集合,添加到灰色集合
if 某个条件(比如标记字节数够了)
goto:程序逻辑
goto:原子步骤(灰色集合为空了)
程序逻辑：
if 产生新节点
goto:写屏障
运行其他逻辑
写屏障：
if 节点被表引用
表退回到再次灰色集合
节点加入灰色集合
原子步骤:
遍历“再次灰色集合”（为了标记）
goto:清理
清理：
清理白色集合里内容
网友评论