标记清扫法

go在1.3版本之前用的是标记清扫法，核心思想就是扫描对象，然后给扫描到的对象打标记，未扫描到的对象就是垃圾，需要被回收的。

1. 先暂停整个程序
2. 从根对象开始扫描，找到所有的引用，并标记
3. 开始清除没有标记的垃圾
4. 恢复整个程序

标记清扫的缺点比较明显：需要STW，程序在此期间处于停止状态，标记需要扫描整个heap区，并且清除后可能会产生大量的碎片。当要申请一个大对象的时候，由于碎片太多，可能会再次触发一次GC。

go在1.3版本做了优化，即标记完之后，停止STW，让清扫和用户程序一起并行运行。

go1.3之前：

1. stop the world，停止程序运行
2. 标记
3. 清扫
4. start the world，程序恢复

go1.3：

1. stop the world，停止程序运行
2. 标记
3. start the world，程序恢复
4. 清扫

三色标记法

go在1.5版本及以后GC的方式为三色标记法。
root set：根对象，垃圾回收器最先检查的对象。包括程序在编译期就能确定的那些存在于程序整个生命周期的变量、每个goroutine执行栈上的变量及指向堆区的指针、执行过程中指向堆内存的某些指针。
白色：GC开始前的对象都是白色
灰色：正在搜索的对象
黑色：搜索完的对象

1. 所有的对象都是白色

2. GC开始从根扫描，直接触达的对象，设置为灰色，放入灰色集合中

3. 遍历灰色集合，将灰色对象引用的白色对象标记为灰色，放入灰色集合中，自己同时标记为黑色，放入黑色对象中

4. 重复步骤3，直至所有的灰色变成黑色，此时剩下的就是要回收的。

5. GC结束后，所有的黑色对象还原成白色。下次重复步骤。

屏障机制

一个问题： 在上述的第3个步骤中，如果新来了个F指向的H的指针，因为F已经是黑色，不会再扫描，所以关联的H对象会被GC回收，那么F访问H的时候必然会出错。屏障机制可以简单理解为在对象的创建或者删除之前先拦截下，做个校验等一系列前置工作。

为了让GC程序和用户程序并发，只要保证任一三色不变性，就可以让GC不会错误的回收不应该回收的对象。

• 强三色不变性：黑色对象永远不会指向白色对象
• 弱三色不变性：黑色对象指向的白色对象至少包含一条由灰色对象经过白色对象的可达路径

写屏障

读屏障的目的是为了避免黑色对象直接引用白色对象。一个对象可能创建于栈区也可能创建于堆区，由于栈区空间小，要求速度快，所以写屏障不适合做在栈区。

1. GC开始前全部为白色
2. GC从root set开始标记灰色(A、F)
3. 灰色对象引用的对象为灰色(C、G)，自身变为黑色(A、F)
4. 栈区的A引用A1，堆区的F引用F1，A1不变
5. 堆区写屏障，F1为黑色
6. 没有灰色对象，准备GC前，栈区先STW
7. 栈区重新标记至没有灰色
8. 栈区STW结束
9. 清除白色对象D、H
10. 所有对象重新回归白色，等待下次GC

假设上述第4步，F不新引用新的F1，而是将引用从G变成H，则变成：

插入屏障的思想是把所有可能存活的对象都标记成灰色（H），那么此时已经是灰色的G对象在本轮不会被GC回收，只能在下一轮被回收了。
插入屏障的优点：GC可以和用户程序一起执行，除了栈区短暂的STW
插入屏障的缺点：栈区要重新标记回收，垃圾可能本轮会存活（上述的G）

1. 初始化 GC 任务，包括开启写屏障(write barrier)和开启辅助 GC(mutator assist)，统计 root 对象的任务数量等，这个过程需要STW。
2. Stack scan 阶段，从全局空间和 goroutine 栈空间上收集变量。
3. Mark 阶段，执行上述的三色标记法，直到没有灰色对象。
4. Mark termination阶段，开启STW，重新扫描(re-scan)全局指针和栈，因为 Mark 和 mutator 是并行的，所以在 Mark 过程中可能会有新的对象分配和指针赋值，这个时候就需要通过写屏障(write barrier)记录下来，对他们进行标记。
5. Sweep 阶段，关闭 STW 和 写屏障，对白色对象进行清除。

删除屏障

当删除一个对象时，为了满足弱三色不变性，即防止丢失灰色对象到白色对象的可达路径，被删除的对象，不管自身为灰色或者白色，最终被标记为灰色。

1. 对象全为白色
2. gc开始从root set扫描， A、F为灰色
3. A删除了对C的引用，触发删除屏障，C变为灰色
4. 最终除了H，都是黑色

删除屏障相对于插入屏障，不需要GC完之后再扫描一次栈。但是也有个缺点：C已经被A删除了，为什么C还需要被标记为灰色，躲过被GC清除的现象，其实这是为了满足弱三色不变性，假设在A删除C的同时，F引用了C，那么如果C被清除了，F读取C的时候就报错了。所以C和D本轮GC还可以存活，下一轮如果没被引用，就会被清除。可以看出删除屏障的回收精度偏低，一个对象即使被删除了最后一个指向它的指针，也依然可以活一轮GC，在下一轮GC中才被清除。

