go——协程调度

线程实现模型

Go实现的是两级线程模型(M︰ N)，准确的说是GMP模型，是对两级线程模型的改进实现，使它能够更加灵活地进行线程之间的调度。

背景

三种线程模型

线程实现模型主要分为:内核级线程模型、用户级线程模型、两级线程模型，他们的区别在于用户线程与内核线程之间的对应关系。

1.font<color =red >内核级线程模型（1:1)

1个用户线程对应1个内核线程，这种最容易实现，协程的调度都由CPU完成了

优点:
1.实现起来最简单
2.能够利用多核
3.如果进程中的一个线程被阻塞，不会阻塞其他线程，是能够切换同一进程内的其他线程继续执行
缺点︰
1.上下文切换成本高，创建、删除和切换都由CPU完成

**2.用户级线程N:1 **

优点:
1.上下文切换成本低，在用户态即可完成协程切换
缺点:
1.无法利用多核
2.一旦协程阻塞，造成线程阻塞，本线程的其它协程无法执行

两级线程模型(M：N)CMP

优点:
1.能够利用多核
2.上下文切换成本低
3.如果进程中的一个线程被阻塞，不会阻塞其他线程，是能够切换同一进程内的其他线程继续执行
缺点:
1.实现起来最复杂

---

GMP模型和GM模型

G(Goroutine)︰
代表Go协程Goroutine，存储了Goroutine的执行栈信息、Goroutine状态以及Goroutine的任务函数等。G的数量无限制，理论上只受内存的影响，创建一个G的初始栈大小为2-4K，配置一般的机器也能简简单单开启数十万个Goroutine，而且Go语言在G退出的时候还会把G清理之后放到P本地或者全局的闲置列表gFree中以便复用。

M(Machine):
Go对操作系统线程(OS thread)的封装，可以看作操作系统内核线程，想要在CPU上执行代码必须有线程，通过系统调用clone创建。M在绑定有效的P后，进入一个调度循环，而调度循环的机制大致是从P的本地运行队列以及全局队列中获取G，切换到G的执行栈上并执行G的函数，调用goexit 做清理工作并回到M，如此反复。M并不保留G状态，这是G可以跨M调度的基础。M的数量有限制，默认数量限制是10000，可以通过debug.SetMaxThreads()方法进行设置，如果有M空闲，那么就会回收或者睡眠。

(Processor)︰
虚拟处理器，M执行G所需要的资源和上下文，只有将Р和M绑定，才能让P的runq中的G真正运行起来。P的数量决定了系统内最大可并行的G的数量，P的数量受本机的CPU核数影响，可通过环境变量$GOMAXPROCS或在runtime.GOMAXPROCS()来设置，默认为CPU核心数。

Sched:
调度器结构，它维护有存储M和G的全局队列，以及调度器的一些状态信息

GMP模型的实现算是Go调度器的一大进步，但调度器仍然有一个令人头疼的问题，那就是不支持抢占式调度，这导致一旦某个G中出现死循环的代码逻辑，那么G将永久占用分配给它的Р和M，而位于同一个P中的其他G将得不到调度，出现"饿死"的情况。

当只有一个P(GOMAXPROCS=1)时，整个Go程序中的其他G都将"“饿死”。于是在Go 1.2版本中实现了基于协作的“抢占式"调度，在Go 1.14版本中实现了基于信号的“抢占式"调度。

GM模型：

GM调度存在的问题:
1.全局队列的锁竞争，当M从全局队列中添加或者获取G的时候，都需要获取队列锁，导致激烈的锁竞争 ⒉.M转移G增加额外开销，当M1在执行G1的时候，M1创建了G2，为了继续执行G1，需要把G2保存到全局队列中，无法保证G2是被M处理。因为M1原本就保存了G2的信息，所以G2最好是在M1上执行，这样的话也不需要转移G到全局队列和线程上下文切换
3.线程使用效率不能最大化，没有work-stealing和hand-off 机制

让P去管理这个G对象，M想要运行G，必须绑定P，才能运行Р所管理的G

---

go的调度原理

goroutine调度的本质就是将**Goroutine (G)**按照一定算法放到CPU上去执行。

CPU感知不到Goroutine，只知道内核线程，所以需要Go调度器将协程调度到内核线程上面去，然后操作系统调度器将内核线程放到CPU上去执行

M是对内核级线程的封装，所以Go调度器的工作就是将G分配到M

设计思想
1.线程复用(work stealing机制和hand off 机制)
2.利用并行(利用多核CPU)
3.抢占调度（解决公平性问题)

调度对象
Go调度器

Go调度器是属于Go runtime中的一部分，Go runtime负责实现Go的并发调度、垃圾回收、内存堆栈管理等关键功能

被调度对象

G的来源：

1.P的runnext(只有1个G，局部性原理，永远会被最先调度执行)
2.P的本地队列（数组，最多256个G)
3.全局G队列(链表，无限制)
4.网络轮询器network poller (存放网络调用被阻塞的G)

P的来源

1.全局P队列(数组，GOMAXPROCS个P)

M的来源

1.休眠线程队列(未绑定P，长时间休眠会等待GC回收销毁)·运行线程(绑定P，指向P中的G)
2.自旋线程(绑定P，指向M的GO)
其中运行线程数＋自旋线程数<=P的数量(GOMAXPROCS) ,M个数>=P个数

完整的调度周期图

调度时机：（什么时候进行切换/执行）

抢占式调度

sysmon检测到协程运行过久(比如sleep，死循环)

主动调度

1.新起一个协程和协程执行完毕
2.主动调用runtime.Gosched()
3.垃圾回收之后

