2015上学的时候, golang正在兴起, 参加了一些会议和组织等, 但是工作关系, 一直无缘接触, 在饿了么打算开发分布式文件系统的时候, 也因为自身身体原因提出了离职在家休养, 错过了一次机会. 后来到头条上班, 发现golang承担了主要的系统语言, 重新激起了很强的学习兴趣. – zero.xu

构成

通过proc.go可以知道, golang的调度器实现只要有以下三个部分构成:

  • G: goroutine.
  • M: worker线程, 或者机器.
  • P: 指定Go代码块的资源

关系如下: M必须拥有P来执行Go代码, 但是, M可以在P上被阻塞或者读写的系统调用

个人的理解下来, 是

  • G: golang里面的goroutine代码块, 以及对应的stack等信息
  • M: 对应着操作系统的物理线程
  • P: Goroutine队列, 也称作 logic processor. M执行的时候, 会选择一个P, 然后取出其中的G进行执行

设计的文档: Scalable Go Scheduler Design Doc

设计的思考

proc.go 注释上的详细分析, 个人理解如下: worker线程挂起/唤醒的研究: 一方面, 为了提高并行度尽量多的保持work线程, 一方面, 为了节约cpu和电量, 要挂起运行的worker线程. 为了在这两个方面取得很好的平衡, 我们需要考虑:

  1. 调度状态需要是分布式的(特殊状态下, 可以使用 每个P一个worker 队列), 所以, 不可能快速的计算出全局状态?
  2. 对于最优的线程调度, 我们需要知道未来的状态 (如果一个新的goroutine在不就的未来会被读取, 不要挂起工作线程)

三种被拒绝的方案:

  1. 集中所有的调度器状态, 将抑制可扩展性
  2. 直接goroutine切换, 就是说, 当我们启动一个新的goroutine, 并且有空闲的P, 唤醒一个线程, 并且切换到那个被唤醒的线程和gorouitne. 这将会导致线程状态的频繁变更, 因为刚读取了goroutine的线程在下一刻可能就不工作了(切换到了其他线程), 我们需要唤醒他. 而且, 这也会破坏 计算的本地性 (线程切换的缘故)
  3. 当我们需要开始一个goroutine并且有空闲的P, 唤醒一个额外的线程, 但是不进行切换. 这将导致过度的线程唤醒和挂起, 因为额外的线程在没发现要做的工作的时候, 会被立即唤醒

目前的策略: 当准备一个goroutine的时候, 如果满足下面的条件的时候, 我们会唤醒额外的线程

  1. 有空闲的P, 但是没有自旋的工作线程, 工作线程没有在发现在全局的运行队列或者 netpooller发现工作的时候, 那么, 他就会脱离本地工作, 并进行自旋. 线程的唤醒也是通过自旋实现的; 不使用goroutine切换的策略以避免线程一开始脱离工作. 自选线程在挂起钱会减产每个P运行队列的工作. 如果自旋线程发现了工作, 那么他讲自己脱离自旋状态, 并进行执行. 如果没有发现工作, 那么就离开自旋状态并挂起. 如果至少有一个自旋线程, 当要准备gorouine的时候, 我们就不会挂起唤醒新的线程. 作为补偿, 如果最后的自旋线程发现任务并停止了自旋, 它必须唤醒一个新的自旋线程. 这样的处理方式抚平了线程唤醒的不必要的突刺, 但是同时保证了最终最大的cpu利用率.
    主要的实现的困难是线程 sprinning 自旋 -> non-spinning 非自旋的线程切换. 这种切换会和新的goroutine的提交、唤醒其他的worker线程产生竞态. 如果不能很好的处理这种情况, 我们最终会得到很低的cpu利用率. 针对goroutine启动的通过方式是: 将goroutine 提交到本地工作队列, #StoreLoad-style 的内存屏障, 检查 sched.nmspinning 参数. 自旋->非自旋的转换的通用处理方式是: nmspinning减一, #StoreLoad-style内存屏障, 为了查找新的工作, 检查所有的 每个P的工作队列. 注意, 这些措施并不会运用到全局运行队列, 这样, 我们在提交任务给全局运行队列的时候, 并不会草率的进行线程唤醒.

小结:

  1. 自旋线程的设计来实现线程的唤醒和挂起
  2. 通过检查每个P的运行队列情况来判定是否需要挂起
  3. 最后一个自旋线程处理任务前, 需要唤醒一个新的自旋线程, 保证至少有一个自旋线程.

实现的分析

基本概念

