一 Go调度器GPM分析

背景
- 单进程
  
  早起的操作系统是单核单任务执行，在进行进程调度时，会随着时间推移，CPU会进行调度，在一个时间段内执行一个进程，只有当一个进程执行完成之后，才能继续执行下一个进程。在一个时间段内，有且只有一个任务在被执行。每一个程序或者应用都是串行执行，执行效率低。
  
  于是产生了以下问题：
  
  单核执行，每次只能执行一个单一的流程；
  
  如果被执行的进程任务被阻塞，则会带来CPU的浪费；
  
  于是就有了后续的操作系统的并发操作，当CPU执行某个进程被阻塞时，CPU就会自动切换到其他等待执行的任务，并将挂起的任务的环境与上下文进行保存，这样可以继续执行其他的进程，避免了CPU的浪费与等待。
- 并行
  在多核操作系统中，同一时间、同一时刻多任务同时执行，每一个核都在同时进行任务的调度，每一个核的CPU同一时刻只有一个任务进行调度。
- 并发
  在一个CPU进行多任务调度时，会按照时间片进行轮询调度执行任务，在一个CPU调度的时间轴中，一个时间点下，有且只有一个任务被调用。
  
  在多进程或多线程的操作系统中，解决了单任务的阻塞现象。只要某个进程产生阻塞，则CPU自动切换到其他的进程或线程进行执行，这样，每个进程在宏观上就表现的同时在执行。但是也会存在很多的问题。
  
  不同进程之间的任务在CPU进行切换时，需要保存太多的系统资源以及上下文资源。进程的创建、切换、销毁都会占用过多的时间，如果进程的数量太多，则大部分的时间都浪费在进程之间的调度，缩短了进程的执行时间。
  
  在一个进程内，如果执行多线程，在os层线程的设计变得更加复杂，而且在同一个进程内的线程之间资源共享、锁的操作更加复杂。
  
  多进程、多线程的壁垒：
  
  高内存占用：开辟一个进程所占用的虚拟内存约4G（在32bit Os），开辟一个线程所需要占用的资源也要4M。
  
  高CPU调度消耗：大部分的操作都在进行多任务切换时系统资源的消耗。
- 协程 co-routine
  协程是依赖与os 线程之上的’’用户态’’的线程，即用户态多任务的方式。
  
  线程分为“内核态“线程和”用户态“线程，内核态线程，即os Thread，为CPU所识别的线程，由底层操
  
  作系统进行调用；用户态线程即协程，绑定在内核态线程之上。
  
  如上图所示：CPU所能调度的是内核态线程，由操作系统所调度。CPU识别不了用户态线程，CPU视野之内只识别内核态线程。用户态线程即co-routine。
协程模型
- 协程与内核态线程N:1模型
  
  如上图所示： N个协程绑定1个os Thread；
  
  优点：多任务的切换在用户态线程下完成，不会陷入到内核态。切换非常迅速方便。
  
  缺点：一个进程上所有协程都绑定在一个内核态线程上，没有充分的使用硬件多核CPU加速处理的力；一旦某个执行的协程出现了阻塞现象，则这个进程中其他的协程都没办法继续执行下去，丧失了并发的能力，阻塞瓶颈；
- 协程与内核态线程1:1模型
  1:1模型中，一个协程绑定一个线程，这样的模式和单线程其实没有太多的区别，协程的调度随着os thread的调度而调度，都是由CPU完成调度，也进行协程频繁的创建、切换与销毁，代价昂贵。
- 协程与内核态线程N:M模型
  M:N模型，故名思义，是多个协程和多个os Thread进行绑定。
  
  线程的调度是有CPU抢占式调度；协程的调度在用户态下通过协程调度器进行协作式调度，一个协程让出CPU之后，才会执行下一个协程；
  
  优点：能够充分的利用多核的特效，进行多任务的调度与处理；
  
  缺点：过于依赖协程调度器的优化与算法。
