POSIX 线程 API（实现了这个 api 的库常被称作 pthreads）在很大程度上可以看做是对现有 Unix 进程模型的逻辑延伸，线程和进程有很多相似处。线程有自己的信号掩码，可以分配与 CPU 关联，可以被放入 cgroups，可以被查询使用了哪些资源。所有这些控制的特性都增加了开销，当你的程序中有 10 万个线程的时候，这些开销将会非常巨大。
另一个问题是，操作系统在 Go 模型下不能做出好的调度决策。举例来说，Go 垃圾回收器在执行一次回收时，需要所有线程都停止，使得内存处于一致性状态。这导致需要等待所有运行着的线程到达某一个我们可以确定内存一致的时刻。当你有很多线程被调度运行时，你必须等待它们达到一致性状态。而 Go 调度器可以决策出只调度到它可以确认内存是一致的时刻即可。这意味着当我们停下来做垃圾回收时，我们只需要等待那些正在 CPU 上运行的活跃的线程。
Go GC 的时候需要全局内存一致性，也即全局都停下来不操作内存，Go 的调度器更容易做到这一点。比如所有空闲系统线程不用管，所有运行时的系统线程都在执行完当前协程后暂停。
Go 语言在并发编程方面有强大的能力，通过 协程 （Goroutine）实现，由 调度器 来管理执行。与操作系统提供的线程相比，去掉无用特性，使用一个小的可伸缩的栈，更短的上下文切换，显得十分轻量。调度器通过使用与 CPU 数量相等的线程减少线程频繁切换的内存开销，同时在每一个线程上执行额外开销更低的 Goroutine 来降低操作系统和硬件的负载。

一、Go 调度器

今天的 Go 语言调度器有着优异的性能，最初的调度器不仅实现非常简陋，也无法支撑高并发的服务，调度器经过几个大版本的迭代才有今天的优异性能，几个不同版本的调度器引入了不同的改进，也存在不同的缺陷。

• 单线程调度器 0.x

  • 只包含 40 多行代码；
  • 程序中只能存在一个活跃线程，由 G - M 模型组成；

• 多线程调度器 1.0

  • 允许运行多线程的程序；
  • 全局锁导致竞争严重；

• 任务窃取调度器 1.1

  • 引入了处理器 P，构成了目前的 G -M- P 模型；
  • 在处理器 P 的基础上实现了基于工作窃取的调度器；
  • 在某些情况下，Goroutine 不会让出线程，进而造成饥饿问题；
  • 时间过长的垃圾回收（Stop-the-world，STW）会导致程序长时间无法工作；

• 抢占式调度器 1.2~ 至今

  • 基于协作的抢占式调度器 1.2~1.13
  • 通过编译器在函数调用时插入抢占检查指令，在函数调用时检查当前 Goroutine 是否发起了抢占请求，实现基于协作的抢占式调度；

  • Goroutine 可能会因为垃圾回收和循环长时间占用资源导致程序暂停；

    • 基于信号的抢占式调度器 1.14~ 至今
  • 实现基于信号的真抢占式调度；
  • 垃圾回收在扫描栈时会触发抢占调度；
  • 抢占的时间点不够多，还不能覆盖全部的边缘情况；

• 非均匀存储访问调度器 提案

  • 对运行时的各种资源进行分区；
  • 实现非常复杂，到今天还没有提上日程

1、单线程调度器

0.x 版本调度器只包含表示 Goroutine 的 G 和表示线程的 M 两种结构，全局也只有一个线程。在这时 Go 语言的调度器还是由 C 语言实现的，调度函数 runtime.schedule 也只包含 40 多行代码。该函数会遵循如下的过程调度 Goroutine：

• 获取调度器的全局锁；
• 调用 runtime.gosave 保存栈寄存器和程序计数器；
• 调用 runtime.nextgandunlock 获取下一个需要运行的 Goroutine 并解锁调度器；
• 修改全局线程 m 上要执行的 Goroutine；
• 调用 runtime.gogo 函数运行最新的 Goroutine；
  显然这个单线程调度器的唯一优点就是能运行。

