goroutine调度原理

goroutine即Go中的协程，是Go语言最大的特色之一，这篇文章将介绍goroutine的调度原理。

协程相对于线程的优势

协程可以理解为一种轻量级线程，与线程相比，协程不受操作系统的调度，其调度由用户层管理，即运行在用户态的Go协程调度器负责协程调度。线程虽说已经很轻量级，但是其有一个重大的缺点，即线程调度切换时需要陷入到内核态，再做线程切换。线程切换是一个非常频繁的动作，时刻都在发生：线程的时间片到了，需要让出CPU，此时线程切换；线程发起系统调用，比如read，因此先让出CPU，此时发生线程切换；线程的任务提前完成而时间片未到，此时线程切换。CPU看起来是100%跑满，但是实际上是80%在执行任务，而20%花销在线程切换上，实际CPU利用率只有80%。

正因为这一点，使得线程的调度成本始终还是太高了，毕竟线程切换的上下文开销很大。因此为了追求更好的效率，我们希望把调度直接放在用户态，因此协程就是基于这个思想而出现。协程的调度切换因为都是发生在用户态，因此协程的调度切换的消耗就很小了。

线程是系统调度的最小单位，操作系统调度线程是根据时间片来进行调度，假设每个线程的操作系统分配的时间片为0.1ms，即每个线程占有cpu最大时间为0.1ms，当该时间到了后，就会发生线程切换。如果时间片还没走完，但是线程发生了系统调用，如socket read，又或者是线程的任务提前完成，也会发生线程切换。当引入协程后，一般都是协程:协程 = N:M，假设这里N=3,M=1，即一个线程对应着三个可调度的协程，这三个协程共享线程的时间片，占用CPU。假设此时协程1完成了任务，但是线程时间片还没走完，则直接切换到协程2继续执行，协程2任务也执行完了，但线程时间片还未走完，继续执行协程3任务。如果此时线程时间片到了，协程3还未执行完，则由协程调度器保存现场，线程发生切换。因此我们从这个任务可以看出，对于这类任务执行时间短的场景（尤其是系统调用较多的场景，比如网络IO），协程很好地利用了操作系统资源，避免频繁的用户态和内核态的切换。

协程的轻量还体现在其占用的栈较小。每个系统线程都会有一个固定大小的栈，一般默认为8MB(ulimit -s查看)，这个栈主要用于保存函数调用递归时的参数和局部变量。这样的固定栈有两个弊端：一是2MB的占空间对于大多数线程而言是浪费的，很多线程运行时需空间远小于8MB。二是少数需要巨大栈空间的线程而言，这个8MB栈并不足够，会面临栈溢出的风险。goroutine解决了这两个问题：首先goroutine会以很小的栈启动，默认2KB。当面临栈空间不足时，goroutine会动态伸缩大小，比如栈的最大值可以去到1GB。因此，启动goroutine的代价很小，很轻量，我们可以很容易启动数万个goroutine为我们并发执行任务。

这里总结一下goroutine对比线程的优势：

• goroutine占用的空间更小。一个goroutine占用空间2KB，一个线程占用空间8MB，因此程序可以轻松开启10万个goroutine，占用内存空间仅仅为2KB*100000 = 200MB。同样的内存下，只能启动25个线程。
• goroutine调度运行在用户空间，切换时不需要陷入内核态，切换成本更低。

调度模型

goroutine调度模型包含3个实体：

• M（machine）:工作线程，由操作系统调度
• P（processer）:表面意思是处理器，但不是指CPU，而是一个抽象概念，个人认为P作用为M和G之间的代理人，即调度器，协调线程该如何执行协程。
• G（goroutine）：Go协程，每个go关键字都会创建一个协程

M必须持有P才能执行代码，M本质上是线程资源，因此也会跟系统其它线程一样被系统调用阻塞。P的个数是程序启动时确定的，默认情况下等于CPU核心数，也可以使用环境变量GMAXPROCS或者runtime.GMAXPROCS()来指定P的个数。M的个数通常稍大于P的个数，因为除了运行Go代码外，runtime包还有其它内置的任务需要处理，这些任务会占用一些线程资源。

一般而言，GOMAXPROCS设置为CPU核数，可以让程序充分利用CPU。但这个需要考虑场景来分析，比如IO密集型场景，每个协程执行的时间短，而等待系统调用返回的时间长，因此此时把MAXPROCS开得更大些反而性能更好；而CPU密集型场景，每个协程占用CPU的时间长，或者一个时间片内也完成不了协程的任务，此时就不应该把GOMAXPROCS设置过大，因为此时CPU负载很高，过大GOMAXPROCS意味着允许更多的协程在切换，这称为切换成本过大，得不偿失。

goroutine调度器实现了两种运行队列

• global runqueue（全局运行队列），所有P共享一个global runqueue
• local runqueue（P本地运行队列），每个P持有一个local runqueue，本地队列的长度不超过256。

调度策略

1. 当创建一个goroutine后，该G会优先放入P的本地运行队列，等待执行
2. 如果此时的P队列已满，则将G放入全局队列等待执行
3. M如果已经处理完自己的P队列里的任务后，会尝试从全局队列拉取G任务来执行
4. 如果此时全局队列仍然无任务可执行，则会尝试从其他P队列尾部获取可执行的任务，这称为工作量窃取。每次从其他P队列尾部窃取任务，每次窃取一半。
5. 当发生系统调用时，G会被阻塞，M会释放P，而原来的P队列将由新的M来接管，继续完成执行G的工作。这里接替的M的来源可以是缓存池中休眠的M，也可能是系统新创建出来的M，不过是先优先取缓存池的M，后考虑新建M。
6. 当被系统调用阻塞的G结束系统调用后，G需要被继续执行，此时需要找一个P完成接下来的工作，这里的策略是优先从空闲P池子里取出P来执行，若无空闲P，则将该G放如全部队列，等待调度执行。
7. Go 1.14版本支持了基于信号通知的抢占式调度。在此之前，Go的抢占式调度是基于函数调用间隙检查协程是否可以被抢占，这里有个问题，如果没有发生函数调用，就没法进行抢占了，如一个协程内的for循环for {}，因为这段逻辑没有调用函数，因此goroutine一直占用cpu，且不会被其他协程抢占，因此会无限期地占用执行权。1.14版本后，引入了基于信号的异步抢占机制，即对占用执行权时间过长的协程发送信号通知，收到信号的G就主动让出CPU，自己重新进入P队列等待下次调度。
8. G产生一个新G时，这个新G优先放在跟G相同的本地队列（局部性），之后再考虑放到其他的P队列，最后再考虑放到全局队列。