Go的协程goroutine
go中的协程，由co-routine改为goroutine，不仅仅是名字的更改，goroutine是用户态的线程，可以让一组可复用的函数运行在一组os Thread之上。即便协程出现阻塞，运行在该线程之上的其他协程也可以被runtime所调度，转移到其他可运行的线程上进行执行。goroutine非常的轻量，开辟一个协程只要几kb，并且几kb的资源就能将goroutine运行完成。

特点：

高并发：在有限的内存内，支持大量轻量级的goroutine，支持了更高的并发；

灵活调度：虽然在创建协程时分配的内存为几kb，但是如果业务需求，runtime会进行内存的扩充，伸缩调控，为goroutine进行内存分配。
GM调度器

G：goroutine协程

M：os Thread 内核态线程

说明:

一个进程内的有M1-M3个线程，每个线程要执行G或者放回G，必须要访问全局G队列。多线程对同一资源进行竞争时，会加锁对资源进行互斥与同步。所以，全局G队列是被锁进行保护。要想获取全局G队列中的goroutine，必须先获取锁，才能进行执行。

GM调度器缺陷：

创建、销毁、调度G都需要每个M获取锁，这就形成了激烈的锁竞争。

M转移G会造成延迟和额外的系统负载。比如当G中包含创建新协程的时候，M创建了G’，为了继续执行G，需要把G’交给M’执行，也造成了很差的局部性，因为G’和G是相关的，最好放在M上执行，而不是其他M’。系统调用(CPU在M之间的切换)导致频繁的线程阻塞和取消阻塞操作增加了系统开销。
GMP调度器
- 何为GPM
  面对之前调度器的问题，Go设计了新的调度器。在新调度器中，除了M(thread)和G(goroutine)，又引进了P(Processor)。
  
  G 代表一个Goroutine；
  
  M 代表一个操作系统的线程；
  
  P 代表一个CPU处理器，通常P的数量等于CPU核数（GOMAXPROCS）；
  
  其中：
  
  G协程时运行在os Thread线程之上；
  
  每一个要运行的线程，必须要和P（处理器）进行绑定，否则在全局线程队列中处理休眠状态，获取到P的线程分为执行线程、自旋线程。且程序中的多个M并不会同时都处于执行状态，最多只有GOMAXPROCS个线程在运行。
  
  Processor，它包含了运行goroutine的资源，如果线程想运行goroutine，必须先获取P，P中还包含了运行的G队列，叫做P的本地队列。
- GMP模型
  在Go中，线程是运行goroutine的实体，调度器的功能是把可运行的goroutine分配到工作线程上。
流程说明：

其一：多核操作系统的硬件CPU被操作系统调度器所进行调度，从而对内核态的线程进行调度与执行；这个是由操作系统所进行的调度；

其二：每一个线程要执行goroutine时，必须先要和调度器P进行绑定，此时P会和起一个队列，为P的本地队列，进行存储将要执行的G。如果本地队列达到设置限制数量，则会将本地队列中一半的G和新创建的G放入到全局G队列中，等待被其他的线程所绑定的P进行获取与调度。当然如果创建新的G时，如果当前线程所绑定的P本地队列没有满，则优先加入到P的本地队列中。

其三：P队列，当程序运行时就会创建P处理器，并存储在列表中，即P的全局队列，其最大的数量为GOMAXPROCS的个数，可以使用runtime进行配置，每个线程会去对P进行竞争获取；

其四：线程M想要运行，就先要从P队列中获取P，并与之进行绑定，然后优先执行P的本地队列中的任务；当本地P队列中G数量为空时，便优先从全局G列中获取 min(len(GQ)/GOMAXPROCS + 1, len(GQ)/2)个goroutine放入到本地队列中，有P的G0进行调度；如果全局G队列也是空，则会从别的P中偷取一半的G放入到本地队列中进行执行(从尾部偷取)；

