标记-清除（mark & sweep）

标记-清除算法是第一种自动内存管理，基于追踪的垃圾收集算法。算法思想在 70 年代就提出了，是一种非常古老的算法。内存单元并不会在变成垃圾立刻回收，而是保持不可达状态，直到到达某个阈值或者固定时间长度。这个时候系统会挂起用户程序，也就是 STW，转而执行垃圾回收程序。 垃圾回收程序对所有的存活单元进行一次全局遍历确定哪些单元可以回收。算法分两个部分：标记（mark）和清除（sweep）。标记阶段表明所有的存活单元，清除阶段将垃圾单元回收。

标记-清除算法的优点也就是基于追踪的垃圾回收算法具有的优点：避免了引用计数算法的缺点（不能处理循环引用，需要维护指针）。缺点也很明显，需要 STW。

三色标记算法是对标记阶段的改进，原理如下：

• 起初所有对象都是白色。
• 从根出发扫描所有可达对象，标记为灰色，放入待处理队列。
• 从队列取出灰色对象，将其引用对象标记为灰色放入队列，自身标记为黑色。
• 重复 3，直到灰色对象队列为空。此时白色对象即为垃圾，进行回收。

三色法标记主要是第一部分是扫描所有对象进行三色标记，标记为黑色、灰色和白色，标记完成后只有黑色和白色对象，黑色代表使用中对象，白色对象代表垃圾，灰色是白色过渡到黑色的中间临时状态，第二部分是清扫垃圾，即清理白色对象。

第一部分包含了栈扫描、标记和标记结束3个阶段。在栈扫描之前有2个重要的准备：STW（Stop The World）和开启写屏障（WB，Write Barrier）。

STW是Stop The World，指会暂停所有正在执行的用户线程/协程，进行垃圾回收的操作，在这之前会进行一些准备工作，比如开启Write Barrier，把全局变量，以及每个goroutine中的 Root对象 收集起来，Root对象是标记扫描的源头，可以从Root对象依次索引到使用中的对象,STW为垃圾对象的扫描和标记提供了必要的条件。

每个P都有一个 mcache ，每个 mcache 都有1个Span用来存放 TinyObject，TinyObject 都是不包含指针的对象，所以这些对象可以直接标记为黑色，然后关闭 STW。

每个P都有1个进行扫描标记的 goroutine，可以进行并发标记，关闭STW后，这些 goroutine 就变成可运行状态，接收 Go Scheduler 的调度，被调度时执行1轮标记，它负责第1部分任务：栈扫描、标记和标记结束。

栈扫描阶段就是把前面搜集的Root对象找出来，标记为黑色，然后把它们引用的对象也找出来，标记为灰色，并且加入到gcWork队列，gcWork队列保存了灰色的对象，每个灰色的对象都是一个Work。

后面可以进入标记阶段，它是一个循环，不断的从gcWork队列中取出work，所指向的对象标记为黑色，该对象指向的对象标记为灰色，然后加入队列，直到队列为空。 然后进入标记结束阶段，再次开启STW，不同的版本处理方式是不同的。

在Go1.7的版本是Dijkstra写屏障，这个写屏障只监控堆上指针数据的变动，由于成本原因，没有监控栈上指针的变动，由于应用goroutine和GC的标记goroutine都在运行，当栈上的指针指向的对象变更为白色对象时，这个白色对象应当标记为黑色，需要再次扫描全局变量和栈，以免释放这类不该释放的对象。

在Go1.8及以后的版本引入了混合写屏障，这个写屏障依然不监控栈上指针的变动，但是它的策略，使得无需再次扫描栈和全局变量，但依然需要STW然后进行一些检查。

标记结束阶段的最后会关闭写屏障，然后关闭STW，唤醒熟睡已久的负责清扫垃圾的goroutine。

清扫goroutine是应用启动后立即创建的一个后台goroutine，它会立刻进入睡眠，等待被唤醒，然后执行垃圾清理：把白色对象挨个清理掉，清扫goroutine和应用goroutine是并发进行的。清扫完成之后，它再次进入睡眠状态，等待下次被唤醒。

最后执行一些数据统计和状态修改的工作，并且设置好触发下一轮GC的阈值，把GC状态设置为Off。

这写基本是Go垃圾回收的流程，但是在go1.12的源码稍微有一些不同，例如在标记结束后，就开始设置各种状态数据以及把GC状态成了Off，在开启一轮GC时，会自动检测当前是否处于Off，如果不是Off，则当前goroutine会调用清扫函数，帮助清扫goroutine一起清扫span，实际的Go垃圾回收流程以源码为准。

这里需要提下go的对象大小定义:

• 大对象是大于32KB的.
• 小对象16KB到32KB的.
• Tiny对象指大小在1Byte到16Byte之间并且不包含指针的对象.

三色标记的一个明显好处是能够让用户程序和 mark 并发的进行.