前言

随着服务器硬件迭代升级，配置也越来越高。为充分利用服务器资源，并发编程也变的越来越重要。在开始之前，需要了解一下并发(concurrency)和并行(parallesim)的区别。

  • 并发: 逻辑上具有处理多个同时性任务的能力。
  • 并行: 物理上同一时刻执行多个并发任务。

通常所说的并发编程，也就是说它允许多个任务同时执行，但实际上并不一定在同一时刻被执行。在单核处理器上，通过多线程共享CPU时间片串行执行(并发非并行)。而并行则依赖于多核处理器等物理资源，让多个任务可以实现并行执行(并发且并行)。

多线程或多进程是并行的基本条件，但单线程也可以用协程(coroutine)做到并发。简单将Goroutine归纳为协程并不合适，因为它运行时会创建多个线程来执行并发任务，且任务单元可被调度到其它线程执行。这更像是多线程和协程的结合体，能最大限度提升执行效率，发挥多核处理器能力。

Go编写一个并发编程程序很简单，只需要在函数之前使用一个Go关键字就可以实现并发编程。

func main() {    
    go func(){
        fmt.Println("Hello,World!")
    }()
}

为什么Go要实现自己调度器

  1. POSIX线程API是对已有的UNIX进程模型的逻辑扩展，因此线程和进程在很多方面都类似。例如，线程有自己的信号掩码，CPU affinity（进程要在某个给定的 CPU 上尽量长时间地运行而不被迁移到其他处理器的倾向性），cgroups。但是有很多特性对于Go程序来说都是累赘。

  2. 另外一个问题是基于Go语言模型，OS的调度决定并不一定合理。例如，Go的垃圾回收需要内存处于一致性的状态，这需要所有运行的线程都停止。垃圾回收的时间点是不确定的，如果仅由OS来调度，将会由大量的线程停止工作。

  3. 单独开发一个Go的调度器能让我们知道什么时候内存处于一致性的状态。也就是说，当开始垃圾回收时，运行时只需要为当时正在CPU核上运行的那个线程等待即可，而不是等待所有的线程。

Go调度器组成

操作系统的调度模型是大致上有两种N:1和1:1.。N:1模型中用户态的线程运行在一个内核线程上，这种方式上下文切换快，但不能有效利用多核。

1:1模型中的一个用户态线程对应一个内核线程，这种方式有效利用了多核，但上下文切换非常慢(因为要不停 trap 陷入内核)。Goroutine是协程，即轻量级线程，用户态完成调度，Rob Pike先生想利用有限的os线程去调度和执行任意数量的goroutine，显然是想把N:1模型和1:1模型的优点都收入囊中。

1、 初级设想： 任务队列 + 线程

thread+queue

其中G就是goroutine，先开一个线程池，线程不停地从queue中取goroutine执行。如果一个goroutine里面出现了长时间系统调用，那么就会阻塞线程直到系统调用结束。

假设队列里面所有的goroutine都是长时间系统调用，那么线程都会被阻塞住，这显然不合理。我们需要的是：goroutine可以阻塞，但线程不可以阻塞或者说线程不可以出现长时间阻塞。要做到这点线程必须知道此时goroutine的状态，然后是wait状态的时候就将它换出去，执行其他goroutine，同时记住上次goroutine的上下文，以便下次继续执行。goroutine的状态：

goroutine-stauts

这样G的数据结构就很清楚了：

struct G  {
     uintptr    stackguard;    // 分段栈的可用空间下界
     uintptr    stackbase;    // 分段栈的栈基址
     Gobuf      sched;        //进程切换时，利用sched域来保存上下文
     uintptr    stack0;
     FuncVal*    fnstart;    // goroutine运行的函数
     void*    param;          // 用于传递参数，睡眠时其它goroutine设置param，唤醒时此goroutine可以获取
     int16    status;        // 状态Gidle,Grunnable,Grunning,Gsyscall,Gwaiting,Gdead
     int64    goid;          // goroutine的id号
     G*    schedlink;
     M*    m;      // for debuggers, but offset not hard-coded
     M*    lockedm;          // G被锁定只能在这个m上运行
     uintptr    gopc;        // 创建这个goroutine的go表达式的pc
};

