1 垃圾回收算法有哪些
1.1 引用计数
算法思想：每个单元维护一个域，保存其它单元指向它的引用数量（类似有向图的入度）。当引用数量为 0 时，将其回收。引用计数是渐进式的，能够将内存管理的开销分布到整个程序之中。C++ 的 share_ptr 使用的就是引用计算方法。
引用计数算法实现一般是把所有的单元放在一个单元池里，比如类似 free list。这样所有的单元就被串起来了，就可以进行引用计数了。新分配的单元计数值被设置为 1（注意不是 0，因为申请一般都说 ptr = new object 这种）。每次有一个指针被设为指向该单元时，该单元的计数值加 1；而每次删除某个指向它的指针时，它的计数值减 1。当其引用计数为 0 的时候，该单元会被进行回收。虽然这里说的比较简单，实现的时候还是有很多细节需要考虑，比如删除某个单元的时候，那么它指向的所有单元都需要对引用计数减 1。
优点
- 渐进式。内存管理与用户程序的执行交织在一起，将 GC 的代价分散到整个程序。不像标记-清扫算法需要 STW (Stop The World，GC 的时候挂起用户程序)。
- 算法简单。
- 内存回收快。由于是跟用户程序的执行交织在一起，遇到引用计数为0的对象就可立即回收，因此可以快速回收内存，不像其他的垃圾回收算法，需要等到内存耗尽或者达到某个阈值才进行垃圾回收。
缺点:
- 不能处理循环引用。大概这是被诟病最多的缺点了。不过针对这个问题，也除了很多解决方案，比如强引用等
- 降低运行效率。内存单元的更新删除等都需要维护相关的内存单元的引用计数，降低了程序运行效率。
1.2 标记清除
算法思想：把堆栈上的本地变量和任意静态变量叫做根（roots），该算法分成两个阶段，第一个阶段是标记。遍历所有的根变量，并且标记它，并且递归标记它所引用的变量。第二个阶段，遍历所有对象，没有被标记的对象可以回收内存，被标记过的对象去掉标记，方便下次重新标记。
第一阶段伪代码
func mark(objectP) {
if !objectP.marked {
objectP.marked = true
for p := range objectP.refedObjs {
mark(p)
}
}
}第二阶段伪代码
func sweep() {
for p range in the heap {
if p.marked{
p.marked = false
}else{
head.release(p)
}
}
}因为标记清除式的垃圾回收跟踪了由根(root)访问的所有对象,所以即使是在有循环引用时,它也可以正确的标记并执行垃圾回收工作，这是标记清除最大的优势，并且对对象不会有额外的内存开销和维护。
缺点是垃圾回收的时候需要stop the word,影响用户程序的运行。
1.3 节点复制
也叫做复制算法（copying算法）。一开始就会将可用内存分为两块，from域和to域， 每次只是使用from域，to域则空闲着。当from域内存不够了，开始执行GC操作，这个时候，会把from域存活的对象拷贝到to域,然后直接把from域进行内存清理。
jvm将Heap 内存划分为新生代与老年代，又将新生代划分为Eden(伊甸园) 与2块Survivor Space(幸存者区) ,然后在Eden –>Survivor Space 以及From Survivor Space 与To Survivor Space 之间实行Copying 算法。 不过jvm在应用coping算法时，并不是把内存按照1:1来划分的，这样太浪费内存空间了。一般的jvm都是8:1。也即是说,Eden区:From区:To区域的比例是：8:1:1。始终有90%的空间是可以用来创建对象的,而剩下的10%用来存放回收后存活的对象。
大概步骤：
- 1.当Eden区满的时候,会触发第一次young gc,把还活着的对象拷贝到Survivor From区；当Eden区再次触发young gc的时候,会扫描Eden区和From区域,对两个区域进行垃圾回收,经过这次回收后还存活的对象,则直接复制到To区域,并将Eden和From区域清空。
- 2.当后续Eden又发生young gc的时候,会对Eden和To区域进行垃圾回收,存活的对象复制到From区域,并将Eden和To区域清空。
- 3.可见部分对象会在From和To区域中复制来复制去,如此交换15次(由JVM参数MaxTenuringThreshold决定,这个参数默认是15),最终如果还是存活,就存入到老年代
优点：在存活对象不多的情况下，性能高，能解决内存碎片和标记清除算法的引用更新问题
缺点：会造成一部分的内存浪费。不过可以根据实际情况，将内存块大小比例适当调整；
如果存活对象的数量比较大，coping的性能会变得很差。
1.4 分代收集
基于追踪的垃圾回收算法（标记-清扫、节点复制）一个主要问题是在生命周期较长的对象上浪费时间（长生命周期的对象是不需要频繁扫描的）。同时，内存分配存在这么一个事实 “most object die young”。基于这两点，分代垃圾回收算法将对象按生命周期长短存放到堆上的两个（或者更多）区域，这些区域就是分代（generation）。对于新生代的区域的垃圾回收频率要明显高于老年代区域。
分配对象的时候从新生代里面分配，如果后面发现对象的生命周期较长，则将其移到老年代，这个过程叫做 promote。随着不断 promote，最后新生代的大小在整个堆的占用比例不会特别大。收集的时候集中主要精力在新生代就会相对来说效率更高，STW 时间也会更短。
优点：性能更优。生命周期长的对象GC频率少，生命周期短的对象GC频率高，大部分对象都是生命周期短的，同时也缩短了STW时间。
缺点：算法实现复杂。
2 go 垃圾回收机制–三色标记法
三色标记法是一种改进的标记清除算法，主要是改进了标记部分，使得垃圾回收与用户程序并发执行
算法思想：
- 首先把所有的对象都放到白色的集合中
- 从根节点开始遍历对象，遍历到的白色对象从白色集合中放到灰色集合中
- 遍历灰色集合中的对象，把灰色对象引用的白色集合的对象放入到灰色集合中，同时把遍历过的灰色集合中的对象放到黑色的集合中
- 循环上一步，直到灰色集合中没有对象
- 灰色集合中没有对象了，白色集合中的对象就是不可达对象，也就是垃圾，进行回收
2.1 写屏障
Go在进行三色标记的时候并没有STW，也就是说，此时的对象还是可以进行修改，这个时候会有问题，当在进行三色标记中扫描灰色集合中，扫描到了对象A，并标记了对象A的所有引用，如下图
这时候，开始扫描对象D的引用，而此时，另一个goroutine修改了D->E的引用，变成了如下图所示
这样会不会导致E对象就扫描不到了，而被误认为 为白色对象，也就是垃圾
写屏障就是为了解决这样的问题，引入写屏障后，在上述步骤后，E会被认为是存活的，即使后面E被A对象抛弃，E会被在下一轮的GC中进行回收，这一轮GC中是不会对对象E进行回收的。
写屏障原理：在每一处内存写操作的前面，编译器会生成的一小段代码段，来确保不要打破一些约束条件。即在改变D->E的引用关系到A->E的时候，会有一小段代码，来禁止这个操作。这一小段代码就是一个约束条件，这个约束条件就是：黑色对象不能引用白色对象。
标记阶段：本来标记节点是需要STW，但是为了不STW，标记阶段与用户程序也做成了并发，并没有STW,标记协程是由多个MarkWorker goroutine 共同完成，它们在回收任务完成前绑定到 P，然后进入休眠状态，知道被调度器唤醒，他们与用户协程是并发执行的。
标记阶段与用户程序并发带来两个问题：
1.用户程序新建的对象。对于正在正在进行标记阶段，用户新建的对象可能不会被标记到。因此用户新建的对象直接认为是黑色的，本次标记不会标记到它，这样用户程序新建对象就没有问题了。
2.用户程序修改对象的引用关系。写屏障不允许黑色的对象直接引用白色的对象，当然写屏障并不是真的不让黑色对象引用白色对象，而是发⽣⼀个信号，垃圾回收器会捕获到这样的信号后就知道这个对象发⽣改变，然后重新扫描这个对象，看看它的引⽤或者被引⽤是否被改变，这样利⽤状态的重置从⽽实现当对象状态发⽣改变的时候依然可以判断它是活着的还是死的。
那标记阶段什么时候会STW呢？
清理阶段：不会STW，因为清理的是白色的对象，白色的对象不可能被用户程序用到，因此清理程序可以与用户程序并发执行，不需要STW。
并发清理本质上是一个死循环，被唤醒后开始执行清理任务。 通过遍历所有span 对象，触发内存回收器的回收操作。任务完成后，再次休眠，等待下次任务
总结一些GO 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)全局指针和栈。因为GC Drains阶段和用户程序是并行的，所以在GC Drains过程中可能会有新的对象分配和指针赋值，GC Drains就需要通过写屏障（write barrier）记录下来，re-scan 再检查一下，这个过程也是会STW的。
- Sweep: 按照标记结果回收所有的白色对象，该过程后台并行执行。
- Sweep Termination: 对未清扫的span进行清扫, 只有上一轮的GC的清扫工作完成才可以开始新一轮的GC。
总结一下，Golang的GC过程有两次STW:第一次STW会准备根对象的扫描, 启动写屏障(Write Barrier)和辅助GC(mutator assist)，为GC Drains阶段做准备.第二次STW会重新扫描部分根对象, 禁用写屏障(Write Barrier)和辅助GC(mutator assist)，因为GC Drains阶段已结束.
GO GC分成这么多阶段主要是为了让GC与用户程序并发执行。分成多个阶段，在必须STW的阶段才去STW，这样其他阶段就可以跟用户阶段并发执行了。
每一次STW耗时极小，一般在1ms以内。
2.2 GO GC触发的时间和条件
（1）触发的时间。在堆上分配大于 32K byte 对象的时候进行检测此时是否满足垃圾回收条件，如果满足则进行垃圾回收。
（2）触发的条件。
// gcShouldStart returns true if the exit condition for the _GCoff
// phase has been met. The exit condition should be tested when
// allocating.
//
// If forceTrigger is true, it ignores the current heap size, but
// checks all other conditions. In general this should be false.
func gcShouldStart(forceTrigger bool) bool {
return gcphase == _GCoff && (forceTrigger || memstats.heap_live >= memstats.gc_trigger) && memstats.enablegc && panicking == 0 && gcpercent >= 0
}forceTrigger 是 forceGC 的标志；后面半句的意思是当前堆上的活跃对象大于我们初始化时候设置的 GC 触发阈值。在 malloc 以及 free 的时候 heap_live 会一直进行更新。
3 GO GC调优
1.硬性参数
假设进程所占内存为reachable， 则reachable*(1+GOGC/100)=8M 的时候，gc 就会被触发，开始进行相关的 gc 操作。
因此可根据进程占用内存大小来调整GOGC参数，减少GC触发的次数
2.代码层面的tiops
(1)减少对象分配：所谓减少对象的分配，实际上是尽量做到，对象的重用。
例如下面两个函数：
func(r*Reader)Read()([]byte,error)
func(r*Reader)Read(buf[]byte)(int,error)第一个函数没有入参，因此第一个函数里面每次都会分配空间并返回；第二个函数有入参buf，因此在函数内部可利用传入的buf，不需要分配内存。
（2）少做string和[]byte转化。减少gc压力
（3）少使用字符串拼接。使用+进行字符串拼接会生成新的对象
（4）提前预知数组大小。数组初始化的时候一定要用make，及时大小是0，不过最好预估一下大小，这样在append的时候就不会经常去扩容
4 参考
【1】Go 垃圾回收
【2】Golang 垃圾回收剖析
【3】以标记清除的方式垃圾回收
【4】为什么 Go 在 GC 时 STW 的时间很短？
【5】垃圾回收算法（计数、标记、复制），golang垃圾回收
【6】Golang源码探索(三) GC的实现原理
【7】深入理解Go-垃圾回收机制
【8】java垃圾回收之复制算法
