在java的gc中，主要有三种算法，即：标记-删除，标记-整理，复制，网上有很多资料介绍相关内容，其中标记主要是为了找到内存中不可达的对象，并将其回收。而gc过程中最关键的指标就是STW时间，如果STW过长，会影响整体程序的响应。
Serial
采用单一线程进行GC。
特点：STW时间长，但是无线程切换开销，简单高效
ParNew
与Serial一样，只是在新生代采用并发gc
CMS
CMS收集器主要用于老年代内存的回收，致力于降低STW时间，但是却拉长了gc的整体时间。
- 对CPU资源非常敏感，可能会导致应用程序变慢，吞吐率下降。
- 无法处理浮动垃圾，因为在并发清理阶段用户线程还在运行，自然就会产生新的垃圾，而在此次收集中无法收集他们，只能留到下次收集，这部分垃圾为浮动垃圾，同时，由于用户线程并发执行，所以需要预留一部分老年代空间提供并发收集时程序运行使用。
- 由于采用的标记 - 清除算法，会产生大量的内存碎片，不利于大对象的分配，可能会提前触发一次Full GC。虚拟机提供了-XX:+UseCMSCompactAtFullCollection参数来进行碎片的合并整理过程，这样会使得停顿时间变长，虚拟机还提供了一个参数配置，-XX:+CMSFullGCsBeforeCompaction，用于设置执行多少次不压缩的Full GC后，接着来一次带压缩的GC
G1
G1回收器是目前用的比较前沿的回收策略，通过冗余一定量的Survivor空间来提升复制的效率以及减少内存碎片，其也是像CMS一样通过并发标记。
gc in golang
golang1.5也引入了标记清除的回收算法，为了达到更好的并发清除效果，其设计了一个三原色回收法，具体回收过程见文章
其基本思路就是：(开始时所有对象都被标为白色(可被回收))
- STW，将所有栈及global变量标为灰色 (Stack scan)
- 从灰色对象开始并发标记所有可达对象，将可达对象标为灰色，当一个对象所有引用对象都被标为灰色后，该对象就被置为黑色。(Mark)
- 当所有对象都被标为黑色后，再进行一次STW，重新扫描栈和global未扫描过的对象。(Mark termination)
- 并发的清除所有白色对象。(Sweep)
看完这篇文章后，可能会有几个疑问：
- 在golang并发标记的同时，会有新对象创建出来，这些对象被标位白色，如果新的白色对象被黑色对象引用该怎处理？
- 在golang并发标记的同时，会有指针的重指向，如果一个黑色对象指向一个白色对象，而之前指向这个白色的对象的指针都被删除了该怎么处理？ （e.g: a(black)->b = c->d; c->d = null;）
原理
那么这里就需要引出三色原理：
- 强三色原理：黑色对象不会指向白色对象，所有的黑色对象都只能指向非白色对象就不会出现如上的情况，就不会出现以上的情况，这样所有的白色对象就不会被hiding，从而保证是安全的。
- 弱三色原理：所有黑色对象引用的白色对象，一定能被另外一个灰色对象引用，有了这个约束后，就算一个黑色对象hiding了白色对象，那么这个白色对象还是被其他灰色对象shade的。
这里hiding就是指不安全的指向，shade就是安全的保护指向，只要有这个shade的存在，就不会被误删除。
既然有了这个三色原理的理论保证，那么怎么实现这个理论呢？那么就引出了写屏障write barrier机制来保证在对象的重定向以及对象的创建时满足强三色或者弱三色原理。
写屏障 write barrier
所以这里就需要了解一下写屏障的概念。写屏障的目标就是要保障约束原理，写屏障的实现有很多模式，在golang1.7之前主要采用的是Dijkstra-style insertion write barrier [Dijkstra ‘78], 其伪码实现如下：
writePointer(slot, ptr):
shade(ptr)
*slot = ptr
其思路就是在进行指针的重定向时，将被指向的指针对象标记为灰色(shade it)，这样如果有新的对象被创建或者黑色对象指向白色对象时，目标对象就会标灰，从而满足了黑色对象不会指向白色对象的强三色约束。
由于将栈对象的写屏障实现比较困难，有较大损失（这个为啥难我也不知道0.0: 文档原文： In particular, it presents a trade-off for pointers on stacks: either writes to pointers on the stack must have write barriers, which is prohibitively expensive, or stacks must be permagrey. Go chooses the later, which means that many stacks must be re-scanned during STW，粗略原因应该是gorutine太多，不能太影响性能）。
因此对于栈中的元素需要一次STW来进行rescan，以确保栈指针所指向的对象不会被误删。
*c // c是栈上的指针。
c = b -> d; // 此时d还是**白色**， 而对于栈上的指针c是没有写屏障的
b -> d = null // 删除了所有d的所有堆对象的指向，这样d就没有被**shade**了，需要rescan栈来防止这种情况
eliminate rescan in golang 1.8
为了尽可能的缩短STW时间，golang将写屏障进行优化，以此来去掉rescan，缩短STW时间。
其提出了一种混合写屏障机制：hybrid write barrier that combines a Yuasa-style deletion write barrier [Yuasa '90] with a Dijkstra-style insertion write barrier [Dijkstra '78]，其伪码实现如下：
writePointer(slot, ptr):
shade(*slot)
if current stack is grey:
shade(ptr)
*slot = ptr
上述伪码实现中，需要保障一个前提就是新建对象都是标为黑色，这样如果栈中指针指向新创建的对象的话也不需要重新扫描栈，因为已经标记为黑色，但是会出现如下情况：
{
... // B is already created
A *a = new A(); // *a is colored in black
a = b->c; // c is white, but there is no WB for a(stack pointer).
b->c = null;
}
显而易见：如果新建对象为黑色，而栈又没有写屏障保护，会打破黑色对象引用白色对象的约束，因此混合写保障了弱的三原色约束：Any white object pointed to by a black object is reachable from a grey object via a chain of white pointers (it is grey-protected). 所有黑色对象引用的白色对象，一定能被另外一个灰色对象引用，这样就算黑色对象hiding了白色对象，这个白色对象依旧被灰色对象shade着。
正确性证明
对于内存对象的操作主要包括四种基本情况：
- 栈指针重指向到了另一个堆指针对象；
- 栈指针重指向到了另一个栈指针对象；
- 堆指针重指向到了另一个堆指针对象；
4 堆指针重指向到了另一个栈指针对象；
所以我们只要能在上述四种情况下，保障弱三原色约束，就能证明该写屏障是可靠的：
最开始的混合写屏障实现如下：（后面再讨论为啥栈不是gray后，不需要shade了）
writePointer(slot, ptr):
shade(*slot)
shade(ptr)
*slot = ptr
对于情况1：
{
A *a = new A(); // in stack (black or gray)
a = b->c; // 栈操作没有写屏障，但是c对象依旧被b->p保护着
b->c = null; // b 不再引用c；此时写屏障中shade(*slot)会将c shade，因此是安全的。满足弱约束
}
对于情况2：
{
A *a = new A(); // in stack (black or gray)
B *b = new B(); // black
a = b; // 栈操作没有写屏障，但是栈对象已经是灰或者黑，不需要操作
}
对于情况3：
{
// a is black in heap
a->d = b->d; // 写屏障 shade(ptr) 依旧保护d对象
b->d = null; // shade(*slot) 与 shade(ptr) 效果一样
}
对于情况4：
{
// a is black in heap
D *d = new D(); // in stack (black or gray)
a->c = d; // 堆对象shade(*slot) 保护了 a->c指向的对象，依旧是安全的
}
综上所述，混合屏障可以实现弱三原色约束。
后来为了性能，又优化了一版：
writePointer(slot, ptr):
shade(*slot)
if current stack is grey: // 只有当栈中还存在灰色对象时才需要执行
shade(ptr)
*slot = ptr
为啥栈都标记为黑色后，不需要shade 被指对象
一个栈的所有对象被扫描为黑色后，栈对象的子对象要么是灰色的，要么子白色对象被另外一个灰色的堆对象引用着。所以栈对象此时不shade任何对象，那么所有的子对象都会被shade(*slot) 守护，也就不需要shade(ptr)了。
主要针对以下情况
其中A是栈对象，B是栈指针指向的堆对象，如果栈依旧是gray的，那么A shade的b对象就没法通过删除写屏障shade(*slot)保护起来，如上图，如果b对象如果不调用shade(prt)的话，如果A->b这一条链路被删除时，就不满足弱三色原理了，A是栈对象没有写屏障。如果当栈是black的之后，就不会有栈对象保护b了，那么对于b对象的引用就是安全的（其他堆对象的写屏障会保护它）。
综上所述：
shade(*slot) 用来满足灰色对象能保护其所有指向的对象约束。
shade(ptr) 当ptr对象是被栈对象保护时，由于对栈对象的指针操作是没有写屏障的，如果有对象被这个栈对象shade的时候，就需要插入写屏障shade(ptr)来保护。
