Golang——GMP原理与调度

一. Golang调度器的由来

1.1 单进程时代不需要调度器

我们知道，一切软件都跑在操作系统上，真正用来干活(计算)的是CPU。早期的操作系统每一个程序就是一个进程，直到一个程序运行完，才能进行下一个进程，就是"单进程时代"。

一切程序只能串行发生。

早期的单进程系统面临两个问题：

单一的执行流程，计算机只能一个任务一个任务的处理
进程阻塞所带来的CPU时间浪费

那么能不能有有个进程来宏观一起来执行多个任务呢？

后来操作系统就具有了最早的并发能力：多进程并发，当一个进程阻塞时，切换到另外一个等待执行的进程，这样就能尽量把CPU利用起来，CPU就不浪费了。

1.2 多进程/多线程时代有了调度器的需求

在多进程/多线程的操作系统中，就解决了阻塞的问题因为一个进程阻塞cpu可以立刻切换到其他进程中去执行，而且调度cpu算法可以保证在运行的进程都可以被分配到cpu的运行时间片。这样宏观来看，似乎多个进程是在同时被运行的。

但是新的问题是，进程拥有太多的资源，进程创建，切换，销毁都会占用很长时间，CPU虽然利用起来了，但是如果进程过多，CPU有很大一部分都被用来进行进程调度了。

但是对于Linux操作系统来讲，cpu对进程的态度和线程的态度都是一样的。都使用的是PCB(struct task_struct)来描述。

很明显，CPU调度切换的是进程和线程，尽管线程占用的资源比较少，但是实际上多线程的开发设计会变得更加复杂，需要考虑到很多同步竞争等问题，例如：锁，竞争冲突等。

1.3 协程来提高CPU利用率

多线程，多进程已经提高了系统的并发能力，但是在当前互联网高并发场景下，为每一个任务都创建一个线程是不现实的，因为会消耗大量的内存(进程虚拟地址在32位系统下大小为4GB，但是一个线程也要4MB)。

大量的进程/线程出现了新的问题：

高内存的占用
调度高消耗CPU

其实一个线程分为"内核态"线程和"用户态"线程。就是在用户态管理着一个线程，在内核态管理着一个线程，两者是不同的结构，但是具有关联。

一个"用户态"线程必须绑定一个"内核态"线程，但是CPU并不知道有"用户态"线程的存在，它只知道它运行的是一个"内核态"线程(Linux的PCB控制块)。

再细化分类一下，内核线程依然叫做线程(thread)，用户线程叫做协程(co-routine)。

既然，一个协程可以绑定一个线程，那么可不可以多个协程绑定到一个或者多个线程上呢？

下面介绍3中协程和线程的映射关系：

N:1的关系，N个协程绑定一个线程

优点：

协程在用户态就可以进行切换，不会陷入内核态，这种切换非常轻量迅速

缺点：

一个进程的所有协程绑定在一个线程上，用不了硬件的多核加速能力
一旦某协程阻塞，造成线程阻塞，其他协程也无法运行，没有并发能力了。

一个协程绑定一个线程

这种最容易实现。协程的调度都由CPU完成了，不存在N个协程绑定一个线程的缺点。

缺点：

协程的创建，删除和切换的代价都由CPU完成，有点略显昂贵了。

M个协程绑定N个线程，是N个协程绑定1个线程，1个协程绑定1个线程的结合，克服了这两个模型的缺点，但是实现起来最为复杂。

协程和线程是有区别的，线程由CPU调度是抢占式的，协程由用户态调度是协作式的，一个协程让出CPU后，才执行下一个协程，不是抢占式的。

1.4 Go语言的协程goroutine

Go为了提供更容易使用的并发方法，使用了goroutine和channel。goroutine来自协程的概念，让一组可复用的函数运行在一组线程之上，即使有协程阻塞，该线程的其他协程也可以被runtime调度，转移到其它可运行的线程上。最关键的是，程序员看不到底层的细节，这就降低了编程的难度，提供了更容易的并发。

