Golang学习实战笔记-基础 > golang底层实现原理
golang内存回收-三色标记法

在golang1.5之前,golang主要是采用标记清除的方法,这样的话STW时间会很长,1.5出来后采用了三色标记法,也是我们今天主要说的。 golang为何要选择三色标记算法呢?我们知道golang比较适合网络高并发的服务场景,那么如果使用STW时间较长的GC算法,对服务来说是致命的,故而要选用STW时间较少的算法,在标记清除的基础上发展来的三色标记出现了。 三色标记的思想其实是尽量把标记阶段、清除阶段与程序同时跑,它其实是一种增量式GC算法,所谓增量式其实就是把GC过程拆分出来的意思,跟我们要把最大的STW时间减少的思想吻合。

在看整个过程之前,我们先同步几件事情:

1.在三色标记算法中,我们给对象进行了标记颜色,分别是白色、灰色、黑色,在GC开始的时候,所有的对象默认都是白色,标记完成之后,所有的可达的对象都会被标记为黑色,而灰色就是我们的中间状态

2.我们Golang的GC的根对象,都在栈上,所谓栈其实就是协程栈。

我们来看下其整个过程:

1.首先,当要GC触发的时候,首先,我们会初始化写屏障(Write barrier),我们的垃圾回收器从根对象开始扫描,把所有的垃圾根对象压入一个栈当中,并且把对象都会标记为灰色

2.从栈中pop出一个对象,把该对象所有指向的子对象都入栈,并且标记为灰色,并且把该对象标记为黑色,然后放入黑色的对象集合中

3.无限的重复第二个步骤,直到栈为空。

4.在第一步骤中我们看到有写屏障,这个写屏障其实就是记录我们进行第一次扫描的时候漏掉的那些对内存的操作,我们会再次遍历这些记录(稍后细说),注意这个过程会进行STW,但是时间会很短。

5.最后扫描所有的堆,把白色对象清除即可。

注意:

1.还记得我们在说golang的堆内存管理与协程栈管理吗?首先栈的管理中有一个stackmap可以帮助我们寻找到到协程栈上的指针,这其实就是我们的根对象

2.Edsger W. Dijkstra提出的三色标记法中,有一个地方需要注意,在标记阶段如果出现以下情况我们是要进行特殊处理的:

a.如果有新创建的对象,而指向该对象的是黑色的对象,或者指向该对象的恰好也是刚创建的根对象,这样这个刚创建的对象会被漏标记

b.如果有如下图的情况,某个白色对象在被灰色对象引用的情况下,被改为被黑色对象引用了,而我们知道黑色的对象其实已经被扫描过了,这样这个白色的对象就不会被标记到。

这个时候我们就要用到写屏障了,看下Edsger W. Dijkstra提出的写屏障算法。

write_barrier(obj, field, newobj){
    //未被标记,就标记
    if(newobj.mark == FALSE)
        newobj.mark = TRUE
        push(newobj, $mark_stack)
    *field = newobj
}

这里看到,只要我们指向的对象是白色的,我们就把它标记为灰色的,这样的话,新创建的对象以及黑色对象指向白色对象的情况就能被解决,如下图所示。

3.我们说过三色标记是增量式的,具体体现在哪呢?看下它的伪代码

incremental_mark_phase(){
    //这里有一个MARK_MAX,这是最大扫描的个数
    for(i : 1..MARK_MAX)
        //如果灰色的栈集合不为空,则继续扫描
        if(is_empty($mark_stack) == FALSE)
            obj = pop($mark_stack)
            for(child : children(obj))
            mark(*child)
        else
            //如果扫描完毕了,则重新扫描一遍根对象
            for(r : $roots)
                mark(*r)
            //扫描完根对象后发现有漏掉的,那么继续扫描
            while(is_empty($mark_stack) == FALSE)
                obj = pop($mark_stack)
                for(child : children(obj))
                    mark(*child)
            //如果发现到清除阶段,则进入清除
            $gc_phase = GC_SWEEP
            $sweeping = $heap_start
            return
}

注意看上面的代码的MARK_MAX,这里的意思是从灰色的栈集合中,每次最多扫描MARK_MAX个灰色对象。也就是说把扫描阶段拆开了,一次一部分,所以叫增量式。

4.我们再来看下,如果在清除阶段很应用程序同时跑会有问题吗?

(1)想象下,如果引用变化会引起清除掉活跃的对象吗?其实是不会的,想象下什么情况下可能会出现清除活跃对象呢,白色的对象又重新被引用了才可能会出问题,但是其实不会的,如果它原本是白色对象,就不可能被黑色对象找到了,如果它能通过某个方式找到这个白色对象,那么在之前扫描的时候一定会把它最后标记为黑色的。

(2)如果在清除阶段出现新的对象呢?我们知道新创建的对象默认是白色的,确实有可能是被清除的,那么我们怎么做呢,很简单,我们知道清除阶段是扫描整个堆内存,其实我们是可以知道当前清除到什么位置,那么我们创建的新对象判定下,如果新对象的指针位置已经被扫描过了,那么就不用作任何操作,不会被误清除,如果在当前扫描的位置的后面,那就要注意了,我们直接把该对象的颜色标记为黑色,这样就不会被误清除了。如下图所示

5.我们来分析下优缺点:

(1)最大的优点是STW时间很短

(2)缺点就是吞吐量低,原因就是有写入屏障

6.不同的写入屏障策略 为了防止在扫描阶段,与程序同时跑的话,出现白色的活跃的对象(被灰色)在还未被标记的时候,从被会被灰色对象指向改为被黑色对象指向,我们上面说过一种写入屏障的策略是记录黑色直线白色的引用,其实还有其他几种方式,我们来说一下。 (1)Steele算法 该算法不同的地方就在于,当发现黑色对象指向白色对象的时候,就把黑色对象标记为灰色即可。这样的话,该对象就会被再次扫描,相应的那个白色对象也会被扫描到,如图所示

(2)汤浅算法 该算法在mark的时候,不会再次扫描根对象,同样我们需要注意两个问题,新生成的对象,以及引用的变更,对于新生成的对象就直接标记为黑色,对于引用的变更,该算法的写入屏障是记录指针删除的操作,记录的条件是,当有指针删除的操作的时候,并且被删除的指引指向的是白色的对象,那么我们就把这个白色的对象给标记成灰色就行了,如图所示

来源: https://zhuanlan.zhihu.com/p/53928921

更多参考:https://i6448038.github.io/2019/03/04/golang-garbage-collector/