2、多线程调度器

Go 语言在 1.0 版本正式发布时就支持了多线程的调度器，与上一个版本几乎不可用的调度器相比，Go 语言团队在这一阶段实现了从不可用到可用的跨越。多线程版本的调度函数 runtime.schedule 包含 70 多行代码。整体的逻辑与单线程调度器没有太多区别，因为我们的程序中可能同时存在多个活跃线程，所以多线程调度器引入了 GOMAXPROCS 变量帮助我们灵活控制程序中的最大处理器数，即活跃线程数。多线程调度器的主要问题是调度时的锁竞争会严重浪费资源。该调度器有以下问题需要解决：

• 调度器和锁是全局资源，所有的调度状态都是中心化存储的，锁竞争问严重；
• 线程需要经常互相传递可运行的 Goroutine，引入了大量的延迟；
• 每个线程都需要处理内存缓存，导致大量的内存占用并影响数据局部性（Data locality）；
• 系统调用频繁阻塞和解除阻塞正在运行的线程，增加了额外开销；

3、任务窃取调度器

在现有多线程调度器基础上提出了两个改进的手段：

• 在当前的 G - M 模型中引入了处理器 P，增加中间层；
• 在处理器 P 的基础上实现基于工作窃取的调度器；

使用了新的 G -M- P 模型，调度器的 runtime.schedule 函数在这个版本的调度器中反而更简单了：

static void schedule(void) {
    G *gp;
 top:
    if(runtime·gcwaiting) {
        gcstopm();
        goto top;
    }

    gp = runqget(m->p);
    if(gp == nil)
        gp = findrunnable();

    ...

    execute(gp);
}

• 如果当前运行时在等待垃圾回收，调用 runtime.gcstopm 函数；
• 调用 runtime.runqget 和 runtime.findrunnable 从本地或者全局的运行队列中获取待执行的 Goroutine；
• 调用 runtime.execute 函数在当前线程 M 上运行 Goroutine；
  当前处理器本地的运行队列中不包含 Goroutine 时，调用 findrunnable 函数会触发工作窃取，从其它的处理器的队列中随机获取一些 Goroutine。运行时 G -M- P 模型中引入的处理器 P 是线程 M 和线程 G 的中间层。基于工作窃取的多线程调度器将每一个线程绑定到了独立的 CPU 上，这些线程会被不同处理器管理，不同的处理器通过工作窃取对任务进行再分配实现任务的平衡，也能提升调度器和 Go 语言程序的整体性能。

4、抢占式调度器

对 Go 语言并发模型的修改提升了调度器的性能，但是 1.1 版本中的调度器仍然不支持抢占式调度，程序只能依靠 Goroutine 主动让出 CPU 资源才能触发调度。Go 语言的调度器在 1.2 版本中引入基于协作的抢占式调度解决下面的问题：

• 某些 Goroutine 可以长时间占用线程，造成其它 Goroutine 的饥饿；
• 垃圾回收需要暂停整个程序（Stop-the-world，STW），最长可能需要几分钟的时间 6，导致整个程序无法工作；
  1.2 版本的抢占式调度虽然能够缓解这个问题，但是它实现的抢占式调度是基于协作的，在之后很长的一段时间里 Go 语言的调度器都有一些无法被抢占的边缘情况，例如：for 循环或者垃圾回收长时间占用线程，这些问题中的一部分直到 1.14 才被基于信号的抢占式调度解决。

基于协作的抢占式调度：
Go 语言在分段栈的机制上实现抢占调度，利用编译器在分段栈上插入的函数，所有 Goroutine 在函数调用时都有机会进入运行时执行检查函数判断是否需要执行抢占。基于协作的抢占式调度的工作原理：