Go中，协程被称为goroutine，它非常的轻量，一个goroutine只占几KB，并且这几KB就足够goroutine运行完，这就能在非常有限的内存空间支持大量goroutine，支持了更多的并发。虽然一个goroutine的栈只占几KB，但实际是可伸缩的，如果需要更多的内容，runtime会自动为goroutine分配。

goroutine特点：

占用内存小(几KB)
调度灵活(runtime调度)

goroutine协程与协程的关系为M:N(多对多)的。

1.5 被废弃的goroutine调度器

Go目前使用的调度器是2012年重新设计的，因为之前的调度器性能存在问题，所以使用4年就被废弃了，那么我们先分析一下被废弃的调度器是如何运作的。

大部分文章都会使用G来表示goroutine，用M来表示线程，那么我们也会用这种表达的对应关系。

被废弃的golang调度器是如何实现的？

M想要执行，放回G都必须访问全局G队列，并且M有多个，即多个线程访问同一资源需要加锁进行保存互斥/同步，所以全局G队列是有互斥锁进行保护的。

老调度器的缺点：

创建，销毁，调度G都需要每个M获取锁，这就形成了激烈的锁竞争
M转移G会造成延迟和额外的系统负载。比如当G中包含创建新协程的时候，M创建G~，为了继续执行G，需要把G~交给M~执行，也造成了很差的局限性，因为G~和G是相关的，最好放在M上执行，而不是其他M~
系统调用(CPU在M之间切换)导致频繁的线程阻塞和取消阻塞操作增加了系统开销

1.6 Goroutine 调度器的GMP模型的设计思想

面对之前的调度器的问题，Go设计了新的调度器。

在新调度器中，出列了M(thread)和G(goroutine)，又引进了P(Processor)。

Processor，它包含了运行goroutine的资源，如果线程想运行goroutine，必须先获取P，P中还包含了可运行的G队列。

1.6.1 GMP模型

在Go中，线程是运行goroutine的实体，调度器的功能是把可运行的goroutine分配到工作线程上。

全局队列：存放等待运行的G，同样有互斥锁的保护
P的本地队列：同全局队列相似存放的也是等待运行的G，存的数量有限，不超过256个。新建G~时，G~优先加入到P的本地队列，如果队列满了，则会把本地队列中的一半的G移动到全局队列
P列表：所有的P都在程序启动时创建，并保持在数组中，最多有GOMAXPROCS(可配置)个。
M：线程想运行任务就得获取P，从P的本地队列获取G，P的队列为空时，M也会尝试从全局队列拿一批G放到P的本地队列，或从其他P的本地队列拿一半放到自己P的本地队列。M运行G，G执行之后，M会从P获取下一个G，不断重复下去
M(machine)是Go运行时(runtime)对操作系统内核线程的虚拟，M与内核线程一般是一一对应的关系，一个goroutine最终是要放到M上执行的

Goroutine调度器和OS调度器是通过M结合起来的，每个M都代表1个内核线程，OS调度器负责把内核线程分配到CPU上。

1.6.2 P和M的个数问题

1. P的数量

由启动时环境变量$GOMAXPROCS或者时由runtime的方法GOMAXPROCS()决定。这意味着在程序执行的任意时刻都只有$GOMAXPROCS个goroutine在同时进行。(goroutine由P调度，P与M对应，一个M只能运行一个G)

2. M的数量

go语言本身的限制：go程序启动时，会设置M的最大数量，默认10000，但是内核很难支持这么多的线程数，所以这个限制可以忽略。
runtime/debug中的SetMaxThreads函数，设置M的最大数量
一个M阻塞了，会创建新的M。

M与P的数量没有绝对的关系，一个M阻塞，P就会去创建或者切换另一个M，所以即使P的默认数量是1，也可能会创建很多个M出来。

3. P和M何时会被创建

P何时创建：在确定了P的最大数量n后，运行时系统会根据这个数量创建n个P
M何时创建：没有足够的M来关联P并运行其中的可运行的G。比如：所有的M此时都阻塞住了，而P中还有很多就绪任务，就会去寻找空闲的M，当没有空闲的M，就回去创建新的M。