混合屏障

go1.8引入混合屏障，集合了写屏障和删除屏障的优点。在go1.8之前，我们知道，栈空间不会插入写屏障，当GC结束后，再进行一次扫描栈，这一步需要耗费10~100 ms。 混合屏障逻辑如下：

• GC开始时将栈上所有对象标记为黑色，无须STW
• GC期间在栈上创建的新对象均标记为黑色
• 被删除的下游对象标记为灰色
• 被添加的下游对象标记为灰色

场景1

1. 扫描栈触达的对象都是黑色
2. 栈空间A引用堆空间G，栈空间无插入屏障，所以G的颜色不变
3. 堆空间删除F到G的引用，触发删除屏障，G变为灰色

场景2

1. 扫描栈触达的对象都是黑色
2. 栈空间新建B，为黑色，A引用B，直接引用
3. B引用D，直接引用
4. C删除到D的引用，直接删除

STW阶段

• 当前运行的所有程序将被暂停，扫描内存的root节点和添加写屏障
• 处理器 P (无论是正在运行代码的处理器还是已在 idle 列表中的处理器)，都会被被标记成停止状态 (stopped)， 不再运行任何代码。 调度器把每个处理器的 M从各自对应的处理器 P分离出来，放到idle列表中去。goroutine本身，他们会被放到一个全局队列中等待

内存标记

golang 中采用 span 数据结构管理内存，span 中维护了一个个内存块，并由一个位图 allocBits 表示内存块的分配情况，而上文中提到的 gcmarkBits 是记录每块内存块被引用情况的。

• gcmarkBits 对应位为 1（黑色），该对象不会在本次GC中被回收
• gcmarkBits 对应位为 0（白色），该对象将会在本次GC中被清理

1. allocBits记录了每块内存的分配情况 1：已分配 0：未分配
2. gcmarkBits记录了每块内存的标记情况 1：已标记 0：未标记
3. allocBits 和 gcmarkBits 的数据结构是完全一样的，
4. 在标记结束后，将 allocBits 指向 gcmarkBits，则有标记的才是存活的，这样就完成了内存回收
5. gcmarkBits会在下次标记时重新分配内存

清理阶段

1. 在后台启动一个worker等待清理内存，一个一个mspan处理

当开始运行程序时，Go 将设置一个后台运行的 Worker(唯一的任务就是去清理内存)，它将进入睡眠状态并等待内存段扫描。

2. 当分配需要一个范围的时候即时执行。

当应用程序goroutine尝试在堆内存中分配新内存时，会触发该操作。内存段已经被分发到每一个处理器 P 的本地缓存mcache中，因此很难追踪首先清理哪些内存。这就是为什么Go首先将所有内存段移动到mcentral的原因。然后，它将会让本地缓存 mcache 再次请求它们，去即时清理。

gc历史

1. go v1.1：标记-清除法，整个过程都需要STW，STW时间可能是秒级别
2. go v1.3：标记-清除法，标记过程仍然需要STW但清除过程并行化（Mark和Sweep分离. Mark STW, Sweep并发），STW几百ms
3. go v1.4：runtime代码基本都由C和少量汇编改为Go和少量汇编, 包括GC部分, 以此实现了准确式GC,减少了堆大小, 同时对指针的写入引入了写屏障, 为1.5铺垫 STW几百ms
4. go v1.5：引入插入写屏障技术的三色标记法，仅在堆空间启动插入写屏障，全部扫描后需要STW重新扫描栈空间，并发Mark, 并发Sweep，STW耗时降到10-40ms
5. go v1.6： v1.5中一些与并发GC不协调的地方更改. 集中式的GC协调协程, 改为状态机实现 STW耗时降到5-20ms
6. go v1.7：GC时栈收缩改为并发, span中对象分配状态由freelist改为bitmap STW耗时降到1-3ms左右
7. go v1.8：引入混合写屏障技术的三色标记法，仅在堆空间启动混合写屏障，不需要在GC结束后对栈空间重新扫描，STW耗时降到0.5ms左右
8. go v1.14：引入新的页分配器用于优化内存分配的速度，STW非常短。

何时触发GC

1. gcTriggerHeap 当前分配的内存达到一定阈值时触发，这个阈值在每次GC过后都会根据堆内存的增长情况和CPU占用率来调整；

运行时GC Percentage参数默认为100，你程序的上一次GC完，驻留内存是10MB，那么下一次堆内存达到20MB，会触发GC。如果设置的200，那么下一次堆内存达到30MB会触发GC

2. gcTriggerTime 自从上次GC后间隔时间达到了runtime.forcegcperiod 时间（默认为2分钟），将启动GC；sysmon线程负责监控

3. gcTriggerCycle 如果当前没有开启垃圾收集，则启动GC（runtime.GC()）

上述三个条件满足其一即可。

欢迎大家关注公众号《假装懂编程》，我将持续输出网络、数据库、go、缓存、架构、面试、程序人生相关文章。