其五：goroutine调度器和os调度器通过线程M结合，os调度器负责将M运行在CPU内核上，而goroutine调度器则负责将协程在线程上进行切换，降低了内核态对线程切换资源的开销与延迟。
- P与M数量问题
  P：P的数量是通过环境变量中 GOMAXPROCS或者runtime.GOMAXPROCS(num)进行设置；默认当前服务器最大CPU核数；
  
  M： go语言默认设置的最大线程数量为10000；当然可以有runtime/debug中的SetMaxThreads函数，设置M的最大数量；在实际运行过程中，当一个M阻塞时，将绑定的P-M进行解绑，然后先判断全局线程队列中是否存在空闲的M，如果没有，就会创建一个新的M。
- P与M的创建时机
  P何时创建：在确定了P的最大数量n后，运行时系统会根据这个数量创建n个P
  
  M何时创建：没有足够的M来关联P并运行其中的可运行的G。比如所有的M此时都阻塞住了，而P中还有很多就绪任务，就会去寻找空闲的M，而没有空闲的，就会去创建新的M。
GMP调度器调度策略
- 复用线程
  复用线程：避免频繁的创建、销毁线程，而是对线程的复用，降低系统开销；
  - work stealing
    当本线程所绑定的本地队列P为空时，并且全局G队列中也没有可运行的G，此时将会从其他线程所绑定的P中去偷取一半的G（向下取整）进行调度执行。
  - hand off
    当本地线程执行的G任务进行阻塞，此时就会将P与M进行解绑，如果P中存在待执行的G，则P会从全局线程队列中获取一个空闲的M与之绑定继续执行；
- 利用并行
  GOMAXPROCS设置P的数量，最多有GOMAXPROCS个线程分布在多个CPU上同时运行。GOMAXPROCS也限制了并发的程度，比如GOMAXPROCS = 核数/2，则最多利用了一半的CPU核进行并行。
- 抢占
  在coroutine中要等待一个协程主动让出CPU才执行下一个协程，在Go中，一个goroutine最多占用CPU 10ms，防止其他goroutine被饿死，这就是goroutine不同于coroutine的一个地方。
- 全局G队列
  在新的调度器中依然有全局G队列，但功能已经被弱化了，当M执行work stealing从其他P偷不到G时，它可以从全局G队列获取G。
调度流程分析
从上图我们可以分析出几个结论：

1、我们通过 go func()来创建一个goroutine；

2、有两个存储G的队列，一个是局部调度器P的本地队列、一个是全局G队列。新创建的G会先保存在P的本地队列中，如果P的本地队列已经满了就会保存在全局的队列中；

3、G只能运行在M中，一个M必须持有一个P，M与P是1：1的关系。M会从P的本地队列弹出一个可执行状态的G来执行，如果P的本地队列为空，就会想其他的MP组合偷取一个可执行的G来执行；

4、一个M调度G执行的过程是一个循环机制；

5、当M执行某一个G时候如果发生了syscall或则其余阻塞操作，M会阻塞，如果当前有一些G在执行，runtime会把这个线程M从P中摘除(detach)，然后再创建一个新的操作系统的线程(如果有空闲的线程可用就复用空闲线程)来服务于这个P；

6、当M系统调用结束时候，这个G会尝试获取一个空闲的P执行，并放入到这个P的本地队列。如果获取不到P，那么这个线程M变成休眠状态，加入到空闲线程中，然后这个G会被放入全局队列中。
调度生命周期

特殊的M0和G0

M0： M0是启动程序后的编号为0的主线程，这个M对应的实例会在全局变量runtime.m0中，不需要在heap上分配，M0负责执行初始化操作和启动第一个G，在之后M0就和其他的M一样了。

G0 ：G0是每次启动一个M都会第一个创建的gourtine，G0仅用于负责调度的G，G0不指向任何可执行的函数, 每个M都会有一个自己的G0。在调度或系统调用时会使用G0的栈空间, 全局变量的G0是M0的G0。

代码实战分析
1
2
3
4
5
6
7
package main

import "fmt"

func main() {
fmt.Println("Hello world")
}
接下来我们来针对上面的代码对调度器里面的结构做一个分析：

也会经历如上图所示的过程：

其一：runtime创建起始线程M0和goroutine G0，并把2者关联。