1.6.3 调度器的设计策略

避免频繁的创建，销毁线程，而是对线程的复用。

work stealing机制

当本线程无可运行的G时，尝试从其它线程绑定的P获取G，而不是销毁线程。

hand off机制

当本线程因为G进行系统调用阻塞时，线程释放绑定的G，把P转移给其他空闲线程执行。

利用并行：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.6.4 go func()执行流程

协程的执行流程：

从上图中我们可以分析出几个结论：

我们通过go func()来创建一个goroutine
有两个存储G的队列，一个局部调度器P的本地队列，一个全局G队列。新创建的G会先保存在P的本地队列中，如果P的本地队列已经满了就会保存在全局的队列中
G只能运行在M中，一个M必须持有一个P，M与P是1：1的关系。M会从P的本地队列弹出一个可执行状态的G来执行，如果P的本地队列为空，就会向其他P的队列中偷取一个可执行的G来执行，如果在其他P的队列中获取不到G，则从全局G队列中获取
一个M调度G的执行过程是一个循环机制
当M执行某一个G的时候如果发生了syscall(系统调用)或者其它阻塞操作，M会阻塞，如果当前有一些G正在执行，runtime会把这个线程M从P中摘除(detach)，然后再创建一个新的操作系统线程(如果有空闲的线程则复用空闲线程)来服务这个P
当M系统调用结束时候，go func()创建的这个G会尝试获取一个空闲的P执行，并放入到这个P的本地队列。如果获取不到P，那么这个线程M变成休眠状态，加入空闲线程中，这个G会被放入全局队列中。

1.6.5 调度器的生命周期

特殊的M0和G0

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

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

首先创建M0是为了进行调度器的初始化，等初始化完后，M0就和其他M一样，为了执行G。然后M0启动G0，G0是为了给M0调度可执行G的。

我们来跟踪一段代码

package main

import "fmt"

func main(){
    fmt.Println("hello world!")
}

下面我们来针对上面的代码对调度器里面的结构做一个分析：

runtime创建最初的线程m0和goroutine G0，并把两个关联
调度器初始化：初始化m0，栈，垃圾回收，以及创建和初始化由GOMAXPROCS个P构成P列表
示例代码中的main函数是main.main，runtime中也有一个main函数一个runtime.main，代码经过编译后，runtime.main会调用main.main，程序启动时会为runtime.main创建goroutine，称他为main goroutine吧，然后把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结束而结束。

1.6.6 可视化GMP编程

有两种方式可以查看一个程序的GMP数据。

方式1：go tool trace

trace 记录了运行时的信息，能提供可视化的web页面。

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

package main

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

func main() {
	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()

	fmt.Println("hello world")

}

运行程序，会在当前目录得到一个trace.out文件，

然后我们使用工具打开这个文件

我们可以用浏览器打开http://127.0.0.1:65034/ 网站，在网页中可以点击下面两个按钮查看信息。

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

一共有两个G在程序中，一个是特殊的G0，是每一个M必须有的一个初始化G。分配本地P中G列表的空闲G的。

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

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

一共有两个M在程序中，一个是特殊的M0。

P信息：G1中调用了main.main，创建了trace goroutine g

查看Goroutine分析：

发现现在有5个goroutine：

G0会创建四个M，来执行。

点击View trace by thread，可以看到M信息：

我们知道一个M必须绑定一个P，才能调度G。所以View trace by proc里面会有5个P。

1.7 Go调度器调度场景过程全解析

场景1：创建G

P1拥有G1，M1获取P1后开始运行G1，G1使用go func()创建G2，为了局部性G2优先加入到P1的本地队列中。

场景2：G执行完，执行下一个G。

G1运行完成后(函数goexit)，M上运行的goroutine切换为G0，G0负责调度时协程的切换(函数：schedule)。从P的本地队列获取G2，从G0切换到G2，并开始运行G2(函数：execute)。实现了线程M1的复用。

