先来看看GC(自动垃圾回收)的主要问题:
- 额外的开销(内存/CPU)
- 执行GC的时机无法预测，在实时性要求高的场景或事务处理来说可能是不可容忍的
- 部分GC算法会Stop-the-world
各语言运行时在选取GC算法时，都要从这几个方面进行衡量与取舍，下面是一些常见的GC算法。
引用计数(Reference counting):
为每个对象维护一个计数，保存其它对象指向它的引用数量。当一个引用被覆盖或销毁，该引用对象的引用计数-1，当一个引用被建立或拷贝，引用对象的引用计数+1，如果对象的引用计数为0，则表明该对象不再被访问(inaccessible)，将被回收。引用计数有如下优缺点:
优点:
- GC开销将被均摊到程序运行期，不会有长时间的回收周期。
- 每个对象的生命周期被明确定义，可用于某些编译器的runtime优化。
- 算法简单，易于实现。
- 即时回收，不会等内存状态到达某个阀值再执行回收。
缺点:
- 引用计数会频繁更新，带来效率开销
- 原生的引用计数算法无法回收循环引用的对象链(如C++ shared_ptr引用链)
针对第一个频繁更新的缺点，可以使用延迟更新和合并更新等技术，这通常能够很好优化局部频繁的引用更新(如for循环)，虽然这也增加了算法实现复杂度。
针对循环引用的问题，一种解决方案是弱引用(weak reference)，弱引用不影响GC，通常的实践是owner持有child的强引用，child持有owner的弱引用，在事件注册器或其它容器中，如果你只希望保存这个引用，但不希望这个引用影响GC时，也可弱引用。弱引用在使用时，需要先判断对象是否还存在，如C++的weak_ptr需要先转换为shared_ptr。但这不能完全避免无意的循环墙引用，一些GC算法可以检测循环引用，例如以追踪式GC的思路，从根出发，回收那些不可达的对象。
标记-清扫(Mark-and-Sweep):
标记-清扫算法为每个对象预留一个Flag位，分为两个阶段，标记阶段会从Root向下递归遍历所有对象，并将所有可达对象的Flag位设为”正在使用”。第二阶段，清扫阶段，遍历所有内存，回收那些所有未被标记为”正在使用”的对象。整个算法的思路很简单，也基本上避免了引用计数法的缺点，但最大的缺点在于回收期间整个系统必须暂停(Stop-the-world)。
三色标记法(Tri-color marking):
针对原生标记-清扫算法标记过程会STW的缺点，三色标记法改进了标记方案。三色标记法将所有对象分为三类:
- 白色: GC的候选对象集合(待处理)
- 灰色: 可从根访问，并且还未扫描对白色集合对象的引用(处理中,不会被GC,但引用待确认)
- 黑色: 可从根访问，并且不存在对白色集合的引用(处理完成)
步骤如下:
- 初始化，所有对象都是白色
- 从根遍历，所有可达对象标记为灰色
- 从灰色对象队列中取出对象，将其引用的对象标记为灰色，并将自己标记为黑色
- 重复第三步，直到灰色队列为空，此时白色对象即为孤儿对象，进行回收
三色标记法有个重要的不变量: 黑色对象不会引用任何白色对象，因此白色对象可以在灰色对象处理完成之后立即回收。此算法最大的特点在于将标记过程拆分和量化，使得用户程序和标记过程可并行执行(需要其它技术追踪标记过程中的对象引用变更)，不用Stop-the-world，算法可按照各个集合的大小阶段性执行GC，并且不用遍历整个内存空间。
半空间回收器(semi-space collector)
半空间收集器将内存分为两半，分别叫from space和to space，初始时，所有的对象都在to space中分配直到空间用完，触发一次回收周期，此时to space和from space互换，然后将所有根可访问的对象从from space拷贝到to space，之后程序可以继续执行。新的对象继续在新的to space中分配，直到再次空间用完触发回收。该算法的优点是所有存活的数据结构都紧凑排列在to space，内存分配也可通过简单的分配指针自增来实现，缺点是浪费了一半的内存空间。这种GC方案也叫stop-and-copy。
三色标记法的一些变形
moving or non-moving
三色标记法执行标记流程后(灰色队列为空)，所有的白色对象可被回收，那么这些白色对象是直接被回收，其它不变还是执行内存拷贝(non-moving)，将黑色对象移动并覆盖不再使用的白色对象内存(moving)。相当于执行内存块调整(compact)，可以让内存结构更有序，下次分配更快。这部分算法独立于三色标记，可以由GC算法在运行时选择。
mark and non-sweep
基于半空间收集器的copy思路，可以运用到三色标记法中，通过颜色互换来模拟space互换，该算法对三色标记的颜色定义有所不同，步骤如下:
- 对象只有黑色与白色两种颜色，并且黑色与白色是可以互换的(可通过修改黑白的位映射来实现，无需修改对象)
- 所有可被访问的对象都是黑色，所有可被回收的对象为白色
- 对象从白色对象空间分配，被分配后即标记为黑色
- 当内存空间不足(不再有白色对象)，触发GC，此时所有黑色对象变为白色对象，从根遍历所有可访问的对象，将其由白色变为黑色，此时剩下的白色即为可被回收对象，程序可继续运行
- 程序继续从白色空间分配，直到白色空间用完，再次触发GC
分代GC(Generational GC)
前面的各种标记扫描算法，都有一个缺点，每次需要遍历标记所有可达对象，包括一些长期存活的对象，或者说，GC也具有局部性: 最近被分配的对象越容易不再使用。分代GC即基于这一启发，它将内存空间按”代(Generation)”分为几个部分(通常是两代，即Young Generation和Old Generation)，并尽可能频繁地在年轻的一代执行GC，当年轻一代的内存空间不够时，将可达对象全部移到上一代，此时年轻代的内存全部闲置，可用于分配新对象，这样更快并且通常也更有效率。当老一代GC不够用时，才执行Full Sweep。
通常大部分语言的运行时都会混合多种GC算法，比如Erlang的GC(参考1,2)就混合了分代GC和引用计数(高效)，在进程堆内使用分代GC，对全局数据使用引用计数(即时释放内存)。
Golang GC
简单学习了一下Golang GC，Golang使用的是三色标记法方案，并且支持并行GC，即用户代码何以和GC代码同时运行。具体来讲，Golang GC分为以下阶段:
- Mark: 包含两部分:
- Mark Prepare: 初始化GC任务，包括开启写屏障(write barrier)和辅助GC(mutator assist)，统计root对象的任务数量等，这个过程需要STW
- GC Drains: 扫描所有root对象，包括全局指针和goroutine(G)栈上的指针（扫描对应G栈时需停止该G)，将其加入标记队列(灰色队列)，并循环处理灰色队列的对象，直到灰色队列为空。该过程后台并行执行
- Mark Termination: 完成标记工作，重新扫描(re-scan)全局指针和栈。因为Mark和用户程序是并行的，所以在Mark过程中可能会有新的对象分配和指针赋值，这个时候就需要通过写屏障（write barrier）记录下来，re-scan 再检查一下，这个过程也是会STW的。
- Sweep: 按照标记结果回收所有的白色对象，该过程后台并行执行
- Sweep Termination: 对未清扫的span进行清扫, 只有上一轮的GC的清扫工作完成才可以开始新一轮的GC。
Golang GC流程图:
1. STW(Stop The World)
Golang的GC过程有两次STW:
第一次STW会准备根对象的扫描, 启动写屏障(Write Barrier)和辅助GC(mutator assist).
第二次STW会重新扫描部分根对象, 禁用写屏障(Write Barrier)和辅助GC(mutator assist).
2. Write Barrier
写屏障用于在编译器在写操作时插入一段代码，对应的还有读屏障。在三色标记法的标记过程中，我们需要保证黑色对象只能引用黑色对象或者灰色对象，不能引用白色对象，否则该白色对象可能无法被标记到从而被回收。因此需要写屏障对写操作插入代码来做对应的记录，以用于re-scan。
在Go1.8之前，Go使用Dijkstra-style insertion write barrier [Dijkstra ‘78]来完成在Mark过程中，用户程序对指针的赋值和覆盖追踪，该方案的优点是无需读屏障(read barrier)，但保守地将有变更的栈标记为灰色，这样在第一遍Mark之后，还需要re-scan所有灰色的栈。
Go1.8及之后采用另一种混合屏障(hybrid write barrier that combines a Yuasa-style deletion write barrier [Yuasa ‘90] and a Dijkstra-style insertion write barrier [Dijkstra ‘78]. )，大幅度减少了第二次STW的时间，详细参考17503-eliminate-rescan。
参考: