Golang 最大的特色可以说是协程 (goroutine) 了, 协程让本来很复杂的异步编程变得简单, 让程序员不再需要面对回调地狱,
虽然现在引入了协程的语言越来越多, 但 go 中的协程仍然是实现的是最彻底的.
这篇文章将通过分析 golang 的源代码来讲解协程的实现原理.

这个系列分析的 golang 源代码是 Google 官方的实现的 1.9.2 版本, 不适用于其他版本和 gccgo 等其他实现,
运行环境是 Ubuntu 16.04 LTS 64bit.

要理解协程的实现, 首先需要了解 go 中的三个非常重要的概念, 它们分别是G, M和P,
没有看过 golang 源代码的可能会对它们感到陌生, 这三项是协程最主要的组成部分, 它们在 golang 的源代码中无处不在.

G (goroutine)

G 是 goroutine 的头文字, goroutine 可以解释为受管理的轻量线程, goroutine 使用go关键词创建.

举例来说, func main() { go other() }, 这段代码创建了两个 goroutine,
一个是 main, 另一个是 other, 注意 main 本身也是一个 goroutine.

goroutine 的新建, 休眠, 恢复, 停止都受到 go 运行时的管理.
goroutine 执行异步操作时会进入休眠状态, 待操作完成后再恢复, 无需占用系统线程,
goroutine 新建或恢复时会添加到运行队列, 等待 M 取出并运行.

M (machine)

M 是 machine 的头文字, 在当前版本的 golang 中等同于系统线程.
M 可以运行两种代码:

  • go 代码, 即 goroutine, M 运行 go 代码需要一个 P
  • 原生代码, 例如阻塞的 syscall, M 运行原生代码不需要 P

M 会从运行队列中取出 G, 然后运行 G, 如果 G 运行完毕或者进入休眠状态, 则从运行队列中取出下一个 G 运行, 周而复始.
有时候 G 需要调用一些无法避免阻塞的原生代码, 这时 M 会释放持有的 P 并进入阻塞状态, 其他 M 会取得这个 P 并继续运行队列中的 G.
go 需要保证有足够的 M 可以运行 G, 不让 CPU 闲着, 也需要保证 M 的数量不能过多.

P (process)

P 是 process 的头文字, 代表 M 运行 G 所需要的资源.
一些讲解协程的文章把 P 理解为 cpu 核心, 其实这是错误的.
虽然 P 的数量默认等于 cpu 核心数, 但可以通过环境变量GOMAXPROC修改, 在实际运行时 P 跟 cpu 核心并无任何关联.

P 也可以理解为控制 go 代码的并行度的机制,
如果 P 的数量等于 1, 代表当前最多只能有一个线程 (M) 执行 go 代码,
如果 P 的数量等于 2, 代表当前最多只能有两个线程 (M) 执行 go 代码.
执行原生代码的线程数量不受 P 控制.

因为同一时间只有一个线程 (M) 可以拥有 P, P 中的数据都是锁自由 (lock free) 的, 读写这些数据的效率会非常的高.

在讲解协程的工作流程之前, 还需要理解一些内部的数据结构.

G 的状态

  • 空闲中 (_Gidle): 表示 G 刚刚新建, 仍未初始化
  • 待运行 (_Grunnable): 表示 G 在运行队列中, 等待 M 取出并运行
  • 运行中 (_Grunning): 表示 M 正在运行这个 G, 这时候 M 会拥有一个 P
  • 系统调用中 (_Gsyscall): 表示 M 正在运行这个 G 发起的系统调用, 这时候 M 并不拥有 P
  • 等待中 (_Gwaiting): 表示 G 在等待某些条件完成, 这时候 G 不在运行也不在运行队列中 (可能在 channel 的等待队列中)
  • 已中止 (_Gdead): 表示 G 未被使用, 可能已执行完毕 (并在 freelist 中等待下次复用)
  • 栈复制中 (_Gcopystack): 表示 G 正在获取一个新的栈空间并把原来的内容复制过去 (用于防止 GC 扫描)

M 的状态

M 并没有像 G 和 P 一样的状态标记, 但可以认为一个 M 有以下的状态:

  • 自旋中 (spinning): M 正在从运行队列获取 G, 这时候 M 会拥有一个 P
  • 执行 go 代码中: M 正在执行 go 代码, 这时候 M 会拥有一个 P
  • 执行原生代码中: M 正在执行原生代码或者阻塞的 syscall, 这时 M 并不拥有 P
  • 休眠中: M 发现无待运行的 G 时会进入休眠, 并添加到空闲 M 链表中, 这时 M 并不拥有 P

自旋中 (spinning) 这个状态非常重要, 是否需要唤醒或者创建新的 M 取决于当前自旋中的 M 的数量.

P 的状态

  • 空闲中 (_Pidle): 当 M 发现无待运行的 G 时会进入休眠, 这时 M 拥有的 P 会变为空闲并加到空闲 P 链表中
  • 运行中 (_Prunning): 当 M 拥有了一个 P 后, 这个 P 的状态就会变为运行中, M 运行 G 会使用这个 P 中的资源
  • 系统调用中 (_Psyscall): 当 go 调用原生代码, 原生代码又反过来调用 go 代码时, 使用的 P 会变为此状态
  • GC 停止中 (_Pgcstop): 当 gc 停止了整个世界 (STW) 时, P 会变为此状态
  • 已中止 (_Pdead): 当 P 的数量在运行时改变, 且数量减少时多余的 P 会变为此状态

本地运行队列

在 go 中有多个运行队列可以保存待运行 (_Grunnable) 的 G, 它们分别是各个 P 中的本地运行队列和全局运行队列.
入队待运行的 G 时会优先加到当前 P 的本地运行队列, M 获取待运行的 G 时也会优先从拥有的 P 的本地运行队列获取,
本地运行队列入队和出队不需要使用线程锁.

本地运行队列有数量限制, 当数量达到 256 个时会入队到全局运行队列.
本地运行队列的数据结构是环形队列, 由一个 256 长度的数组和两个序号 (head, tail) 组成.

当 M 从 P 的本地运行队列获取 G 时, 如果发现本地队列为空会尝试从其他 P 盗取一半的 G 过来,
这个机制叫做Work Stealing, 详见后面的代码分析.

全局运行队列

全局运行队列保存在全局变量sched中, 全局运行队列入队和出队需要使用线程锁.
全局运行队列的数据结构是链表, 由两个指针 (head, tail) 组成.

空闲 M 链表

当 M 发现无待运行的 G 时会进入休眠, 并添加到空闲 M 链表中, 空闲 M 链表保存在全局变量sched.
进入休眠的 M 会等待一个信号量 (m.park), 唤醒休眠的 M 会使用这个信号量.

go 需要保证有足够的 M 可以运行 G, 是通过这样的机制实现的:

  • 入队待运行的 G 后, 如果当前无自旋的 M 但是有空闲的 P, 就唤醒或者新建一个 M
  • 当 M 离开自旋状态并准备运行出队的 G 时, 如果当前无自旋的 M 但是有空闲的 P, 就唤醒或者新建一个 M
  • 当 M 离开自旋状态并准备休眠时, 会在离开自旋状态后再次检查所有运行队列, 如果有待运行的 G 则重新进入自旋状态

因为 “入队待运行的 G” 和 “M 离开自旋状态” 会同时进行, go 会使用这样的检查顺序:

入队待运行的 G => 内存屏障 => 检查当前自旋的 M 数量 => 唤醒或者新建一个 M
减少当前自旋的 M 数量 => 内存屏障 => 检查所有运行队列是否有待运行的 G => 休眠

这样可以保证不会出现待运行的 G 入队了, 也有空闲的资源 P, 但无 M 去执行的情况.

空闲 P 链表

当 P 的本地运行队列中的所有 G 都运行完毕, 又不能从其他地方拿到 G 时,
拥有 P 的 M 会释放 P 并进入休眠状态, 释放的 P 会变为空闲状态并加到空闲 P 链表中, 空闲 P 链表保存在全局变量sched
下次待运行的 G 入队时如果发现有空闲的 P, 但是又没有自旋中的 M 时会唤醒或者新建一个 M, M 会拥有这个 P, P 会重新变为运行中的状态.

下图是协程可能出现的工作状态, 图中有 4 个 P, 其中 M1~M3 正在运行 G 并且运行后会从拥有的 P 的运行队列继续获取 G:

Golang源码探索(二) 协程的实现原理 - q303248153 - 博客园 - 图1

只看这张图可能有点难以想象实际的工作流程, 这里我根据实际的代码再讲解一遍:

  1. package main
  3. import (
  4.     "fmt"
  5.     "time"
  6. )
  8. func printNumber(from, to int, c chan int) {
  9.     for x := from; x <= to; x++ {
  10.         fmt.Printf("%d\n", x)
  11.         time.Sleep(1 * time.Millisecond)
  12.     }
  13.     c <- 0
  14. }
  16. func main() {
  17.     c := make(chan int, 3)
  18.     go printNumber(1, 3, c)
  19.     go printNumber(4, 6, c)
  20.     _ = <- c
  21.     _ = <- c
  22. }

程序启动时会先创建一个 G, 指向的是 main(实际是 runtime.main 而不是 main.main, 后面解释):
图中的虚线指的是 G 待运行或者开始运行的地址, 不是当前运行的地址.

Golang源码探索(二) 协程的实现原理 - q303248153 - 博客园 - 图2

M 会取得这个 G 并运行:

Golang源码探索(二) 协程的实现原理 - q303248153 - 博客园 - 图3

这时 main 会创建一个新的 channel, 并启动两个新的 G:

Golang源码探索(二) 协程的实现原理 - q303248153 - 博客园 - 图4

接下来G: main会从 channel 获取数据, 因为获取不到, G 会保存状态并变为等待中 (_Gwaiting) 并添加到 channel 的队列:

Golang源码探索(二) 协程的实现原理 - q303248153 - 博客园 - 图5

因为G: main保存了运行状态, 下次运行时将会从_ = <- c继续运行.
接下来 M 会从运行队列获取到G: printNumber并运行:

Golang源码探索(二) 协程的实现原理 - q303248153 - 博客园 - 图6

printNumber 会打印数字, 完成后向 channel 写数据,
写数据时发现 channel 中有正在等待的 G, 会把数据交给这个 G, 把 G 变为待运行 (_Grunnable) 并重新放入运行队列:

Golang源码探索(二) 协程的实现原理 - q303248153 - 博客园 - 图7

接下来 M 会运行下一个G: printNumber, 因为创建 channel 时指定了大小为 3 的缓冲区, 可以直接把数据写入缓冲区而无需等待:

Golang源码探索(二) 协程的实现原理 - q303248153 - 博客园 - 图8

然后 printNumber 运行完毕, 运行队列中就只剩下G: main了:

Golang源码探索(二) 协程的实现原理 - q303248153 - 博客园 - 图9

最后 M 把G: main取出来运行, 会从上次中断的位置_ <- c继续运行:

Golang源码探索(二) 协程的实现原理 - q303248153 - 博客园 - 图10

第一个_ <- c的结果已经在前面设置过了, 这条语句会执行成功.
第二个_ <- c在获取时会发现 channel 中有已缓冲的 0, 于是结果就是这个 0, 不需要等待.
最后 main 执行完毕, 程序结束.

有人可能会好奇如果最后再加一个_ <- c会变成什么结果, 这时因为所有 G 都进入等待状态, go 会检测出来并报告死锁:

  1. fatal error: all goroutines are asleep - deadlock!

关于概念的讲解到此结束, 从这里开始会分析 go 中的实现代码, 我们需要先了解一些基础的内容.

汇编代码

从以下的 go 代码:

  1. package main
  3. import (
  4.     "fmt"
  5.     "time"
  6. )
  8. func printNumber(from, to int, c chan int) {
  9.     for x := from; x <= to; x++ {
  10.         fmt.Printf("%d\n", x)
  11.         time.Sleep(1 * time.Millisecond)
  12.     }
  13.     c <- 0
  14. }
  16. func main() {
  17.     c := make(chan int, 3)
  18.     go printNumber(1, 3, c)
  19.     go printNumber(4, 6, c)
  20.     _, _ = <- c, <- c
  21. }

可以生成以下的汇编代码 (平台是 linux x64, 使用的是默认选项, 即启用优化和内联):

  1. (lldb) di -n main.main
  2. hello`main.main:
  3. hello[0x401190] <+0>:   movq   %fs:-0x8, %rcx
  4. hello[0x401199] <+9>:   cmpq   0x10(%rcx), %rsp
  5. hello[0x40119d] <+13>:  jbe    0x401291                  ; <+257> at hello.go:16
  6. hello[0x4011a3] <+19>:  subq   $0x40, %rsp
  7. hello[0x4011a7] <+23>:  leaq   0xb3632(%rip), %rbx       ; runtime.rodata + 38880
  8. hello[0x4011ae] <+30>:  movq   %rbx, (%rsp)
  9. hello[0x4011b2] <+34>:  movq   $0x3, 0x8(%rsp)
  10. hello[0x4011bb] <+43>:  callq  0x4035a0                  ; runtime.makechan at chan.go:49
  11. hello[0x4011c0] <+48>:  movq   0x10(%rsp), %rax
  12. hello[0x4011c5] <+53>:  movq   $0x1, 0x10(%rsp)
  13. hello[0x4011ce] <+62>:  movq   $0x3, 0x18(%rsp)
  14. hello[0x4011d7] <+71>:  movq   %rax, 0x38(%rsp)
  15. hello[0x4011dc] <+76>:  movq   %rax, 0x20(%rsp)
  16. hello[0x4011e1] <+81>:  movl   $0x18, (%rsp)
  17. hello[0x4011e8] <+88>:  leaq   0x129c29(%rip), %rax      ; main.printNumber.f
  18. hello[0x4011ef] <+95>:  movq   %rax, 0x8(%rsp)
  19. hello[0x4011f4] <+100>: callq  0x430cd0                  ; runtime.newproc at proc.go:2657
  20. hello[0x4011f9] <+105>: movq   $0x4, 0x10(%rsp)
  21. hello[0x401202] <+114>: movq   $0x6, 0x18(%rsp)
  22. hello[0x40120b] <+123>: movq   0x38(%rsp), %rbx
  23. hello[0x401210] <+128>: movq   %rbx, 0x20(%rsp)
  24. hello[0x401215] <+133>: movl   $0x18, (%rsp)
  25. hello[0x40121c] <+140>: leaq   0x129bf5(%rip), %rax      ; main.printNumber.f
  26. hello[0x401223] <+147>: movq   %rax, 0x8(%rsp)
  27. hello[0x401228] <+152>: callq  0x430cd0                  ; runtime.newproc at proc.go:2657
  28. hello[0x40122d] <+157>: movq   $0x0, 0x30(%rsp)
  29. hello[0x401236] <+166>: leaq   0xb35a3(%rip), %rbx       ; runtime.rodata + 38880
  30. hello[0x40123d] <+173>: movq   %rbx, (%rsp)
  31. hello[0x401241] <+177>: movq   0x38(%rsp), %rbx
  32. hello[0x401246] <+182>: movq   %rbx, 0x8(%rsp)
  33. hello[0x40124b] <+187>: leaq   0x30(%rsp), %rbx
  34. hello[0x401250] <+192>: movq   %rbx, 0x10(%rsp)
  35. hello[0x401255] <+197>: callq  0x4043c0                  ; runtime.chanrecv1 at chan.go:354
  36. hello[0x40125a] <+202>: movq   $0x0, 0x28(%rsp)
  37. hello[0x401263] <+211>: leaq   0xb3576(%rip), %rbx       ; runtime.rodata + 38880
  38. hello[0x40126a] <+218>: movq   %rbx, (%rsp)
  39. hello[0x40126e] <+222>: movq   0x38(%rsp), %rbx
  40. hello[0x401273] <+227>: movq   %rbx, 0x8(%rsp)
  41. hello[0x401278] <+232>: leaq   0x28(%rsp), %rbx
  42. hello[0x40127d] <+237>: movq   %rbx, 0x10(%rsp)
  43. hello[0x401282] <+242>: callq  0x4043c0                  ; runtime.chanrecv1 at chan.go:354
  44. hello[0x401287] <+247>: movq   0x28(%rsp), %rbx
  45. hello[0x40128c] <+252>: addq   $0x40, %rsp
  46. hello[0x401290] <+256>: retq   
  47. hello[0x401291] <+257>: callq  0x4538d0                  ; runtime.morestack_noctxt at asm_amd64.s:365
  48. hello[0x401296] <+262>: jmp    0x401190                  ; <+0> at hello.go:16
  49. hello[0x40129b] <+267>: int3   
  50. hello[0x40129c] <+268>: int3   
  51. hello[0x40129d] <+269>: int3   
  52. hello[0x40129e] <+270>: int3   
  53. hello[0x40129f] <+271>: int3   
  55. (lldb) di -n main.printNumber
  56. hello`main.printNumber:
  57. hello[0x401000] <+0>:   movq   %fs:-0x8, %rcx
  58. hello[0x401009] <+9>:   leaq   -0x8(%rsp), %rax
  59. hello[0x40100e] <+14>:  cmpq   0x10(%rcx), %rax
  60. hello[0x401012] <+18>:  jbe    0x401185                  ; <+389> at hello.go:8
  61. hello[0x401018] <+24>:  subq   $0x88, %rsp
  62. hello[0x40101f] <+31>:  xorps  %xmm0, %xmm0
  63. hello[0x401022] <+34>:  movups %xmm0, 0x60(%rsp)
  64. hello[0x401027] <+39>:  movq   0x90(%rsp), %rax
  65. hello[0x40102f] <+47>:  movq   0x98(%rsp), %rbp
  66. hello[0x401037] <+55>:  cmpq   %rbp, %rax
  67. hello[0x40103a] <+58>:  jg     0x40112f                  ; <+303> at hello.go:13
  68. hello[0x401040] <+64>:  movq   %rax, 0x40(%rsp)
  69. hello[0x401045] <+69>:  movq   %rax, 0x48(%rsp)
  70. hello[0x40104a] <+74>:  xorl   %ebx, %ebx
  71. hello[0x40104c] <+76>:  movq   %rbx, 0x60(%rsp)
  72. hello[0x401051] <+81>:  movq   %rbx, 0x68(%rsp)
  73. hello[0x401056] <+86>:  leaq   0x60(%rsp), %rbx
  74. hello[0x40105b] <+91>:  cmpq   $0x0, %rbx
  75. hello[0x40105f] <+95>:  je     0x40117e                  ; <+382> at hello.go:10
  76. hello[0x401065] <+101>: movq   $0x1, 0x78(%rsp)
  77. hello[0x40106e] <+110>: movq   $0x1, 0x80(%rsp)
  78. hello[0x40107a] <+122>: movq   %rbx, 0x70(%rsp)
  79. hello[0x40107f] <+127>: leaq   0xb73fa(%rip), %rbx       ; runtime.rodata + 54400
  80. hello[0x401086] <+134>: movq   %rbx, (%rsp)
  81. hello[0x40108a] <+138>: leaq   0x48(%rsp), %rbx
  82. hello[0x40108f] <+143>: movq   %rbx, 0x8(%rsp)
  83. hello[0x401094] <+148>: movq   $0x0, 0x10(%rsp)
  84. hello[0x40109d] <+157>: callq  0x40bb90                  ; runtime.convT2E at iface.go:128
  85. hello[0x4010a2] <+162>: movq   0x18(%rsp), %rcx
  86. hello[0x4010a7] <+167>: movq   0x20(%rsp), %rax
  87. hello[0x4010ac] <+172>: movq   0x70(%rsp), %rbx
  88. hello[0x4010b1] <+177>: movq   %rcx, 0x50(%rsp)
  89. hello[0x4010b6] <+182>: movq   %rcx, (%rbx)
  90. hello[0x4010b9] <+185>: movq   %rax, 0x58(%rsp)
  91. hello[0x4010be] <+190>: cmpb   $0x0, 0x19ea1b(%rip)      ; time.initdone.
  92. hello[0x4010c5] <+197>: jne    0x401167                  ; <+359> at hello.go:10
  93. hello[0x4010cb] <+203>: movq   %rax, 0x8(%rbx)
  94. hello[0x4010cf] <+207>: leaq   0xfb152(%rip), %rbx       ; go.string.* + 560
  95. hello[0x4010d6] <+214>: movq   %rbx, (%rsp)
  96. hello[0x4010da] <+218>: movq   $0x3, 0x8(%rsp)
  97. hello[0x4010e3] <+227>: movq   0x70(%rsp), %rbx
  98. hello[0x4010e8] <+232>: movq   %rbx, 0x10(%rsp)
  99. hello[0x4010ed] <+237>: movq   0x78(%rsp), %rbx
  100. hello[0x4010f2] <+242>: movq   %rbx, 0x18(%rsp)
  101. hello[0x4010f7] <+247>: movq   0x80(%rsp), %rbx
  102. hello[0x4010ff] <+255>: movq   %rbx, 0x20(%rsp)
  103. hello[0x401104] <+260>: callq  0x45ad70                  ; fmt.Printf at print.go:196
  104. hello[0x401109] <+265>: movq   $0xf4240, (%rsp)          ; imm = 0xF4240 
  105. hello[0x401111] <+273>: callq  0x442a50                  ; time.Sleep at time.go:48
  106. hello[0x401116] <+278>: movq   0x40(%rsp), %rax
  107. hello[0x40111b] <+283>: incq   %rax
  108. hello[0x40111e] <+286>: movq   0x98(%rsp), %rbp
  109. hello[0x401126] <+294>: cmpq   %rbp, %rax
  110. hello[0x401129] <+297>: jle    0x401040                  ; <+64> at hello.go:10
  111. hello[0x40112f] <+303>: movq   $0x0, 0x48(%rsp)
  112. hello[0x401138] <+312>: leaq   0xb36a1(%rip), %rbx       ; runtime.rodata + 38880
  113. hello[0x40113f] <+319>: movq   %rbx, (%rsp)
  114. hello[0x401143] <+323>: movq   0xa0(%rsp), %rbx
  115. hello[0x40114b] <+331>: movq   %rbx, 0x8(%rsp)
  116. hello[0x401150] <+336>: leaq   0x48(%rsp), %rbx
  117. hello[0x401155] <+341>: movq   %rbx, 0x10(%rsp)
  118. hello[0x40115a] <+346>: callq  0x403870                  ; runtime.chansend1 at chan.go:99
  119. hello[0x40115f] <+351>: addq   $0x88, %rsp
  120. hello[0x401166] <+358>: retq   
  121. hello[0x401167] <+359>: leaq   0x8(%rbx), %r8
  122. hello[0x40116b] <+363>: movq   %r8, (%rsp)
  123. hello[0x40116f] <+367>: movq   %rax, 0x8(%rsp)
  124. hello[0x401174] <+372>: callq  0x40f090                  ; runtime.writebarrierptr at mbarrier.go:129
  125. hello[0x401179] <+377>: jmp    0x4010cf                  ; <+207> at hello.go:10
  126. hello[0x40117e] <+382>: movl   %eax, (%rbx)
  127. hello[0x401180] <+384>: jmp    0x401065                  ; <+101> at hello.go:10
  128. hello[0x401185] <+389>: callq  0x4538d0                  ; runtime.morestack_noctxt at asm_amd64.s:365
  129. hello[0x40118a] <+394>: jmp    0x401000                  ; <+0> at hello.go:8
  130. hello[0x40118f] <+399>: int3

这些汇编代码现在看不懂也没关系, 下面会从这里取出一部分来解释.

调用规范

不同平台对于函数有不同的调用规范.
例如 32 位通过栈传递参数, 通过 eax 寄存器传递返回值.
64 位 windows 通过 rcx, rdx, r8, r9 传递前 4 个参数, 通过栈传递第 5 个开始的参数, 通过 eax 寄存器传递返回值.
64 位 linux, unix 通过 rdi, rsi, rdx, rcx, r8, r9 传递前 6 个参数, 通过栈传递第 7 个开始的参数, 通过 eax 寄存器传递返回值.
go 并不使用这些调用规范 (除非涉及到与原生代码交互), go 有一套独自的调用规范.

