golang-浅谈goroutine调度器

前言

相信听说go这门语言的同学都知道go在并发方面相对其它语言而言更突出，并发是所有的语言都有的功能，而为什么go相对较好，它究竟哪里好，底层的实现是怎么样的？基于这些疑惑并为了对goroutine有近一步了解，近期参考相关的资料，并在此对goroutine一些相关的知识做个总结，希望本篇文章能有大家有所帮助。

基本概念

在开始认识goroutine之前，我们需要对以下一些知识点有个基本了解

1.进程、线程、协程

我们知道在操作系统中能够用进程和线程进行并发编程，但进程和线程存在着什么差异呢？之后为什么又会有协程的概念出来呢？

图1--进程虚拟地址空间图片来源: https://sylvanassun.github.io/2017/10/29/2017-10-29-virtual_memory/

进程，以linux系统为例，在创建一个进程时，一般会调用fork函数，fork后会产生一个子进程，该子进程是复制其父进程的虚拟地址空间而得来的(其结构类似图1)，因此其主要的缺点是创建的代价相对较大，并且相对占用内存（注：刚fork出来的进程主要是其内核区相关的结构占用内存，其它内容只要没有对其做修改操作，在物理上是与父进程共享内存块的）。

linux进程在内核区中存在一个进程控制块(PCB)，PCB是一个进程的唯一标识，处理器要调度进程运行是需要依赖它的。在单处理器的情况，系统为了实现并发，会轮流分给每个PCB分配一定的时间片段去运行每个进程中的代码。进程轮流执行代码并迅速切换，这样子在用户看来即使只有一个处理器，也让人感觉让它同一时间执行多个任务。

进程的优点是，进程与进程之间内存是独立，相对安全。如果希望共享数据那得采用一些跨进程通讯的手段（如管道，socket 等）

线程，线程它对比进程会更轻量，但一个线程不能独立存在于系统中，它必须存在于一个进程内，即一个进程内存可以包含多个线程。线程很多方面是和进程很相似，在linux 中创建一个线程时，会在进程空间中再创建新的PCB、栈空间，程序计数据器等。这样子系统就可以基于PCB为线程分配一定的时间片。另外在同一个进程空间内的线程，它们之间的数据是共享的。

对于线程也可以这样理解，一个进程创建时，它内部本来就有一个主线程，它占据一个PCB。后来主线程内新建一个线程，系统会在原有一个PCB的基本上增加一个新的变成两个PCB，一起来轮流获取时间片。

协程，它对比线程又更显得轻量。从上面我们知道，线程之间的切换是由操作系统控制，而这个过程是需要从进程的用户区陷入到内核区，大概需要 50 到 100 纳秒的开销，考虑硬件的合理情况是可以每纳秒执行12条指令，直接浪费600-1200条指令的执行时间。如果单个处理器有1000个线程进行并发，会将许多的时间浪费在切换这个过程上。因此才有了协程的出现，协程同线程一样，但唯独不同的是它的切换操作都是在进程的用户区完成，这个切换就好比改变内存指向的操作，代价对陷入内核而言相对小很多。所以即使在单处理器上同时运行1000个协程，也不会对处理器有过多负担。

在Go 中实现并发只有通过 goroutine，对它的初步理解大家就可以当它是协程+线程的一个结合，能够轻松创建成千上万个goroutine实现并发也不会对处理器有太大的负担。

2.Go Runtime

图2--Runtime同Go程序的关系图片来源:http://www.cs.columbia.edu/~aho/cs6998/reports/12-12-11_DeshpandeSponslerWeiss_GO.pdf

在进入正题之前，还需要对Runtime有个基本的认识比较好一些。Go Runtime 是 Go程序的运行环境，管理着调度器，垃圾回收和一些go程序运行环境相关的的重要特性，其中的调度器是实现goroutine的关键。

对于一个完整可运行的go程序，可以将它两层，一层是用户代码（开发者编写的代码），另一层就是Runtime（在编译器在编译时自动链接上的）。用户代码所有对操作系统API的调用，都会被 Runtime拦截集中调度，而调度器也就是基于这样的环境上实现的。图2 是runtime 同用户代码和操作系统之间的关系。

G-P-M调度模型

golang在1.1版本引入的G-M-P调度模型，解决了原有G-M调度模型的许多性能问题，并对该模型引用到现在。接下来我们先对其模型中G、M、P的定义进行说明，再对它们的关系进行说明。（注: golang源码在/src/runtime/runtime2.go中有相关的代码）

定义

type g struct {
    stack       stack   // offset known to runtime/cgo
    stackguard0 uintptr // offset known to liblink
    stackguard1 uintptr // offset known to liblink
    m              *m      // current m; offset known to arm liblink
    sched          gobuf
    syscallsp      uintptr        // if status==Gsyscall, syscallsp = sched.sp to use during gc
    syscallpc      uintptr        // if status==Gsyscall, syscallpc = sched.pc to use during gc
    param          unsafe.Pointer // passed parameter on wakeup
    goid           int64
    ...
}

G:就是我们平时开发中所使用的gorountine，作为一个任务的存在。当调用go func() 操作，就会生成一个G结构体(代码如上)，每个G拥有各自的函数栈，栈指针，及一些重要的调度配置参数，用来记录代码的执行情况。

