协程调度器的由来

单进程时代

早期的操作系统为单进程,按照时间轴顺序执行进程,同一时刻只可以执行一个进程。

但是单进程也会遇到一些问题,比如效率低,只能一个任务一个任务的处理;可能会遇到阻塞问题

多线程/多进程操作系统

并发

此时就需要引入CPU调度器。

比如存在多个进程,调度器可以按照时间分为一个个的时间片,划分给不同进程,对于一个进程,如果超过了时间片,就会强制停止,切换下一个进程,然后等待它的下一个时间片。这么做虽然看起来断断续续进行,但是在宏观上是连续的。

这么做可以达到并发的效果,同时也解决了阻塞的问题,当一个进程阻塞时,就切换下一个进程。

但是这么做也存在问题,既然要切换进程,就要保存当前进程的状态,同时切换也会存在时间成本,这个问题就会使进程/线程的数量越多,切换的成本就会越大,也就越浪费。此外,多线程也会使开发变得更加复杂,就要涉及到竞争之类的领域。

并发还会造成高消耗调度CPU,高内存占用等问题。

用户/内核空间

对于一个线程,操作系统把它分为了用户空间和内核空间,内核空间用来处理系统相关,比如IO操作,内存相关,而用户空间用来处理用户的代码。操作系统只可以看到内核空间。

1:1模型

在标准情况下,用户空间和内核空间的数量对应关系1:1对应的,这也是最标准的线程模型

N:1模型

既然对于操作系统而言,只可以看到内核空间,那么可以想到这么一种优化:在一个线程之中,创建多个协程,再设置一个协程调度器,像CPU调度器一样轮询各个协程,这样可以起到优化的作用。

但是这么做又会出现阻塞的问题,如果一个协程运行出错,就会让后面的协程堵塞,影响效率。同时也利用不了多核系统的加速能力。

N:M模型

使用N:M模型就可以有效利用多核优势。

所以事实上使用的是这种N:M模型,这样就把程序的瓶颈设置在了协程调度器上面,一个语言协程调度器做得越好,效率就越高。

协程调度器的优化

在golang中,协程(co-routing)被称之为(gorouting)

gorouting的优化做的很到位,内存占用小,只有几KB,可以大量开辟,同时切换成本低,可以灵活调度。

早期的GO调度器

早期的Go调度器做的很拉跨,使用了一个全局的Go队列,M需要使用G是需要进行轮询。

M想要执行、放回G都必须访问全局G队列,并且M有多个 ,即多线程访问同一资源需要加锁进行保证互斥/同步,所以全局G队列是有互斥锁进行保护的。

老调度器有几个缺点:

  1. 创建、销毁、调度G都需要每个M获取锁,这就形成了激烈的锁竞争
  2. M转移G会造成延迟和额外的系统负载。比如当G中包含创建新协程的时候,M创建了G’,为了继续执行G,需要把G’交给M’执行,也造成了很差的局部性,因为G’和G是相关的,最好放在M上执行,而不是其他M’。
  3. 系统调用(CPU在M之间的切换)导致频繁的线程阻塞和取消阻塞操作增加了系统开销。

Goroutine调度器的GMP模型

在Golang中,除了M(thread)和G(goroutine),还引入了P(Processor)

Processor,它包含了运行goroutine的资源,如果线程想运行goroutine,必须先获取P,P中还包含了可运行的G队列。

GMP模型

在Go中,线程是运行goroutine的实体,调度器的功能是把可运行的goroutine分配给工作线程上。

  • 全局队列(Global Queue):存放等待运行的G。
  • P的本地队列:和全局队列类似,存放等待运行的G,但是存的数量有限,不超过256个。在一个P新建G’时,G’会优先加入P的本地队列,如果其满了,则会把本地队列中的一半的G移动到全局队列。
  • P列表:所有的P都在程序启动时创建,最多有GOMAXPROCS
  • M:线程想运行任务就得获取P,从P的本地队列获取G,P队列为空时,M也会尝试从全局队列一批G放到P的本地队列,或从其他P的本地队列一半放到自己P的本地队列。M运行G,G执行之后,M会从P获取下一个G,不断重复下去。

Goroutine调度器和OS调度器是通过M结合起来的,每个M都代表了1个内核线程,OS调度器负责把内核线程(M)分配到CPU的核上执行

M和P没有绝对的数量关系,如果一个M阻塞,P就会创建或者切换另一个P。

如果没有足够的M来关联P并运行其中可运行的G,比如所有的M此时都阻塞住了,而P中还有许多就绪任务,就会去寻找空闲的M,如果没有空闲的M,就会去创建新的M。

调度器的设计策略

复用线程

目的时避免频繁的创建和销毁线程,而是对线程的复用。

work stealing机制

当本线程无可运行的G时,尝试从其它线程绑定的P偷取G,而不是销毁线程

hand off机制

当本线程因为G进行系统调用阻塞时,线程释放绑定的P,把P转移给其它空闲的线程执行

利用并行

GOMAXPROCS设置P的数量,最多有GOMAXPROCS个线程分布在多个CPU上同时运行。GOMAXPROCS也限制了并发的程度,比如GOMAXPROCS = 核数/2,则最多利用了一半的CPU核进行并行。