M、P、G的主体设计在 runtime2.go 中, 除去 m、p、g 的关键对象, 其他的讲解如下

  1. 特殊对象

    1. g0: 有调度栈的goroutine, 负责管理任务. 每个m0都有自己的g0, 在调度的时候/系统调用的时候会使用g0的栈空间. g0本身不指向任何可执行函数. 全局变量g0是m0的g0
    2. m0: 启动程序后的主线程, 负责初始化以及第一个g, 之后和其他的m一样了

  2. sudog

    1. sudog表示等待列表中的一个g, 比如在channel上的 sending/receiving. 因为 go<->同步对象之间的关系是多对多的, 需要通过sudog进行维护. 一个可能在多个等待列表上, 这样一个g可能有多个 sudog; 很多g可能在相同的同步对象, 所以一个对象可能有多个sudog. sudog 通过特殊的pool进行分配的, 通过 acquireSudog 和 releaseSudog进行封装. 实现上, 通过双列表结构 pre + next 实现了列表.

  3. schedt 维护了全局的运行队列, sudog结构的集中缓存, 不同大小的defer结构的集中pool

  4. 栈

  5. itab iface eface: interface相关, 后面讲

  6. defer: 后面讲, 有趣的是:defer维护在P上

  7. 状态:

    • g:
    _Gidle _Grunnable _Grunning _Gsyscall _Gwaiting   _Gmoribund_unused _Gdead _Genqueue_unused _Gcopystack _Gscan _Gscanrunnable _Gscanrunning _Gscansyscall _Gscanwaiting

    最后的五种状态和gc有关

    • p: _Pidle _Prunning _Psyscall _Pgcstop _Pdead

调度执行

  1. 初始化: 参考初始化的文章, 在初始化的时候, 会创建 m 执行第一个goroutine任务.
  2. 执行goroutine代码: 新建的goroutine: proc.go#newproc
  3. 阻塞调用 参考 runtime.go#entersyscallblock #reentersyscall
  4. sudog的使用: 分析channel的时候用
  5. 切换 当发生系统调用/M锁住的情况下, 会切换P.#handleoff goready goparkunlock gopark releaseSudog/acquireSudog ready

faq:

  1. 新的goroutine什么时候放入全局队列, 什么时候放入 本地队列呢? 本地队列放不下的时候,
  2. 什么时候实现抢占: sysmon函数, 无限循环 + sleep, 20us开始, sleep延迟*2 倍增, 最大不超过10ms. 处理 netpoll、retake(阻塞在系统调用上的P)、强制gc、内存收缩. 其中retake的实现中, 遍历所有的goroutine, 将连续执行10ms的goroutine的stackguard0设置为stackPreempt, 触发 stack check.

更多参考:golang密集场景下的协程调度饥饿问题

写屏障:

具体参考 runtime2.go

  1. reachable:

    P 和 G 通过 allgs 和 allp 列表的真正的指针或者 栈上变量 (在达到列表前分配的时候)实现了reachable M 通过 allm 和 freem 的真正的指针实现了可达

  2. gc指针 分别使用 gunitptr、munitpter、punitptr 用来传递写屏障.

    1. guintptr 存储了goroutine指针, 并通过 unitptr类型传递了写屏障. gunitptr 在 Gobuf goroutine状态 以及 没有P操作的调度列表中使用

    2. muintptr 不是用来gc追踪的m指针, 因为在释放M的时候, 我们对muintptr做了约束:

      1. 通过安全点不在本地持有 munitptr
      2. muintptr 在堆上必须要被M自己持有, 这样, 在*m被释放的时候, mintptr不会被使用

    3. gobuf的设计, 存储sp, pc. 其中, ctxt 和gc有关, 并通过汇编进行设置和清除, 区别于写屏障. 但是 ctxt 是真实保存的, 活的寄存器, 只会在 真实的寄存器和gobuf之间进行交换. 因此, 在进行stack scanning的时候会被当做root, 也就是说不需要通过写屏障, 是通过汇编进行存储和恢复的. 同时, 他也会被当做指针, 这样其他的Go的写将会得到写屏障

    特殊处理: 在当前P被释放的情况下, 要避免写屏障? 因为GC会认为世界停止了, 而且不可预期的写屏障并不会和GC同步, 会导致 写屏障的半同步 (标记了对象, 但是没有将他放入队列). 如果GC跳过了这些对象并在入队之前完成 可能会发生, 那么 他将会不正确的释放对象. [细节需要参考下GC的设计]