垃圾回收(Garbage Collection，简称GC)是编程语言中提供的自动的内存管理机制。

GC背景

C/C++等传统编程语言需要对内存手动释放，操作繁琐，处理不好容易内存泄露，尤其系统比较错综复杂情况下，释放内存可能会产生连锁问题。应对这个问题，后续出现的语言都引入了自动内存管理，内存释放由虚拟机（virtual machine）或运行时（runtime）来自动进行管理。而这种对不再使用的内存资源进行自动回收的功能就被称为垃圾回收。

常见垃圾回收机制

引用计数（reference counting）

对每个对象维护一个引用计数，当引用该对象的对象被销毁时，引用计数减1，当引用计数器为0是回收该对象

优点：对象可以很快的被回收，不会出现内存耗尽或达到某个阀值时才回收。

缺点：不能很好的处理循环引用，而且需要额外的空间存放计数，频繁更新引用计数降低了性能。

代表语言：Python、PHP

标记清除（mark and sweep）

从根变量开始遍历所有引用的对象，引用的对象标记为”被引用”，没有被标记的进行回收。

优点：解决了引用计数的缺点。

缺点：需要STW（stop the world），即要暂时停掉程序运行，不能满足实时性要求较高系统

对于标记清除，有一种标记-压缩算法的衍生算法：

对于压缩阶段，它的工作就是移动所有的可达对象到堆内存的同一个区域中，使他们紧凑的排列在一起，从而将所有非可达对象释放出来的空闲内存都集中在一起，通过这样的方式来达到减少内存碎片的目的。

golang语言采用了另一种衍生算法三色标记，见下文详细介绍

代表语言：golang

分代收集（generation）

按照对象生命周期长短划分不同的代空间，生命周期长的放入老年代，而短的放入新生代，不同代有不同的回收算法和回收频率。

新创建的对象存放在称为新生代（young generation）中（一般来说，新生代的大小会比老年代小很多）。高频对新生成的对象进行回收，称为「小回收」，低频对所有对象回收，称为「大回收」。

每一次「小回收」过后，就把存活下来的对象归为老年代，「小回收」的时候，遇到老年代直接跳过。大多数分代回收算法都采用的「复制收集」方法，因为小回收中垃圾的比例较大。

优点：回收性能好

缺点：实现复杂，引入『写屏障』（Write Barrier）

代表语言：JAVA

复制收集（Copying）

复制收集的方式只需要对对象进行一次扫描。准备一个「新的空间」，从根开始，对对象进行扫，如果存在对这个对象的引用，就把它复制到「新空间中」。一次扫描结束之后，所有存在于「新空间」的对象就是所有的非垃圾对象。

优点：只需臊面扫描一次，有『局部性』

收集过程中会按照对象被引用的顺序将对象复制到新空间中。关系较近的对象被放在距离较近的内存空间的可能性会提高，这叫做局部性。局部性高的情况下，内存缓存会更有效地运作，程序的性能会提高。

缺点：需要额外开辟一块用来复制的内存

代表语言：JAVA

golang垃圾回收

演进过程

go语言垃圾回收总体采用的是mark and sweep的衍生算法『三色标记』，演进过程如下

1.3以前的版本使用标记-清扫的方式，整个过程都需要STW。
1.3版本分离了标记和清扫的操作，标记过程STW，清扫过程并发执行。
1.5版本在标记过程中使用三色标记法。回收过程主要有四个阶段，其中，标记和清扫都并发执行的，但标记阶段的前后需要STW一定时间来做GC的准备工作和栈的re-scan。

三色标记

三色标记算法是对标记阶段的改进，解决STW时间过长，将程序中的对象分为黑、白、灰三种颜色

白色对象 — 潜在的垃圾，其内存可能会被垃圾收集器回收；
黑色对象 — 活跃的对象，包括不存在任何引用外部指针的对象以及从根对象可达的对象；
灰色对象 — 活跃的对象，因为存在指向白色对象的外部指针，垃圾收集器会扫描这些对象的子对象；

起初所有对象都是白色。
从根出发扫描所有可达对象，标记为灰色，放入待处理队列。
从队列取出灰色对象，将其引用对象标记为灰色放入队列，自身标记为黑色。
重复3，直到灰色对象队列为空。此时白色对象即为垃圾，进行回收。

操作流程如下图：

标记过程需的要STW，因为对象引用关系如果在标记阶段做了修改，会影响标记结果的正确性。但是STW的过程有明显的资源浪费，对所有的用户程序都有很大影响，如何能在保证对象不丢失的情况下合理的尽可能的提高GC效率，减少STW时间呢？

在Golang中使用并发的垃圾回收，也就是多个赋值器与回收器并发执行，与此同时，应用屏障技术来保证回收器的正确性

屏障技术

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

弱三色不变式：所有被黑色对象引用的白色对象都处于灰色保护状态（直接或间接从灰色对象可达）。

强三色不变式：不存在黑色对象到白色对象的指针。