其中status字段就表示goroutine的状态。有了这些信息，线程就可以自如地调度和执行协程了。这个方案是完美的吗? 至少我们能看出一个地方不好：线程每次取G的时候都要加排它锁，这样势必导致调度和执行的效率下降。我们把G分成多个queue，每一个queue都归属于一个线程去执行(M* lockedm)。这样线程只需要管理自己的queue队列就好了，不需要每次都竞争解决了。

2、中级设想：线程独享任务队列 + 线程 + 调度器

queues

这样是不是完美了呢？牛人说过：计算机上的所有问题都可以通过增加一个抽象层来解决。我们希望线程不要过多的担负调度的任务，调度应该由抽象层来完成，线程只管执行，于是乎：

m-queues

M的数据结构出来了：

struct M   {
     G*    g0;        // 带有调度栈的goroutine
     G*    gsignal;    // signal-handling G 处理信号的goroutine
     void    (*mstartfn)(void);  // 线程入口
     G*    curg;        // M中当前运行的goroutine
    P*    p;        // 关联P以执行Go代码 (如果没有执行Go代码则P为nil)
    P*    nextp;
    int32    mallocing; //状态
    int32    helpgc;        //不为0表示此m在做帮忙gc。helpgc等于n只是一个编号
    M*    alllink;    // 这个域用于链接allm
    M*    schedlink;
     MCache    *mcache;
    G*    lockedg;
    M*    nextwaitm;    // next M waiting for lock
    GCStats    gcstats;
};

增加了一个M层来参与调度goroutine，这样让线程从调度和执行任务里面解脱出来。M是machine的缩写，是对机器的抽象，每个m都是对应到一条操作系统的物理线程。

3、终极进化：线程独享任务队列 + 线程 + 调度器 + 抢占式

假设一个情况：如果一个Goroutine一直占用CPU，长时间没有被调度过， 就会被runtime抢占掉，把CPU时间交给其他Goroutine。又需要一个抽象层来帮忙下了：

m-p-queues

P的数据结构出来了：

struct P  {
    Lock;
    uint32    status;  // Pidle或Prunning等
    P*    link;
    uint32    schedtick;  // 每次调度时将它加一
    M*    m;    // 链接到它关联的M (nil if idle)
    MCache*    mcache;
    G*    runq[256];
    int32    runqhead;
    int32    runqtail;
    G*    gfree;
};

P是Go1.1中新加入的一个数据结构，它是Processor的缩写。结构体P的加入是为了提高Go程序的并发度，实现更好的调度。M代表OS线程。P代表Go代码执行时需要的资源。当M执行Go代码时，它需要关联一个P，当M为idle或者在系统调用中时，它也需要P。有刚好GOMAXPROCS个P。所有的P被组织为一个数组，在P上实现了工作流窃取的调度器。

4、Golang 的终极BOSS：Sched

不考虑 g0 和 gsignal 的话，我们可以简单地认为调度就是将 m 绑定到 p，然后在 m 中不断循环执行调度函数(runtime.schedule)，寻找可用的 g 来执行，所以，P和M的现场是不用加锁的，但是如果多个P去操作全局的G队列，则需要加全局锁，而 Sched 就是全局调度器。

全局调度器只有一个：

type schedt struct {
    // 下面两个变量需以原子访问访问。保持在 struct 顶部，以使其在 32 位系统上可以对齐
    goidgen  uint64
    lastpoll uint64

    lock mutex

    // 当修改 nmidle，nmidlelocked，nmsys，nmfreed 这些数值时
    // 需要记得调用 checkdead

    midle        muintptr // idle m's waiting for work
    nmidle       int32    // 当前等待工作的空闲 m 计数
    nmidlelocked int32    // 当前等待工作的被 lock 的 m 计数
    mnext        int64    // 当前预缴创建的 m 数，并且该值会作为下一个创建的 m 的 ID
    maxmcount    int32    // 允许创建的最大的 m 数量
    nmsys        int32    // number of system m's not counted for deadlock
    nmfreed      int64    // cumulative number of freed m's

    ngsys uint32 // number of system goroutines; updated atomically

    pidle      puintptr // 空闲 p's
    npidle     uint32
    nmspinning uint32 // See "Worker thread parking/unparking" comment in proc.go.

    // 全局的可运行 g 队列
    runqhead guintptr
    runqtail guintptr
    runqsize int32

    // dead G 的全局缓存
    gflock       mutex
    gfreeStack   *g
    gfreeNoStack *g
    ngfree       int32

    // sudog 结构的集中缓存
    sudoglock  mutex
    sudogcache *sudog

    // 不同大小的可用的 defer struct 的集中缓存池
    deferlock mutex
    deferpool [5]*_defer

    // 被设置了 m.exited 标记之后的 m，这些 m 正在 freem 这个链表上等待被 free
    // 链表用 m.freelink 字段进行链接
    freem *m

    gcwaiting  uint32 // gc is waiting to run
    stopwait   int32
    stopnote   note
    sysmonwait uint32
    sysmonnote note

    // safepointFn should be called on each P at the next GC
    // safepoint if p.runSafePointFn is set.
    safePointFn   func(*p)
    safePointWait int32
    safePointNote note

    profilehz int32 // cpu profiling rate

    procresizetime int64 // 上次修改 gomaxprocs 的纳秒时间
    totaltime      int64 // ∫gomaxprocs dt up to procresizetime
}

调度流程图如下：

yesnonoyesnoyesscheduleschedtick%61 == 0globrunqgetrunqgetgp == nilexecutegp == nilfindrunnable

Go调度器调度过程

首先创建一个G对象，G对象保存到P本地队列或者是全局队列。P此时去唤醒一个M。P继续执行它的执行序。M寻找是否有空闲的P，如果有则将该G对象移动到它本身。接下来M执行一个调度循环(调用G对象->执行->清理线程→继续找新的Goroutine执行)。

M执行过程中，随时会发生上下文切换。当发生上线文切换时，需要对执行现场进行保护，以便下次被调度执行时进行现场恢复。Go调度器M的栈保存在G对象上，只需要将M所需要的寄存器(SP、PC等)保存到G对象上就可以实现现场保护。当这些寄存器数据被保护起来，就随时可以做上下文切换了，在中断之前把现场保存起来。如果此时G任务还没有执行完，M可以将任务重新丢到P的任务队列，等待下一次被调度执行。当再次被调度执行时，M通过访问G的vdsoSP、vdsoPC寄存器进行现场恢复(从上次中断位置继续执行)。

1、P 队列

通过上图可以发现，P有两种队列：本地队列和全局队列。

本地队列： 当前P的队列，本地队列是Lock-Free，没有数据竞争问题，无需加锁处理，可以提升处理速度。

全局队列：全局队列为了保证多个P之间任务的平衡。所有M共享P全局队列，为保证数据竞争问题，需要加锁处理。相比本地队列处理速度要低于全局队列。

2、 G 的调度

在1.3版本以前，G的调度是非抢占式的，只要你的状态共享的代码块不跨越调度点或者IO调度点, 是不需要加锁的, 天然的无锁状态。1.3以后实现了类似抢占式的调度（编译器会在代码中插内容触发调度），上面的天然无锁状态也就不存在了。就算用GOMAXPROCS把最大并行数（P）设置为1, 也无法用无锁的模型玩耍了。

那么如果G中执行了带阻塞的系统调用，调度会有什么样的变化呢？如下图所示：

