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:

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

package main

import (
    "fmt"
    "time"
)

func printNumber(from, to int, c chan int) {
    for x := from; x <= to; x   {
        fmt.Printf("%d\n", x)
        time.Sleep(1 * time.Millisecond)
    }
    c <- 0
}

func main() {
    c := make(chan int, 3)
    go printNumber(1, 3, c)
    go printNumber(4, 6, c)
    _ = <- c
    _ = <- c
}

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

M会取得这个G并运行:

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

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

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

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

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

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

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

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

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

fatal error: all goroutines are asleep - deadlock!

开始代码分析

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

汇编代码

从以下的go代码:

package main

import (
    "fmt"
    "time"
)

func printNumber(from, to int, c chan int) {
    for x := from; x <= to; x   {
        fmt.Printf("%d\n", x)
        time.Sleep(1 * time.Millisecond)
    }
    c <- 0
}

func main() {
    c := make(chan int, 3)
    go printNumber(1, 3, c)
    go printNumber(4, 6, c)
    _, _ = <- c, <- c
}

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

(lldb) di -n main.main
hello`main.main:
hello[0x401190] < 0>:   movq   %fs:-0x8, %rcx
hello[0x401199] < 9>:   cmpq   0x10(%rcx), %rsp
hello[0x40119d] < 13>:  jbe    0x401291                  ; < 257> at hello.go:16
hello[0x4011a3] < 19>:  subq   $0x40, %rsp
hello[0x4011a7] < 23>:  leaq   0xb3632(%rip), %rbx       ; runtime.rodata   38880
hello[0x4011ae] < 30>:  movq   %rbx, (%rsp)
hello[0x4011b2] < 34>:  movq   $0x3, 0x8(%rsp)
hello[0x4011bb] < 43>:  callq  0x4035a0                  ; runtime.makechan at chan.go:49
hello[0x4011c0] < 48>:  movq   0x10(%rsp), %rax
hello[0x4011c5] < 53>:  movq   $0x1, 0x10(%rsp)
hello[0x4011ce] < 62>:  movq   $0x3, 0x18(%rsp)
hello[0x4011d7] < 71>:  movq   %rax, 0x38(%rsp)
hello[0x4011dc] < 76>:  movq   %rax, 0x20(%rsp)
hello[0x4011e1] < 81>:  movl   $0x18, (%rsp)
hello[0x4011e8] < 88>:  leaq   0x129c29(%rip), %rax      ; main.printNumber.f
hello[0x4011ef] < 95>:  movq   %rax, 0x8(%rsp)
hello[0x4011f4] < 100>: callq  0x430cd0                  ; runtime.newproc at proc.go:2657
hello[0x4011f9] < 105>: movq   $0x4, 0x10(%rsp)
hello[0x401202] < 114>: movq   $0x6, 0x18(%rsp)
hello[0x40120b] < 123>: movq   0x38(%rsp), %rbx
hello[0x401210] < 128>: movq   %rbx, 0x20(%rsp)
hello[0x401215] < 133>: movl   $0x18, (%rsp)
hello[0x40121c] < 140>: leaq   0x129bf5(%rip), %rax      ; main.printNumber.f
hello[0x401223] < 147>: movq   %rax, 0x8(%rsp)
hello[0x401228] < 152>: callq  0x430cd0                  ; runtime.newproc at proc.go:2657
hello[0x40122d] < 157>: movq   $0x0, 0x30(%rsp)
hello[0x401236] < 166>: leaq   0xb35a3(%rip), %rbx       ; runtime.rodata   38880
hello[0x40123d] < 173>: movq   %rbx, (%rsp)
hello[0x401241] < 177>: movq   0x38(%rsp), %rbx
hello[0x401246] < 182>: movq   %rbx, 0x8(%rsp)
hello[0x40124b] < 187>: leaq   0x30(%rsp), %rbx
hello[0x401250] < 192>: movq   %rbx, 0x10(%rsp)
hello[0x401255] < 197>: callq  0x4043c0                  ; runtime.chanrecv1 at chan.go:354
hello[0x40125a] < 202>: movq   $0x0, 0x28(%rsp)
hello[0x401263] < 211>: leaq   0xb3576(%rip), %rbx       ; runtime.rodata   38880
hello[0x40126a] < 218>: movq   %rbx, (%rsp)
hello[0x40126e] < 222>: movq   0x38(%rsp), %rbx
hello[0x401273] < 227>: movq   %rbx, 0x8(%rsp)
hello[0x401278] < 232>: leaq   0x28(%rsp), %rbx
hello[0x40127d] < 237>: movq   %rbx, 0x10(%rsp)
hello[0x401282] < 242>: callq  0x4043c0                  ; runtime.chanrecv1 at chan.go:354
hello[0x401287] < 247>: movq   0x28(%rsp), %rbx
hello[0x40128c] < 252>: addq   $0x40, %rsp
hello[0x401290] < 256>: retq   
hello[0x401291] < 257>: callq  0x4538d0                  ; runtime.morestack_noctxt at asm_amd64.s:365
hello[0x401296] < 262>: jmp    0x401190                  ; < 0> at hello.go:16
hello[0x40129b] < 267>: int3   
hello[0x40129c] < 268>: int3   
hello[0x40129d] < 269>: int3   
hello[0x40129e] < 270>: int3   
hello[0x40129f] < 271>: int3   

(lldb) di -n main.printNumber
hello`main.printNumber:
hello[0x401000] < 0>:   movq   %fs:-0x8, %rcx
hello[0x401009] < 9>:   leaq   -0x8(%rsp), %rax
hello[0x40100e] < 14>:  cmpq   0x10(%rcx), %rax
hello[0x401012] < 18>:  jbe    0x401185                  ; < 389> at hello.go:8
hello[0x401018] < 24>:  subq   $0x88, %rsp
hello[0x40101f] < 31>:  xorps  %xmm0, %xmm0
hello[0x401022] < 34>:  movups %xmm0, 0x60(%rsp)
hello[0x401027] < 39>:  movq   0x90(%rsp), %rax
hello[0x40102f] < 47>:  movq   0x98(%rsp), %rbp
hello[0x401037] < 55>:  cmpq   %rbp, %rax
hello[0x40103a] < 58>:  jg     0x40112f                  ; < 303> at hello.go:13
hello[0x401040] < 64>:  movq   %rax, 0x40(%rsp)
hello[0x401045] < 69>:  movq   %rax, 0x48(%rsp)
hello[0x40104a] < 74>:  xorl   
您可能感兴趣的文章：

                   go 协程

                   探索Golang协程实现——从v1.0开始

                   Go test实现原理前言

                   Golang的魅力

                   GO 互斥锁实现原理剖析

                   Go 并发编程的思考

                   go 协程的实现笔记

                   Golang之高并发原理

                   深入浅出Golang Runtime

                   golang debug 配置_缓存击穿导致 golang 组件死锁的问题分享