其二：调度器初始化：初始化M0、栈、GC，以及创建和初始化由GOMAXPROCS个P构成的P列表。示例代码中的main函数是main.main，runtime中也有1个main函数——runtime.main，代码经过编译后，runtime.main会调用main.main，程序启动时会为runtime.main创建goroutine，称它为main goroutin吧，然后把main goroutine加入到P的本地队列。

其三：启动M0，M0已经绑定了P，会从P的本地队列获取G，获取到main goroutine。

其四：G拥有栈，M根据G中的栈信息和调度信息设置运行环境 M运行G, 执行完协程后G退出，再次回到M。获取可运行的G，这样重复下去，直到main.main退出，runtime.main执行Defer和Panic处理，或调用runtime.exit退出程序。

其五：调度器的生命周期几乎占满了一个Go程序的一生，runtime.main的goroutine执行之前都是为调度器做准备工作，runtime.main的goroutine运行，才是调度器的真正开始，直到runtime.main结束而结束。

GPM可视化编程

使用go tool trace trace.out进行分析

trace记录了运行时的信息，并提供了web进行可视化追踪；

简单测试代码：main函数创建trace，trace会运行在单独的goroutine中，然后main打印”Hello World”退出。

trace.go

package main

import (
    "os"
    "fmt"
    "runtime/trace"
)

func main() {

    //创建trace文件
    f, err := os.Create("trace.out")
    if err != nil {
        panic(err)
    }

    defer f.Close()

    //启动trace goroutine
    err = trace.Start(f)
    if err != nil {
        panic(err)
    }
    defer trace.Stop()

    //main
    fmt.Println("Hello World")
}

运行程序会得到一个trace.out文件；

使用工具进行打开：

1	go tool trace trace.out

得到下列输出：

austsxkdeMacBook-Pro:tour austsxk$ go tool trace trace.out 
2020/08/19 21:53:01 Parsing trace...
2020/08/19 21:53:01 Splitting trace...
2020/08/19 21:53:01 Opening browser. Trace viewer is listening on http://127.0.0.1:57842

访问http://127.0.0.1:57842,可以得到下面界面：

trace首页

点击 View trace：

view trace

G 信息

点击 Goroutines 那一行可视化的数据条，我们会看到一些详细的信息。

一共有两个G在程序中，一个是特殊的G0，是每个M必须有的一个初始化的G，这个我们不必讨论。

其中 G1 应该就是 main goroutine (执行 main 函数的协程)，在一段时间内处于可运行和运行的状态。

M 信息

点击 Threads 那一行可视化的数据条，我们会看到一些详细的信息。

M信息

一共有两个 M 在程序中，一个是特殊的 M0，用于初始化使用，这个我们不必讨论。

P 信息

P信息

G1 中调用了 main.main，创建了 trace goroutine g18。G1 运行在 P1 上，G18 运行在 P0 上。

这里有两个 P，我们知道，一个 P 必须绑定一个 M 才能调度 G。

我们在来看看上面的 M 信息。

M内部信息

我们会发现，确实 G18 在 P0 上被运行的时候，确实在 Threads 行多了一个 M 的数据，点击查看如下：

多了一个 M2 应该就是 P0 为了执行 G18 而动态创建的 M2。

使用GODEBUG=schedtrace=时间段可执行文件

package main

import (
    "fmt"
    "time"
)

func main() {
    for i := 0; i < 5; i++ {
        time.Sleep(time.Second)
        fmt.Println("Hello World")
    }
}

执行go build trace2.go

得到一个可执行文件 trace2，然后进行GODEBUG运行

GODEBUG=schedtrace=1000 ./trace2 
SCHED 0ms: gomaxprocs=2 idleprocs=0 threads=4 spinningthreads=1 idlethreads=1 runqueue=0 [0 0]
Hello World
SCHED 1003ms: gomaxprocs=2 idleprocs=2 threads=4 spinningthreads=0 idlethreads=2 runqueue=0 [0 0]
Hello World
SCHED 2014ms: gomaxprocs=2 idleprocs=2 threads=4 spinningthreads=0 idlethreads=2 runqueue=0 [0 0]
Hello World
SCHED 3015ms: gomaxprocs=2 idleprocs=2 threads=4 spinningthreads=0 idlethreads=2 runqueue=0 [0 0]
Hello World
SCHED 4023ms: gomaxprocs=2 idleprocs=2 threads=4 spinningthreads=0 idlethreads=2 runqueue=0 [0 0]
Hello World

