Go v1.3 标记—清楚(mark and sweep)方法

  • 主要流程

    • 暂停程序业务逻辑,找出可达对象和不可达对象;
    • 开始标记,程序找出它所有可达的对象,并做上标记;
    • 标记完了之后,然后开始清除未标记的对象;
    • 停止暂停,让程序继续跑,然后循环重复这个过程,直到process程序声明周期结束;
  • 标记清除整体逻辑

在这里插入图片描述

  • 标记清除的缺点

    • STW,stop the world ;让程序暂停,程序出现卡顿
    • 标记需要扫描整个heap;
    • 清楚数据会产生heap碎片;【如果地址不连续】

    其中最大的问题还是因为STW太费时间,早期的探索是通过将sweep阶段移到STW之外,这确实是一种改善的方法,但是始终难以改变这种低级效能。所以需要尝试采用新的标记模式来代替清楚标记法(mark-sweep)—三色标记法。

在这里插入图片描述

Go V1.5 三色标记法

  • 主要流程

在这里插入图片描述

在这里插入图片描述

主要的流程如下【广度优先搜索】:

  • 只要是新创建的对象,默认的颜色都是标记为"白色";
  • 每次GC回收开始,然后从根节点开始遍历所有对象,把遍历到的对象从白色集合中放入"灰色"集合中;
  • 遍历灰色集合,将灰色对象引用的对象从白色集合放入灰色集合,之后将原先的灰色对象放入黑色集合当中;
  • 重复第三步,直到灰色中无任何对象;
  • 回收所有白色标记表的对象,也就是回收垃圾;

三色标记过程无STW的问题

  • 如果三色标记中不启动STW会怎么样?

在这里插入图片描述

简单来说,就是没有STW,那么如果对象2对对象3依赖的指针取消了,而对象四新建了一个对对象3的依赖,那么按照之前的原则,每次都是对灰色节点进行遍历,所以这个时候,无法将对象3标记为灰色,故会造成错误。

  • 三色标记最不希望发生的事情

    • 条件1:一个白色对象被黑色对象引用(白色挂在黑色下)
    • 条件2:灰色对象与它之间的可达关系的白色对象遭到破坏(灰色同时丢了该白色)

    以上两个条件同时满足就会发生对象的丢失。因此有必要使用STW,但是应当尽可能的提高GC效率,减少STW时间。

在这里插入图片描述

强弱三色不变式

  • 强三色不变式

    强制性的不允许黑色对象引用白色对象。

  • 弱三色不变式

    黑色对象可以引用白色对象,但是白色对象存在其他灰色对象对它的引用,或者可达它的链路上游存在灰色对象。

在三色标记中如果满足强/弱之一,即可保证对象不丢失。为了使用上面这种思想,引入了屏障

插入写屏障

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

在这里插入图片描述

也就是说在堆上的对象才会启用插入屏障。在准备回收白色前,重新遍历扫描一边栈空间,此时加STW暂停保护栈,防止有外界干扰(有新的白色被黑色添加)

在这里插入图片描述

插入写屏障的不足就是在结束时需要用STW来重新扫描栈,大约需要10ms~100ms
// 伪代码
添加下游对象(当前下游对象slot,新下游对象ptr) 「
// 1
if (当前下游对象slot是灰色 || 当前下游对象slot是白色) {标记灰色(新下游对象ptr)
}
// 2
当前下游对象slot = 新下游对象ptr

Go V1.8的三色标记法+混合写屏障机制

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

混合写屏障场景

场景1:对象被一个堆对象删除引用,成为栈对象的下游

// 伪代码
// 前提:堆对象->对象7 = 对象7;// 对象7 被 对象4 引用
栈对象1->对象7 = 堆对象7;// 将堆对象7挂载在 栈对象 下游
堆对象4->对象7 = null;//对象4 删除引用 对象7 

对象4删除了对象7的引用关系,因为对象4是堆区,所以触发删除屏障,标记被删除的对象7为灰。【注意这个地方不能认为栈里面元素添加一个就直接标记为黑色,因为栈的区域不启用屏障】

场景2:对象被一个栈对象删除引用,成为另一个新建栈对象的下游

(1)、新创建一个对象9在栈上(因为是混合写屏障模式中,GC过程汇总任何在栈中新创建的对象均标记为黑色)

(2)、对象9添加下游引用栈堆对象3(直接添加,栈不启动屏障,无屏障效果)

(3)、对象2删除对象3的引用关系(直接删除,栈不启动写屏障,无屏障效果)

场景3:对象被一个堆对象删除引用,成为另一个堆对象的下游

//伪代码
堆对象10 -> 对象7 = 堆对象7; // 将堆对象7 挂在 堆对象10 下游
堆对象4 -> 对象7 = null; // 对象4 删除引用 对象7

(1)、堆对象10已经扫描标记为黑(黑色情况比较特殊,其他颜色暂不考虑)。

(2)、堆对象10添加下游引用堆对象7,触发屏障机制,被添加的对象标记为灰色,对象7变成灰色(对象6被保护)。

(3)、堆对象删除下游引用堆对象7,触发屏障机制,被删除的对象标记为灰色,对象7被标记为灰色。

场景4:对象从一个栈对象删除引用,成为另一个堆对象的下游

// 伪代码
栈对象1 -> 对象2 = null; // 对象1 删除引用 对象2
栈对象4 -> 对象2 = 栈对象2 // 对象4 添加栈对象2
堆对象 -> 对象7 = null; // 对象4 删除一个对象7

(1)、栈对象1删除对堆对象2的引用。(栈空间不触发写屏障)。

(2)、堆对象将之前引用对象7的关系,转移至对象2(对象4删除对象7的引用关系)。

(3)、对象4在删除的时候,触发写屏障,标记被删除对象7为灰色。保护对象7及其下游节点。

总结

Go V1.3 使用普通标记清除法,整体过程需要STW,效率极其低

Go V1.5 三色标记法,堆空间启动写屏障,栈空间不启动,全部扫描一次后,需要重新扫描一次栈(需要STW),效率极其普通

Go V1.8 三色标记法+混合写屏障机制,堆空间启动,栈空间不启动,整体过程几乎不需要STW,效率较高