场景3 ：创建过多的G导致本地队列满了

假设每个P的本地队列只能存4个G。G2创建了6个G，加入本地队列满了。

场景4：本地队列满的情况

G2在创建按G7的时候，发现P1的本地队列已满，需要执行负载均衡(把P1中本地队列前一半的G，还有新创建的G转移到全局队列中)

实现中并不一定是新G，如果G是G2之后就执行的，会被保存在本地队列，利用某个老的G替换新G加入全局队列。

这些G被转移到全局队列时，会被打乱顺序。所以G3，G4，G7被转移到全局队列。

场景5

G2创建G8时，P1的本地队列未满，所以G8会被加入到P1的本地队列中。

G8加入到P1点本地队列的原因还是因为P1此时在与M1绑定，而G2此时是M1在执行。所以以G2创建的新的G会优先放置到自己的M绑定的P上。

场景6

规定：在创建G时，运行的G会尝试唤醒其他空闲的P和M组合去执行。

假设G2唤醒了M2，M2绑定了P2，并运行G0，但P2本地队列没有G，M2此时为自旋线程(没有G但为运行状态的线程，不断寻找G)。

场景7

M2尝试从全局队列(简称"GQ")取一批G放到P2的本地队列(函数：findrunnable())。M2从全局队列取的G数量符合下面的公式：

n = min(len(GQ) / GOMAXPROCS, len(GQ / 2))

至少从全局队列取1个G，但每次不要从全局队列移动太多的g到p本地队列，给其他p留点。这是从全局队列到P队列的负载均衡。

假设我们场景中一共有4个P(GOMAXPROCS设置为4，那么我们允许最多就能用到4个P来供M使用)。所以M2只能从全局队列取1个G(即图中G3)移动到本地队列，然后完成从G0到G3的切换，运行G3。

场景8

假设G2一直在M1上运行，经过2轮后，M2已经把G7，G4从全局队列中获取到了P2的本地队列，并完成运行，全局队列和P2的本地队列都空了，如场景8图的坐半部分。

全局队列中已经没有G，那么M2就要执行work stealing(偷取)，从其它有G的P哪里偷取一半G过来，放到自己P的本地队列中。P2从P1的本地队列尾部偷取一半的G，本例中一半的G则只有一个G8，放到P2的本地队列执行。

场景9

G1本地队列G5，G6已经被其他M偷走本运行完成，当前M1和M2分别运行G2和G8，M3和M4没有goroutine运行，M3和M4处于自旋状态，它们不断寻找goroutine。

为什么要让M3和M4自旋，自旋的本质就是运行，线程在运行却没有执行G，就变成了浪费CPU。为什么不直接销毁，来节约CPU资源。因为创建和销毁CPU也会浪费时间，我们希望有新的goroutine创建时，立刻有M来运行它，如果销毁再创建就增加了时延，降低了效率。

当然也考虑了过多的自旋线程是浪费CPU，所以系统最多有GOMAXPROCS个自旋线程(当前例子中的GOMAXPROCS为4，所以一共4个P)，多余的没事做的线程会让他们休眠。

场景9

假设当前除了M3和M4为自旋线程，还有M5和M6为空闲的线程(没有P的绑定，注意我们这里最多只能存在4个P，所以P的数量应该永远M>=P，大部分都是M在抢占需要运行的P)，G8创建了G9，G8进行了阻塞的系统调用，M2和P2立刻解绑，P2会执行一下判断：如果P2本地队列有G，全局队列有G或有空闲的M，P2都会立马唤醒一个M和它绑定，否则P2则会加入空闲P列表，等待M来获取可用的P。

本场景中，P2本地队列有G9，可以和空闲的M5绑定。

总结起来就是：当P本地队列有G或者全局队列有G，且绑定的线程阻塞了，P会找其他空闲的M取绑定，如果本地队列且全局队列没有G且没有空闲的M，P会加入空闲P，等待M来获取。