SCHED：调试信息输出标志字符串，代表本行是goroutine调度器的输出；

0ms：即从程序启动到输出这行日志的时间；

gomaxprocs: P的数量，本例有2个P, 因为默认的P的属性是和cpu核心数量默认一致，当然也可以通过GOMAXPROCS来设置；

idleprocs: 处于idle状态的P的数量；通过gomaxprocs和idleprocs的差值，我们就可知道执行go代码的P的数量；

threads: os threads/M的数量，包含scheduler使用的m数量，加上runtime自用的类似sysmon这样的thread的数量；

spinningthreads: 处于自旋状态的os thread数量；

idlethread: 处于idle状态的os thread的数量；

runqueue=0： Scheduler全局队列中G的数量；

[0 0]: 分别为2个P的local queue中的G的数量。

二 Go调度器调度场景分析

局部性（协程创建的子协程添加到当前绑定的P-M的本地队列）

当程序运行之后，P和M1进行绑定，P都是运行在绑定的M上；此时P的本地队列中有G1，正在进行运行，当G1运行中需要另起一个goroutine即G2时，使用go func() 创建，G2会优先添加到当前P-M所绑定的P本地队列。好处：子鞋程可能会共享资源，减少了资源复制以及上下文切换的CPU开销；即创建的些称会优先添加到与至向关的Processer中；
协程执行完毕（使用每个M所创建的G0进行goroutine切换）

如上图所描述：当G1执行完毕，M上运行的goroutine会先切换为G0，有G0统一负责调度协程切换(使用schedule进行调度),从本地队列P中获取goroutine,并开始执行协程(execute).从而实现了对os thread M1的重复使用.
子协程的创建数目大于P限定的最大协程数目(无限开辟goroutine)
1. 如果G2创建6个协程,但是设置了所绑定的本地队列最大存储的goroutine的数目为4个.则前4个按照创建的局部性进行创建,在P1的本地队列中添加4个协程;
2. G2还要继续创建协程G7,此时发现P1本地队列已经满了,则进行负载均衡, 则先将P1本地队列进行二分法,取出队头的一半,然后将任务和创建的G7打乱顺序,将其放入到全局队列中, P本地队列队尾的任务自动前移;
3. G2继续创建G8, 此时本地队列未满,将G8加入到本地队列P中;当时间轮询结束后,G2被加到本地队列中,等待调度;G8加入到P1点本地队列的原因还是因为P1此时在与M1绑定，而G2此时是M1在执行。所以G2创建的新的G会优先放置到自己的M绑定的P上。
创建G时唤醒自旋线程

在创建协程时，就会去唤醒os Thread Queue中的M，尝试去进行与空闲的Processer进行绑定，进行P-M组合。如果没有M，则不进行操作；如果全局队列中有M或者存在多个M，则取出M，队列中剩余的M前移，如果没有空闲的P，则返回队列中；当有空闲的P时，则进行绑定，绑定之后，就会产生G0调度协程进行初始化与调度；如果新绑定的P本地队列中没有goroutine，则线程一直处于等待状态，尝试work stealing 或从全局中获取待执行的任务；在此期间，G0在一直寻找任务，此时的线程为自旋线程。
GMP内部的负载均衡（被唤醒的线程从全局队列中获取G）

当P-M组合完成后，G0将会不断的去寻找执行的G，会优先从GQ(Global Queue)中获取批量的G，如果GQ中存在待执行的goroutine，则会采用负载均衡的算法进行计算需要取出的G的数量；

函数：findrunnable()

计算公式：n = min(len(GQ)/GOMAXPROCS + 1, len(GQ)/2)