垃圾收集中的屏障技术更像是一个钩子方法，它是在用户程序读取对象、创建新对象以及更新对象指针时执行的一段代码，根据操作类型的不同，我们可以将它们分成读屏障（Read barrier）和写屏障（Write barrier）两种，因为读屏障需要在读操作中加入代码片段，对用户程序的性能影响很大，所以编程语言往往都会采用写屏障保证三色不变性。

插入屏障

插入屏障拦截将白色指针插入黑色对象的操作，标记其对应对象为灰色状态，这样就不存在黑色对象引用白色对象的情况了，满足强三色不变式，如上图例中，在插入指针f时将C对象标记为灰色。Go1.5版本使用的Dijkstra写屏障就是这个原理，伪代码如下：

writePointer(slot, ptr):
    shade(ptr)
    *slot = ptr

在Golang中，对栈上指针的写入添加写屏障的成本很高，所以Go选择仅对堆上的指针插入增加写屏障，这样就会出现在扫描结束后，栈上仍存在引用白色对象的情况，这时的栈是灰色的，不满足三色不变式，所以需要对栈进行重新扫描使其变黑，完成剩余对象的标记，这个过程需要STW。这期间会将所有goroutine挂起，当有大量应用程序时，时间可能会达到10～100ms。

删除屏障

删除屏障也是拦截写操作的，但是是通过保护灰色对象到白色对象的路径不会断来实现的。这种方式的回收精度低，一个对象即使被删除了最后一个指向它的指针也依旧可以活过这一轮，在下一轮GC中被清理掉。Yuasa屏障伪代码如下：

writePointer(slot, ptr):
    if (isGery(slot) || isWhite(slot))
        shade(*slot)
    *slot = ptr

在这种实现方式中，回收器悲观的认为所有被删除的对象都可能会被黑色对象引用。

混合写屏障

插入屏障和删除屏障各有优缺点，Dijkstra的插入写屏障在标记开始时无需STW，可直接开始，并发进行，但结束时需要STW来重新扫描栈，标记栈上引用的白色对象的存活；Yuasa的删除写屏障则需要在GC开始时STW扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象，但结束时无需STW。Go1.8版本引入的混合写屏障结合了Yuasa的删除写屏障和Dijkstra的插入写屏障，结合了两者的优点，伪代码如下：

writePointer(slot, ptr):
    shade(*slot)
    if current stack is grey:
        shade(ptr)
    *slot = ptr

这里使用了两个shade操作，shade(*slot)是删除写屏障的变形，例如，一个堆上的灰色对象B，引用白色对象C，在GC并发运行的过程中，如果栈已扫描置黑，而赋值器将指向C的唯一指针从B中删除，并让栈上其他对象引用它，这时，写屏障会在删除指向白色对象C的指针的时候就将C对象置灰，就可以保护下来了，且它下游的所有对象都处于被保护状态。如果对象B在栈上，引用堆上的白色对象C，将其引用关系删除，且新增一个黑色对象到对象C的引用，那么就需要通过shade(ptr)来保护了，在指针插入黑色对象时会触发对对象C的置灰操作。如果栈已经被扫描过了，那么栈上引用的对象都是灰色或受灰色保护的白色对象了，所以就没有必要再进行这步操作。

Golang中的混合写屏障满足的是变形的弱三色不变式，同样允许黑色对象引用白色对象，白色对象处于灰色保护状态，但是只由堆上的灰色对象保护。由于结合了Yuasa的删除写屏障和Dijkstra的插入写屏障的优点，只需要在开始时并发扫描各个goroutine的栈，使其变黑并一直保持，这个过程不需要STW，而标记结束后，因为栈在扫描后始终是黑色的，也无需再进行re-scan操作了，减少了STW的时间。

触发时机

自动垃圾回收的触发条件有两个：

超过内存大小阈值阈值是由一个gcpercent的变量控制的,当新分配的内存占已在使用中的内存的比例超过gcprecent时就会触发。比如一次回收完毕后，内存的使用量为5M，那么下次回收的时机则是内存分配达到10M的时候。也就是说，并不是内存分配越多，垃圾回收频率越高。
达到定时时间如果一直达不到内存大小的阈值呢？这个时候GC就会被定时时间触发，比如一直达不到10M，那就定时（默认2min触发一次）触发一次GC保证资源的回收。

总结

本文介绍了常见垃圾回收算法，对golang GC的演进及三色标记做了详细介绍，屏障技术的使用使得golang可以并发回收垃圾。但是GC不是万能的，最好还是养成手动回收内存的习惯：比如手动把不再使用的内存释放，把对象置成nil，也可以考虑在合适的时候调用runtime.GC()触发GC。

参考文章

https://segmentfault.com/a/1190000004665100 https://segmentfault.com/a/1190000018161588 https://draveness.me/golang/docs/part3-runtime/ch07-memory/golang-garbage-collector/ https://studygolang.com/articles/25096 https://zhuanlan.zhihu.com/p/74853110 https://juejin.im/post/6844903917650722829