被动调度

1.系统调用(比如文件lO)阻塞(同步)
2.网络IO调用阻塞(异步)
3.atomic/mutex/channel等阻塞(异步)

调度策略

由于P中的G分布在runnext、本地队列、全局队列、网络轮询器中，则需要挨个判断是否有可执行的G，大体逻辑如下:

1.每执行61次调度循环，从全局队列获取G，若有则直接返回
2.从P上的runnext看一下是否有G，若有则直接返回
3.从P上的本地队列看一下是否有G，若有则直接返回
4.上面都没查找到时，则去全局队列、网络轮询器查找或者从其他Р中窃取，一直阻塞直到获取到一个可用的G为止

---

work stealing机制

概念

当线程M无可运行的G时，尝试从其他M绑定的P偷取G，减少空转，提高了线程利用率（避免闲着不干活)。

当从本线程绑定Р本地队列、全局G队列、netpoller都找不到可执行的g，会从别的Р里窃取G并放到当前P上面。

从netpoller中拿到的G是_Gwaiting状态（存放的是因为网络IO被阻塞的G)，从其它地方拿到的G是_Grunnable状态

从全局队列取的G数量: N= min(len(GRQ)/GOMAXPROCS + 1, len(GRQ/2))(根据GOMAXPROCS负载均衡)

从其它P本地队列窃取的G数量:N= len(LRQ)/2(平分)

窃取流程

源码见runtime/proc.go stealWork函数，窃取流程如下，如果经过多次努力一直找不到需要运行的goroutine则调用stopm进入睡眠状态,等待被其它工作线程唤醒。

1.选择要窃取的P
2.从P中偷走一半G

选择要窃取的P

窃取的实质就是遍历allp中的所有p，查看其运行队列是否有goroutine，如果有，则取其一半到当前工作线程的运行队列

为了保证公平性，遍历allp时并不是固定的从allp[0]即第一个p开始，而是从随机位置上的p开始，而且遍历的顺序也随机化了，并不是现在访问了第i个p下一次就访问第i+1个p，而是使用了一种伪随机的方式遍历allp中的每个p,防止每次遍历时使用同样的顺序访问allp中的元素

---

hand off

概念
也称为P分离机制，当本线程M因为G进行的系统调用阻塞时，线程释放绑定的P，把Р转移给其他空闲的M执行，也提高了线程利用率（避免站着茅坑不拉shi)。

分离流程
当前线程M阻塞时，释放P.给其它空闲的M处理

---

go抢占式调度

在1.2版本之前，Go的调度器仍然不支持抢占式调度，程序只能依靠Goroutine主动让出CPU资源才能触发调度，这会引发一些问题，比如:

1.某些Goroutine可以长时间占用线程，造成其它Goroutine的饥饿
2.垃圾回收器是需要stop the world的，如果垃圾回收器想要运行了，那么它必须先通知其它的goroutine停下来，这会造成较长时间的等待时间

为解决这个问题:
1.Go 1.2中实现了基于协作的"抢占式"调度.
2.Go 1.14中实现了基于信号的"抢占式"调度

基于协作的抢占式调度：

协作式︰
大家都按事先定义好的规则来，比如:一个goroutine执行完后，退出，让出p，然后下一个goroutine被调度到p上运行。这样做的缺点就在于是否让出p的决定权在groutine自身。一旦某个g不主动让出p或执行时间较长，那么后面的goroutine只能等着，没有方法让前者让出p，导致延迟甚至饿死。

非协作式:
就是由runtime来决定一个goroutine运行多长时间，如果你不主动让出，对不起，我有手段可以抢占你，把你踢出去，让后面的goroutine进来运行。

基于协作的抢占式调度流程:

1.编译器会在调用函数前插入runtime.morestack，让运行时有机会在这段代码中检查是否需要执行抢占调度
2.Go语言运行时会在垃圾回收暂停程序、系统监控发现Goroutine运行超过10ms，那么会在这个协程设置一个抢占标记
3.当发生函数调用时，可能会执行编译器插入的runtime.morestack，它调用的runtime.newstack会检查抢占标记，如果有抢占标记就会触发抢占让出cpu，切到调度主协程里

这种解决方案只能说局部解决了"饿死"问题，只在有函数调用的地方才能插入"抢占"代码（埋点)，对于没有函数调用而是纯算法循环计算的G，Go调度器依然无法抢占。（死for循环没法抢占！！！！！！！！！！）

为了增加对非协作的抢占式调度的支持，延伸出了基于信号的抢占式调度

真正的抢占式调度是基于信号完成的，所以也称为“异步抢占"。不管协程有没有意愿主动让出cpu运行权，只要某个协程执行时间过长，就会发送信号强行夺取cpu运行权。

1.M注册一个SIGURG信号的处理函数:sighandler
2.sysmon启动后会间隔性的进行监控，最长间隔10ms，最短间隔20us。如果发现某协程独占 P超过10ms，会给M发送抢占信号
3.M收到信号后，内核执行sighandler函数把当前协程的状态从_Grunning正在执行改成_Grunnable可执行，把抢占的协程放到全局队列里，M继续寻找其他goroutine来运行
4.被抢占的G再次调度过来执行时，会继续原来的执行流

抢占分为_Prunning 和_Psyscall，_Psyscall抢占通常是由于阻塞性系统调用引起的，比如磁盘io、cgo。_Prunning抢占通常是由于一些类似死循环的计算逻辑引起的。

---

如何查看运行时的调度信息

有2种方式可以查看一个程序的调度GMP信息，分别是go tool trace和GODEBUG