gc出现

对于任何使用C语言的人，如果问他们C语言的最大烦恼是什么，其中许多人可能会回答说是指针和内存泄漏。以致于后出现的语言，都在帮助程序员来处理内存泄漏的问题，比较有名的语言java、python、go等等，都有一个比较重要的机制，那就是gc(Garbage Collection)，也就是垃圾收集器。当然这也是得意于这些语言的特质，它们在运行的时候，都有一个诸如golang中runtime的机制，java中有jvm来管理。程序员不再需要考虑，我什么时候应该分配内存，什么时候应该回收内存。如果是从c语言开始学习编程的，应该对malloc和free非常熟悉，再写代码的时候回小心翼翼的使用这两个函数。如果是学python的，根本就不会注意到这个问题，有不会关心这个方面的问题。比较值得说明的是，在c语言中使用char列表来存储字符串，是一件非常麻烦的事情，在java等但是，就算如此，在日常的写程序的过程中，程序员也应该注意gc方面的问题。一个比较差的设计，可能使得gc对于整个程序的负担非常的大，可能会发现程序中gc的时间占比非常高。

gc的原理

gc常见的方式有：

引用计数（reference counting）每个对象维护一个引用计数器，当引用该对象的对象被销毁或者更新的时候，被引用对象的引用计数器自动减 1，当被应用的对象被创建，或者赋值给其他对象时，引用 +1，引用为 0 的时候回收，思路简单，但是频繁更新引用计数器降低性能，存在循环以引用（php，Python所使用的）

标记清除（mark and sweep）就是 golang 所使用的，从根变量来时遍历所有被引用对象，标记之后进行清除操作，对未标记对象进行回收，缺点：每次垃圾回收的时候都会暂停所有的正常运行的代码，系统的响应能力会大大降低，各种 mark&swamp 变种（三色标记法），缓解性能问题。

分代搜集（generation）jvm 就使用的分代回收的思路。在面向对象编程语言中，绝大多数对象的生命周期都非常短。分代收集的基本思想是，将堆划分为两个或多个称为代（generation）的空间。新创建的对象存放在称为新生代（young generation）中（一般来说，新生代的大小会比 老年代小很多），随着垃圾回收的重复执行，生命周期较长的对象会被提升（promotion）到老年代中（这里用到了一个分类的思路，这个是也是科学思考的一个基本思路）。

golang中的gc原理

go1.3以前gc最大的问题在于stw(stop the word)，即在gc的时候需要暂停程序行为，然后进标记，最后将未标记的垃圾清除。如果频繁的触发gc的话，程序的运行就一卡一卡的。其基本的思路就是：

1.标记：在内存堆中（由于有的时候管理内存页的时候要用到堆的数据结构，所以称为堆内存）存储着有一系列的对象，这些对象可能会与其他对象有关联（references between these objects） a tracing garbage collector 会在某一个时间点上停止原本正在运行的程序，之后它会扫描 runtim e已经知道的的 object 集合（already known set of objects），通常它们是存在于 stack 中的全局变量以及各种对象。gc 会对这些对象进行标记，将这些对象的状态标记为可达，从中找出所有的，从当前的这些对象可以达到其他地方的对象的 reference，并且将这些对象也标记为可达的对象，这个步骤被称为 mark phase，即标记阶段，这一步的主要目的是用于获取这些对象的状态信息。

2.回收：一旦将所有的这些对象都扫描完，gc 就会获取到所有的无法 reach 的对象（状态为 unreachable 的对象），并且将它们回收，这一步称为 sweep phase，即是清扫阶段。

3.清除：gc 仅仅搜集那些未被标记为可达（reachable）的对象。如果 gc 没有识别出一个 reference，最后有可能会将一个仍然在使用的对象给回收掉，就引起了程序运行错误。

go在1.3的时候引入了并发清理，go team 自己的说法是减少了 50%-70% 的暂停时间。
go在1.5时候使用了三色标记法，这个是标记清除算法的一个升级变种。流程如下：

1.灰色：对象已被标记，但这个对象包含的子对象未标记

2.黑色：对象已被标记，且这个对象包含的子对象也已标记，gcmarkBits对应的位为1（该对象不会在本次GC中被清理）

3.白色：对象未被标记，gcmarkBits对应的位为0（该对象将会在本次GC中被清理）

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

1.初始状态下所有对象都是白色的。

2.接着开始扫描根对象a、b; 由于根对象引用了对象A、B,那么A、B变为灰色对象，接下来就开始分析灰色对象，分析A时，A没有引用其他对象很快就转入黑色，B引用了D，则B转入黑色的同时还需要将D转为灰色，进行接下来的分析。

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

4.最终，黑色的对象会被保留下来，白色对象会被回收掉。

go中的gc过程

GO的GC是并行GC, 也就是GC的大部分处理和普通的go代码是同时运行的, 这让GO的GC流程比较复杂。

1.Stack scan：Collect pointers from globals and goroutine stacks。收集根对象（全局变量，和G stack），开启写屏障。全局变量、开启写屏障需要STW，G stack只需要停止该G就好，时间比较少。

2.Mark: Mark objects and follow pointers。标记所有根对象, 和根对象可以到达的所有对象不被回收。

3.Mark Termination: Rescan globals/changed stack, finish mark。重新扫描全局变量，和上一轮改变的stack（写屏障），完成标记工作。这个过程需要STW。

4.Sweep: 按标记结果清扫span

从1.8以后的golang将第一步的stop the world 也取消了，这又是一次优化；1.9开始, 写屏障的实现使用了Hybrid Write Barrier, 大幅减少了第二次STW的时间.
因为go支持并行GC, GC的扫描和go代码可以同时运行, 这样带来的问题是GC扫描的过程中go代码有可能改变了对象的依赖树。
例如开始扫描时发现根对象A和B, B拥有C的指针。

1.GC先扫描A，A放入黑色

2.B把C的指针交给A

3.GC再扫描B，B放入黑色

4.C在白色，会回收；但是A其实引用了C。

为了避免这个问题, go在GC的标记阶段会启用写屏障(Write Barrier)。启用了写屏障(Write Barrier)后，在GC第三轮rescan阶段，根据写屏障标记将C放入灰色，防止C丢失。