go垃圾回收[2]—标记准备

I can make things very fast if they don’t have to be correct. — Russ Cox

各位看官，有问题可以后面留言交流，前文和预告可以翻一下历史文章。

Go语言中的垃圾回收

Go语言采用了并发三色标记算法来进行垃圾回收。三色标记本身是最简单的一种垃圾回收策略，实现也很简单。引用计数由于固有的缺陷，在并发时不可扩展的特性很少被使用，不适合Go这样高并发的语言。真正值得探讨的是压缩GC 与 分代GC。

为什么不选择压缩GC？

压缩算法的主要优势是减少碎片、并且分配快速。在Go语言中，使用了现代内存分配算法TCmalloc、虽然没有压缩算法那样极致，但是已经很好的解决了内存碎片的问题。并且，由于需要加锁、压缩算法并不适合在并发程序的使用。最后在Go语言的设计初期由于紧迫的时间计划，放弃了考虑更加复杂的压缩实现算法，转而使用了更简单的三色标记[1].

为什么不选择分代GC？

Go语言并不是没有尝试过分代GC。分代GC的主要假定是大部分变成垃圾的对象都是新创建的对象。但是在Go语言中由于编译器的优化，通过内存逃逸的机制，将会继续使用的对象转移到了堆中。大部分新创建的对象很快变为垃圾的对象会在栈中分配。这和其他使用隔代GC的编程语言有显著的不同，这减弱了使用隔代GC的优势。同时， 隔代GC需要额外的写屏障来保护并发垃圾回收时对象的隔代性，这会减慢GC的速度。因此，隔代GC是被尝试过并抛弃的方案。[1]

在后面的小节中，首先围绕垃圾回收最重要的两个问题展开：何时进行垃圾收集 以及如何进行垃圾收集。

标记准备阶段

在标记准备阶段,最重要的任务是清扫上一阶段gc遗留的需要清扫的对象，因为清扫使用了懒清扫策略，当执行下一次GC时，可能没有垃圾对象没有清扫完毕。

同时，重置各种状态，统计指标，启动专门用于标记的协程。统计需要扫描的任务数量，开启写屏障，启动标记协程等。总之，在标记准备阶段是为了开始标记而进行的初始阶段，并执行轻量级的任务。在标记准备阶段、上面大部分步骤需要在STW（stop the world）时进行

关于STW

stw阶段指的是程序暂停所有运行中的协程，否则不会开始垃圾回收阶段。就跟练武功一样，如果把垃圾回收比作一本武功秘籍，我们来看一看Go语言修炼的过程：

第一层就是Go1，需要STW。红色的线表示STW，绿色用户协程、黄色垃圾回收协程。并且在垃圾回收阶段只有一个协程执行垃圾回收。

Go1.1进入到第二层，并且有多个协程在并行执行垃圾回收

Go1.5进入到第三层，并发GC，垃圾回收阶段用户协程与垃圾回收协程并发执行。

Go1.8进入到第四层，大幅缩短STW时间，小于100微妙。

那么STW是不是必要的呢，其实不是的。理论和实践都证明，可以实现一种完全不需要STW的并发三色标记。真正的问题在于，有没有必要？其实现在在STW中，做的事情已经非常的少了，做一些简单的统计工作，把写屏障打开，时间已经降低到了小于100微妙。而且有STW有一个好处，这样我们能够有一个完整的GC的周期，这在做统计GC完成的时间、trace追踪的时候都很好用。而且要实现完全不需要STW的程序，实现起来也更加的困难了，所以现在有STW还算是OK的。

关于写屏障、清扫与懒清扫将在下面的小节中介绍。标记准备阶段会为每个逻辑处理器P启动一个标记协程，但并不是所有的标记协程都能得到执行的机会。因为在标记阶段，标记协程与正常执行用户代码的协程需要同时并行，减少由于GC而给用户程序带来的影响。在这里，笔者关注于标记准备阶段两个重要的问题：如何决定需要有多少标记协程进行工作以及如何进行调度使标记协程运行。

计算执行标记协程的数量

