Go调度器系列(3)图解调度原理

如果你已经阅读了前2篇文章:《调度起源》《宏观看调度器》,你对G、P、M肯定已经不再陌生,我们这篇文章就介绍Go调度器的基本原理,本文总结了12个主要的场景,覆盖了以下内容:

  1. G的创建和分配。
  2. P的本地队列和全局队列的负载均衡。
  3. M如何寻找G。
  4. M如何从G1切换到G2。
  5. work stealing,M如何去偷G。
  6. 为何需要自旋线程。
  7. G进行系统调用,如何保证P的其他G'可以被执行,而不是饿死。
  8. Go调度器的抢占。

12场景

提示:图在前,场景描述在后。

上图中三角形、正方形、圆形分别代表了M、P、G,正方形连接的绿色长方形代表了P的本地队列。

场景1:p1拥有g1,m1获取p1后开始运行g1,g1使用go func()创建了g2,为了局部性g2优先加入到p1的本地队列。

场景2g1运行完成后(函数:goexit),m上运行的goroutine切换为g0,g0负责调度时协程的切换(函数:schedule。从p1的本地队列取g2,从g0切换到g2,并开始运行g2(函数:execute)。实现了线程m1的复用

场景3:假设每个p的本地队列只能存4个g。g2要创建了6个g,前4个g(g3, g4, g5, g6)已经加入p1的本地队列,p1本地队列满了。

蓝色长方形代表全局队列。

场景4:g2在创建g7的时候,发现p1的本地队列已满,需要执行负载均衡,把p1中本地队列中前一半的g,还有新创建的g转移到全局队列(实现中并不一定是新的g,如果g是g2之后就执行的,会被保存在本地队列,利用某个老的g替换新g加入全局队列),这些g被转移到全局队列时,会被打乱顺序。所以g3,g4,g7被转移到全局队列。

场景5:g2创建g8时,p1的本地队列未满,所以g8会被加入到p1的本地队列。

场景6在创建g时,运行的g会尝试唤醒其他空闲的p和m执行。假定g2唤醒了m2,m2绑定了p2,并运行g0,但p2本地队列没有g,m2此时为自旋线程(没有G但为运行状态的线程,不断寻找g,后续场景会有介绍)。

场景7:m2尝试从全局队列(GQ)取一批g放到p2的本地队列(函数:findrunnable)。m2从全局队列取的g数量符合下面的公式:

n = min(len(GQ)/GOMAXPROCS + 1, len(GQ/2))

公式的含义是,至少从全局队列取1个g,但每次不要从全局队列移动太多的g到p本地队列,给其他p留点。这是从全局队列到P本地队列的负载均衡

假定我们场景中一共有4个P,所以m2只从能从全局队列取1个g(即g3)移动p2本地队列,然后完成从g0到g3的切换,运行g3。

场景8:假设g2一直在m1上运行,经过2轮后,m2已经把g7、g4也挪到了p2的本地队列并完成运行,全局队列和p2的本地队列都空了,如上图左边。

全局队列已经没有g,那m就要执行work stealing:从其他有g的p哪里偷取一半g过来,放到自己的P本地队列。p2从p1的本地队列尾部取一半的g,本例中一半则只有1个g8,放到p2的本地队列,情况如上图右边。

场景9:p1本地队列g5、g6已经被其他m偷走并运行完成,当前m1和m2分别在运行g2和g8,m3和m4没有goroutine可以运行,m3和m4处于自旋状态,它们不断寻找goroutine。为什么要让m3和m4自旋,自旋本质是在运行,线程在运行却没有执行g,就变成了浪费CPU?销毁线程不是更好吗?可以节约CPU资源。创建和销毁CPU都是浪费时间的,我们希望当有新goroutine创建时,立刻能有m运行它,如果销毁再新建就增加了时延,降低了效率。当然也考虑了过多的自旋线程是浪费CPU,所以系统中最多有GOMAXPROCS个自旋的线程,多余的没事做线程会让他们休眠(见函数:notesleep())。

场景10:假定当前除了m3和m4为自旋线程,还有m5和m6为自旋线程,g8创建了g9,g8进行了阻塞的系统调用,m2和p2立即解绑,p2会执行以下判断:如果p2本地队列有g、全局队列有g或有空闲的m,p2都会立马唤醒1个m和它绑定,否则p2则会加入到空闲P列表,等待m来获取可用的p。本场景中,p2本地队列有g,可以和其他自旋线程m5绑定。

场景11:(无图场景)g8创建了g9,假如g8进行了非阻塞系统调用(CGO会是这种方式,见cgocall()),m2和p2会解绑,但m2会记住p,然后g8和m2进入系统调用状态。当g8和m2退出系统调用时,会尝试获取p2,如果无法获取,则获取空闲的p,如果依然没有,g8会被记为可运行状态,并加入到全局队列。

场景12:(无图场景)Go调度在go1.12实现了抢占,应该更精确的称为请求式抢占,那是因为go调度器的抢占和OS的线程抢占比起来很柔和,不暴力,不会说线程时间片到了,或者更高优先级的任务到了,执行抢占调度。go的抢占调度柔和到只给goroutine发送1个抢占请求,至于goroutine何时停下来,那就管不到了。抢占请求需要满足2个条件中的1个:1)G进行系统调用超过20us,2)G运行超过10ms。调度器在启动的时候会启动一个单独的线程sysmon,它负责所有的监控工作,其中1项就是抢占,发现满足抢占条件的G时,就发出抢占请求。

场景融合

如果把上面所有的场景都融合起来,就能构成下面这幅图了,它从整体的角度描述了Go调度器各部分的关系。图的上半部分是G的创建、负债均衡和work stealing,下半部分是M不停寻找和执行G的迭代过程。

如果你看这幅图还有些似懂非懂,建议赶紧开始看雨痕大神的Golang源码剖析,章节:并发调度。

总结,Go调度器和OS调度器相比,是相当的轻量与简单了,但它已经足以撑起goroutine的调度工作了,并且让Go具有了原生(强大)并发的能力,这是伟大的。如果你记住的不多,你一定要记住这一点:Go调度本质是把大量的goroutine分配到少量线程上去执行,并利用多核并行,实现更强大的并发。

下集预告

下篇会是源码层面的内容了,关于源码分析的书籍、文章可以先看起来了,先剧透一篇图,希望阅读下篇文章赶紧关注本公众号。

推荐阅读

Go调度器系列(1)起源 Go调度器系列(2)宏观看调度器

参考资料

在学习调度器的时候,看了很多文章,这里列一些重要的:

  1. The Go scheduler: https://morsmachine.dk/go-scheduler
  2. Go's work-stealing scheduler: https://rakyll.org/scheduler/,中文翻译版: https://lingchao.xin/post/gos-work-stealing-scheduler.html
  3. Go夜读:golang 中 goroutine 的调度: https://reading.developerlearning.cn/reading/12-2018-08-02-goroutine-gpm/
  4. Scheduling In Go : Part I、II、III: https://www.ardanlabs.com/blog/2018/08/scheduling-in-go-part2.html,中文翻译版: https://www.jianshu.com/p/cb6881a2661d
  5. 雨痕大神的golang源码剖析: github.com/qyuhen/book
  6. 也谈goroutine调度器: https://tonybai.com/2017/06/23/an-intro-about-goroutine-scheduler/
  7. kavya的调度PPT: https://speakerdeck.com/kavya719/the-scheduler-saga
  8. 抢占的设计提案,Proposal: Non-cooperative goroutine preemption: https://github.com/golang/proposal/blob/master/design/24543-non-cooperative-preemption.md

0 个评论

要回复文章请先登录注册