Golang垃圾回收

所谓垃圾回收，即释放我们不再使用对象的内存

三色标记法

要找出存活对象，根据可达性分析，从GC Roots开始进行遍历访问，可达的则为存活对象。我们把遍历对象图过程中遇到的对象，按“是否访问过”这个条件标记成以下三种颜色：

白色：尚未访问过。
黑色：本对象已访问过，而且本对象引用到的其他对象也全部访问过了。
灰色：本对象已访问过，但是本对象引用到的其他对象尚未全部访问完。全部访问后，会转换为黑色

一张图说明：

假设现在有白、灰、黑三个集合（表示当前对象的颜色），其遍历访问过程为：

初始时，所有对象都在【白色集合】中；
将GC Roots 直接引用到的对象挪到【灰色集合】中；
从灰色集合中获取对象：
1. 将本对象引用到的其他对象全部挪到【灰色集合】中；
2. 将本对象挪到【黑色集合】里面。
重复步骤3，直至【灰色集合】为空时结束。
结束后，仍在【白色集合】的对象即为GC Roots 不可达，可以进行回收。

当Stop The World 时，如果对象间的引用是不会发生变化的，可以轻松完成标记。而当需要支持并发标记时，即标记期间应用线程还在继续跑，对象间的引用可能发生变化，多标和漏标的情况就有可能发生。

问题1: 多标-浮动垃圾

如下图：

此刻之后，对象E/F/G是“应该”被回收的。然而因为E已经变为灰色了，其仍会被当作存活对象继续遍历下去。最终的结果是：这部分对象仍会被标记为存活，即本轮GC不会回收这部分内存。

这部分本应该回收但是没有回收到的内存，被称之为“浮动垃圾”。浮动垃圾并不会影响应用程序的正确性，只是需要等到下一轮垃圾回收中才被清除。

问题2: 漏标-读写屏障

假设GC线程已经遍历到E（变为灰色了），此时应用线程先执行了：

var G = objE.fieldG; 
objE.fieldG = null;  // 灰色E 断开引用 白色G 
objD.fieldG = G;  // 黑色D 引用 白色G

此时切回GC线程继续跑，因为E已经没有对G的引用了，所以不会将G放到灰色集合；尽管因为D重新引用了G，但因为D已经是黑色了，不会再重新做遍历处理。最终导致的结果是：G会一直停留在白色集合中，最后被当作垃圾进行清除。这直接影响到了应用程序的正确性，是不可接受的。

漏标发生条件：

灰色对象断开了白色对象的引用（直接或间接的引用）；即灰色对象原来成员变量的引用发生了变化。
黑色对象重新引用了该白色对象；即黑色对象成员变量增加了新的引用

从代码的角度看：

var G = objE.fieldG; // 1.读
objE.fieldG = null;  // 2.写
objD.fieldG = G;     // 3.写

读取对象E的成员变量fieldG的引用值，即对象G；对象E 往其成员变量fieldG，写入 null值。对象D 往其成员变量fieldG，写入对象G ；我们只要在上面这三步中的任意一步中做一些“手脚”，将对象G记录起来，然后作为灰色对象再进行遍历即可。比如放到一个特定的集合，等初始的GC Roots遍历完（并发标记），该集合的对象遍历即可（重新标记）

写屏障

给某个对象的成员变量赋值时，其底层代码大概长这样：

void oop_field_store(oop* field, oop new_value) {  
    pre_write_barrier(field); // 写屏障-写前操作
    *field = new_value; 
    post_write_barrier(field, value);  // 写屏障-写后操作
}

写屏障 + SATB

当对象E的成员变量的引用发生变化时（objE.fieldG = null;），我们可以利用写屏障，将E原来成员变量的引用对象G记录下来

void pre_write_barrier(oop* field) {
    if($gc_phase == GC_CONCURRENT_MARK && !isMarkd(field)) {
        oop old_value = *field; // 获取旧值
        remark_set.add(old_value); // 记录 原来的引用对象
    }
}

这种做法的思路是：尝试保留开始时的对象图，即原始快照（Snapshot At The Beginning，SATB），当某个时刻的GC Roots确定后，当时的对象图就已经确定了。比如当时 D是引用着G的，那后续的标记也应该是按照这个时刻的对象图走（D引用着G）。如果期间发生变化，则可以记录起来，保证标记依然按照原本的视图来。

值得一提的是，扫描所有GC Roots 这个操作（即初始标记）通常是需要STW的，否则有可能永远都扫不完，因为并发期间可能增加新的GC Roots。

SATB破坏了条件一：【灰色对象断开了白色对象的引用】，从而保证了不会漏标。

写屏障 + 增量更新

当对象D的成员变量的引用发生变化时（objD.fieldG = G;），我们可以利用写屏障，将D新的成员变量引用对象G记录下来

