【GC】垃圾回收原理分析

本文基于小许先生的编程世界学习了gc机制。
面试官：了解gc机制吗？简述一下。
我：golang为清除不再被使用的对象，回收内存的机制。采用了三色标记法+混合写屏障。首先开启屏障，一旦在gc期间发生指针引用变化，删除或添加就标记为灰色，gc开始是将所有对像置为白色，扫描根对象将他标记为灰色入队，扫描他指向的对象入队置为灰色，将本身置黑；重复扫描队列中的对象直到对象为空，然后将没有被引用的对象清除。
面试官：gc会有stw吗？
我：在1.3的时候，golang在gc时stw标记清除，期间程序停止，有卡顿
在1.5的时候，golang在gc采用了三色标记法，渐进扫描，减少了stw时间,清除期间stw防止gc的时候对象引用改变，被错误清除
在1.8的时候加入混合写屏障，在对象引用变化后会通知垃圾回收器重新扫描，没有全局stw，只是扫描具体的栈的时候需要停止相应的goroutinue
面试官：什么时候发生gc？
我：1.系统触发，堆内存分配达到阈值，距离上一次分配已经达到超时时间
2.手动触发
不处于gc、允许gc、程序没有崩溃

0.前言

垃圾回收（Garbage Collection，简称 GC）是一种内存管理策略，由垃圾收集器以类似守护协程的方式在后台运作，按照既定的策略为用户回收那些不再被使用的对象，释放对应的内存空间.
（1）GC 带来的优势包括：

• 屏蔽内存回收的细节
  拥有 GC 能力的语言能够为用户屏蔽复杂的内存管理工作，使用户更好地聚焦于核心的业务逻辑.
• 以全局视野执行任务
  现代软件工程项目体量与日剧增，一个项目通常由团体协作完成，研发人员负责各自模块的同时，不可避免会涉及到临界资源的使用. 此时由于缺乏全局的视野，手动对内存进行管理无疑会增加开发者的心智负担. 因此，将这部分工作委托给拥有全局视野的垃圾回收模块来完成，方为上上之策.
  （2）GC 带来的劣势：
• 提高了下限但降低了上限
  将释放内存的工作委托给垃圾回收模块，研发人员得到了减负，但同时也失去了控制主权. 除了运用有限的GC调优参数外，更多的自由度都被阉割，需要向系统看齐，服从设定.
• 增加了额外的成本
  全局的垃圾回收模块化零为整，会需要额外的状态信息用以存储全局的内存使用情况. 且部分时间需要中断整个程序用以支持垃圾回收工作的执行，这些都是GC额外产生的成本.
  （3）GC 的总体评价
  除开少量追求极致速度的特殊小规模项目之外，在绝大多数高并发项目中，GC模块都为我们带来了极大的裨益，已经成为一项不可或缺的能力.

1.垃圾回收的方法

1.1标记清除

缺点：
这是一种类似于排除法的间接处理思路，不直接查找垃圾对象，而是标记存活对象，从而取补集推断出垃圾对象.
至于标记清扫算法的不足之处，通过上图也得以窥见一二，那就是会产生内存碎片. 经过几轮标记清扫之后，空闲的内存块可能零星碎片化分布，此时倘若有大对象需要分配内存，可能会因为内存空间无法化零为整从而导致分配失败.
1.2标记压缩

标记压缩（Mark-Compact）算法，是在标记清扫算法的基础上做了升级，在第二步”清扫“的同时还会对存活对象进行压缩整合，使得整体空间更为紧凑，从而解决内存碎片问题.
标记压缩算法在功能性上呈现得很出色，而其存在的缺陷也很简单，就是实现时会有很高的复杂度.

1.3半空间复制

相信用过 Java 的同学对半空间复制（Semispace Copy）算法并不会感到陌生，它的核心点如下：
1.分配两片相等大小的空间，称为 fromspace 和 tospace
2. 每轮只使用 fromspace 空间，以GC作为分水岭划分轮次
3. GC时，将fromspace存活对象转移到tospace中，并以此为契机对空间进行压缩整合
4. GC后，交换fromspace和tospace，开启新的轮次
显然，半空间复制算法应用了以空间换取时间的优化策略，解决了内存碎片的问题，也在一定程度上降低了压缩空间的复杂度. 但其缺点也同样很明显——比较浪费空间.

1.4引用计数

1.对象每被引用一次，计数器加1
2. 对象每被删除引用一次，计数器减1
3. GC时，把计数器等于 0 的对象删除
然而，这个朴素的算法存在一个致命的缺陷：无法解决循环引用或者自引用问题.

2.各个版本go语言垃圾回收的发展

