Golang GPM Models

在了解 Go 的 gorutine 时，我们还是得先复习下，并发和并行的区别：

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

在单核处理器上，通过多线程共享CPU时间片串行执行(并发非并行)。而并行则依赖于多核处理器等物理资源，让多个任务可以实现并行执行(并发且并行)。

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

并发模型

常见的并发模型有七种：

  • 线程与锁
  • 函数式编程
  • Clojure之道
  • actor
  • 通讯顺序进程（CSP）
  • 数据级并行
  • Lambda架构

CSP

CSP，全称Communicating Sequential Processes，意为通讯顺序进程，它是七大并发模型中的一种，它的核心观念是将两个并发执行的实体通过通道channel连接起来，所有的消息都通过channel传输。其实CSP概念早在1978年就被东尼·霍尔提出，由于近来Go语言的兴起，CSP又火了起来。

那么CSP与Go语言有什么关系呢？接下来我们来看Go语言对CSP并发模型的实现——GPM调度模型。

GPM的三个角色

GPM代表了三个角色，分别是Goroutine、Processor、Machine。

  • Goroutine：就是代码中使用go关键词创建的执行单元，也是大家熟知的有“轻量级线程”之称的协程，协程是不为操作系统所知的，它由编程语言层面实现，上下文切换不需要经过内核态，再加上协程占用的内存空间极小，所以有着非常大的发展潜力。Goroutine由一个名为runtime.go的结构体表示，该结构体非常复杂，有40多个成员变量，主要存储执行栈、状态、当前占用的线程、调度相关的数据。还有玩大家很想获取的goroutine标识，官方考虑到Go语言的发展，设置成私有了。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    type g struct {
        stack struct {
            lo uintptr
            hi uinptr
        }                             // 栈内存：[stack.lo, stack.hi)
        stackguard0    uintptr
        stackguard1 uintptr

        _panic       *_panic
        _defer       *_defer
        m            *m                // 当前的 m
        sched        gobuf
        stktopsp     uintptr        // 期望 sp 位于栈顶，用于回溯检查
        param        unsafe.Pointer // wakeup 唤醒时候传递的参数
        atomicstatus uint32
        goid         int64
        preempt      bool           // 抢占信号，stackguard0 = stackpreempt 的副本
        timer        *timer         // 为 time.Sleep 缓存的计时器

        ...
    }

    Goroutine调度相关的数据存储在sched，在协程切换、恢复上下文的时候用到。

    1
    2
    3
    4
    5
    6
    7
    type gobuf struct {
        sp   uintptr
        pc   uintptr
        g    guintptr
        ret  sys.Uintreg
        ...
    }

  • Machine：表示操作系统的线程。最多会有GOMAXPROCS个活跃线程能够正常运行，默认情况下GOMAXPROCS被设置为内核数，假如有四个内核，那么默认就创建四个线程，每一个线程对应一个runtime.m结构体。线程数等于CPU个数的原因是，每个线程分配到一个CPU上就不至于出现线程的上下文切换，可以保证系统开销降到最低。

    在绑定有效的 P 后，进入 schedule 循环；而 schedule 循环的机制大致是从 Global 队列、P 的 Local 队列以及 wait 队列中获取 G，切换到 G 的执行栈上并执行 G 的函数，调用 goexit 做清理工作并回到 M，如此反复。M 并不保留 G 状态，这是 G 可以跨 M 调度的基础，M 的数量是不定的，由 Go Runtime 调整，为了防止创建过多 OS 线程导致系统调度不过来，目前默认最大限制为 10000 个。

    1
    2
    3
    4
    5
    6
    7
    8
    type m struct {
        g0   *g 
        curg *g
        ...
        p             puintptr
        nextp         puintptr
        oldp          puintptr
    }

    M里面存了两个比较重要的东西，一个是g0，一个是curg。

    • g0：会深度参与运行时的调度过程，比如goroutine的创建、内存分配等
    • curg：代表当前正在线程上执行的goroutine。

    刚才说P是负责M与G的关联，所以M里面还要存储与P相关的数据。

    • p：正在运行代码的处理器
    • nextp：暂存的处理器
    • old：系统调用之前的线程的处理器

  • Processor：负责Machine与Goroutine的连接，它能提供线程需要的上下文环境，也能分配G到它应该去的线程上执行，保证每个G都能得到合理的调用。同样的，处理器的数量也是默认按照GOMAXPROCS来设置的，与线程的数量一一对应。但是不论 GOMAXPROCS 设置为多大，P 的数量最大为 256。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    type p struct {
        m           muintptr

        runqhead uint32
        runqtail uint32
        runq     [256]guintptr
        runnext guintptr
        ...
    }

    结构体P中存储了性能追踪、垃圾回收、计时器等相关的字段外，还存储了处理器的待运行队列，队列中存储的是待执行的Goroutine列表。

调度算法