• 编译器会在调用函数前插入 runtime.morestack；
• Go 语言运行时会在垃圾回收暂停程序、系统监控发现 Goroutine 运行超过 10ms 时发出抢占请求 StackPreempt；
• 当发生函数调用时，可能会执行编译器插入的 runtime.morestack 函数，它调用的 runtime.newstack 会检查 Goroutine 的 stackguard0 字段是否为 StackPreempt；
• 如果 stackguard0 是 StackPreempt，就会触发抢占让出当前线程；
  这种实现方式虽然增加了运行时的复杂度，但是实现相对简单，也没有带来过多的额外开销，总体来看还是比较成功的实现。因为这里的抢占是通过编译器插入函数实现的，还是需要函数调用作为入口才能触发抢占，所以这是一种协作式的抢占式调度。

基于信号的抢占式调度：
Go 语言在 1.14 版本中实现了非协作的抢占式调度，在实现的过程中重构已有的逻辑并为 Goroutine 增加新的状态和字段来支持抢占。目前的抢占式调度也只会在垃圾回收扫描任务时触发，调度过程：

• 程序启动时，在 runtime.sighandler 函数中注册 SIGURG 信号的处理函数 runtime.doSigPreempt；

• 在触发垃圾回收的栈扫描时会调用 runtime.suspendG 挂起 Goroutine，该函数会执行下面的逻辑：

  • 将_Grunning 状态的 Goroutine 标记成可以被抢占，即将 preemptStop 设置成 true；
  • 调用 runtime.preemptM 触发抢占；
• runtime.preemptM 会调用 runtime.signalM 向线程发送信号 SIGURG；
• 操作系统会中断正在运行的线程并执行预先注册的信号处理函数 runtime.doSigPreempt；
• runtime.doSigPreempt 函数会处理抢占信号，获取当前的 SP 和 PC 寄存器并调用 runtime.sigctxt.pushCall；
• runtime.sigctxt.pushCall 会修改寄存器并在程序回到用户态时执行 runtime.asyncPreempt；
• 汇编指令 runtime.asyncPreempt 会调用运行时函数 runtime.asyncPreempt2；
• runtime.asyncPreempt2 会调用 runtime.preemptPark；
• runtime.preemptPark 会修改当前 Goroutine 的状态到_Gpreempted 并调用 runtime.schedule 让当前函数陷入休眠并让出线程，调度器会选择其它的 Goroutine 继续执行；

根据以下的四个原因选择 SIGURG 作为触发异步抢占的信号；

• 该信号需要被调试器透传；
• 该信号不会被内部的 libc 库使用并拦截；
• 该信号可以随意出现并且不触发任何后果；
• 需要处理多个平台上的不同信号；

STW 和栈扫描是一个可以抢占的安全点（Safe-points），所以 Go 语言会在这里先加入抢占功能。

5、非均匀内存访问调度器

非均匀内存访问（Non-uniform memory access，NUMA）调度器现在只是 Go 语言的提案，因为该提案过于复杂，而目前的调度器的性能已经足够优异，所以我们暂时没有实现该提案。该提案的原理就是通过拆分全局资源，让各个处理器能够就近获取，减少锁竞争并增加数据的局部性。
在目前的运行时中，线程、处理器、网络轮询器、运行队列、全局内存分配器状态、内存分配缓存和垃圾收集器都是全局资源。运行时没有保证本地化，也不清楚系统的拓扑结构，部分结构可以提供一定的局部性，但是从全局来看没有这种保证。

二、GMP 模型

运行时调度器有三个重要组成部分：

• G：代表一个 Goroutine 对象，每次 go 调用的时候，都会创建一个 G 对象，它包括栈、指令指针以及对于调用 goroutines 很重要的其它信息，比如阻塞它的任何 channel
• M：表示一个操作系统的线程，由操作系统的调度器调度和管理；每次创建一个 M 的时候，都会有一个底层线程创建，所有的 G 任务，最终还是在 M 上执行
• P：表示一个处理器，每一个运行的 M 都必须绑定一个 P，就像线程必须在一个 CPU 核上执行一样，由 P 来调度 G 在 M 上的运行，P 的个数是 GOMAXPROCS。

