垃圾回收算法

业界常见的垃圾回收算法有以下几种：
引用计数:对每个对象维护一个引用计数，当引用该对象的对象被销毁时，引用计数减1，当引用计数器为0是回收该对象。
优点：对象可以很快的被回收，不会出现内存耗尽或达到某个阀值时才回收。
缺点：不能很好的处理循环引用，而且实时维护引用计数，有也一定的代价。
代表语言：Python、PHP、Swift
标记-清除:从根变量开始遍历所有引用的对象，引用的对象标记为"被引用"，没有被标记的进行回收。
优点：解决了引用计数的缺点。
缺点：需要STW，即要暂时停掉程序运行。
代表语言：Golang(其采用三色标记法)
分代收集:按照对象生命周期长短划分不同的代空间，生命周期长的放入老年代，而短的放入新生代，不同代有不能的回收算法和回收频率。
优点：回收性能好
缺点：算法复杂
代表语言： JAVA

Golang GC

Golang的GC算法主要是基于 标记-清扫(markandsweep)算法，并在此基础上做了改进。因此，在此主要介绍一下标记-清扫(mark and sweep)算法，关于引用计数(reference counting)和复制收集(copy and collection)可自行百度。

此算法主要有两个主要的步骤：

标记(Mark phase)
清除(Sweep phase)

第一步，找出不可达的对象，然后做上标记。
第二步，回收标记好的对象。

标记-清扫(Mark And Sweep)算法这种算法虽然非常的简单，但是还存在一些问题：
STW，stop the world；让程序暂停，程序出现卡顿。
标记需要扫描整个heap
清除数据会产生heap碎片
这里面最重要的问题就是：mark-and-sweep 算法会暂停整个程序。
Go是如何面对并这个问题的呢？

三色并发标记法

我们先来看看Golang的三色标记法的大体流程。

首先：程序创建的对象都标记为白色。
gc开始：扫描所有可到达的对象，标记为灰色
从灰色对象中找到其引用对象标记为灰色，把灰色对象本身标记为黑色
监视对象中的内存修改，并持续上一步的操作，直到灰色标记的对象不存在
此时，gc回收白色对象。

例如，当前内存中有A~F一共6个对象，根对象a,b本身为栈上分配的局部变量，根对象a、b分别引用了对象A、B, 而B对象又引用了对象D，则GC开始前各对象的状态如下图所示:

56937675-FEC9-4BE7-AF51-BF02207EDAA2.png

初始状态下所有对象都是白色的。
接着开始扫描根对象a、b:

248FE530-234B-41AB-83C4-AA3A0D290541.png

由于根对象引用了对象A、B,那么A、B变为灰色对象，接下来就开始分析灰色对象，分析A时，A没有引用其他对象很快就转入黑色，B引用了D，则B转入黑色的同时还需要将D转为灰色，进行接下来的分析。如下图所示：

427D6305-7248-4ECA-8797-DB7E79BF7107.png

上图中灰色对象只有D，由于D没有引用其他对象，所以D转入黑色。标记过程结束：

01C18FFF-19A6-4C99-8F22-8A007978FB3B.png

最终，黑色的对象会被保留下来，白色对象会被回收掉。
Go是如何解决标记-清除(mark and sweep)算法中的卡顿(stw，stop the world)问题的呢？

清除操作和逻辑操作并发

我们知道Golang三色标记法中最后只剩下的黑白两种对象，黑色对象是程序恢复后接着使用的对象，如果不碰触黑色对象，只清除白色的对象，肯定不会影响程序逻辑。所以： 清除操作和用户逻辑可以并发。

标记操作和逻辑操作并发

写屏障：该屏障之前的写操作和之后的写操作相比，先被系统其它组件感知。
通俗的讲：就是在gc跑的过程中，可以监控对象的内存修改，并对对象进行重新标记。(实际上也是超短暂的stw，然后对对象进行标记)
gc一旦开始，无论是创建对象还是对象的引用改变，都会先变为灰色