goroutine调度器

你的名字 2021-09-07 06:09 318阅读 0赞

Goroutine是[Go语言][Go]原生支持并发的具体实现，你的Go代码都无一例外地跑在goroutine中（哪怕是go的runtime也不例外）。你可以启动许多甚至成千上万的goroutine，Go的runtime负责对goroutine进行管理。所谓的管理就是“调度”，粗糙地说调度就是决定何时哪个goroutine将获得资源开始执行、哪个goroutine应该停止执行让出资源、哪个goroutine应该被唤醒恢复执行等。goroutine的调度是Go team care的事情，大多数gopher们无需关心。但适当了解一下Goroutine的调度模型和原理，对于编写出更好的go代码是大有裨益的。

# 一、协程介绍 #

## 1、传统资源调度： ##

提到“调度”，我们首先想到的就是操作系统对进程、线程的调度。操作系统调度器会将系统中的多个线程按照一定算法调度到物理CPU上去运行。传统的编程语言比如C、C++等的并发实现实际上就是基于操作系统调度的，即程序负责创建线程(一般通过pthread等lib调用实现)，操作系统负责调度。这种传统支持并发的方式有诸多不足：（详见：[https://blog.csdn.net/liuxiao723846/article/details/113574739][https_blog.csdn.net_liuxiao723846_article_details_113574739]）

**复杂：**

*  创建容易，退出难：做过C/C++ Programming的童鞋都知道，创建一个thread(比如利用pthread)虽然参数也不少，但好歹可以接受。但一旦涉及到thread的退出，就要考虑thread是detached，还是需要parent thread去join？是否需要在thread中设置cancel point，以保证join时能顺利退出？
 *  并发单元间通信困难，易错：多个thread之间的通信虽然有多种机制可选，但用起来是相当复杂；并且一旦涉及到shared memory，就会用到各种lock，死锁便成为家常便饭；
 *  thread stack size的设定：是使用默认的，还是设置的大一些，或者小一些呢？

**难于Scaling：**

*  一个thread的代价已经比进程小了很多了，但我们依然不能大量创建thread，因为除了每个thread占用的资源不小之外，操作系统调度切换thread的代价也不小；
 *  对于很多网络服务程序，由于不能大量创建thread，就要在少量thread里做网络多路复用，即：使用epoll/kqueue/IoCompletionPort这套机制，即便有libevent/libev这样的第三方库帮忙，写起这样的程序也是很不易的，存在大量callback，给程序员带来不小的心智负担。

为此，Go采用了用户层轻量级thread或者说是coroutine（协程）的概念来解决这些问题，Go将之称为”goroutine“。goroutine占用的资源非常小(Go 1.4将每个goroutine stack的size默认设置为2k，而线程是8M)，goroutine调度的切换也不用陷入(trap)操作系统内核层完成，代价很低。因此，一个Go程序中可以创建成千上万个并发的goroutine。

不过，一个Go程序对于操作系统来说只是一个用户层程序，对于操作系统而言，它的眼中只有thread，它甚至不知道有什么叫Goroutine的东西的存在。goroutine的调度全要靠Go自己完成，实现Go程序内goroutine之间“公平”的竞争“CPU”资源，这个任务就落到了Go runtime头上，要知道在一个Go程序中，除了用户代码，剩下的就是go runtime了。

于是Goroutine的调度问题就演变为go runtime如何将程序内的众多goroutine按照一定算法调度到“CPU”资源上运行了。在操作系统层面，Thread竞争的“CPU”资源是真实的物理CPU，但在Go程序层面，各个Goroutine要竞争的”CPU”资源是什么呢？Go程序是用户层程序，它本身整体是运行在一个或多个操作系统线程上的，因此goroutine们要竞争的所谓“CPU”资源就是操作系统线程。这样Go scheduler的任务就明确了：将goroutines按照一定算法放到不同的操作系统线程中去执行。这种在语言层面自带调度器的，我们称之为原生支持并发。

## 2、go的并发模型： ##

Go实现了两种并发形式。第一种是大家普遍认知的：多线程共享内存，也是Java或者C++等语言中的多线程开发。另外一种是Go语言特有的，也是Go语言推荐的：CSP（communicating sequential processes，通信序列进程）并发模型。

### 2.1）共享内存并发： ###

普通的线程并发模型，就是像Java、C++、或者Python，他们线程间通信都是通过共享内存的方式来进行的。非常典型的方式就是，在访问共享数据（例如数组、Map、或者某个结构体或对象）的时候，通过锁来访问，因此在很多时候，衍生出一种方便操作的数据结构，叫做“线程安全的数据结构”。例如Java提供的包”java.util.concurrent”中的数据结构。Go中也实现了传统的线程并发模型。

### 2.2）CSP： ###

CSP并发模型是在1970年左右提出的概念，属于比较新的概念，不同于传统的多线程通过共享内存来通信，CSP讲究的是“以通信的方式来共享内存”。请记住下面这句话：DO NOT COMMUNICATE BY SHARING MEMORY; INSTEAD, SHARE MEMORY BY COMMUNICATING.“不要以共享内存的方式来通信，相反，要通过通信来共享内存。”

Go的CSP并发模型，是通过goroutine和channel来实现的：

*  goroutine 是Go语言中并发的执行单位。有点抽象，其实就是和传统概念上的”线程“类似，可以理解为”线程“。
 *  channel 是Go语言中各个并发结构体(goroutine)之前的通信机制。 通俗的讲，就是各个goroutine之间通信的”管道“，有点类似于Linux中的管道。

在go语言中，生成一个goroutine非常简单，直接go一下就可以：go f();

通信机制channel也很方便，传数据用channel <- data，取数据用<-channel。

# 二、Go调度器模型演化 #

操作系统根据资源访问权限的不同，体系架构可分为用户空间和内核空间。内核空间主要操作访问CPU资源、I/O资源、内存资源等硬件资源，为上层应用程序提供最基本的基础资源；用户空间就是上层应用程序的固定活动空间，用户空间不可以直接访问资源，必须通过“系统调用”、“库函数”或“Shell脚本”来调用内核空间提供的资源。

无论语言层面何种并发模型，到了操作系统层面，一定是以线程的形态存在的，在操作系统上的线程模型有以下三种：

1.  多对一(M:1)的用户级线程模型
2.  一对一(1:1)的内核级线程模型
3.  多对多(M:N)的两级线程模型（混合模型）

可以简单认为，Go语言的Goroutine调度器就是一种特殊的两级线程模型（GPM调度模型）。

## 1、G-M模型 ##

2012年3月28日，Go 1.0正式发布。在这个版本中，Go team实现了一个简单的调度器。在这个调度器中，每个goroutine对应于runtime中的一个抽象结构：G，而os thread作为“物理CPU”的存在而被抽象为一个结构：M(machine)。这个结构虽然简单，但是却存在着许多问题。前Intel blackbelt工程师、现Google工程师[Dmitry Vyukov][]在其[《Scalable Go Scheduler Design》][Scalable Go Scheduler Design]一文中指出了G-M模型的一个重要不足： 限制了Go并发程序的伸缩性，尤其是对那些有高吞吐或并行计算需求的服务程序。主要体现在如下几个方面：

*  单一全局互斥锁(Sched.Lock)和集中状态存储的存在导致所有goroutine相关操作，比如：创建、重新调度等都要上锁；
 *  goroutine传递问题：M经常在M之间传递”可运行”的goroutine，这导致调度延迟增大以及额外的性能损耗；
 *  每个M做内存缓存，导致内存占用过高，数据局部性较差；
 *  由于syscall调用而形成的剧烈的worker thread阻塞和解除阻塞，导致额外的性能损耗。

## 2、G-P-M模型 ##

于是Dmitry Vyukov亲自操刀改进Go scheduler，在[Go 1.1][]中实现了G-P-M调度模型和[work stealing][]算法，这个模型一直沿用至今：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXhpYW83MjM4NDY_size_16_color_FFFFFF_t_70][]