go 的调用规范非常的简单, 所有参数都通过栈传递, 返回值也通过栈传递,
例如这样的函数:

  1. type MyStruct struct { X int; P *int }
  2. func someFunc(x int, s MyStruct) (int, MyStruct) { ... }

调用函数时的栈的内容如下:

Golang源码探索(二) 协程的实现原理 - q303248153 - 博客园 - 图11

可以看得出参数和返回值都从低位到高位排列, go 函数可以有多个返回值的原因也在于此. 因为返回值都通过栈传递了.
需要注意的这里的 “返回地址” 是 x86 和 x64 上的, arm 的返回地址会通过 LR 寄存器保存, 内容会和这里的稍微不一样.
另外注意的是和 c 不一样, 传递构造体时整个构造体的内容都会复制到栈上, 如果构造体很大将会影响性能.

TLS

TLS 的全称是Thread-local storage, 代表每个线程的中的本地数据.
例如标准 c 中的 errno 就是一个典型的 TLS 变量, 每个线程都有一个独自的 errno, 写入它不会干扰到其他线程中的值.
go 在实现协程时非常依赖 TLS 机制, 会用于获取系统线程中当前的 G 和 G 所属的 M 的实例.

因为 go 并不使用 glibc, 操作 TLS 会使用系统原生的接口, 以 linux x64 为例,
go 在新建 M 时会调用arch_prctl这个 syscall 设置 FS 寄存器的值为 M.tls 的地址,
运行中每个 M 的 FS 寄存器都会指向它们对应的 M 实例的 tls, linux 内核调度线程时 FS 寄存器会跟着线程一起切换,
这样 go 代码只需要访问 FS 寄存器就可以存取线程本地的数据.

上面的汇编代码中的

  1. hello[0x401000] <+0>:   movq   %fs:-0x8, %rcx

会把指向当前的 G 的指针从 TLS 移动到 rcx 寄存器中.

栈扩张

因为 go 中的协程是stackful coroutine, 每一个 goroutine 都需要有自己的栈空间,
栈空间的内容在 goroutine 休眠时需要保留, 待休眠完成后恢复 (这时整个调用树都是完整的).
这样就引出了一个问题, goroutine 可能会同时存在很多个, 如果每一个 goroutine 都预先分配一个足够的栈空间那么 go 就会使用过多的内存.

为了避免这个问题, go 在一开始只为 goroutine 分配一个很小的栈空间, 它的大小在当前版本是 2K.
当函数发现栈空间不足时, 会申请一块新的栈空间并把原来的栈内容复制过去.

上面的汇编代码中的

  1. hello[0x401000] <+0>:   movq   %fs:-0x8, %rcx
  2. hello[0x401009] <+9>:   leaq   -0x8(%rsp), %rax
  3. hello[0x40100e] <+14>:  cmpq   0x10(%rcx), %rax
  4. hello[0x401012] <+18>:  jbe    0x401185                  ; <+389> at hello.go:8

会检查比较 rsp 减去一定值以后是否比 g.stackguard0 小, 如果小于等于则需要调到下面调用 morestack_noctxt 函数.
细心的可能会发现比较的值跟实际减去的值不一致, 这是因为 stackguard0 下面会预留一小部分空间, 编译时确定不超过预留的空间可以省略比对.

写屏障 (Write Barrier)

因为 go 支持并行 GC, GC 的扫描和 go 代码可以同时运行, 这样带来的问题是 GC 扫描的过程中 go 代码有可能改变了对象的依赖树,
例如开始扫描时发现根对象 A 和 B, B 拥有 C 的指针, GC 先扫描 A, 然后 B 把 C 的指针交给 A, GC 再扫描 B, 这时 C 就不会被扫描到.
为了避免这个问题, go 在 GC 的标记阶段会启用写屏障 (Write Barrier).

启用了写屏障 (Write Barrier) 后, 当 B 把 C 的指针交给 A 时, GC 会认为在这一轮的扫描中 C 的指针是存活的,
即使 A 可能会在稍后丢掉 C, 那么 C 就在下一轮回收.
写屏障只针对指针启用, 而且只在 GC 的标记阶段启用, 平时会直接把值写入到目标地址:

关于写屏障的详细将在下一篇 (GC 篇) 分析.
值得一提的是 CoreCLR 的 GC 也有写屏障的机制, 但作用跟这里的不一样 (用于标记跨代引用).

闭包 (Closure)

闭包这个概念本身应该不需要解释, 我们实际看一看 go 是如何实现闭包的:

  1. package main
  3. import (
  4.     "fmt"
  5. )
  7. func executeFn(fn func() int) int {
  8.     return fn();
  9. }
  11. func main() {
  12.     a := 1
  13.     b := 2
  14.     c := executeFn(func() int {
  15.         a += b
  16.         return a
  17.     })
  18.     fmt.Printf("%d %d %d\n", a, b, c)
  19. }

这段代码的输出结果是3 2 3, 熟悉 go 的应该不会感到意外.
main 函数执行 executeFn 函数的汇编代码如下:

  1. hello[0x4a096f] <+47>:  movq   $0x1, 0x40(%rsp)          ; 变量a等于1
  2. hello[0x4a0978] <+56>:  leaq   0x151(%rip), %rax         ; 寄存器rax等于匿名函数main.main.func1的地址
  3. hello[0x4a097f] <+63>:  movq   %rax, 0x60(%rsp)          ; 变量rsp+0x60等于匿名函数的地址
  4. hello[0x4a0984] <+68>:  leaq   0x40(%rsp), %rax          ; 寄存器rax等于变量a的地址
  5. hello[0x4a0989] <+73>:  movq   %rax, 0x68(%rsp)          ; 变量rsp+0x68等于变量a的地址
  6. hello[0x4a098e] <+78>:  movq   $0x2, 0x70(%rsp)          ; 变量rsp+0x70等于2(变量b的值)
  7. hello[0x4a0997] <+87>:  leaq   0x60(%rsp), %rax          ; 寄存器rax等于地址rsp+0x60
  8. hello[0x4a099c] <+92>:  movq   %rax, (%rsp)              ; 第一个参数等于地址rsp+0x60
  9. hello[0x4a09a0] <+96>:  callq  0x4a08f0                  ; 执行main.executeFn
  10. hello[0x4a09a5] <+101>: movq   0x8(%rsp), %rax           ; 寄存器rax等于返回值

我们可以看到传给 executeFn 的是一个指针, 指针指向的内容是[匿名函数的地址, 变量 a 的地址, 变量 b 的值].
变量 a 传地址的原因是匿名函数中对 a 进行了修改, 需要反映到原来的 a 上.
executeFn 函数执行闭包的汇编代码如下:

  1. hello[0x4a08ff] <+15>: subq   $0x10, %rsp                ; 在栈上分配0x10的空间
  2. hello[0x4a0903] <+19>: movq   %rbp, 0x8(%rsp)            ; 把原来的寄存器rbp移到变量rsp+0x8
  3. hello[0x4a0908] <+24>: leaq   0x8(%rsp), %rbp            ; 把变量rsp+0x8的地址移到寄存器rbp
  4. hello[0x4a090d] <+29>: movq   0x18(%rsp), %rdx           ; 把第一个参数(闭包)的指针移到寄存器rdx
  5. hello[0x4a0912] <+34>: movq   (%rdx), %rax               ; 把闭包中函数的指针移到寄存器rax
  6. hello[0x4a0915] <+37>: callq  *%rax                      ; 调用闭包中的函数
  7. hello[0x4a0917] <+39>: movq   (%rsp), %rax               ; 把返回值移到寄存器rax
  8. hello[0x4a091b] <+43>: movq   %rax, 0x20(%rsp)           ; 把寄存器rax移到返回值中(参数后面)
  9. hello[0x4a0920] <+48>: movq   0x8(%rsp), %rbp            ; 把变量rsp+0x8的值恢复寄存器rbp(恢复原rbp)
  10. hello[0x4a0925] <+53>: addq   $0x10, %rsp                ; 释放栈空间
  11. hello[0x4a0929] <+57>: retq                              ; 从函数返回

可以看到调用闭包时参数并不通过栈传递, 而是通过寄存器 rdx 传递, 闭包的汇编代码如下:

  1. hello[0x455660] <+0>:  movq   0x8(%rdx), %rax            ; 第一个参数移到寄存器rax(变量a的指针)
  2. hello[0x455664] <+4>:  movq   (%rax), %rcx               ; 把寄存器rax指向的值移到寄存器rcx(变量a的值)
  3. hello[0x455667] <+7>:  addq   0x10(%rdx), %rcx           ; 添加第二个参数到寄存器rcx(变量a的值+变量b的值)
  4. hello[0x45566b] <+11>: movq   %rcx, (%rax)               ; 把寄存器rcx移到寄存器rax指向的值(相加的结果保存回变量a)
  5. hello[0x45566e] <+14>: movq   %rcx, 0x8(%rsp)            ; 把寄存器rcx移到返回结果
  6. hello[0x455673] <+19>: retq                              ; 从函数返回

闭包的传递可以总结如下:

  • 闭包的内容是[匿名函数的地址, 传给匿名函数的参数 (不定长)…]
  • 传递闭包给其他函数时会传递指向 “闭包的内容” 的指针
  • 调用闭包时会把指向 “闭包的内容” 的指针放到寄存器 rdx(在 go 内部这个指针称为 “上下文”)
  • 闭包会从寄存器 rdx 取出参数
  • 如果闭包修改了变量, 闭包中的参数会是指针而不是值, 修改时会修改到原来的位置上

闭包 + goroutine

细心的可能会发现在上面的例子中, 闭包的内容在栈上, 如果不是直接调用 executeFn 而是 go executeFn 呢?
把上面的代码改为go executeFn(func() ...)可以生成以下的汇编代码:

  1. hello[0x455611] <+33>:  leaq   0xb4a8(%rip), %rax        ; 寄存器rax等于类型信息
  2. hello[0x455618] <+40>:  movq   %rax, (%rsp)              ; 第一个参数等于类型信息
  3. hello[0x45561c] <+44>:  callq  0x40d910                  ; 调用runtime.newobject
  4. hello[0x455621] <+49>:  movq   0x8(%rsp), %rax           ; 寄存器rax等于返回值(这里称为新对象a)
  5. hello[0x455626] <+54>:  movq   %rax, 0x28(%rsp)          ; 变量rsp+0x28等于新对象a
  6. hello[0x45562b] <+59>:  movq   $0x1, (%rax)              ; 新对象a的值等于1
  7. hello[0x455632] <+66>:  leaq   0x136e7(%rip), %rcx       ; 寄存器rcx等于类型信息
  8. hello[0x455639] <+73>:  movq   %rcx, (%rsp)              ; 第一个参数等于类型信息
  9. hello[0x45563d] <+77>:  callq  0x40d910                  ; 调用runtime.newobject
  10. hello[0x455642] <+82>:  movq   0x8(%rsp), %rax           ; 寄存器rax等于返回值(这里称为新对象fn)
  11. hello[0x455647] <+87>:  leaq   0x82(%rip), %rcx          ; 寄存器rcx等于匿名函数main.main.func1的地址
  12. hello[0x45564e] <+94>:  movq   %rcx, (%rax)              ; 新对象fn+0的值等于main.main.func1的地址
  13. hello[0x455651] <+97>:  testb  (%rax), %al               ; 确保新对象fn不等于nil
  14. hello[0x455653] <+99>:  movl   0x78397(%rip), %ecx       ; 寄存器ecx等于当前是否启用写屏障
  15. hello[0x455659] <+105>: leaq   0x8(%rax), %rdx           ; 寄存器rdx等于新对象fn+0x8的地址
  16. hello[0x45565d] <+109>: testl  %ecx, %ecx                ; 判断当前是否启用写屏障
  17. hello[0x45565f] <+111>: jne    0x455699                  ; 启用写屏障时调用后面的逻辑
  18. hello[0x455661] <+113>: movq   0x28(%rsp), %rcx          ; 寄存器rcx等于新对象a
  19. hello[0x455666] <+118>: movq   %rcx, 0x8(%rax)           ; 设置新对象fn+0x8的值等于新对象a
  20. hello[0x45566a] <+122>: movq   $0x2, 0x10(%rax)          ; 设置新对象fn+0x10的值等于2(变量b的值)
  21. hello[0x455672] <+130>: movq   %rax, 0x10(%rsp)          ; 第三个参数等于新对象fn(额外参数)
  22. hello[0x455677] <+135>: movl   $0x10, (%rsp)             ; 第一个参数等于0x10(函数+参数的大小)
  23. hello[0x45567e] <+142>: leaq   0x22fb3(%rip), %rax       ; 第二个参数等于一个常量构造体的地址
  24. hello[0x455685] <+149>: movq   %rax, 0x8(%rsp)           ; 这个构造体的类型是funcval, 值是executeFn的地址
  25. hello[0x45568a] <+154>: callq  0x42e690                  ; 调用runtime.newproc创建新的goroutine

我们可以看到 goroutine + 闭包的情况更复杂, 首先 go 会通过逃逸分析算出变量 a 和闭包会逃逸到外面,
这时 go 会在 heap 上分配变量 a 和闭包, 上面调用的两次 newobject 就是分别对变量 a 和闭包的分配.
在创建 goroutine 时, 首先会传入函数 + 参数的大小 (上面是 8+8=16), 然后传入函数 + 参数, 上面的参数即闭包的地址.

m0 和 g0

go 中还有特殊的 M 和 G, 它们是 m0 和 g0.

m0 是启动程序后的主线程, 这个 m 对应的实例会在全局变量 m0 中, 不需要在 heap 上分配,
m0 负责执行初始化操作和启动第一个 g, 在之后 m0 就和其他的 m 一样了.

g0 是仅用于负责调度的 G, g0 不指向任何可执行的函数, 每个 m 都会有一个自己的 g0,
在调度或系统调用时会使用 g0 的栈空间, 全局变量的 g0 是 m0 的 g0.

如果上面的内容都了解, 就可以开始看 golang 的源代码了.

go 程序的入口点是runtime.rt0_go, 流程是:

  • 分配栈空间, 需要 2 个本地变量 + 2 个函数参数, 然后向 8 对齐
  • 把传入的 argc 和 argv 保存到栈上
  • 更新 g0 中的 stackguard 的值, stackguard 用于检测栈空间是否不足, 需要分配新的栈空间
  • 获取当前 cpu 的信息并保存到各个全局变量
  • 调用_cgo_init 如果函数存在
  • 初始化当前线程的 TLS, 设置 FS 寄存器为 m0.tls+8(获取时会 - 8)
  • 测试 TLS 是否工作
  • 设置 g0 到 TLS 中, 表示当前的 g 是 g0
  • 设置 m0.g0 = g0
  • 设置 g0.m = m0
  • 调用runtime.check做一些检查
  • 调用runtime.args保存传入的 argc 和 argv 到全局变量

  • 调用runtime.osinit根据系统执行不同的初始化

    • 这里 (linux x64) 设置了全局变量 ncpu 等于 cpu 核心数量

  • 调用runtime.schedinit执行共同的初始化

    • 这里的处理比较多, 会初始化栈空间分配器, GC, 按 cpu 核心数量或 GOMAXPROCS 的值生成 P 等
    • 生成 P 的处理在procresize中

  • 调用runtime.newproc创建一个新的 goroutine, 指向的是runtime.main

    • runtime.newproc 这个函数在创建普通的 goroutine 时也会使用, 在下面的 “go 的实现” 中会详细讲解

  • 调用runtime·mstart启动 m0

    • 启动后 m0 会不断从运行队列获取 G 并运行, runtime.mstart 调用后不会返回
    • runtime.mstart 这个函数是 m 的入口点 (不仅仅是 m0), 在下面的 “调度器的实现” 中会详细讲解

第一个被调度的 G 会运行runtime.main, 流程是:

  • 标记主函数已调用, 设置 mainStarted = true
  • 启动一个新的 M 执行 sysmon 函数, 这个函数会监控全局的状态并对运行时间过长的 G 进行抢占
  • 要求 G 必须在当前 M(系统主线程) 上执行
  • 调用runtime_init函数
  • 调用gcenable函数
  • 调用 main.init 函数, 如果函数存在
  • 不再要求 G 必须在当前 M 上运行
  • 如果程序是作为 c 的类库编译的, 在这里返回
  • 调用 main.main 函数
  • 如果当前发生了 panic, 则等待 panic 处理
  • 调用 exit(0) 退出程序

