垃圾回收Garbage CollectionGC

常用垃圾回收算法手段

这一部分八股文内容一笔带过，做一个知识了解即可。

1、引用计数

对象被使用这个对象被引用计数+1，解除引用-1，引用数为0时就是垃圾，被回收。

若两个对象相互引用存在无法归零的可能，需要有相应的解决方案。

2、比较压缩

第一种整块复制：有两块相同的内存待清扫区域A和空白干净区域B，清扫A区域时将A区域有用的对象到B区域，然后清理整块A区域。

第二种存活临近复制：没有所谓AB两块区域，仅在A区域扫描到存活对象后复制到相似对象临近，相当于加入了一个碎片整理功能。

3、分代回收

这种算法基于一个概率论：大部分对象会从产生开始在很短的时间内变成垃圾，而存在的很长时间的对象往往都有较长的生命周期。

高频对新生成的对象进行回收称为「小回收」，低频对所有对象回收称为「大回收」。每一次「小回收」过后，就把存活下来的对象归为老年代，「小回收」的时候，遇到老年代直接跳过。基于上述概率论小回收中垃圾的比例较大。

如果在某个新生代的对象中，存在「老生代」的对象对它的引用，它就不是垃圾了，那么怎么制止「小回收」对其回收呢？这里用到了一种叫做写屏障（Write Barrier）的处理方式。

4、标记清扫

内存对象往往是相互关联的，从根对象往下连，标记清扫的理论基点：可达性近似等于存活性这种设定。

该方法分为两步，标记从根对象开始标记，对能够通过引用关联访问到的对象标记为存活；标记完成后那些没有关联到也就是不可达的对象就是垃圾，进行回收。

标记清扫有个极大的缺点就是标记清扫阶段需要暂停整个程序（Stop the world，简称STW）仅执行GC逻辑。

go语言的垃圾会收就是该种方式，只不过深度使用了协程的并发特性并且配合使用了混合写屏障技术。

三色标记抽象

三色标记抽象： 

白色
灰色
黑色

三色标记抽象过程大致如下：

  1. 标记开始时所有对象为白色；
  2. 把直接能追踪到的根对象标记为灰色，灰色表示基于当前节点的追踪标记尚未完成；
  3. 基于灰色节点进行追踪，找到下一层关联的白色节点，标记灰色节点为黑色白色节点为灰色；
  4. 重复基于灰色节点的追踪流程并标记，最终只有黑色节点和白色节点，黑色就是存活对象白色就是垃圾可以在清理阶段执行清理；

三色不变式

垃圾回收器的正确性体现在：不应出现对象的丢失，也不应错误的回收还不需要回收的对象。三色不变式是三色标记过程中保障标记正确性的重要理论： 

强三色不变式
弱三色不变式

算法理论已证明只要满足上述任意一种不变式，就能保障对象不会被错误的回收。而屏障机制就是标记过程中保证三色不变式的重要技术实现。

屏障机制 

插入写屏障
删除写屏障

go语言gc进化流程

go语言的垃圾回收gc一直在持续不断的优化。以下列出版本迭代情况的摘抄：

  • go1.0：完全串行的标记和清除过程，需要暂停整个程序；
  • go1.1：在多核主机并行执行垃圾收集的标记和清除阶段；
  • go1.3：运行时基于只有指针类型的值包含指针的假设增加了对栈内存的精确扫描支持，实现了真正精确的垃圾收集；将 unsafe.Pointer 类型转换成整数类型的值认定为不合法的，可能会造成悬挂指针等严重问题；
  • go1.5：实现了基于三色标记清扫的并发垃圾收集器；大幅度降低垃圾收集的延迟从几百 ms 降低至 10ms 以下；计算垃圾收集启动的合适时间并通过并发加速垃圾收集的过程；
  • go1.6：实现了去中心化的垃圾收集协调器；基于显式的状态机使得任意 Goroutine 都能触发垃圾收集的状态迁移；使用密集的位图替代空闲链表表示的堆内存，降低清除阶段的 CPU 占用；
  • go1.7：通过并行栈收缩将垃圾收集的时间缩短至 2ms 以内；
  • go1.8：使用混合写屏障将垃圾收集的时间缩短至 0.5ms 以内；
  • go1.9 ：彻底移除暂停程序的重新扫描栈的过程；
  • go1.10：更新了垃圾收集调频器（Pacer）的实现，分离软硬堆大小的目标；
  • go1.12 ：使用新的标记终止算法简化垃圾收集器的几个阶段；
  • go1.13 ：通过新的 Scavenger 解决瞬时内存占用过高的应用程序向操作系统归还内存的问题；
  • go1.14：使用全新的页分配器优化内存分配的速度；

三色标记和混合写屏障gc

上面介绍了三色抽象和屏障机制，go语言实现的三色标记+混合写屏障集中了插入屏障和删除屏障的优点，这种屏障称之为混合写屏障。go语言标记过程因混合写屏障存在要点如下：

  • 标记开始是栈上的可达对象全部标记为黑色，因为栈上没有实现屏障；
  • 在栈上创建的新对象均为黑色；
  • 混合写屏障保障任何被删除的对象被标记为灰色，这是删除屏障的优点；
  • 混合写屏障保障被添加的对象被标记为灰色，这是插入屏障的优点；
  • 按可达性执行三色标记最终只有黑色和白色；

go语言gc流程和我们的业务代码流程是间隔交替并发执行的，参考go源码runtime包中的mgc.go文件的相关注释（见参考资料⑥），gc执行的流程按执行周期可划分为4个阶段： 

p.gcBgMarkWorkder

1、清理终止阶段（sweep termination）

上一轮的gc过程需要彻底结束，清理尚未清理完的上一轮的白色区域。

  • STW，每个P进入GC safepoint（安全点）；
  • 清理未被清理的span，如果GC被强制执行时才会出现这些未清理的span；

2、标记阶段（mark） 

_GCoff_GCmarkwrite barriesmutator assistsdistributed termination algorithmmark termination

----

用户程序协助（Mutator Assists） 

p.gcBgMarkWorkder

----

3、标记终止阶段（mark termination） 

_GCmarktermination

4、清理阶段（sweep） 

_GCoff

---- 

mark termination

参考资料：

① https://segmentfault.com/a/1190000018161588

② https://zhuanlan.zhihu.com/p/92210761

③ https://draveness.me/golang/docs/part3-runtime/ch07-memory/golang-garbage-collector/

④ https://blog.csdn.net/qiya2007/article/details/107622603

⑤ https://blog.haohtml.com/archives/25372

⑥ https://github.com/golang/go/blob/a83a5587331392fc9483d183e446586b463ad8aa/src/runtime/mgc.go#L24-L82

⑦ https://github.com/golang/proposal/blob/master/design/17503-eliminate-rescan.md