1.3以前：stw
golang的垃圾回收算法都非常简陋，其性能也广被诟病：go runtime在一定条件下（内存超过阈值或定期如2min），暂停所有任务的执行，进行mark&sweep操作，操作完成后启动所有任务的执行。在内存使用较多的场景下，go程序在进行垃圾回收时会发生非常明显的卡顿现象（Stop The World）。在对响应速度要求较高的后台服务进程中，这种延迟简直是不能忍受的！这个时期国内外很多在生产环境实践go语言的团队都或多或少踩过gc的坑。当时解决这个问题比较常用的方法是尽快控制自动分配内存的内存数量以减少gc负荷，同时采用手动管理内存的方法处理需要大量及高频分配内存的场景。
1.3：Mark STW & Sweep
1.3版本中，go runtime分离了mark和sweep操作，和以前一样，也是先暂停所有任务执行并启动mark，mark完成后马上就重新启动被暂停的任务了，而是让sweep任务和普通协程任务一样并行的和其他任务一起执行。如果运行在多核处理器上，go会试图将gc任务放到单独的核心上运行而尽量不影响业务代码的执行。go team自己的说法是减少了50%-70%的暂停时间。
1.5：三色标记
go 1.5正在实现的垃圾回收器“非分代的、非移动的、并发的、三色的标记清除垃圾收集器”。这种方法的mark操作是可以渐进执行的而不需每次都扫描整个内存空间，可以减少stop the world的时间。 由此可以看到，一路走来直到1.5版本，go的垃圾回收性能也是一直在提升。
1.8：混合写屏障（hybrid write barrier）
由于标记操作和用户逻辑是并发执行的，用户逻辑会时常生成对象或者改变对象的引用。例如把⼀个对象标记为白色准备回收时，用户逻辑突然引用了它，或者又创建了新的对象。由于对象初始时都看为白色，会被 GC 回收掉，为了解决这个问题，引入了写屏障机制。
GC 对扫描过后的对象使⽤操作系统写屏障功能来监控这段内存。如果这段内存发⽣引⽤改变，写屏障会给垃圾回收器发送⼀个信号，垃圾回收器捕获到信号后就知道这个对象发⽣改变，然后重新扫描这个对象，看看它的引⽤或者被引⽤是否改变。利⽤状态的重置实现当对象状态发⽣改变的时候，依然可以再次其引用的对象。

3.GO的gc

3.1三色标记

• 白色对象：潜在的垃圾，其内存可能会被垃圾收集器回收；
• 黑色对象：活跃的对象，包括不存在任何引用外部指针的对象以及从根对象可达的对象；
• 灰色对象：活跃的对象，因为存在指向白色对象的外部指针，垃圾收集器会扫描这些对象的子对象；
  三色标记垃圾收集器的工作原理很简单，我们可以将其归纳成以下几个步骤：
  

1.从灰色对象的集合中选择一个灰色对象并将其标记成黑色；
2.将黑色对象指向的所有对象都标记成灰色，保证该对象和被该对象引用的对象都不会被回收；
3.重复上述两个步骤直到对象图中不存在灰色对象。
当三色的标记清除的标记阶段结束之后，应用程序的堆中就不存在任何的灰色对象，我们只能看到黑色的存活对象以及白色的垃圾对象，垃圾收集器可以回收这些白色的垃圾

因为用户程序可能在标记执行的过程中修改对象的指针，所以三色标记清除算法本身是不可以并发或者增量执行的，它仍然需要 STW,否则：用户在gc时候引用D，或许D会被错误回收

本来不应该被回收的对象却被回收了，这在内存管理中是非常严重的错误，我们将这种错误称为悬挂指针，即指针没有指向特定类型的合法对象，影响了内存的安全性，想要并发或者增量地标记对象还是需要使用屏障技术。

3.2混合写屏障

想要在并发或者增量的标记算法中保证正确性，我们需要达成以下两种三色不变性（Tri-color invariant）中的一种：

• 强三色不变性：黑色对象不会指向白色对象，只会指向灰色对象或者黑色对象；（写屏障）
• 弱三色不变性：黑色对象指向的白色对象必须包含一条从灰色对象经由多个白色对象的可达路径。（删除写屏障）

垃圾收集中的屏障技术更像是一个钩子方法，它是在用户程序读取对象、创建新对象以及更新对象指针时执行的一段代码，根据操作类型的不同，我们可以将它们分成读屏障（Read barrier）和写屏障（Write barrier）两种，因为读屏障需要在读操作中加入代码片段，对用户程序的性能影响很大，所以编程语言往往都会采用写屏障保证三色不变性。
Go 语言在 v1.8 组合 Dijkstra 插入写屏障和 Yuasa 删除写屏障构成混合写屏障，该写屏障会将被覆盖的对象标记成灰色并在当前栈没有扫描时将新对象也标记成灰色。
为了移除栈的重扫描过程，除了引入混合写屏障之外，在垃圾收集的标记阶段，我们还需要将创建的所有新对象都标记成黑色，防止新分配的栈内存和堆内存中的对象被错误地回收，因为栈内存在标记阶段最终都会变为黑色，所以不再需要重新扫描栈空间。

3.3.增量和并发

传统的垃圾收集算法会在垃圾收集的执行期间暂停应用程序，一旦触发垃圾收集，垃圾收集器会抢占 CPU 的使用权占据大量的计算资源以完成标记和清除工作，然而很多追求实时的应用程序无法接受长时间的 STW。
为了减少应用程序暂停的最长时间和垃圾收集的总暂停时间，我们会使用下面的策略优化现代的垃圾收集器：

• 增量垃圾收集：增量地标记和清除垃圾，降低应用程序暂停的最长时间；
• 并发垃圾收集：利用多核的计算资源，在用户程序执行时并发标记和清除垃圾；
  因为增量和并发两种方式都可以与用户程序交替运行，所以我们需要使用屏障技术保证垃圾收集的正确性；与此同时，应用程序也不能等到内存溢出时触发垃圾收集，因为当内存不足时，应用程序已经无法分配内存，这与直接暂停程序没有什么区别，增量和并发的垃圾收集需要提前触发并在内存不足前完成整个循环，避免程序的长时间暂停
  增量收集
  增量式（Incremental）的垃圾收集是减少程序最长暂停时间的一种方案，它可以将原本时间较长的暂停时间切分成多个更小的 GC 时间片，虽然从垃圾收集开始到结束的时间更长了，但是这也减少了应用程序暂停的最大时间：
  

需要注意的是，增量式的垃圾收集需要与三色标记法一起使用，为了保证垃圾收集的正确性，我们需要在垃圾收集开始前打开写屏障，这样用户程序修改内存都会先经过写屏障的处理，**保证了堆内存中对象关系的强三色不变性或者弱三色不变性。**虽然增量式的垃圾收集能够减少最大的程序暂停时间，但是增量式收集也会增加一次 GC 循环的总时间，在垃圾收集期间，因为写屏障的影响用户程序也需要承担额外的计算开销，所以增量式的垃圾收集也不是只带来好处的，但是总体来说还是利大于弊。
并发收集
并发（Concurrent）的垃圾收集不仅能够减少程序的最长暂停时间，还能减少整个垃圾收集阶段的时间，通过开启读写屏障、利用多核优势与用户程序并行执行，并发垃圾收集器确实能够减少垃圾收集对应用程序的影响：

虽然并发收集器能够与用户程序一起运行，但是并不是所有阶段都可以与用户程序一起运行，部分阶段还是需要暂停用户程序的，不过与传统的算法相比，并发的垃圾收集可以将能够并发执行的工作尽量并发执行；当然，因为读写屏障的引入，并发的垃圾收集器也一定会带来额外开销，不仅会增加垃圾收集的总时间，还会影响用户程序，这是我们在设计垃圾收集策略时必须要注意的。

4.GC的时机

运行时会通过如下所示的 runtime.gcTrigger.test 方法决定是否需要触发垃圾收集，当满足触发垃圾收集的基本条件时 — 允许垃圾收集、程序没有崩溃并且没有处于垃圾收集循环，该方法会根据三种不同方式触发进行不同的检查：

func (t gcTrigger) test() bool {
// 允许垃圾收集、程序没有崩溃并且没有处于垃圾收集循环
        if !memstats.enablegc || panicking != 0 || gcphase != _GCoff {
                return false
        }
        switch t.kind {
        case gcTriggerHeap:
        //堆内存的分配达到达控制器计算的触发堆大小；
                return memstats.heap_live >= memstats.gc_trigger
        case gcTriggerTime:
        //如果一定时间内没有触发，就会触发新的循环，
        //该触发条件由 runtime.forcegcperiod 变量控制，默认为 2 分钟；
                if gcpercent < 0 {
                        return false
                }
                lastgc := int64(atomic.Load64(&memstats.last_gc_nanotime))
                return lastgc != 0 && t.now-lastgc > forcegcperiod
        case gcTriggerCycle:
        //如果当前没有开启垃圾收集，则触发新的循环；
                return int32(t.n-work.cycles) > 0
        }
        return true
}

用于开启垃圾收集的方法 runtime.gcStart 会接收一个 runtime.gcTrigger 类型的结构，所有出现 runtime.gcTrigger 结构体的位置都是触发垃圾收集的代码：
a.runtime.sysmon 和 runtime.forcegchelper ：后台运行定时检查和垃圾收集；
b.runtime.GC ：用户程序手动触发垃圾收集；
c.runtime.mallocgc ：申请内存时根据堆大小触发垃圾收集。
如果你对gc的源码有兴趣，指路小徐先生的编程世界