G 的定义在这里.
M 的定义在这里.
P 的定义在这里.

G 里面比较重要的成员如下

  • stack: 当前 g 使用的栈空间, 有 lo 和 hi 两个成员
  • stackguard0: 检查栈空间是否足够的值, 低于这个值会扩张栈, 0 是 go 代码使用的
  • stackguard1: 检查栈空间是否足够的值, 低于这个值会扩张栈, 1 是原生代码使用的
  • m: 当前 g 对应的 m
  • sched: g 的调度数据, 当 g 中断时会保存当前的 pc 和 rsp 等值到这里, 恢复运行时会使用这里的值
  • atomicstatus: g 的当前状态
  • schedlink: 下一个 g, 当 g 在链表结构中会使用
  • preempt: g 是否被抢占中
  • lockedm: g 是否要求要回到这个 M 执行, 有的时候 g 中断了恢复会要求使用原来的 M 执行

M 里面比较重要的成员如下

  • g0: 用于调度的特殊 g, 调度和执行系统调用时会切换到这个 g
  • curg: 当前运行的 g
  • p: 当前拥有的 P
  • nextp: 唤醒 M 时, M 会拥有这个 P
  • park: M 休眠时使用的信号量, 唤醒 M 时会通过它唤醒
  • schedlink: 下一个 m, 当 m 在链表结构中会使用
  • mcache: 分配内存时使用的本地分配器, 和 p.mcache 一样 (拥有 P 时会复制过来)
  • lockedg: lockedm 的对应值

P 里面比较重要的成员如下

  • status: p 的当前状态
  • link: 下一个 p, 当 p 在链表结构中会使用
  • m: 拥有这个 P 的 M
  • mcache: 分配内存时使用的本地分配器
  • runqhead: 本地运行队列的出队序号
  • runqtail: 本地运行队列的入队序号
  • runq: 本地运行队列的数组, 可以保存 256 个 G
  • gfree: G 的自由列表, 保存变为_Gdead 后可以复用的 G 实例
  • gcBgMarkWorker: 后台 GC 的 worker 函数, 如果它存在 M 会优先执行它
  • gcw: GC 的本地工作队列, 详细将在下一篇 (GC 篇) 分析

使用 go 命令创建 goroutine 时, go 会把 go 命令编译为对 runtime.newproc 的调用, 堆栈的结构如下:

Golang源码探索(二) 协程的实现原理 - q303248153 - 博客园 - 图12

第一个参数是 funcval + 额外参数的长度, 第二个参数是 funcval, 后面的都是传递给 goroutine 中执行的函数的额外参数.
funcval 的定义在这里, fn 是指向函数机器代码的指针.
runtime.newproc的处理如下:

  • 计算额外参数的地址 argp
  • 获取调用端的地址 (返回地址)pc
  • 使用systemstack调用 newproc1

systemstack会切换当前的 g 到 g0, 并且使用 g0 的栈空间, 然后调用传入的函数, 再切换回原来的 g 和原来的栈空间.
切换到 g0 后会假装返回地址是 mstart, 这样 traceback 的时候可以在 mstart 停止.
这里传给 systemstack 的是一个闭包, 调用时会把闭包的地址放到寄存器 rdx, 具体可以参考上面对闭包的分析.

runtime.newproc1的处理如下:

  • 调用 getg 获取当前的 g, 会编译为读取 FS 寄存器 (TLS), 这里会获取到 g0
  • 设置 g 对应的 m 的 locks++, 禁止抢占
  • 获取 m 拥有的 p

  • 新建一个 g

    • 首先调用gfget从 p.gfree 获取 g, 如果之前有 g 被回收在这里就可以复用
    • 获取不到时调用malg分配一个 g, 初始的栈空间大小是 2K
    • 需要先设置 g 的状态为已中止 (_Gdead), 这样 gc 不会去扫描这个 g 的未初始化的栈
  • 把参数复制到 g 的栈上
  • 把返回地址复制到 g 的栈上, 这里的返回地址是 goexit, 表示调用完目标函数后会调用 goexit

  • 设置 g 的调度数据 (sched)

    • 设置 sched.sp 等于参数 + 返回地址后的 rsp 地址
    • 设置 sched.pc 等于目标函数的地址, 查看gostartcallfn和gostartcall
    • 设置 sched.g 等于 g
  • 设置 g 的状态为待运行 (_Grunnable)

  • 调用runqput把 g 放到运行队列

    • 首先随机把 g 放到 p.runnext, 如果放到 runnext 则入队原来在 runnext 的 g
    • 然后尝试把 g 放到 P 的 “本地运行队列”

    • 如果本地运行队列满了则调用runqputslow把 g 放到 “全局运行队列”

      • runqputslow 会把本地运行队列中一半的 g 放到全局运行队列, 这样下次就可以继续用快速的本地运行队列了

  • 如果当前有空闲的 P, 但是无自旋的 M(nmspinning 等于 0), 并且主函数已执行则唤醒或新建一个 M

    • 这一步非常重要, 用于保证当前有足够的 M 运行 G, 具体请查看上面的 “空闲 M 链表”

    • 唤醒或新建一个 M 会通过wakep函数

      • 首先交换 nmspinning 到 1, 成功再继续, 多个线程同时执行 wakep 只有一个会继续

      • 调用startm函数

        • 调用pidleget从 “空闲 P 链表” 获取一个空闲的 P
        • 调用mget从 “空闲 M 链表” 获取一个空闲的 M

        • 如果没有空闲的 M, 则调用newm新建一个 M

          • newm 会新建一个 m 的实例, m 的实例包含一个 g0, 然后调用 newosproc 动一个系统线程
          • newosproc 会调用syscall clone创建一个新的线程
          • 线程创建后会设置 TLS, 设置 TLS 中当前的 g 为 g0, 然后执行 mstart
        • 调用 notewakeup(&mp.park) 唤醒线程

创建 goroutine 的流程就这么多了, 接下来看看 M 是如何调度的.

M 启动时会调用 mstart 函数, m0 在初始化后调用, 其他的的 m 在线程启动后调用.
mstart函数的处理如下:

  • 调用 getg 获取当前的 g, 这里会获取到 g0
  • 如果 g 未分配栈则从当前的栈空间 (系统栈空间) 上分配, 也就是说 g0 会使用系统栈空间

  • 调用mstart1函数

    • 调用gosave函数保存当前的状态到 g0 的调度数据中, 以后每次调度都会从这个栈地址开始
    • 调用asminit函数, 不做任何事情
    • 调用minit函数, 设置当前线程可以接收的信号 (signal)
    • 调用schedule函数

调用 schedule 函数后就进入了调度循环, 整个流程可以简单总结为:

  1. schedule函数获取g => [必要时休眠] => [唤醒后继续获取] => execute函数执行g => 执行后返回到goexit => 重新执行schedule函数