在标记准备阶段，会计算当前需要多少后台标记协程开始工作。在当前，GO语言规定后台标记协程消耗的CPU应该接近于25%。其核心代码位于startCycle()中

func (c *gcControllerState) startCycle() {
    ...
    totalUtilizationGoal := float64(gomaxprocs) * 0.25
    c.dedicatedMarkWorkersNeeded = int64(totalUtilizationGoal + 0.5)
    utilError := float64(c.dedicatedMarkWorkersNeeded)/totalUtilizationGoal - 1
    const maxUtilError = 0.3
    if utilError < -maxUtilError || utilError > maxUtilError {
        if float64(c.dedicatedMarkWorkersNeeded) > totalUtilizationGoal {
            c.dedicatedMarkWorkersNeeded--
        }
        c.fractionalUtilizationGoal = (totalUtilizationGoal - float64(c.dedicatedMarkWorkersNeeded)) / float64(gomaxprocs)
    } else {
        c.fractionalUtilizationGoal = 0
    }
     ...
}

一种简单的想法,要实现后台标记协程消耗的CPU接近于25%的目标，可以根据当前有多少逻辑处理器P，开启的数量应该为0.25 * P 就可以了。为什么startCycle函数的计算过程却如此复杂呢？关键在于需要处理当协程数量过小，例如P≤3时，0.25 * P 不为整数的情况。

dedicatedMarkWorkersNeeded代表了执行完整的后台标记协程的数量.例如当p=4时，dedicatedMarkWorkersNeeded = 1 。

而fractionalUtilizationGoal是一个附加的参数，其小于1，例如当P=2时，值为0.25。代表了每个P在标记阶段需要花25%的时间去执行后台标记协程，不需要连续的如下图。

设计fractionalUtilizationGoal的主要目的是专门为P=1，2，3，6时使用的。因为这些数量和25%的CPU处理时间的差距太大。比如当P=2时，这时2*0.25 = 0.5,即只能花0.5个P来执行标记任务，但如果专门用了一个P来执行后台任务，这时标记的CPU使用量变为了1/2 =0.5, 这和0.25CPU的设计目标差距太大。

所以，当P=2时，fractionalUtilizationGoal计算结果为0.25，它表明在整个并发标记的周期t内，每一个P都需要花25%的时间来执行后台标记工作。这是一种基于时间的调度安排。当超出时间后，意味着当前的后台标记协程可以被抢占，从而执行其他的协程。

切换到后台标记协程

标记准备阶段的第二个问题是如何切换到后台标记协程执行。在标记准备阶段执行了STW、在STW阶短暂的暂停了所有的协程。可以预料到，当关闭STW准备再次启动所有的协程时，每一个逻辑处理器P会进入一轮新的调度循环，在调度循环的最开始的一步会判断是否处于GC阶段，如果是，尝试判断当前P 是否需要执行后台标记任务。

func schedule() {
//  正在 GC，去找 GC 的 g
    if gp == nil && gcBlackenEnabled != 0 {
        gp = gcController.findRunnableGCWorker(_g_.m.p.ptr())
        tryWakeP = tryWakeP || gp != nil
    }
}

如果代表了执行完整的后台标记协程的字段dedicatedMarkWorkersNeeded大于0，则直接执行后台标记任务。否则，如果协助协程字段fractionalUtilizationGoal大于0，并且当前P执行标记任务的时间 小于 fractionalUtilizationGoal*当前标记周期总时间，仍然会执行后台标记任务，但是并不会在整个标记周期内一直执行，只会执行对应的CPU时间，保证总的25%cpu执行时间。下一小节会看到，这对应着后台标记协程的不同执行模式。

if decIfPositive(&c.dedicatedMarkWorkersNeeded) {
        _p_.gcMarkWorkerMode = gcMarkWorkerDedicatedMode
    } else if c.fractionalUtilizationGoal == 0 {
        return nil
    } else {
        delta := nanotime() - gcController.markStartTime
        if delta > 0 && float64(_p_.gcFractionalMarkTime)/float64(delta) > c.fractionalUtilizationGoal {
            return nil
        }
        _p_.gcMarkWorkerMode = gcMarkWorkerFractionalMode
    }

下一篇文章再见，see you~