有名人曾说过：“计算机科学领域的任何问题都可以通过增加一个间接的中间层来解决”，我觉得Dmitry Vyukov的G-P-M模型恰是这一理论的践行者。Dmitry Vyukov通过向G-M模型中增加了一个P，实现了Go scheduler的scalable。

P是一个“逻辑Proccessor”，每个G要想真正运行起来，首先需要被分配一个P（进入到P的local runq中，这里暂忽略global runq那个环节）。对于G来说，P就是运行它的“CPU”，可以说：G的眼里只有P。但从Go scheduler视角来看，真正的“CPU”是M，只有将P和M绑定才能让P的runq中G得以真实运行起来。这样的P与M的关系，就好比Linux操作系统调度层面用户线程(user thread)与核心线程(kernel thread)的对应关系那样(N x M)。

## 3、抢占式调度问题 ##

G-P-M模型的实现算是Go scheduler的一大进步，但Scheduler仍然有一个头疼的问题，那就是不支持抢占式调度，导致一旦某个G中出现死循环或永久循环的代码逻辑，那么G将永久占用分配给它的P和M，位于同一个P中的其他G将得不到调度，出现“饿死”的情况。更为严重的是，当只有一个P时(GOMAXPROCS=1)时，整个Go程序中的其他G都将“饿死”。于是Dmitry Vyukov又提出了[《Go Preemptive Scheduler Design》][Go Preemptive Scheduler Design]并在[Go 1.2][]中实现了“抢占式”调度。