1、G

G（Gorotuine）就是 Go 语言调度器中待执行的任务，它在运行时调度器中的地位与线程在操作系统中差不多，但是它占用了更小的内存空间，也降低了上下文切换的开销。Goroutine 只存在于 Go 语言的运行时，它是 Go 语言在用户态提供的线程，作为一种粒度更细的资源调度单元，如果使用得当能够在高并发的场景下更高效地利用机器的 CPU。Goroutine 在运行时里使用私有结构体 runtime.g 表示。这个私有结构体非常复杂，总共包含 40 多个用于表示各种状态的成员变量，首先是与栈相关的两个字段：

type g struct {
    stack       stack
    stackguard0 uintptr
}

其中 stack 字段描述了当前 Goroutine 的栈内存范围 [stack.lo, stack.hi)，另一个字段 stackguard0 可以用于调度器抢占式调度。除了 stackguard0 之外，Goroutine 中还包含另外三个与抢占密切相关的字段：

type g struct {
    preempt       bool // 抢占信号
    preemptStop   bool // 抢占时将状态修改成 `_Gpreempted`
    preemptShrink bool // 在同步安全点收缩栈
}

Goroutine 与我们在前面章节提到的 defer 和 panic 也有千丝万缕的联系，每一个 Goroutine 上都持有两个分别存储 defer 和 panic 对应结构体的链表：

type g struct {
    _panic       *_panic // 最内侧的 panic 结构体
    _defer       *_defer // 最内侧的延迟函数结构体
}

结构体 runtime.g 的 atomicstatus 字段就存储了当前 Goroutine 的状态。除了几个已经不被使用的以及与 GC 相关的状态之外，Goroutine 可能处于以下 9 个状态：

虽然 Goroutine 在运行时中定义的状态及触发迁移的方法非常多而且复杂，但是我们可以将这些不同的状态聚合成最终的三种：等待中 、 可运行 、 运行中 ，在运行期间我们会在这三种不同的状态来回切换：

• 等待中：Goroutine 正在等待某些条件满足，例如：系统调用结束等，包括_Gwaiting、_Gsyscall 和_Gpreempted 几个状态；
• 可运行：Goroutine 已经准备就绪，可以在线程运行，如果当前程序中有非常多的 Goroutine，每个 Goroutine 就可能会等待更多的时间，即_Grunnable；
• 运行中：Goroutine 正在某个线程上运行，即_Grunning；

2、M

Go 语言并发模型中的 M（Machine）是操作系统线程。调度器最多可以创建 10000 个线程，但是其中大多数的线程都不会执行用户代码（可能陷入系统调用），最多只会有 GOMAXPROCS 个活跃线程能够正常运行。在默认情况下，运行时会将 GOMAXPROCS 设置成当前机器的核数，我们也可以使用 runtime.GOMAXPROCS 来改变程序中最大的线程数。在大多数情况下，我们都会使用 Go 的默认设置，也就是线程数等于 CPU 个数，在这种情况下不会触发操作系统的线程调度和上下文切换，所有的调度都会发生在用户态，由 Go 语言调度器触发，能够减少非常多的额外开销。
操作系统线程在 Go 语言中会使用私有结构体 runtime.m 来表示，这个结构体中也包含了几十个私有的字段，与 Goroutine 直接相关的字段：

type m struct {
    g0   *g 
    curg *g
    ...
}

其中 g0 是持有调度栈的 Goroutine，curg 是在当前线程上运行的用户 Goroutine，这也是操作系统线程唯一关心的两个 Goroutine。g0 是一个运行时中比较特殊的 Goroutine，它会深度参与运行时的调度过程，包括 Goroutine 的创建、大内存分配和 CGO 函数的执行。runtime.m 结构体中还存在着三个处理器字段，它们分别表示正在运行代码的处理器 p、暂存的处理器 nextp 和执行系统调用之前的使用线程的处理器 oldp：

