标记-清除法
标记-清除法（Mark-Sweep）是一种基于追踪回收（tracing GC）技术的垃圾回收算法。它分为两个阶段：
标记阶段：从根对象（root object）开始遍历，将所有可达的（reachable）对象标记为活动对象
root object 可以是全局对象、调用栈上的对象等
清除阶段：扫描整个内存空间，回收没有标记的非活动对象
标记-清除法的缺点是回收期间会 STW（Stop The World）。
三色标记法
针对原生标记-清除法标记过程会 STW 的缺点，三色标记法（Tri-Color Marking）改进了标记方案。三色标记法将所有对象分成三类：
- 白色：GC 的候选对象集合
- 灰色：从根对象可达，但是还未扫描对白色集合对象的引用
- 黑色：从根对象可达，黑色对象不会引用任何白色对象
三色标记法的过程如下：
- 初始时，所有对象都为白色
- 从根对象开始遍历，将所有可达对象标记为灰色
- 从灰色队列中取出对象，将其引用的对象标记为灰色，并且将自己标记为黑色
- 重复执行上面的过程，直到灰色队列为空
因为黑色对象不会引用任何白色对象，所以可以在处理完灰色对象之后，立即回收白色对象。此算法的最大特点是标记过程可以与用户程序并行运行（需要其它技术追踪标记过程中的对象引用变更）。
GC in Go
Golang GC 使用的是三色标记法方案，并且支持并行 GC，即用户程序可以与 GC 任务同时运行。其过程如下：
Mark
- Mark Prepare：初始化 GC 任务，包括开启写屏障（Write Barrier）和辅助 GC（mutator assist）、统计 root object 数量等，这个过程会 STW
- GC Drains：扫描所有 root object，包括全局指针、Goroutine 栈上的指针，将其放到灰色队列，然后循环处理灰色队列中的对象，直到灰色队列为空，这个过程会在后台并行执行
Mark Termination
标记过程完成后，re-scan 全局指针和栈。因为标记过程和用户程序并行执行，所以需要通过写屏障（Write Barrier）来记录标记过程中的对象分配和指针赋值，然后 re-scan，这个过程也会 STW
Sweep
回收所有白色对象，这个过程会并行执行
Sweep Termination
清扫未清扫的 span注释1，只有在上一轮 GC 的清扫工作完成后，才能开启下一轮 GC
注释
注释1：
为了解决内存碎片的问题。Go 将内存块分成大小不同的 67 种，然后把这 67 种大内存块逐个拆分成小块，每个小块是一个 span。分配内存时，根据对象的大小选择长度相近的 span。这样就解决了内存碎片问题
原文地址
https://wudaijun.com/2017/12/gc-study/