type m struct {
    g0      *g     // goroutine with scheduling stack
    morebuf gobuf  // gobuf arg to morestack
    divmod  uint32 // div/mod denominator for arm - known to liblink

    procid        uint64       // for debuggers, but offset not hard-coded
    gsignal       *g           // signal-handling g
    goSigStack    gsignalStack // Go-allocated signal handling stack
    curg          *g       // current running goroutine
    id            int64
    ...
}

M:代表的是系统线程，一个M代表一个系统线程，所有的G代码执行都要依赖于M去执行。

type p struct {
    lock mutex

    id          int32
    status      uint32 // one of pidle/prunning/...
    link        puintptr
    sysmontick  sysmontick // last tick observed by sysmon
    m           muintptr   // back-link to associated m (nil if idle)
    mcache      *mcache

    // Queue of runnable goroutines. Accessed without lock.
    runqhead uint32
    runqtail uint32
    runq     [256]guintptr
    ...
}

P:对G和M起到上下文的作用，所以的M要去执行任务G，都必须持有一个P，且G又在每个P中持有的局部队列中管理着，然后M需要执行的G都是需要从它P这里获取的。

原有的runtime 中是G-M模型，并不存在P这个角色的，引进它是为了解决原有全局队列单一锁(Sched)带来的性能问题和M中mcache对内存的浪费，在P结构体中，可以看到mcache和local runq，它们分别是从M和Sched挪过来的。

关系

G-P-M关系图片来源:https://povilasv.me/go-scheduler/

结合上图，并参考了多篇文章梳理了以下关系：
1.当代码中调用go func()，会产生G,此时G会加入对应P的local queue中。每个M执行任务必须持有一个P, P会从自身local queue中取出任务供G执行。

2.当一个没有绑定P的M（比如从系统调用返回）,它会先偿试需要寻找一个可进行绑定的P,如果没有找到，就将M放入Global queue，并将自身睡眠加入闲置线程列表。注：每个P会周期性检查Global queue，避免有G饿死。

3.P的最大数量是由 GOMAXPROCS 决定，GOMAXPROCS是个可以配置的变量，启动时固定，在1.5 版本后默认是被设置成cpu的核数，因此不建议个人修改它。由于P和M是保持着1:1的关系，意味着runtime 中在同一时间内活跃的线程是保持在与cpu核数相同的数量，这样做的好处是尽量保持每个cpu持有一个线程，减少线程切换的消耗。

4.如果P中的G执行完了，那么这时候会执行work-stealing调度算法从全局队列中获取G，如果没有找到，那它会随机选取一个P从它的队尾获取一半的G执行。从而保证每个处理器能处于工作饱合的状态。

从上面相关的梳理可以简单的说，G是任务，供P调度，M负责执行；调度器会尽量保持同活跃线程数与cpu核数一致，并自动协调每个M的工作量，从而使程序的并发效果达到最好。

系统调用（system call）

为了保持同一时刻有GOMAXPROCS个M保持活跃并不是什么容易的事，考虑系统调用的情况就话比较特殊了，任何的系统调用都必须陷入到内核处理，并且会强制当前的线程进入堵塞状态，直到这个系统调用返回。类似文件读写，是相对耗时的，如果放置让线程堵塞就会造成CPU闲置。所以runtime中，针对系统调用做了以下处理。

系统调用处理图片来源:http://morsmachine.dk/go-scheduler

当go代码中有函数触发系统调用，那么在线程陷入内核时，它必须确保至少有一个线程来执行当前的P,首先它会先从当前的闲置的线程列表中查找闲置线程，如果有就唤醒其中一个，要是没有则创建一个新的M并将P转交给它，然后自已默默进入系统调用堵塞。当系统调用返回时，那就会进行上面 G-P-M 关系中说到的第2点情况。

netpoller

网络I/O操作同样也是属于系统调用，但是如果是按上面说的正常的系统调用处理的话会存在一个问题。如果在高并发服务器中，可能一时间会有上万个请求，那此时系统难道要创建并堵塞上万个线程？这很明显不合理。

针对网络I/O，runtime 又有一个更强大的机制 --- netpoller。netpoller 能够将堵塞I/O转换成异步I/O的效果，它自身有独立的线程，用于做I/O轮询。其实现是基于操作系统自身提供的api，比如在linux使用epoll，windows则使用IoCompletionPort等，以此来优化网络I/O。

当一个goroutine进行访问一个网络请求时，它会通知到netpoller，将对应的文件描述符传递给它，让netpoller统一负责处理I/O操作。然后goroutine自身进行堵塞（注：该堵塞是用户层面上的）加入等待列表。直到对应的文件描述符准备就绪，netpoller才会去唤醒goroutine执行相应的操作。

总结

本篇文章先从进程、线程和协程的对比，从其轻量来引入为什么我们需要gorountine，再对G-P-M模型的讲解来简单地说明调度器的底层原理，最后再通过runtime中对系统调用和I/O处理来衬托调度器的强大。而这仅仅只是调度器的一部分，在文中有很多调度器相关的也没并提及，类似sysmon、轮询机制等也都是值得让人探索的。

最后再感叹一句，不得不说我们是幸运的，能够基于golang这样的强大的语言上做开发，它极大地帮助开发人员减轻开发负担，并让我们从中从学习到很多东西。