void post_write_barrier(oop* field, oop new_value) {
    if($gc_phase == GC_CONCURRENT_MARK && !isMarkd(field)) {  
        remark_set.add(new_value); // 记录新引用的对象
    }
}

这种做法的思路是：不要求保留原始快照，而是针对新增的引用，将其记录下来等待遍历（重新丢到灰色区），即增量更新

增量更新破坏了条件二：【黑色对象重新引用了该白色对象】，从而保证了不会漏标。

读屏障

读屏障是直接针对第一步：var G = objE.fieldG;，当读取成员变量时，一律记录下来：

if($gc_phase == GC_CONCURRENT_MARK && !isMarkd(field)) {
    oop old_value = *field;
    remark_set.add(old_value); // 记录读取到的对象
}

这种做法是保守的，但也是安全的。因为条件二中【黑色对象重新引用了该白色对象】，重新引用的前提是：得获取到该白色对象，此时已经读屏障就发挥作用了。

其他的垃圾回收策略

标记-清除法

思想大致如下：

先从根对象进行扫描，当我们的根对象指向了某个堆上的对象，我们就认为这个对象是可达的
可达对象指向的对象也是可达的
从根对象开始遍历（广度遍历或深度遍历）

步骤：

有触发垃圾回收的事件发生，一般是当申请堆内存的时候，做一个检测机制，或者定时回收
STW（Stop The World），挂起整个程序，等待GC
从根对象开始扫描，在堆上给每个可达的对象的header做一个活跃标记
清除阶段，扫描整个堆，发现是活跃对象的话，则清除掉它的标志位即可。如果发现是非活跃对象即不可达对象，则把对象作为分小块，连接到被称为 空闲链表 的单向链表。在之后进行分配时只要遍历这个空闲链表，就可以找到分块了。
清除完成，继续程序

优缺点：

思想简单，很好实现
缺点是会容易产生要多的碎片，分配的时候速度较低，分配需要遍历空闲链表，最坏的情况是遍历到最后也没有找到合适的
STW时间过长

引用计数法

思路：

给每一个对象都分配一个计数器，代表有多少其他的对象引用我
当没有对象再引用我的时候，就代表我是垃圾

步骤：

当对象A刚被创建的时候，肯定有一个对象B指向自己，所以对象A的计数器为1
当我们要更新一个指针的时候，原来引用对象的计数器-1，新引用对象的计数器+1
当遇到某个计数器为0的对象A时，我们要把所有引用了A的对象的计数器-1，同样的道理，如果引用了A的对象-1后可能也为0，需要递归地更新计数器

优缺点：

优点：不需要STW，回收过程分布在应用程序的运行中；垃圾会被立即回收
缺点：需要开发人员手动回收，容易内存泄露；无法回收循环引用的对象；递归更新计数器可能会非常深

分代收集

思路：

把堆分配的对象，给他分代，这种算法基于这样的认知，大部分对象创建后很快就变成垃圾，其余的就是很长时间才会变成垃圾，那么我们没必要对这种长时间才变成垃圾的对象进行GC，浪费时间

该算法把堆空间划分为四个部分，分别是生成空间，幸存空间1，幸存空间2，老年代空间。并且我们把前三者合并成为新生代空间。
当对象刚创建的时候，分配的空间就是在生成空间。
当生成空间满的时候，我们就对新生代空间进行GC，这里是是对整个新生代空间进行GC，采用的GC的算法就是节点复制。我们看图说话
我们每次GC的时候，都会对对象的“年龄”加1，当判断对象的年龄到达一定阈值的时候，就把对象移动到老年代空间
当我们对新生代对象进行GC的时候，是从新生代的根节点开始扫描，但是注意一有可能我们的老年代的对象也会指向新生代，所以如果我们把这点漏掉了，会多清除一些活跃的对象。为了解决这个问题，我们需要把老年代的对象扫描一遍，但是想想如果这样做的话我们岂不是每次要GC新生代对象的时候，都要把新、老都扫描了？
用一个记录集来记录那些老年代的对象指向新生代的情况。这样的话，当我们的GC新生代的时候，从根对象与记录集中就行，那么这个记录怎么做到呢，采用的写入屏障（write barrier）的方法
那么我们什么时候GC老年代对象的呢？当我们发现新生代的对象的年龄到了之后，要晋升为老年代对象的时候，会先检查老年代空间是否满了，满的话我们就开始老年代GC，老年代对象GC采用的就是标记清除的方法，注意这里应该是把整个堆都进行了GC

Golang垃圾回收#

三色标记法#

问题1: 多标-浮动垃圾#

问题2: 漏标-读写屏障#

写屏障#

其他的垃圾回收策略#

标记-清除法#

引用计数法#

分代收集#