这个抢占式调度的原理则是在每个函数或方法的入口，加上一段额外的代码，让runtime有机会检查是否需要执行抢占调度。这种解决方案只能说局部解决了“饿死”问题，对于没有函数调用，纯算法循环计算的G，scheduler依然无法抢占。

## 4、NUMA调度模型 ##

从Go 1.2以后，Go似乎将重点放在了对GC的低延迟的优化上了，对scheduler的优化和改进似乎不那么热心了，只是伴随着GC的改进而作了些小的改动。Dmitry Vyukov在2014年9月提出了一个新的proposal design doc：[《NUMA‐aware scheduler for Go》][Go Preemptive Scheduler Design]，作为未来Go scheduler演进方向的一个提议，不过至今似乎这个proposal也没有列入开发计划。

## 5、其他优化 ##

Go runtime已经实现了**netpoller**，这使得即便G发起网络I/O操作也不会导致M被阻塞（仅阻塞G），从而不会导致大量M被创建出来。但是对于regular file的I/O操作一旦阻塞，那么M将进入sleep状态，等待I/O返回后被唤醒；这种情况下P将与sleep的M分离，再选择一个idle的M。如果此时没有idle的M，则会新创建一个M，这就是为何大量I/O操作导致大量Thread被创建的原因。

I[an Lance Taylor][]在[Go 1.9][] dev周期中增加了一个[Poller for os package][]的功能，这个功能可以像netpoller那样，在G操作支持pollable的fd时，仅阻塞G，而不阻塞M。不过该功能依然不能对regular file有效，regular file不是pollable的。不过，对于scheduler而言，这也算是一个进步了。

# 三、详细理解G-P-M #

1、G、P、M：

*  M指的是Machine，一个M直接关联了一个内核线程，由操作系统管理。
 *  P指的是”processor”，代表了M所需的上下文环境，也是处理用户级代码逻辑的处理器。它负责衔接M和G的调度上下文，将等待执行的G与M对接。
 *  G指的是Goroutine，其实本质上也是一种轻量级的线程，包括了调用栈，重要的调度信息，例如channel等。

P的数量由环境变量中的GOMAXPROCS决定（通常来说它是和核心数对应）。G会有很多个，每个P会将Goroutine从一个就绪的队列中做Pop操作，为了减小锁的竞争，通常情况下每个P会负责一个队列(local queue)。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXhpYW83MjM4NDY_size_16_color_FFFFFF_t_70 1][]

## 2、G被抢占调度： ##

和操作系统按时间片调度线程不同，Go并没有时间片的概念。如果某个G没有进行system call调用、没有进行I/O操作、没有阻塞在一个channel操作上，那么m是如何让G停下来并调度下一个runnable G的呢？答案是：G是被抢占调度的。

前面说过，除非极端的无限循环或死循环，否则只要G调用函数，Go runtime就有抢占G的机会。Go程序启动时，runtime会去启动一个名为**sysmon**的m(一般称为监控线程)，该m无需绑定p即可运行，该m在整个Go程序的运行过程中至关重要，sysmon每20us~10ms启动一次，主要完成如下工作：

*  释放闲置超过5分钟的span物理内存；
 *  如果超过2分钟没有垃圾回收，强制执行；
 *  将长时间未处理的netpoll结果添加到任务队列；
 *  向长时间运行的G任务发出抢占调度；
 *  收回因syscall长时间阻塞的P；

## 3、阻塞时的调度： ##

### 3.1）channel阻塞或network I/O情况下的调度： ###

如果G被阻塞在某个channel操作或network I/O操作上时，G会被放置到某个wait队列中，而M会尝试运行下一个runnable的G；如果此时没有runnable的G供m运行，那么m将解绑P，并进入sleep状态。当I/O available或channel操作完成，在wait队列中的G会被唤醒，标记为runnable，放入到某P的队列中（local queue），绑定一个M继续执行。

注：由于netpoller，即使G发生了network I/O，也不会阻塞M；

### 3.2）system call阻塞情况下的调度： ###

**这里就体现出了P的价值**：当遇到内核线程阻塞的时候，p让我们可以直接放开其他线程。