type m struct {
    p             puintptr
    nextp         puintptr
    oldp          puintptr
}

3、P

调度器中的处理器 P(Processor) 是线程和 Goroutine 的中间层，它能提供线程需要的上下文环境，也会负责调度线程上的等待队列，通过处理器 P 的调度，每一个内核线程都能够执行多个 Goroutine，它能在 Goroutine 进行一些 I / O 操作时及时切换，提高线程的利用率。因为调度器在启动时就会创建 GOMAXPROCS 个处理器，所以 Go 语言程序的处理器数量一定会等于 GOMAXPROCS，这些处理器会绑定到不同的内核线程上并利用线程的计算资源运行 Goroutine。runtime.p 是处理器的运行时表示，作为调度器的内部实现，它包含的字段也非常多，其中包括与性能追踪、垃圾回收和计时器相关的字段，主要关注其中的线程和运行队列：

type p struct {
    m           muintptr

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

反向存储的线程维护着线程与处理器之间的关系，而 runhead、runqtail 和 runq 三个字段表示处理器持有的运行队列，其中存储着待执行的 Goroutine 列表，runnext 中是线程下一个需要执行的 Goroutine。
runtime.p 结构体中的状态 status 字段会是以下五种中的一种：

通过分析处理器 P 的状态，我们能够对处理器的工作过程有一些简单理解，例如处理器在执行用户代码时会处于_Prunning 状态，在当前线程执行 I / O 操作时会陷入_Psyscall 状态。

三、调度

运行时有一个重要的全局变量 sched，可以看做一个全局的调度者，数据类型是 schedt。

type schedt struct {
    ...
    lock mutex

    midle        muintptr // idle状态的m
    nmidle       int32    // idle状态的m个数
    nmidlelocked int32    // lockde状态的m个数
    mcount       int32    // 创建的m的总数
    maxmcount    int32    // m允许的最大个数

    ngsys uint32 // 系统中goroutine的数目，会自动更新

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

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

大多数需要的信息都已放在了结构体 M、G 和 P 中，schedt 结构体只是一个壳。可以看到，其中有 M 的 idle 队列，P 的 idle 队列，以及一个全局的就绪的 G 队列。schedt 结构体中的 Lock 是非常必须的，如果 M 或 P 等做一些非局部的操作，它们一般需要先锁住调度器。

1、调度器启动

运行时通过 runtime.schedinit 函数初始化调度器：

func schedinit() {
    _g_ := getg()
    ...

    sched.maxmcount = 10000

    ...
    sched.lastpoll = uint64(nanotime())
    procs := ncpu
    if n, ok := atoi32(gogetenv("GOMAXPROCS")); ok && n > 0 {
        procs = n
    }
    if procresize(procs) != nil {
        throw("unknown runnable goroutine during bootstrap")
    }
}

在调度器初始函数执行的过程中会将 maxmcount 设置成 10000，这也就是一个 Go 语言程序能够创建的最大线程数，虽然最多可以创建 10000 个线程，但是可以同时运行的线程还是由 GOMAXPROCS 变量控制。启动完成之后，等待用户创建运行新的 Goroutine 并为 Goroutine 调度处理器资源。

2、创建 Goroutine

想要启动一个新的 Goroutine 来执行任务时，需要使用 Go 语言中的 go 关键字。编译器会将其转换成 runtime.newproc 函数，该函数会接收大小和表示函数的指针 funcval。在这个函数中会获取 Goroutine 以及调用方的程序计数器，然后调用 runtime.newproc1 函数：

func newproc(siz int32, fn *funcval) {
    argp := add(unsafe.Pointer(&fn), sys.PtrSize)
    gp := getg()
    pc := getcallerpc()
    newproc1(fn, (*uint8)(argp), siz, gp, pc)
}

runtime.newproc1 会根据传入参数初始化一个 g，该函数分成以下几个步骤：

• 获取或者创建新的 Goroutine 结构体；
• 将传入的参数移到 Goroutine 的栈上；
• 更新 Goroutine 调度相关的属性；
• 将 Goroutine 加入处理器的运行队列；
  Go 语言中有两个运行队列，其中一个是处理器本地的运行队列，另一个是调度器持有的全局运行队列，只有在本地运行队列没有剩余空间时才会使用全局队列。

3、调度循环

调度器启动之后，会调用 runtime.schedule 进入调度循环：

func schedule() {
    _g_ := getg()

top:
    var gp *g
    var inheritTime bool

    if gp == nil {
        if _g_.m.p.ptr().schedtick%61 == 0 && sched.runqsize > 0 {
            lock(&sched.lock)
            gp = globrunqget(_g_.m.p.ptr(), 1)
            unlock(&sched.lock)
        }
    }
    if gp == nil {
        gp, inheritTime = runqget(_g_.m.p.ptr())
    }
    if gp == nil {
        gp, inheritTime = findrunnable()
    }

    execute(gp, inheritTime)
}

runtime.schedule 函数的会从不同地方查找待执行的 Goroutine：

• 为了保证公平，当全局运行队列中有待执行的 Goroutine 时，通过 schedtick 保证有一定几率会从全局的运行队列中查找对应的 Goroutine；
• 从处理器本地的运行队列中查找待执行的 Goroutine；
• 如果前两种方法都没有找到 Goroutine，就会通过 runtime.findrunnable 进行阻塞地查找 Goroutine；
  runtime.findrunnable 通过以下的过程获取可运行的 Goroutine，且一定会返回一个可执行的 Goroutine，如果当前不存在就会阻塞等待。
• 从本地运行队列、全局运行队列中查找；
• 从网络轮询器中查找是否有 Goroutine 等待运行；

• 通过 runtime.runqsteal 函数尝试从其他随机的处理器中窃取待运行的 Goroutine，在该过程中还可能窃取处理器中的计时器；
  接下来由 runtime.execute 函数执行获取的 Goroutine，做好准备工作后，它会通过 runtime.gogo 将 Goroutine 调度到当前线程上执行。

  func execute(gp *g, inheritTime bool) {

    _g_ := getg()
  
    _g_.m.curg = gp
    gp.m = _g_.m
    casgstatus(gp, _Grunnable, _Grunning)
    gp.waitsince = 0
    gp.preempt = false
    gp.stackguard0 = gp.stack.lo + _StackGuard
    if !inheritTime {
        _g_.m.p.ptr().schedtick++
    }
  
    gogo(&gp.sched)

  }

最后会调用 runtime.goexit0 函数，该函数会将 Goroutine 转换会_Gdead 状态、清理其中的字段、移除 Goroutine 和线程的关联并调用 runtime.gfput 重新加入处理器的 Goroutine 空闲列表 gFree。

func goexit0(gp *g) {
    _g_ := getg()

    casgstatus(gp, _Grunning, _Gdead)
    gp.m = nil
    ...
    gp.param = nil
    gp.labels = nil
    gp.timer = nil

    dropg()
    gfput(_g_.m.p.ptr(), gp)
    schedule()
}

在最后 runtime.goexit0 函数会重新调用 runtime.schedule 触发新的 Goroutine 调度，我们可以认为调度循环永远都不会返回。

Go 语言中的运行时调度循环会从 runtime.schedule 函数开始，最终又回到 runtime.schedule；上述介绍的是 Goroutine 正常执行并退出的逻辑，实际情况会复杂得多，多数情况下 Goroutine 的执行的过程中都会经历协作式或者抢占式调度，这时会让出线程的使用权等待调度器的唤醒。