P转而在OS线程M1上运行，这样就不会因为一个阻塞调用，而阻塞了P上所有的G。图中的M1可能是被创建，或者从线程池中取出。当被丢弃的M0-G对完成系统调用变成可执行状态时，它必须尝试取得一个context P来运行goroutine，一般情况下，它会从其他的OS线程那里偷一个P过来，如果没有偷到的话，它就把goroutine放在一个global runqueue里，然后自己就去睡大觉了（回到线程池里）。Contexts们也会周期性的检查global runqueue，否则global runqueue上的goroutine永远无法执行。这也就是为什么即使GOMAXPROCS P被设置成1，Goroutine还是能用到多核处理。

当一个P对象将维护的runqueue里的G全部执行完之后，可以从别的P的runqueue底部拿到一半的G放入自己的runqueue中执行，这也就是为什么叫做Work stealing算法，这也是Goroutine为何高效的一个很大原因。如下图所示：

G比系统线程要简单许多，相对于在内核态进行上下文切换，G的切换代价低了很多，调度策略非常简单，毕竟操作系统要为各种复杂的场景提供完整的解决方案，而通常我们应用程序层面解决的问题都相对简单。

3、上线文切换

简单理解为当时的环境即可，环境可以包括当时程序状态以及变量状态。例如线程切换的时候在内核会发生上下文切换，这里的上下文就包括了当时寄存器的值，把寄存器的值保存起来，等下次该线程又得到cpu时间的时候再恢复寄存器的值，这样线程才能正确运行。

对于代码中某个值说，上下文是指这个值所在的局部(全局)作用域对象。相对于进程而言，上下文就是进程执行时的环境，具体来说就是各个变量和数据，包括所有的寄存器变量、进程打开的文件、内存(堆栈)信息等。

4、线程清理

Goroutine被调度执行必须保证P/M进行绑定，所以线程清理只需要将P释放就可以实现线程的清理。什么时候P会释放，保证其它G可以被执行。P被释放主要有两种情况。

主动释放：最典型的例子是，当执行G任务时有系统调用，当发生系统调用时M会处于Block状态。调度器会设置一个超时时间，当超时时会将P释放。

被动释放：如果发生系统调用，有一个专门监控程序，进行扫描当前处于阻塞的P/M组合。当超过系统程序设置的超时时间，会自动将P资源抢走。去执行队列的其它G任务。

5、 非阻塞IO与IO多路复用

现在我们知道协程的创建和上线文切换都非常“轻”，但是在进行带阻塞系统调用时执行体M会被阻塞，这就需要创建新的系统资源，而在高并发的web场景下如果使用阻塞的IO调用，网络IO大概率阻塞较长的时间，导致我们还是要创建大量的系统线程，所以Go需要尽量使用非阻塞的系统调用，虽然Go的标准库提供的是同步阻塞的IO模型，但底层其实是使用内核提供的非阻塞的IO模型。当Goroutine进行IO操作而数据未就绪时，syscall返回error，当前执行的Goroutine被置为阻塞态而M并没有被阻塞，P就可以继续使用当前执行体M继续执行下一个G，这样P就不需要再跑到别的M，从而也就不会去创建新的M。

当然只有非阻塞IO还不够，Go抽象了netpoller对象来进行IO多路复用，在linux下通过epoll来实现IO多路复用。当G由于IO未就绪而被置为阻塞态时，netpoller将对应的文件描述符注册到epoll实例中进行epoll_wait，就绪的文件描述符回调通知给阻塞的G，G更新为就绪状态等待调度继续执行，这种实现使得Golang在进行高并发的网络通信时变得非常强大，相比于php-fpm的多进程模型，Golang Http Server使用很少的线程资源运行非常多的Goroutine，而且尽可能的让每一个线程都忙碌起来，而不是阻塞在IO调用上，提高了CPU的利用率。

参考