其中GQ为全局队列中保存的G的数量， GOMAXPROCS为设置的P的最大使用核数，一般默认为当前最大核数，然后计算出二者最小值为从全局队列中获取的数量，将其放入新P-M组合中P的本地队列中，然后由G0进行调度执行；

全局队列中其他的G，向前移动；一般从全局队列中取出的G至少一个；
P本地队列和GQ皆为空时，从别地P中偷取G（M2从M1的本地队列中偷取goroutine）

当M2中的处理器P2将本地队列中的任务执行完毕后，并且此时全局队列也不存在G；此时M2将会执行work stealing 操作，从其他存在G的processer的本地队列中偷取一半的G，将其放在本地队列中；如上图所示，M2将从P1的尾部偷取一半的G（向下取整），即G8将被偷取存入到P2的本地队列中，然后又M2的G0进行调度执行;
进程中没有可运行的G，自旋线程的最大数目(即GOMAXPROCS)

当进程中所有的线程M所绑定的P处理器本地队列中没有G，同时全局队列中无待执行的G时，此时进程中将会存在GOMAXPROCS数量个线程处于自旋状态；其他产生的线程将会保存在全局线程队列中处于休眠状态，等待下次被调度唤醒进行任务绑定；

如上图所示：当M1线程执行完G2， M2线程执行完G8，M1-M4都会处于自旋状态，配置GOMAXPROCS的数目为4；所以他们都会处于自旋状态，一直去寻找可以调度的G；自旋的本质其实是一直处于运行状态，只是没有执行G而已，其实也在浪费CPU资源。

不销毁这些自旋的线程的原因：在创建和销毁线程是很耗费CPU资源，也浪费时间；但是当新的goroutine被创建时，可以立刻有M进行执行，这样提高了执行的速率；如果之前销毁了线程，则新的goroutine被创建后，则需要重新创建M，并进行初始化G0等一系列初始化操作，增加了执行了时间，降低了执行的效率；所以这里采用了用空间替换时间，也只保留GOMAXPROCS个自旋线程，降低了过多线程对资源的消耗。
Goroutine调度与阻塞

如上图所示：系统中配置的最大处理器为4，此时M1线程正在执行G2， M2线程正在执行G8，G8协程在运行中产生G9，按局部原则，生成的G9优先加入到M2绑定的P2的本地队列中等待M2的G0进行调度；系统中M3和M4无任务执行，GQ中也无goroutine；此时M3和M4处于自旋状态或者将stealing 别的可用的P中的G；（进程运行中M数量远远大于P数量，M往往需要抢占调度P）

此处我们说的是当G9创建时，G8立马发生了阻塞了系统的调用；此时M2-P2将进行解绑；并且P2会进行一系列的判断：

如果P2本地队列有G，全局队列GQ中有G或者有空闲的M，那么P2将立马唤醒一个M与之绑定，并初始化G0，进行任务的调度；

如果P2没有G，那么P2将会添加到全局的P队列中，等待需要P的M取全局P队列中抢占P；

上图中，P2的本地队列中存在G9，则将会把P2-M2进行解绑，将从全局线程队列中获取M5并进行M5-P2的绑定，然后进行任务的调度；
M-P记忆（M会记录曾经绑定的P）

如上图所示：

M2线程正在执行G8，G8创建了协程G9，此时G8发生了阻塞；

M2-P2将会进行解绑；P2队列存在G9，所以P2将会和os 线程队列中的M进行绑定，但是此时M2将会记录P2；

然后G8和M2将会处于系统调用状态，当G8和M2退出系统调用时，M2将会尝试获取曾经绑定过的P2；如果获取P2失败，则会从全局P队列中获取空闲的P与之绑定；

G8则会被标记为可运行状态，从而添加到全局的G队列中，等待被其他的P取从全局G队列中获取执行;

M2此时没有P与之绑定，则将处于休眠状态，添加到全局的M队列中，进行睡眠；

如果休眠时间到达一定时间，则将会被GC所消耗与回收；