抢占

在传统的coroutine中,需要等待一个协程主动让出CPU才可以执行下一个协程,在Go中,一个goroutine最多占用CPU 10ms,防止其他goroutine被饿死。

全局G队列

在新的调度器中依然有全局G队列,但功能被弱化了,当M执行work stealing从其他P偷不到G时,它可以从全局G队列获取G。

执行go func() 经历的过程

无阻塞情况

在无阻塞的情况下就是走正常流程。

首先创建一个G,之后放入局部队列,如果局部队列已经满了,就放入全局队列之中。

接下来M会尝试从本地队列之中获取一个G,如果本地队列为空,则从全局队列之中获取,或者从其它P的本地队列中偷取。其中偷取的优先级大于从全局队列获取,因为后者需要上锁,效率低。

M获取G之后会调度执行,时间片超时的话就会返回,放回P的本地队列尾部。

发生阻塞

在上图的第5步执行过程中,发生了阻塞的情况,这个系统并不会一直等它阻塞完毕。

它会尝试从休眠的M队列之中获取一个已经就绪的M。如果其中没有的话,就会新创建一个M,然后这个新的M会接管正在阻塞G的P,然后正常的去执行这个P的本地队列。

加入M1的被阻塞的G执行完毕,就会把M放回休眠M队列,或者销毁。而G会放到其它P的本地队列或者放到全局队列之中。

调度器的生命周期

M0

M0是启动程序后的编号为0的主线程,这个M对应的案例会在全局变量runtime.m0中,不需要再heap上分配,M0负责执行初始化操作和启动第一个G,在之后M0就会和其它的M一样参与流程

G0

G0是每次启动一个M都会第一个创建的goroutine,G0是仅用于负责调度的G,G0不指向的任何可执行的函数,每个M都会有一个自己的G0.在调度或者系统调用是会使用G0的占空间,全局变量的G0是M0的G0.

一个main函数的流程

  • 首先会创建一个M0,M0绑定了一个G0
  • 接下来会对P,P的本地队列,全局队列等进行初始化
  • 然后会运行到main之中,M0会尝试创建第一个G,放的是Main函数
  • M0会与G0解绑,接下来想执行Main
  • M0会把Main放到一个空闲的P本地队列之中,这个Main就会和常规的G一样走正常流程
  • 把G放到M0中执行,如果执行过程中超时了(10ms),就会放回本地队列中,继续走流程
  • 直到报panic或者exit

一些GMP调取器场景分析

G1执行完毕

G1执行完毕时,会先加载G0,获取G0中保存的一些环境信息,上下文,再加载本地队列中的G0

连续创建多个G导致本地队列满

此时会把P1的全局队列一分为二,取队首部分,再把队首打乱顺序,然后把新创建的G8也放入全局队列之中

打乱顺序可能是为了保证放进全局队列的G有相同的可能性被取出,而放入一半可能是为了避免频繁的操作全局队列。

唤醒正在休眠的M

当一个G尝试创建一个G的时候,就会尝试唤醒一个休眠之中的M,如果休眠M队列没有M就会新创建一个M(这部分不确定)

获取到一个新的M之后,这个M会尝试去获取一个空闲的P,如果没有空闲的P,可能会再次被加入休眠M队列。

当M获取到P后,会加载G0,此时被称为自旋线程,自旋线程会去不断获取G。

自旋线程获取G

自旋线程会优先从全局队列之中去获取G,按照一定公式去取一定数量的G。

如果全局队列没有则会尝试从其它的P中偷取G,策略是把被偷取的P的本地队列分成两半,偷取后半部分。

这里有个疑问:为什么当队列满的时候,取走的是前半部分,而被偷取的时候,取走的又是后半部分?

至于为什么先从全局队列中拿,全局队列没有再从其它的本地队列中偷:

从全局队列中拿需要有锁操作,会有资源消耗,而从其它本地队列之中偷取会破坏那个队列的局部性,导致频繁的资源切换。另一方面,如果优先偷取还可能使得全局队列中的G滞留过久。

自旋线程的最大限制

需要满足一个公式:自旋线程+执行线程 <= GOMAXPROCS

如果某个G创建了新的M,而此时就超过了这个常量,那么就会把这个M放入到休眠线程队列之中。

G发生系统调用/阻塞

假如图中的G8发生了阻塞,如果P2一直与M2进行绑定,此时会造成资源浪费。

这种情况下,P2就会尝试从休眠线程队列之中获取一个休眠的M并与其进行绑定,继续执行其本地队列之中的G。假如休眠线程队列之中没有内容,则会把P放入到空闲P队列之中。

阻塞变为非阻塞

当M2的阻塞结束时,M2会尝试去取之前绑定的P2,但是再图中这种情况下,P2已经与M5绑定了,这会造成抢占失败,此时M2会查看空闲的P队列之中有无内容,假如还是没有,M2会放弃绑定P,放入休眠线程队列之中。

另外休眠线程队列中的M并不是永远存在了,当存在了一定时间而没被调用后,可能会被销毁。