普通栈：普通栈指的是需要调度的 goroutine 组成的函数栈，是可增长的栈，因为 goroutine 可以越开越多。

线程栈：线程栈是由需要将 goroutine 放置线程上的 m 们组成，实质上 m 也是由 goroutine 生成的，线程栈大小固定（设置了 m 的数量）。所有调度相关的代码，会先切换到该goroutine的栈中再执行。也就是说线程的栈也是用的g实现，而不是使用的OS的。

全局队列：

  • 该队列存储的 G 将被所有的 M 全局共享，为保证数据竞争问题，需加锁处理。
  • M 自旋（自己队列上没有 G）会偷取其他队列的一半 G，放置在自己绑定的本地队列上，先从该队列偷取，如果没有则从其他本地队列偷取。
  • sysmon 再次扫描发现上次任然在运行的 G 时（sysmon 起初扫描间隔为 10ns，每次扫描间隔翻倍，最高为 10ms），会将其停止与 M 解绑，放置该队列中；

本地队列：该队列存储数据资源相同的任务，每个本地队列都会绑定一个 M ，指定其完成任务，没有数据竞争，无需加锁处理，处理速度远高于全局队列。

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

线程清理

由于每个P都需要绑定一个 M 进行任务执行，所以当清理线程的时候，只需要将 P 释放（解除绑定）（M就没有任务），即可。P 被释放主要由两种情况：

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

阻塞是正在运行的线程没有运行结束，暂时让出 CPU。

抢占式调度

在runtime.main中会创建一个额外m运行sysmon函数，抢占就是在sysmon中实现的。

sysmon会进入一个无限循环, 第一轮回休眠20us, 之后每次休眠时间倍增, 最终每一轮都会休眠10ms. sysmon中有netpool(获取fd事件), retake(抢占), forcegc(按时间强制执行gc), scavenge heap(释放自由列表中多余的项减少内存占用)等处理。

抢占条件：

  1. 如果 P 在系统调用中，且时长已经过一次 sysmon 后，则抢占；

调用 handoffp 解除 M 和 P 的关联。

  1. 如果 P 在运行，且时长经过一次 sysmon 后，并且时长超过设置的阻塞时长，则抢占；

设置标识，标识该函数可以被中止，当调用栈识别到这个标识时，就知道这是抢占触发的, 这时会再检查一遍是否要抢占。

详细流程

每个 P 维护一个 G 的本地队列

当一个 G 被创建出来，或者变为可执行状态时，就把他放到 P 的本地可执行队列中，如果满了则放入Global；

如果 g 执行时需要被阻塞，则会进行上下文切换，系统归还资源后，再返回继续执行。

当一个G长久阻塞在一个M上时，runtime会新建一个M，阻塞G所在的P会把其他的G 挂载在新建的M上。当旧的G阻塞完成或者认为其已经死掉时 回收旧的M（抢占式调度）。

P会对自己管理的goroutine队列做一些调度（比如把占用CPU时间较长的goroutine暂停、运行后续的goroutine等等）当自己的队列消费完了就去全局队列里取，如果全局队列里也消费完了会去其他P的队列里抢任务（所以需要单独存储下一个 g 的地址，而不是从队列里获取）。

当一个 G 在 M 里执行结束后，P 会从队列中把该 G 取出；如果此时 P 的队列为空，即没有其他 G 可以执行， M 就随机选择另外一个 P，从其可执行的 G 队列中取走一半。

总结

相比大多数并行设计模型，Go比较优势的设计就是P上下文这个概念的出现，如果只有G和M的对应关系，那么当G阻塞在IO上的时候，M是没有实际在工作的，这样造成了资源的浪费，没有了P，那么所有G的列表都放在全局，这样导致临界区太大，对多核调度造成极大影响。

而goroutine在使用上面的特点，感觉既可以用来做密集的多核计算，又可以做高并发的IO应用，做IO应用的时候，写起来感觉和对程序员最友好的同步阻塞一样，而实际上由于runtime的调度，底层是以同步非阻塞的方式在运行（即IO多路复用）。

所以说保护现场的抢占式调度和G被阻塞后传递给其他m调用的核心思想，使得goroutine的产生。

单从线程调度讲，Go语言相比起其他语言的优势在于OS线程是由OS内核来调度的，goroutine则是由Go运行时（runtime）自己的调度器调度的，这个调度器使用一个称为m:n调度的技术（复用/调度m个goroutine到n个OS线程）。 其一大特点是goroutine的调度是在用户态下完成的， 不涉及内核态与用户态之间的频繁切换，包括内存的分配与释放，都是在用户态维护着一块大的内存池， 不直接调用系统的malloc函数（除非内存池需要改变），成本比调度OS线程低很多。 另一方面充分利用了多核的硬件资源，近似的把若干goroutine均分在物理线程上， 再加上本身goroutine的超轻量，以上种种保证了go调度方面的性能。