sysmon
为什么抢占式调度很重要
随着Go的一步步发展，它的调度器部分的实现也越来越好了。goroutine以前是严格意义上的coroutine，也就是协程。用户负责让各个goroutine交互合作完成任务。一个goroutine只有在涉及到加锁，读写通道等操作才会触发gorouine的yield。
Go语言的垃圾回收器是stoptheworld的。如果垃圾回收器想要运行了，那么它必须先通知其它的goroutine合作停下来。这会造成较长时间的垃圾回收等待时间。我们考虑一种很极端的情况，其它的goroutine都停下来了，除了有一个没有停，那么垃圾回收就会一直等待。
抢占式调度可以解决这种问题，在抢占式情况下，不停goroutine是否合作，它都会被yield。
引入抢占式调度，会对最初的设计产生比较大的影响，因此到目前(1.2 alpha)为止Go还只是引入了一些很初级的抢占，并没有像操作系统调度那么复杂，没有对goroutine分时间片，设置优先级等。
只有长时间阻塞于系统调用，或者运行了较长时间才会被抢占。runtime会在后台有一个检测线程，它会检测这些情况，并通知goroutine执行调度。
目前并没有直接在后台的检测线程中做处理调度器相关逻辑，只是相当于给goroutine加了一个“标记”，然后在它进入函数时才会触发调度。这么做应该是出于对现有代码的修改最小的考虑。
sysmon
前面讲Go程序的初始化过程中有提到过，runtime开了一条后台线程，运行一个sysmon函数。这个函数会周期性地做epoll操作，同时它还会检测每个P是否运行了较长时间。
如果检测到某个P状态处于Psyscall超过了一个sysmon的时间周期(20us)，并且还有其它可运行的任务，则切换P。
如果检测到某个P的状态为Prunning，并且它已经运行了超过10ms，则会将P的当前的G的stackguard设置为StackPreempt。这个操作其实是相当于加上一个标记，通知这个G在合适时机进行调度。
目前这里只是尽最大努力送达，但并不保证收到消息的goroutine一定会执行调度让出运行权。
morestack的修改
前面说的，将stackguard设置为StackPreempt实际上是一个比较trick的代码。我们知道Go使用的是分段栈，它会在每个函数入口处比较当前的栈寄存器值和stackguard值来决定是否触发morestack函数。
将stackguard设置为StackPreempt作用是进入函数时必定触发morestack，然后在morestack中再引发调度。
看一下StackPreempt的定义，它是大于任何实际的栈寄存器的值的：
// 0xfffffade in hex.
#define StackPreempt ((uint64)-1314)
然后在morestack中加了一小段代码，如果发现stackguard为StackPreempt，则相当于调用runtime.Gosched。
所以，到目前为止Go的抢占式调度还是很初级的，比如一个goroutine运行了很久，但是它并没有调用另一个函数，则它不会被抢占。当然，一个运行很久却不调用函数的代码并不是多数情况。
我们知道golang是善于做的是服务端开发，大家写的服务端程序或多或少会有这些 network io, channel, disk io, sleep 调用什么的。这些的操作都会导致M跟G的解绑，并且M重新的获取可用G的调度。golang很多的syscall调用之前也会做一些解绑操作。也就是说，golang在正常的场景下似乎很难出现 同一组 MPG 长时间绑定的情况。另外，就算出现mpg长时间绑定运行，sysmon也会帮你做抢占，不管你是Psyscall, 还是Prunning状态。
sysmon retake() 是怎么抢占的？
起初runtime.main会创建一个额外的M运行sysmon函数, 抢占就是在sysmon中实现的. sysmon会进入一个无限循环, 第一轮回休眠20us, 之后每次休眠时间倍增, 最大不会超过10ms. sysmon中有netpool(获取fd事件), retake(抢占), forcegc(按时间强制执行gc), scavenge heap等处理. 这里只说 retake 抢占。
Sysmon会调用retake()函数，retake()函数会遍历所有的P，如果一个P处于Psyscall状态，会被调用handoffp来解绑MP关系。 如果处于Prunning执行状态，一直执行某个G且已经连续执行了 > 10ms的时间，就会被抢占。retake()调用preemptone()将P的stackguard0设为stackPreempt，这将导致该P中正在执行的G进行下一次函数调用时， 导致栈空间检查失败。进而触发morestack()然后进行一连串的函数调用，主要的调用过程如下：
xiaorui.cc
morestack()（汇编代码）-> newstack() -> gopreempt_m() -> goschedImpl() -> schedule()
1
2
3
xiaorui.cc
morestack()（汇编代码）-> newstack() -> gopreempt_m() -> goschedImpl() -> schedule()
golang的PMG怎么可能会一直处于Prunning状态，一般来说只有cpu密集场景才会吧…. （废话）
测试一把cpu密集场景
我先写了一个看起来是协程调度饥饿的例子。 为了高度模拟cpu密集的场景，脚本的逻辑很简单，spawn了10w个协程，每个协程不断的在循环计数, 协程初次和结束都会做一个atomic计数，好让监控协程支持大家都有被调度到。 当监控协程检测到大家都有被触发时, 退出.
另外，runtime.GOMAXPROCS为什么设置为 3 ? 运行的阿里云机器是 4core, procs设为3，在cpu密集场景下应该是cpu 300%. sysmon是在一个独立出一个M也就是线程去执行，这样避免了4个core下cpu 400%的情况下，在满荷载下ssh登陆都是个问题，导致无法进行其他操作。
xiaorui.cc
package main
import (
“fmt”
// “net/http”
“os”
“runtime”
“sync”
“sync/atomic”
“time”
)
var (
startIncr int32
endIncr int32
)
const goCount = 100000
const plusCount = 10000
const callCount = 1000
func IncrCounter(num *int32) {
atomic.AddInt32(num, 1)
}
func LoadCounter(num *int32) int32 {
return atomic.LoadInt32(num)
}
func DecrCounter(num *int32) {
atomic.AddInt32(num, -1)
}
func main() {
runtime.GOMAXPROCS(3)
var wg sync.WaitGroup
startT := time.Now()
go detect(&wg)
for i := 0; i < goCount; i++ {
wg.Add(1)
go work(i, &wg)
}
wg.Wait()
elapsed := time.Since(startT)
fmt.Println("all exit, time cost: ", elapsed) }
func detect(wg *sync.WaitGroup) {
defer wg.Done()
runtime.LockOSThread()
defer runtime.UnlockOSThread()
startT := time.Now()
for {
fmt.Println("time since: ", time.Since(startT))
fmt.Println("start incr: ", LoadCounter(&startIncr))
fmt.Println("end incr: ", LoadCounter(&endIncr))
fmt.Println()
if LoadCounter(&startIncr) == goCount && LoadCounter(&endIncr) == goCount {
fmt.Println("finish detect")
os.Exit(0)
break
}
time.Sleep(1 * time.Millisecond)
} }
func work(gid int, wg *sync.WaitGroup) {
defer wg.Done()
var first = true
var localCounter = 0
for {
if first == true {
IncrCounter(&startIncr)
// fmt.Printf("gid:%d#\n", gid)
}
for i := 0; i < plusCount; i++ {
localCounter += 1
}
if first == true {
IncrCounter(&endIncr)
// fmt.Printf("gid:%d#\n", gid)
first = false
}
} } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 # xiaorui.cc
package main
import (
“fmt”
// “net/http”
“os”
“runtime”
“sync”
“sync/atomic”
“time”
)
var (
startIncr int32
endIncr int32
)
const goCount = 100000
const plusCount = 10000
const callCount = 1000
func IncrCounter(num *int32) {
atomic.AddInt32(num, 1)
}
func LoadCounter(num *int32) int32 {
return atomic.LoadInt32(num)
}
func DecrCounter(num *int32) {
atomic.AddInt32(num, -1)
}
func main() {
runtime.GOMAXPROCS(3)
var wg sync.WaitGroup
startT := time.Now()
go detect(&wg)
for i := 0; i < goCount; i++ {
wg.Add(1)
go work(i, &wg)
}
wg.Wait()
elapsed := time.Since(startT)
fmt.Println("all exit, time cost: ", elapsed) }
func detect(wg *sync.WaitGroup) {
defer wg.Done()
runtime.LockOSThread()
defer runtime.UnlockOSThread()
startT := time.Now()
for {
fmt.Println("time since: ", time.Since(startT))
fmt.Println("start incr: ", LoadCounter(&startIncr))
fmt.Println("end incr: ", LoadCounter(&endIncr))
fmt.Println()
if LoadCounter(&startIncr) == goCount && LoadCounter(&endIncr) == goCount {
fmt.Println("finish detect")
os.Exit(0)
break
}
time.Sleep(1 * time.Millisecond)
} }
func work(gid int, wg *sync.WaitGroup) {
defer wg.Done()
var first = true
var localCounter = 0
for {
if first == true {
IncrCounter(&startIncr)
// fmt.Printf("gid:%d#\n", gid)
}
for i := 0; i < plusCount; i++ {
localCounter += 1
}
if first == true {
IncrCounter(&endIncr)
// fmt.Printf("gid:%d#\n", gid)
first = false
}
} } 我们先看下CPU使用情况，跟我们想象中的结果是一样的几乎到了cpu 300%
程序一直扔在tmux后台跑, 在等了两天之后，发现10w个协程中还有一些goroutine没有被调度到, 也就是说 程序一直还在运行着。 下面的截图是6个小时的cpu运行状态，因为监控系统存储误操作，清理了数据, 丢失了2天的图表。
为什么没有触发抢占?
为什么没有被触发？ golang runtime sysmon代码看起来是10ms会发生触发一次抢占请求, 当然，当M处于处于正在分配内存或者非抢占模式下或其他原因，可能会跳过这次抢占。 但，6个小时过去了，依然有一些协程没有被调度到，这是什么原因？
上面sysmon原理的时候有提过，retake会触发 morestack, 然后调用 newstack, 然后gopreempt_m会重置g的状态，扔到runq并且重新调度. 关键点是 morestack ? goroutine stack默认是2kb, 而然我们的goroutine被spawn之后，基本是自己玩自己的，没有调用其他的function, 那自然stack没啥变化了，所以说，没有发生抢占. runtime代码有说，morestack — > newstack才会真的触发抢占，我们加上一些有层次的函数调用, 让stack扩充不就行了。
使用了递归调用栈来迅速扩充stack大小。经过测试，下面的代码 在 2分钟 内 1w个协程都会被调度到的。
time since: 2m11.493924996s
finish detect
1
2
time since: 2m11.493924996s
finish detect
刚才不是10w个协程么，怎么又缩减1w了… 因为10w协程长时间没动静….. 可以说，go在cpu密集场景下，会产生协程饥饿调度的问题，单看我们的测试结果，所谓的饥饿调度还是有的。在几k的协程下没有看到饥饿调度现象, 几w的协程还有可以看出一定程度的饥饿。
另外， 在CPU密集场景下，你调度器去均衡调度、抢占有个屁用呀，来回切换也有调度器自身产生的cpu消耗，还不如老老实实的处理完。要么加机器，要么优化算法。
xiaorui.cc
func work(gid int, wg *sync.WaitGroup) {
defer wg.Done()
var first = true
var localCounter = 0
for {
if first == true {
IncrCounter(&startIncr)
// fmt.Printf("gid:%d#\n", gid)
}
for i := 0; i < plusCount; i++ {
localCounter += 1
}
if first == true {
IncrCounter(&endIncr)
// fmt.Printf("gid:%d#\n", gid)
first = false
// sysmon配合扩大函数调用栈来调度g.
curCount := 0
call1(&curCount)
}
} }
func call1(cur *int) {
if *cur > callCount {
return
}
*cur += 1
call2(cur)
}
func call2(cur *int) {
if *cur > callCount {
return
}
*cur += 1
call3(cur)
}
func call3(cur *int) {
if *cur > callCount {
return
}
*cur += 1
call1(cur)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
xiaorui.cc
func work(gid int, wg *sync.WaitGroup) {
defer wg.Done()
var first = true
var localCounter = 0
for {
if first == true {
IncrCounter(&startIncr)
// fmt.Printf("gid:%d#\n", gid)
}
for i := 0; i < plusCount; i++ {
localCounter += 1
}
if first == true {
IncrCounter(&endIncr)
// fmt.Printf("gid:%d#\n", gid)
first = false
// sysmon配合扩大函数调用栈来调度g.
curCount := 0
call1(&curCount)
}
} }
func call1(cur *int) {
if *cur > callCount {
return
}
*cur += 1
call2(cur)
}
func call2(cur *int) {
if *cur > callCount {
return
}
*cur += 1
call3(cur)
}
func call3(cur *int) {
if *cur > callCount {
return
}
*cur += 1
call1(cur)
}
讲道理，讲调度
先简单的描述下调度流程，首先空闲的M跟可用空闲的P绑定，然后从P的runq里获取可用的G, 当G长时间执行的时候，会被sysmon做retake()抢占，被中断的G会放到全局队列的尾部. P的runq和全局的runq应该存有fifo的特性，按道理来说，应该都会被调度到呀, 只是时间长短而已… 我这里多次尝试过使用go tool pprof 或者 go tool trace 来追踪来分析原因，但又因为测试模拟了cpu密集，导致cpu打满的，所以 pprof和trace根本就调度不出来。。。
正常场景下, 10w个协程的调度情况
文章开头时，有说过 ! 正常场景很难出现MPG长时间绑定的情况，那么我们再来模拟测试下golang在正常场景下的调度表现 ？
方法1， 在cpu密集里加入一个time.Sleep(), 后台会调用gopark.
time since: 1.2353259s
start incr: 100000
end incr: 100000
finish detect
1
2
3
4
5
time since: 1.2353259s
start incr: 100000
end incr: 100000
finish detect
第二个, 在每组计算完成后主动触发goshed
time since: 1.369199087s
start incr: 100000
end incr: 100000
finish detect
1
2
3
4
5
time since: 1.369199087s
start incr: 100000
end incr: 100000
finish detect
第三个, 触发一个网络io操作.
time since: 5.389349861s
start incr: 100000
end incr: 100000
finish detect
1
2
3
4
5
time since: 5.389349861s
start incr: 100000
end incr: 100000
finish detect
这三种方法在在一个合理的时间里， 10w个协程都被触发调度了. 具体的耗时时间大家可以自己测一把, 这跟机器的cpu hz是有直接关系的.
xiaorui.cc
func work(gid int, wg *sync.WaitGroup) {
defer wg.Done()
var first = true
var localCounter = 0
for {
if first == true {
IncrCounter(&startIncr)
// fmt.Printf("gid:%d#\n", gid)
}
for i := 0; i < plusCount; i++ {
localCounter += 1
}
if first == true {
IncrCounter(&endIncr)
// fmt.Printf("gid:%d#\n", gid)
first = false
}
// 第一种方法
// time.Sleep 会产生调度，被goPark.
// 1s
// time.Sleep(1 * time.Millisecond)
// 第二种方法
// 使用GoSched切换调度
// 1s
// runtime.Gosched()
// 第三种方法
// 我们常见的有网络io的场景.
// 5s
// http.Get("http://127.0.0.2/test")
} } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 # xiaorui.cc
func work(gid int, wg *sync.WaitGroup) {
defer wg.Done()
var first = true
var localCounter = 0
for {
if first == true {
IncrCounter(&startIncr)
// fmt.Printf("gid:%d#\n", gid)
}
for i := 0; i < plusCount; i++ {
localCounter += 1
}
if first == true {
IncrCounter(&endIncr)
// fmt.Printf("gid:%d#\n", gid)
first = false
}
// 第一种方法
// time.Sleep 会产生调度，被goPark.
// 1s
// time.Sleep(1 * time.Millisecond)
// 第二种方法
// 使用GoSched切换调度
// 1s
// runtime.Gosched()
// 第三种方法
// 我们常见的有网络io的场景.
// 5s
// http.Get("http://127.0.0.2/test")
} } 总结
这个所谓饥饿调度测试我承认有些无聊呀，也显得工作不饱和。实际工作中似乎除了机器学习，模型计算之外，似乎少有这样长时间cpu密集纯计算的场景了。但通过实验我们最少可以证明，golang retake抢占在 cpu密集场景下，上w 协程貌似不怎么管用 !
那么，在golang到底存不存在饥饿调度的问题？ 正常使用golang的场景下，不会出现协程饥饿调度的问题。 但cpu bound场景下，饥饿调度现象还是有的。当然这里的测试方法还有待商榷，也不算严谨。
调度器的三个基本对象： Golang 简称 Go，Go 的协程(goroutine) 和我们常见的线程(Thread)一样，拥有其调度器。
G (Goroutine)，代表协程，也就是每次代码中使用 go 关键词时候会创建的一个对象
M (Work Thread)，工作线程
P (Processor)，代表一个处理器，又称上下文
G-M-P三者的关系与特点：
每一个运行的 M 都必须绑定一个 P，线程M 创建后会去检查并执行G (goroutine)对象
每一个 P 保存着一个协程G 的队列
除了每个 P 自身保存的 G 的队列外，调度器还拥有一个全局的 G 队列
M 从队列中提取 G，并执行
P 的个数就是GOMAXPROCS（最大256），启动时固定的，一般不修改
M 的个数和 P 的个数不一定一样多（会有休眠的M 或 P不绑定M ）（最大10000）
P 是用一个全局数组（255）来保存的，并且维护着一个全局的 P 空闲链表
局部G队列与全局G队列的关系
全局G任务队列会和各个本地G任务队列按照一定的策略互相交换。没错，就是协程任务交换
G任务的执行顺序是，先从本地队列找，本地没有则从全局队列找
转移
局部与全局，全局G个数 / P个数
局部与局部，一次性转移一半
Gorutine从入队到执行
当我们创建一个G对象，就是 gorutine，它会加入到本地队列或者全局队列
如果还有空闲的P，则创建一个M 绑定该 P ，注意！这里，P 此前必须还没绑定过M 的，否则不满足空闲的条件。细节点：
先找到一个空闲的P，如果没有则直接返回
P 个数不会占用超过自己设定的cpu个数
P 在被 M 绑定后，就会初始化自己的 G 队列，此时是一个空队列
注意这里的一个点！
无论在哪个 M 中创建了一个 G，只要 P 有空闲的，就会引起新 M 的创建
不需考虑当前所在 M 中所绑的 P 的 G 队列是否已满
新创建的 M 所绑的 P 的初始化队列会从其他 G 队列中取任务过来
这里留下第一个问题：
如果一个G任务执行时间太长，它就会一直占用 M 线程，由于队列的G任务是顺序执行的，其它G任务就会阻塞，如何避免该情况发生？ –①
M 会启动一个底层线程，循环执行能找到的 G 任务。这里的寻找的 G 从下面几方面找：
当前 M 所绑的 P 队列中找
去别的 P 的队列中找
去全局 G 队列中找
G任务的执行顺序是，先从本地队列找，本地没有则从全局队列找
程序启动的时候，首先跑的是主线程，然后这个主线程会绑定第一个 P
入口 main 函数，其实是作为一个 goroutine 来执行
解答问题-①
协程的切换时间片是10ms，也就是说 goroutine 最多执行10ms就会被 M 切换到下一个 G。这个过程，又被称为 中断，挂起
原理：
go程序启动时会首先创建一个特殊的内核线程 sysmon，用来监控和管理，其内部是一个循环：
记录所有 P 的 G 任务的计数 schedtick，schedtick会在每执行一个G任务后递增
如果检查到 schedtick 一直没有递增，说明这个 P 一直在执行同一个 G 任务，如果超过10ms，就在这个G任务的栈信息里面加一个 tag 标记
然后这个 G 任务在执行的时候，如果遇到非内联函数调用，就会检查一次这个标记，然后中断自己，把自己加到队列末尾，执行下一个G
如果没有遇到非内联函数 调用的话，那就会一直执行这个G任务，直到它自己结束；如果是个死循环，并且 GOMAXPROCS=1 的话。那么一直只会只有一个 P 与一个 M，且队列中的其他 G 不会被执行！
例子，下面的这段代码，hello world 不会被输出
func main(){
runtime.GOMAXPROCS(1)
go func(){
fmt.Println(“hello world”)
// panic(“hello world”) // 强制观察输出
}()
go func(){
for {
// fmt.Println(“aaa”) // 非内联函数，这行注释打开，将导致 hello world 的输出
}
}()
select {}
}
中断后的恢复
中断的时候将寄存器里的栈信息，保存到自己的 G 对象里面
当再次轮到自己执行时，将自己保存的栈信息复制到寄存器里面，这样就接着上次之后运
GOMAXPROCS–性能调优
看完上面的内容，相信你已经知道，GOMAXPROCS 就是 go 中 runtime 包的一个函数。它设置了 P 的最多的个数。这也就直接导致了 M 最多的个数是多少，而 M 的个数就决定了各个 G 队列能同时被多少个 M 线程来进行调取执行！
故，我们一般将 GOMAXPROCS 的个数设置为 CPU 的核数，且需要注意的是：
go 1.5 版本之前的 GOMAXPROCS 默认是 1
go 1.5 版本之后的 GOMAXPROCS 默认是 Num of cpu
Golang 垃圾回收机制
- Golang GC 发展
Golang 从第一个版本以来，GC 一直是大家诟病最多的。但是每一个版本的发布基本都伴随着 GC 的改进。下面列出一些比较重要的改动。
v1.1 STW
v1.3 Mark STW, Sweep 并行
v1.5 三色标记法
v1.8 hybrid write barrier
- GC 算法简介
这一小节介绍三种经典的 GC 算法：
引用计数（reference counting）
标记-清扫（mark & sweep）
节点复制（Copying Garbage Collection）
分代收集（Generational Garbage Collection）
- 引用计数
引用计数的思想非常简单：每个单元维护一个域，保存其它单元指向它的引用数量（类似有向图的入度）。当引用数量为 0 时，将其回收。引用计数是渐进式的，能够将内存管理的开销分布到整个程序之中。C++ 的 share_ptr 使用的就是引用计算方法。
引用计数算法实现一般是把所有的单元放在一个单元池里，比如类似 free list。这样所有的单元就被串起来了，就可以进行引用计数了。新分配的单元计数值被设置为 1（注意不是 0，因为申请一般都说 ptr = new object 这种）。每次有一个指针被设为指向该单元时，该单元的计数值加 1；而每次删除某个指向它的指针时，它的计数值减 1。当其引用计数为 0 的时候，该单元会被进行回收。虽然这里说的比较简单，实现的时候还是有很多细节需要考虑，比如删除某个单元的时候，那么它指向的所有单元都需要对引用计数减 1。那么如果这个时候，发现其中某个指向的单元的引用计数又为 0，那么是递归的进行还是采用其他的策略呢？递归处理的话会导致系统颠簸。关于这些细节这里就不讨论了，可以参考文章后面的给的参考资料。
优点
渐进式。内存管理与用户程序的执行交织在一起，将 GC 的代价分散到整个程序。不像标记-清扫算法需要 STW (Stop The World，GC 的时候挂起用户程序)。
算法易于实现。
内存单元能够很快被回收。相比于其他垃圾回收算法，堆被耗尽或者达到某个阈值才会进行垃圾回收。
缺点
原始的引用计数不能处理循环引用。大概这是被诟病最多的缺点了。不过针对这个问题，也除了很多解决方案，比如强引用等。
维护引用计数降低运行效率。内存单元的更新删除等都需要维护相关的内存单元的引用计数，相比于一些追踪式的垃圾回收算法并不需要这些代价。
单元池 free list 实现的话不是 cache-friendly 的，这样会导致频繁的 cache miss，降低程序运行效率。
- 标记-清扫
标记-清扫算法是第一种自动内存管理，基于追踪的垃圾收集算法。算法思想在 70 年代就提出了，是一种非常古老的算法。内存单元并不会在变成垃圾立刻回收，而是保持不可达状态，直到到达某个阈值或者固定时间长度。这个时候系统会挂起用户程序，也就是 STW，转而执行垃圾回收程序。垃圾回收程序对所有的存活单元进行一次全局遍历确定哪些单元可以回收。算法分两个部分：标记（mark）和清扫（sweep）。标记阶段表明所有的存活单元，清扫阶段将垃圾单元回收。可视化可以参考下图。
标记-清扫算法
标记-清扫算法的优点也就是基于追踪的垃圾回收算法具有的优点：避免了引用计数算法的缺点（不能处理循环引用，需要维护指针）。缺点也很明显，需要 STW。
三色标记算法
三色标记算法是对标记阶段的改进，原理如下：
起初所有对象都是白色。
从根出发扫描所有可达对象，标记为灰色，放入待处理队列。
从队列取出灰色对象，将其引用对象标记为灰色放入队列，自身标记为黑色。
重复 3，直到灰色对象队列为空。此时白色对象即为垃圾，进行回收。
可视化如下。
三色标记算法
三色标记的一个明显好处是能够让用户程序和 mark 并发的进行，具体可以参考论文：《On-the-fly garbage collection: an exercise in cooperation.》。Golang 的 GC 实现也是基于这篇论文，后面再具体说明。
- 节点复制
节点复制也是基于追踪的算法。其将整个堆等分为两个半区（semi-space），一个包含现有数据，另一个包含已被废弃的数据。节点复制式垃圾收集从切换（flip）两个半区的角色开始，然后收集器在老的半区，也就是 Fromspace 中遍历存活的数据结构，在第一次访问某个单元时把它复制到新半区，也就是 Tospace 中去。在 Fromspace 中所有存活单元都被访问过之后，收集器在 Tospace 中建立一个存活数据结构的副本，用户程序可以重新开始运行了。
优点
所有存活的数据结构都缩并地排列在 Tospace 的底部，这样就不会存在内存碎片的问题。
获取新内存可以简单地通过递增自由空间指针来实现。
缺点
内存得不到充分利用，总有一半的内存空间处于浪费状态。
- 分代收集
基于追踪的垃圾回收算法（标记-清扫、节点复制）一个主要问题是在生命周期较长的对象上浪费时间（长生命周期的对象是不需要频繁扫描的）。同时，内存分配存在这么一个事实 “most object die young”。基于这两点，分代垃圾回收算法将对象按生命周期长短存放到堆上的两个（或者更多）区域，这些区域就是分代（generation）。对于新生代的区域的垃圾回收频率要明显高于老年代区域。
分配对象的时候从新生代里面分配，如果后面发现对象的生命周期较长，则将其移到老年代，这个过程叫做 promote。随着不断 promote，最后新生代的大小在整个堆的占用比例不会特别大。收集的时候集中主要精力在新生代就会相对来说效率更高，STW 时间也会更短。
优点
性能更优。
缺点
实现复杂
- Golang GC
7.1 Overview
在说 Golang 的具体垃圾回收流程时，我们先来看一下几个基本的问题。
1. 何时触发 GC
在堆上分配大于 32K byte 对象的时候进行检测此时是否满足垃圾回收条件，如果满足则进行垃圾回收。
View Code
上面是自动垃圾回收，还有一种是主动垃圾回收，通过调用 runtime.GC()，这是阻塞式的。
View Code
2. GC 触发条件
触发条件主要关注下面代码中的中间部分：forceTrigger || memstats.heap_live >= memstats.gc_trigger 。forceTrigger 是 forceGC 的标志；后面半句的意思是当前堆上的活跃对象大于我们初始化时候设置的 GC 触发阈值。在 malloc 以及 free 的时候 heap_live 会一直进行更新，这里就不再展开了。
View Code
3. 垃圾回收的主要流程
三色标记法，主要流程如下：
所有对象最开始都是白色。
从 root 开始找到所有可达对象，标记为灰色，放入待处理队列。
遍历灰色对象队列，将其引用对象标记为灰色放入待处理队列，自身标记为黑色。
处理完灰色对象队列，执行清扫工作。
详细的过程如下图所示，具体可参考 [9]。
关于上图有几点需要说明的是。
首先从 root 开始遍历，root 包括全局指针和 goroutine 栈上的指针。
mark 有两个过程。
从 root 开始遍历，标记为灰色。遍历灰色队列。
re-scan 全局指针和栈。因为 mark 和用户程序是并行的，所以在过程 1 的时候可能会有新的对象分配，这个时候就需要通过写屏障（write barrier）记录下来。re-scan 再完成检查一下。
Stop The World 有两个过程。
第一个是 GC 将要开始的时候，这个时候主要是一些准备工作，比如 enable write barrier。
第二个过程就是上面提到的 re-scan 过程。如果这个时候没有 stw，那么 mark 将无休止。
另外针对上图各个阶段对应 GCPhase 如下：
Off: _GCoff
Stack scan ~ Mark: _GCmark
Mark termination: _GCmarktermination
7.2 写屏障 (write barrier)
关于 write barrier，完全可以另外写成一篇文章，所以这里只简单介绍一下，这篇文章的重点还是 Golang 的 GC。垃圾回收中的 write barrier 可以理解为编译器在写操作时特意插入的一段代码，对应的还有 read barrier。
为什么需要 write barrier，很简单，对于和用户程序并发运行的垃圾回收算法，用户程序会一直修改内存，所以需要记录下来。
Golang 1.7 之前的 write barrier 使用的经典的 Dijkstra-style insertion write barrier [Dijkstra ‘78]， STW 的主要耗时就在 stack re-scan 的过程。自 1.8 之后采用一种混合的 write barrier 方式 （Yuasa-style deletion write barrier [Yuasa ‘90] 和 Dijkstra-style insertion write barrier [Dijkstra ‘78]）来避免 re-scan。具体的可以参考 17503-eliminate-rescan。
7.3 标记
下面的源码还是基于 go1.8rc3。这个版本的 GC 代码相比之前改动还是挺大的，我们下面尽量只关注主流程。垃圾回收的代码主要集中在函数 gcStart() 中。
View Code
1. STW phase 1
在 GC 开始之前的准备工作。
View Code
2. Mark
Mark 阶段是并行的运行，通过在后台一直运行 mark worker 来实现。
View Code
Mark 阶段的标记代码主要在函数 gcDrain() 中实现。
View Code
3. Mark termination (STW phase 2)
mark termination 阶段会 stop the world。函数实现在 gcMarkTermination()。1.8 版本已经不会再对 goroutine stack 进行 re-scan 了。细节有点多，这里不细说了。
View Code
7.4 清扫
清扫相对来说就简单很多了。
View Code
对于并行式清扫，在 GC 初始化的时候就会启动 bgsweep()，然后在后台一直循环。
View Code
不管是阻塞式还是并行式，都是通过 sweepone()函数来做清扫工作的。如果对于上篇文章 Golang 内存管理 熟悉的话，这个地方就很好理解。内存管理都是基于 span 的，mheap_ 是一个全局的变量，所有分配的对象都会记录在 mheap_ 中。在标记的时候，我们只要找到对对象对应的 span 进行标记，清扫的时候扫描 span，没有标记的 span 就可以回收了。
View Code
7.5 其他
1. gcWork
这里介绍一下任务队列，或者说灰色对象管理。每个 P 上都有一个 gcw 用来管理灰色对象（get 和 put），gcw 的结构就是 gcWork。gcWork 中的核心是 wbuf1 和 wbuf2，里面存储就是灰色对象，或者说是 work（下面就全部统一叫做 work）。
View Code
既然每个 P 上有一个 work buffer，那么是不是还有一个全局的 work list 呢？是的。通过在每个 P 上绑定一个 work buffer 的好处和 cache 一样，不需要加锁。
View Code
那么为什么使用两个 work buffer （wbuf1 和 wbuf2）呢？我下面举个例子。比如我现在要 get 一个 work 出来，先从 wbuf1 中取，wbuf1 为空的话则与 wbuf2 swap 再 get。在其他时间将 work buffer 中的 full 或者 empty buffer 移到 global 的 work 中。这样的好处在于，在 get 的时候去全局的 work 里面取（多个 goroutine 去取会有竞争）。这里有趣的是 global 的 work list 是 lock-free 的，通过原子操作 cas 等实现。下面列举几个函数看一下 gcWrok。
初始化。
View Code
put。
View Code
get。
View Code
2. forcegc
我们上面讲了两种 GC 触发方式：自动检测和用户主动调用。除此之后 Golang 本身还会对运行状态进行监控，如果超过两分钟没有 GC，则触发 GC。监控函数是 sysmon()，在主 goroutine 中启动。
复制代码
1 // The main goroutine
2 func main() {
3 …
4 systemstack(func() {
5 newm(sysmon, nil)
6 })
7 }
8 // Always runs without a P, so write barriers are not allowed.
9 func sysmon() {
10 …
11 for {
12 now := nanotime()
13 unixnow := unixnanotime()
14
15 lastgc := int64(atomic.Load64(&memstats.last_gc))
16 if gcphase == _GCoff && lastgc != 0 && unixnow-lastgc > forcegcperiod && atomic.Load(&forcegc.idle) != 0 {
17 lock(&forcegc.lock)
18 forcegc.idle = 0
19 forcegc.g.schedlink = 0
20 injectglist(forcegc.g) // 将 forcegc goroutine 加入 runnable queue
21 unlock(&forcegc.lock)
22 }
23 }
24 }
25
26 var forcegcperiod int64 = 2 * 60 *1e9 //两分钟