schedule函数的处理如下:

  • 如果当前 GC 需要停止整个世界（STW), 则调用stopm休眠当前的 M
  • 如果 M 拥有的 P 中指定了需要在安全点运行的函数 (P.runSafePointFn), 则运行它

  • 快速获取待运行的 G, 以下处理如果有一个获取成功后面就不会继续获取

    • 如果当前 GC 正在标记阶段, 则查找有没有待运行的 GC Worker, GC Worker 也是一个 G
    • 为了公平起见, 每 61 次调度从全局运行队列获取一次 G, (一直从本地获取可能导致全局运行队列中的 G 不被运行)
    • 从 P 的本地运行队列中获取 G, 调用runqget函数

  • 快速获取失败时, 调用findrunnable函数获取待运行的 G, 会阻塞到获取成功为止

    • 如果当前 GC 需要停止整个世界（STW), 则调用stopm休眠当前的 M
    • 如果 M 拥有的 P 中指定了需要在安全点运行的函数 (P.runSafePointFn), 则运行它
    • 如果有析构器待运行则使用 “运行析构器的 G”
    • 从 P 的本地运行队列中获取 G, 调用runqget函数
    • 从全局运行队列获取 G, 调用globrunqget函数, 需要上锁
    • 从网络事件反应器获取 G, 函数 netpoll 会获取哪些 fd 可读可写或已关闭, 然后返回等待 fd 相关事件的 G

    • 如果获取不到 G, 则执行Work Stealing

      • 调用runqsteal尝试从其他 P 的本地运行队列盗取一半的 G

    • 如果还是获取不到 G, 就需要休眠 M 了, 接下来是休眠的步骤

      • 再次检查当前 GC 是否在标记阶段, 在则查找有没有待运行的 GC Worker, GC Worker 也是一个 G
      • 再次检查如果当前 GC 需要停止整个世界, 或者 P 指定了需要再安全点运行的函数, 则跳到 findrunnable 的顶部重试
      • 再次检查全局运行队列中是否有 G, 有则获取并返回
      • 释放 M 拥有的 P, P 会变为空闲 (_Pidle) 状态
      • 把 P 添加到 “空闲 P 链表” 中
      • 让 M 离开自旋状态, 这里的处理非常重要, 参考上面的 “空闲 M 链表”
      • 首先减少表示当前自旋中的 M 的数量的全局变量 nmspinning
      • 再次检查所有 P 的本地运行队列, 如果不为空则让 M 重新进入自旋状态, 并跳到 findrunnable 的顶部重试
      • 再次检查有没有待运行的 GC Worker, 有则让 M 重新进入自旋状态, 并跳到 findrunnable 的顶部重试
      • 再次检查网络事件反应器是否有待运行的 G, 这里对 netpoll 的调用会阻塞, 直到某个 fd 收到了事件
      • 如果最终还是获取不到 G, 调用stopm休眠当前的 M
      • 唤醒后跳到 findrunnable 的顶部重试
  • 成功获取到一个待运行的 G

  • 让 M 离开自旋状态, 调用resetspinning, 这里的处理和上面的不一样

    • 如果当前有空闲的 P, 但是无自旋的 M(nmspinning 等于 0), 则唤醒或新建一个 M
    • 上面离开自旋状态是为了休眠 M, 所以会再次检查所有队列然后休眠
    • 这里离开自选状态是为了执行 G, 所以会检查是否有空闲的 P, 有则表示可以再开新的 M 执行 G

  • 如果 G 要求回到指定的 M(例如上面的 runtime.main)

    • 调用startlockedm函数把 G 和 P 交给该 M, 自己进入休眠
    • 从休眠唤醒后跳到 schedule 的顶部重试
  • 调用execute函数执行 G

execute函数的处理如下:

  • 调用 getg 获取当前的 g
  • 把 G 的状态由待运行 (_Grunnable) 改为运行中 (_Grunning)
  • 设置 G 的 stackguard, 栈空间不足时可以扩张
  • 增加 P 中记录的调度次数 (对应上面的每 61 次优先获取一次全局运行队列)
  • 设置 g.m.curg = g
  • 设置 g.m = m

  • 调用gogo函数

    • 这个函数会根据 g.sched 中保存的状态恢复各个寄存器的值并继续运行 g
    • 首先针对 g.sched.ctxt 调用写屏障 (GC 标记指针存活), ctxt 中一般会保存指向[函数 + 参数]的指针
    • 设置 TLS 中的 g 为 g.sched.g, 也就是 g 自身
    • 设置 rsp 寄存器为 g.sched.rsp
    • 设置 rax 寄存器为 g.sched.ret
    • 设置 rdx 寄存器为 g.sched.ctxt (上下文)
    • 设置 rbp 寄存器为 g.sched.rbp
    • 清空 sched 中保存的信息
    • 跳转到 g.sched.pc
    • 因为前面创建 goroutine 的 newproc1 函数把返回地址设为了 goexit, 函数运行完毕返回时将会调用 goexit 函数

g.sched.pc 在 G 首次运行时会指向目标函数的第一条机器指令,
如果 G 被抢占或者等待资源而进入休眠, 在休眠前会保存状态到 g.sched,
g.sched.pc 会变为唤醒后需要继续执行的地址, “保存状态” 的实现将在下面讲解.

目标函数执行完毕后会调用goexit函数, goexit 函数会调用goexit1函数, goexit1 函数会通过mcall调用goexit0函数.
mcall这个函数就是用于实现 “保存状态” 的, 处理如下:

  • 设置 g.sched.pc 等于当前的返回地址
  • 设置 g.sched.sp 等于寄存器 rsp 的值
  • 设置 g.sched.g 等于当前的 g
  • 设置 g.sched.bp 等于寄存器 rbp 的值
  • 切换 TLS 中当前的 g 等于 m.g0
  • 设置寄存器 rsp 等于 g0.sched.sp, 使用 g0 的栈空间
  • 设置第一个参数为原来的 g
  • 设置 rdx 寄存器为指向函数地址的指针 (上下文)
  • 调用指定的函数, 不会返回

mcall 这个函数保存当前的运行状态到 g.sched, 然后切换到 g0 和 g0 的栈空间, 再调用指定的函数.
回到 g0 的栈空间这个步骤非常重要, 因为这个时候 g 已经中断, 继续使用 g 的栈空间且其他 M 唤醒了这个 g 将会产生灾难性的后果.
G 在中断或者结束后都会通过 mcall 回到 g0 的栈空间继续调度, 从 goexit 调用的 mcall 的保存状态其实是多余的, 因为 G 已经结束了.

goexit1 函数会通过 mcall 调用 goexit0 函数, goexit0函数调用时已经回到了 g0 的栈空间, 处理如下:

  • 把 G 的状态由运行中 (_Grunning) 改为已中止 (_Gdead)
  • 清空 G 的成员
  • 调用dropg函数解除 M 和 G 之间的关联
  • 调用gfput函数把 G 放到 P 的自由列表中, 下次创建 G 时可以复用
  • 调用schedule函数继续调度

G 结束后回到 schedule 函数, 这样就结束了一个调度循环.
不仅只有 G 结束会重新开始调度, G 被抢占或者等待资源也会重新进行调度, 下面继续来看这两种情况.

上面我提到了 runtime.main 会创建一个额外的 M 运行sysmon函数, 抢占就是在 sysmon 中实现的.
sysmon 会进入一个无限循环, 第一轮回休眠 20us, 之后每次休眠时间倍增, 最终每一轮都会休眠 10ms.
sysmon 中有 netpool(获取 fd 事件), retake(抢占), forcegc(按时间强制执行 gc), scavenge heap(释放自由列表中多余的项减少内存占用) 等处理.

retake函数负责处理抢占, 流程是:

  • 枚举所有的 P

    • 如果 P 在系统调用中 (_Psyscall), 且经过了一次 sysmon 循环 (20us~10ms), 则抢占这个 P

      • 调用handoffp解除 M 和 P 之间的关联

    • 如果 P 在运行中 (_Prunning), 且经过了一次 sysmon 循环并且 G 运行时间超过 forcePreemptNS(10ms), 则抢占这个 P

      • 调用preemptone函数

        • 设置 g.preempt = true
        • 设置 g.stackguard0 = stackPreempt

为什么设置了 stackguard 就可以实现抢占?
因为这个值用于检查当前栈空间是否足够, go 函数的开头会比对这个值判断是否需要扩张栈.
stackPreempt 是一个特殊的常量, 它的值会比任何的栈地址都要大, 检查时一定会触发栈扩张.

栈扩张调用的是morestack_noctxt函数, morestack_noctxt 函数清空 rdx 寄存器并调用morestack函数.
morestack 函数会保存 G 的状态到 g.sched, 切换到 g0 和 g0 的栈空间, 然后调用newstack函数.
newstack 函数判断 g.stackguard0 等于 stackPreempt, 就知道这是抢占触发的, 这时会再检查一遍是否要抢占:

  • 如果 M 被锁定 (函数的本地变量中有 P), 则跳过这一次的抢占并调用 gogo 函数继续运行 G
  • 如果 M 正在分配内存, 则跳过这一次的抢占并调用 gogo 函数继续运行 G
  • 如果 M 设置了当前不能抢占, 则跳过这一次的抢占并调用 gogo 函数继续运行 G
  • 如果 M 的状态不是运行中, 则跳过这一次的抢占并调用 gogo 函数继续运行 G