如果G被阻塞在某个system call操作上，那么不光G会阻塞，执行该G的M也会解绑P(实质是被sysmon抢走了)，M与G一起进入sleep状态。如果此时有idle的M，则P与其绑定继续执行其他G；如果没有idle M，但仍然有其他G要去执行，那么就会创建一个新M。

当阻塞在syscall上的G完成syscall调用后，G会去尝试获取一个可用的P，如果没有可用的P，那么将G放入全局队列，之前的那个sleep的M将再次进入sleep。

看一个例子：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXhpYW83MjM4NDY_size_16_color_FFFFFF_t_70 2][]

1.  当G0发生系统调用sysall，一个线程肯定不能同时执行代码和系统调用被阻塞，这时M0需要放弃当前的上下文环境P，以便可以让其他的Goroutine被调度执行，此时：M0和G0进入sleep，同时创建一个新的M1（也可能是缓存的）接管p，继续执行其他G。
2.  当系统调用syscall结束后，M0会“偷”一个可用的上下文P，如果不成功，M0就把它的Gouroutine G0放到一个全局的runqueue中，将自己置于线程缓存中并进入休眠状态。全局runqueue是各个P在运行完自己的本地的Goroutine runqueue后用来拉取新goroutine的地方。P也会周期性的检查这个全局runqueue上的goroutine，否则，全局runqueue上的goroutines可能得不到执行而饿死。

## 4、工作窃取： ##

按照以上的说法，上下文P会定期的检查全局的goroutine 队列中的goroutine，以便自己在消费掉自身Goroutine队列的时候有事可做。假如全局goroutine队列中的goroutine也没了呢？就从其他运行的中的P的runqueue里偷。

每个P中的Goroutine不同导致他们运行的效率和时间也不同，在一个有很多P和M的环境中，不能让一个P跑完自身的Goroutine就没事可做了，因为或许其他的P有很长的goroutine队列要跑，得需要均衡。

该如何解决呢？Go的做法倒也直接，从其他P中偷一半！

**补充：**在goroutine模型中，有以下几类队列，它们都是用来存放goroutine的：

*  local queue：本地队列，每一个p负责一个local queue；每有一个go语句被执行，local queue就在其末尾加入一个goroutine，一旦上下文运行goroutine直到调度点，它会从其local queue中弹出goroutine，设置堆栈和指令指针并开始运行goroutine。
 *  global queue：全局队列，当goroutine发生system call阻塞后，M和P解绑，同时将G放到global queu中；
 *  wait queue：等待队列，当G发生了channel 阻塞或者network 阻塞，G会被放入wait queue，M继续出来local queue中的下一个G；

[https://tonybai.com/2017/06/23/an-intro-about-goroutine-scheduler/][https_tonybai.com_2017_06_23_an-intro-about-goroutine-scheduler]

[https://segmentfault.com/a/1190000018150987][https_segmentfault.com_a_1190000018150987]

[Go]: https://golang.org/
[https_blog.csdn.net_liuxiao723846_article_details_113574739]: https://blog.csdn.net/liuxiao723846/article/details/113574739
[Dmitry Vyukov]: https://github.com/dvyukov
[Scalable Go Scheduler Design]: https://docs.google.com/document/d/1TTj4T2JO42uD5ID9e89oa0sLKhJYD0Y_kqxDv3I3XMw/edit#!
[Go 1.1]: https://golang.org/doc/go1.1
[work stealing]: http://supertech.csail.mit.edu/papers/steal.pdf
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXhpYW83MjM4NDY_size_16_color_FFFFFF_t_70]: /images/20210511/35dff5ef0920426ab99badb6e6427e28.png
[Go Preemptive Scheduler Design]: https://docs.google.com/document/u/0/d/1d3iI2QWURgDIsSR6G2275vMeQ_X7w-qxM2Vp7iGwwuM/pub
[Go 1.2]: https://blog.golang.org/go12
[an Lance Taylor]: https://github.com/ianlancetaylor
[Go 1.9]: https://golang.org/doc/go1.9
[Poller for os package]: https://groups.google.com/forum/#!topic/golang-dev/tT8SoKfHty0
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXhpYW83MjM4NDY_size_16_color_FFFFFF_t_70 1]: /images/20210511/dd18d00ad5dd4414915f71e0428d1165.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXhpYW83MjM4NDY_size_16_color_FFFFFF_t_70 2]: /images/20210511/4c1932f4ebd740ad81c2e3141408ec4e.png
[https_tonybai.com_2017_06_23_an-intro-about-goroutine-scheduler]: https://tonybai.com/2017/06/23/an-intro-about-goroutine-scheduler/
[https_segmentfault.com_a_1190000018150987]: https://segmentfault.com/a/1190000018150987