垃圾回收
简介
在计算机科学中，垃圾回收（英语：Garbage Collection，缩写为GC）是指一种自动的存储器管理机制，用来回收heap中不再使用的对象。当某个程序占用的一部分内存空间不再被这个程序访问时，这个程序会借助垃圾回收算法向操作系统归还这部分内存空间。垃圾回收器可以减轻程序员的负担，也减少程序中的错误。垃圾回收最早起源于LISP语言。目前许多语言如Smalltalk、Java、C#、Go和D语言都支持垃圾回收器。
基本原理
区分活对象（live object）与垃圾对象（garbage）
回收垃圾对象的内存，使得程序可以重复使用这些内存
可回收对象的判断
引用计数
概念
引用计数其实就是为每一个内存单元设置一个计数器，当被引用的时候计数器加一，当计数器减少为 0 的时候就意味着这个单元再也无法被引用了，所以可以立即释放内存
缺点
存在循环引用问题
<span style="font-size: inherit;">python通过引用计数+标记清除来解决循环引用问题</span><br>
可达性分析(追踪式)
从GC Roots（每种具体实现对GC Roots有不同的定义,常见的如全局变量，栈上的对于堆对象的引用啊）作为起点，向下搜索它们引用的对象，可以生成一棵引用树，树的节点视为可达对象，反之视为不可达
优点
可以很好的解决引用计数法对象之间循环引用导致不可回收问题
基础算法
标记清除算法
简介
分为两个阶段（标记，清除），先标记出所有需要回收的对象，在标记完成后，当发送GC时统一回收所有被标记的对象。<br><br>
标记整理算法
简介
跟标记清除算法一样同样是两个阶段，标记出可回收的对象，让存货的对象向一端移动，然后清理掉端边界以外的内存
缺点
需要对堆进行多次搜索，毕竟是在一个空间内又标记，又移动的，所以整体而言花费的时间较多，而且如果堆很大的情况，那么消耗的时间将更加突出
标记复制算法
简介
它将可用内存按容量划分为大小相等的两块，每次之使用其中的一块。当这一块内存用完了，就将还存活这着的对象复制到另外一块上面，然后再把已使用过的内存空间一次性清理掉。
优点
内存分配时也就不用考虑内存碎片等复杂情况，只要移动堆顶指针，按顺序分配内存即可，实现简单，运行高效
分代回收算法
简介
基于弱分代假说，大部分对象会再出生灭多久就会死亡，只有少部分对象能长期存活。所以把堆分为老年代与新生代，新声代分为Eden跟Survivor区域。根据对象特征，年轻代使用标记复制算法，老年代一半都用标记-清除，当察觉内存碎片实在太多了就用标记-整理来配合使用。
优点
根据对象存活情况的不同来进行选择合适的垃圾回收算法
缺点
实现复杂，老年代引用新生代的情况，以老年代对象为根的时候扫描老年代效率会非常低(Remembered Set解决)
go GC
设计原理
标记清理作为基础算法
针对会产生的内存碎片问题，go通过把内存划分成68种大小的内存，按需分配，回收来解决这个问题
三色抽象
简介
为了解决原始标记清除算法带来的长时间 STW，多数现代的追踪式垃圾收集器都会实现三色标记算法的变种以缩短 STW 的时间。三色标记算法将程序中的对象分成白色、黑色和灰色三类
对象分类
白色对象 — 潜在的垃圾，其内存可能会被垃圾收集器回收；
黑色对象 — 活跃的对象，包括不存在任何引用外部指针的对象以及从根对象可达的对象；
灰色对象 — 活跃的对象，因为存在指向白色对象的外部指针，垃圾收集器会扫描这些对象的子对象
执行过程
从灰色对象的集合中选择一个灰色对象并将其标记成黑色；
将黑色对象指向的所有对象都标记成灰色，保证该对象和被该对象引用的对象都不会被回收
重复上述两个步骤直到对象图中不存在灰色对象
存在的问题
上面的流程在标记过程中用户程序完全停止(STW)，但是GO是<b>增量式并发GC</b>，用户程序可能在标记执行的过程中修改对象的指针，这就可能导致本来不应该被回收的对象却被回收了，这在内存管理中是非常严重的错误，我们将这种错误称为<b>悬挂指针</b>，即指针没有指向特定类型的合法对象，影响了内存的安全性，想要并发或者增量地标记对象还是需要使用<b>屏障技术</b>
屏障技术
简介
用户程序读取对象、创建新对象以及更新对象指针时执行的一段代码，根据操作类型的不同，我们可以将它们分成读屏障（Read barrier）和写屏障（Write barrier）两种，因为读屏障需要在读操作中加入代码片段，对用户程序的性能影响很大，所以编程语言往往都会采用写屏障保证三色不变性。
三色不变
强三色不变
黑色对象不会指向白色对象，只会指向灰色对象或者黑色对象
弱三色不变
黑色对象指向的白色对象必须包含一条从灰色对象经由多个白色对象的可达路径
插入写屏障
简介
在A对象引用B对象时将B对象标记会灰色(满足强三色不变式)
存在问题
插入写屏障是一种相对保守的屏障技术，它会将有存活可能的对象都标记成灰色以满足强三色不变性。在如上所示的垃圾收集过程中，实际上不再存活的 B 对象最后没有被回收；而如果我们在第二和第三步之间将指向 C 对象的指针改回指向 B，垃圾收集器仍然认为 C 对象是存活的，这些被错误标记的垃圾对象只有在下一个循环才会被回收
栈上的对象在垃圾收集中也会被认为是根对象，所以为了保证内存的安全，Dijkstra 必须为栈上的对象增加写屏障或者在标记阶段完成重新对栈上的对象进行扫描，这两种方法各有各的缺点，前者会大幅度增加写入指针的额外开销，后者重新扫描栈对象时需要暂停程序(go1.7之前，选择<b>在标记完成阶段，暂停用户程序，然后把栈对象标记成灰色，并进行重新扫描</b>，这也导致了10-100ms的GC时间)
删除写屏障
简介
老对象的引用被删除时，将白色的老对象涂成灰色(保证弱三色不变)
存在问题
B对象在下轮垃圾回收的时候才会被回收
需要开始时把整个根部扫描一遍(STW)，让所有的可达对象全都在灰色保护下（根黑，下一级在堆上的全灰）
混合写屏障
实现原理
插入/删除屏障总结
插入写屏障，由于栈上对象无写屏障（不 hook），那么导致黑色的栈可能指向白色的堆对象，而且到白色的其它可达路径被删除了，需要STW重新扫描栈
删除写屏障,存在堆上的黑色对象C，引用另外堆上的白色对象D，而且刚好栈上对象无屏障，断开了对D的引用，需要快照的STW解决问题
如何无需重新扫描栈，也无需快照？
创建的所有新对象都标记成黑色
被删除的对象标记为灰色
被添加的对象标记为灰色
并发处理每个goroutine 栈(栈上最后都是黑色)
主体并发增量式垃圾回收
什么是增量垃圾回收
传统的垃圾收集算法会在垃圾收集的执行期间暂停应用程序，一旦触发垃圾收集，垃圾收集器会抢占 CPU 的使用权占据大量的计算资源以完成标记和清除工作，然而很多追求实时的应用程序无法接受长时间的 STW。<b>增量式</b>（Incremental）的垃圾收集是减少程序最长暂停时间的一种方案，它可以将原本时间较长的暂停时间切分成多个更小的 GC 时间片
通过开启读写屏障、利用多核优势与用户程序并行执行，不仅能够减少程序的STW时间，还能减少整个垃圾收集阶段的时间
执行流程
清理终止阶段
<b>暂停程序</b>，所有的处理器在这时会进入安全点（Safe point）
如果当前垃圾收集循环是强制触发的，我们还需要处理还未被清理的内存管理单元
标记阶段
将状态切换至 _GCmark、<b>开启写屏障</b>、用户程序协助（Mutator Assists）并将根对象入队
恢复执行程序，标记进程和用于协助的用户程序会开始并发标记内存中的对象，写屏障会将被覆盖的指针和新指针都标记成灰色，而所有新创建的对象都会被直接标记成黑色
开始扫描根对象，包括所有 Goroutine 的栈、全局对象以及不在堆中的运行时数据结构，扫描 Goroutine 栈期间会暂停当前处理器
依次处理灰色队列中的对象，将对象标记成黑色并将它们指向的对象标记成灰色
使用分布式的终止算法检查剩余的工作，发现标记阶段完成后进入标记终止阶段
标记终止阶段
<b>暂停程序</b>，将状态切换至 _GCmarktermination 并关闭辅助标记的用户程序
清理处理器上的线程缓存
清理阶段
将状态切换至 _GCoff 开始清理阶段，初始化清理状态并<b>关闭写屏障</b>
恢复用户程序，所有新创建的对象会标记成白色
后台并发清理所有的内存管理单元，当 Goroutine 申请新的内存管理单元时就会触发清理
触发方式
gcTriggerCycle 如果当前没有开启垃圾收集，则启动GC；主要是调用函数 runtime.GC()
gcTriggerHeap 当前分配的内存达到一定阈值时触发，这个阈值在每次GC过后都会根据堆内存的增长情况和CPU占用率来调整；主要是 mallocgc() 函数,其中分配内存对象大小又分多种情况，建议看下源码实现。
gcTriggerTime 自从上次GC后间隔时间达到了runtime.forcegcperiod 时间（默认为2分钟），将启动GC；主要是 sysmon 监控线程
引用
https://zhuanlan.zhihu.com/p/359582221
https://draveness.me/golang/docs/part3-runtime/ch07-memory/golang-garbage-collector/
https://www.ardanlabs.com/blog/2018/12/garbage-collection-in-go-part1-semantics.html
https://zhuanlan.zhihu.com/p/297177002
https://mp.weixin.qq.com/s/d-j0LJyrm0aTvyUGCjfarw
https://liqingqiya.github.io/golang/gc/%E5%9E%83%E5%9C%BE%E5%9B%9E%E6%94%B6/%E5%86%99%E5%B1%8F%E9%9A%9C/2020/07/24/gc5.html