即使这一次抢占失败, 因为 g.preempt 等于 true, runtime 中的一些代码会重新设置 stackPreempt 以重试下一次的抢占.
如果判断可以抢占, 则继续判断是否 GC 引起的, 如果是则对 G 的栈空间执行标记处理 (扫描根对象) 然后继续运行,
如果不是 GC 引起的则调用gopreempt_m函数完成抢占.

gopreempt_m 函数会调用goschedImpl函数, goschedImpl 函数的流程是:

  • 把 G 的状态由运行中 (_Grunnable) 改为待运行 (_Grunnable)
  • 调用dropg函数解除 M 和 G 之间的关联
  • 调用globrunqput把 G 放到全局运行队列
  • 调用schedule函数继续调度

因为全局运行队列的优先度比较低, 各个 M 会经过一段时间再去重新获取这个 G 执行,
抢占机制保证了不会有一个 G 长时间的运行导致其他 G 无法运行的情况发生.

在 goroutine 运行的过程中, 有时候需要对资源进行等待, channel 就是最典型的资源.
channel 的数据定义在这里, 其中关键的成员如下:

  • qcount: 当前队列中的元素数量
  • dataqsiz: 队列可以容纳的元素数量, 如果为 0 表示这个 channel 无缓冲区
  • buf: 队列的缓冲区, 结构是环形队列
  • elemsize: 元素的大小
  • closed: 是否已关闭
  • elemtype: 元素的类型, 判断是否调用写屏障时使用
  • sendx: 发送元素的序号
  • recvx: 接收元素的序号
  • recvq: 当前等待从 channel 接收数据的 G 的链表 (实际类型是 sudog 的链表)
  • sendq: 当前等待发送数据到 channel 的 G 的链表 (实际类型是 sudog 的链表)
  • lock: 操作 channel 时使用的线程锁

发送数据到 channel 实际调用的是runtime.chansend1函数, chansend1 函数调用了chansend函数, 流程是:

  • 检查 channel.recvq 是否有等待中的接收者的 G

    • 如果有, 表示 channel 无缓冲区或者缓冲区为空

    • 调用send函数

      • 如果 sudog.elem 不等于 nil, 调用sendDirect函数从发送者直接复制元素
      • 等待接收的 sudog.elem 是指向接收目标的内存的指针, 如果是接收目标是_则 elem 是 nil, 可以省略复制
      • 等待发送的 sudog.elem 是指向来源目标的内存的指针

      • 复制后调用goready恢复发送者的 G

        • 切换到 g0 调用ready函数, 调用完切换回来

          • 把 G 的状态由等待中 (_Gwaiting) 改为待运行 (_Grunnable)
          • 把 G 放到 P 的本地运行队列
          • 如果当前有空闲的 P, 但是无自旋的 M(nmspinning 等于 0), 则唤醒或新建一个 M
    • 从发送者拿到数据并唤醒了 G 后, 就可以从 chansend 返回了

  • 判断是否可以把元素放到缓冲区中

    • 如果缓冲区有空余的空间, 则把元素放到缓冲区并从 chansend 返回

  • 无缓冲区或缓冲区已经写满, 发送者的 G 需要等待

    • 获取当前的 g
    • 新建一个 sudog
    • 设置 sudog.elem = 指向发送内存的指针
    • 设置 sudog.g = g
    • 设置 sudog.c = channel
    • 设置 g.waiting = sudog
    • 把 sudog 放入 channel.sendq

    • 调用goparkunlock函数

      • 调用gopark函数

        • 通过mcall函数调用park_m函数

          • mcall 函数和上面说明的一样, 会把当前的状态保存到 g.sched, 然后切换到 g0 和 g0 的栈空间并执行指定的函数
          • park_m 函数首先把 G 的状态从运行中 (_Grunning) 改为等待中 (_Gwaiting)
          • 然后调用dropg函数解除 M 和 G 之间的关联
          • 再调用传入的解锁函数, 这里的解锁函数会对解除 channel.lock 的锁定
          • 最后调用schedule函数继续调度

  • 从这里恢复表示已经成功发送或者 channel 已关闭

    • 检查 sudog.param 是否为 nil, 如果为 nil 表示 channel 已关闭, 抛出 panic
    • 否则释放 sudog 然后返回

从 channel 接收数据实际调用的是runtime.chanrecv1函数, chanrecv1 函数调用了chanrecv函数, 流程是:

  • 检查 channel.sendq 中是否有等待中的发送者的 G

    • 如果有, 表示 channel 无缓冲区或者缓冲区已满, 这两种情况需要分别处理 (为了保证入出队顺序一致)

    • 调用recv函数

      • 如果无缓冲区, 调用recvDirect函数把元素直接复制给接收者

      • 如果有缓冲区代表缓冲区已满

        • 把队列中下一个要出队的元素直接复制给接收者
        • 把发送的元素复制到队列中刚才出队的位置
        • 这时候缓冲区仍然是满的, 但是发送序号和接收序号都会增加 1
      • 复制后调用goready恢复接收者的 G, 处理同上
    • 把数据交给接收者并唤醒了 G 后, 就可以从 chanrecv 返回了

  • 判断是否可以从缓冲区获取元素

    • 如果缓冲区有元素, 则直接取出该元素并从 chanrecv 返回

  • 无缓冲区或缓冲区无元素, 接收者的 G 需要等待

    • 获取当前的 g
    • 新建一个 sudog
    • 设置 sudog.elem = 指向接收内存的指针
    • 设置 sudog.g = g
    • 设置 sudog.c = channel
    • 设置 g.waiting = sudog
    • 把 sudog 放入 channel.recvq
    • 调用goparkunlock函数, 处理同上

  • 从这里恢复表示已经成功接收或者 channel 已关闭

    • 检查 sudog.param 是否为 nil, 如果为 nil 表示 channel 已关闭
    • 和发送不一样的是接收不会抛 panic, 会通过返回值通知 channel 已关闭
    • 释放 sudog 然后返回

关闭 channel 实际调用的是closechan函数, 流程是:

  • 设置 channel.closed = 1
  • 枚举 channel.recvq, 清零它们 sudog.elem, 设置 sudog.param = nil
  • 枚举 channel.sendq, 设置 sudog.elem = nil, 设置 sudog.param = nil
  • 调用goready函数恢复所有接收者和发送者的 G

可以看到如果 G 需要等待资源时,
会记录 G 的运行状态到 g.sched, 然后把状态改为等待中 (_Gwaiting), 再让当前的 M 继续运行其他 G.
等待中的 G 保存在哪里, 什么时候恢复是等待的资源决定的, 上面对 channel 的等待会让 G 放到 channel 中的链表.

对网络资源的等待可以看 netpoll 相关的处理, netpoll 在不同系统中的处理都不一样, 有兴趣的可以自己看看.

https://github.com/golang/go
https://golang.org/s/go11sched
http://supertech.csail.mit.edu/papers/steal.pdf
https://docs.google.com/document/d/1ETuA2IOmnaQ4j81AtTGT40Y4_Jr6_IDASEKg0t0dBR8/edit#heading=h.x4kziklnb8fr
https://blog.altoros.com/golang-part-1-main-concepts-and-project-structure.html
https://blog.altoros.com/golang-internals-part-2-diving-into-the-go-compiler.html
https://blog.altoros.com/golang-internals-part-3-the-linker-and-object-files.html
https://blog.altoros.com/golang-part-4-object-files-and-function-metadata.html
https://blog.altoros.com/golang-internals-part-5-runtime-bootstrap-process.html
https://blog.altoros.com/golang-internals-part-6-bootstrapping-and-memory-allocator-initialization.html
http://blog.rchapman.org/posts/Linux_System_Call_Table_for_x86_64
http://legendtkl.com/categories/golang
http://www.cnblogs.com/diegodu/p/5803202.html
https://www.douban.com/note/300631999/
http://morsmachine.dk/go-scheduler

legendtkl 很早就已经开始写 golang 内部实现相关的文章了, 他的文章很有参考价值, 建议同时阅读他写的内容.
morsmachine 写的针对协程的分析也建议参考.
golang 中的协程实现非常的清晰, 在这里要再次佩服 google 工程师的功力, 可以写出这样简单易懂的代码不容易.
https://www.cnblogs.com/zkweb/p/7815600.html