一.前言

1.1 调度目的

调度器负责确保内核不空闲。 它还必须造成所有可以执行的线程都在同时执行的错觉。 在制造这种错觉的过程中，调度器需要运行优先级高于低优先级的线程。 但是，具有较低优先级的线程不能缺乏执行时间。 调度程序还需要通过做出快速而明智的决策来尽可能地减少调度延迟。

1.2 写作目的

之前 goloang解析--进程，线程，协程 中介绍了进程，线程，协程各自上下文切换所需要做的工作，由此引申出如下问题

进程，线程，协程是如何进行调度的

二.进程，线程调度

2.1 调度方式

进程的调度在方式上分为两类，抢占式和非抢占式

非抢占式

分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程。

抢占式：

当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程。剥夺原则有：优先权原则、短进程优先原则、时间片原则。

2.2 linux 的 cfs 调度方式（应用于线程，进程）

cfs(Completely Fair Scheduler)，指的是完全公平调度器，负责进程调度，旨在最大限度地提高整体 CPU 利用率，同时最大限度地提高交互性能。

2.2.1 cfs 策略

cfs 定义一种新的模型，它给 cfs_rq（cfs 的 run queue）中的每一个进程安排一个虚拟时钟，vruntime。如果一个进程得以执行，随着时间的增长（即一个个 tick 的到来），其 vruntime 将不断增大。没有得到执行的进程 vruntime 不变。

  调度器总是选择 vruntime 值最低的进程执行。这就是所谓的“完全公平”。对于不同进程，优先级高的进程 vruntime 增长慢，以至于它能得到更多的运行时间。

三.协程调度器

3.1 协程调度机制的结构

协程调度机制主要有三个重要组成部分

Logical Processor (P)： 被视为一个虚拟 cpu

OS Thread(M)：每个 P 上面都会分配一个内核线程，用于进行逻辑操作，如果我有一台计算器，最多有 8 个 cpu 可用，运行 go 语言程序的时候就会针对这 8 个 cpu 创建 8 个 P，每个 P 上都有分配一个 M 用于执行 go 语言的逻辑处理。

Goroutine(G):您可以将 Goroutines 视为应用程序级线程，它们在许多方面类似于 OS 线程。 正如操作系统线程在内核上和内核外进行上下文切换一样，Goroutines 在 M 上进行上下文切换。

全局运行队列（GRQ）和本地运行队列（LRQ）: 每个 P 都有一个 LRQ，用于管理分配到 P 的上下文中执行的 Goroutine。这些 Goroutine 轮流打开和关闭分配给该 P 的 M 的上下文切换。

3.2 协程调度机制运行方式

Go 调度程序内置于 go 语言内的 runtime 包中，这意味着 Go 调度程序运行在内核之上的用户空间中（这是与进程和线程的最大区别之一），Go 调度器的调度不是抢占式调度，而是协作式，意味着需要明确的用户空间事件作出调度抉择。

3.2.1 触发协程调用的四种时机

1.主动是用关键字 go

2.垃圾回收

3.系统调用

4.同步和编排：如果原子、互斥或通道操作调用将导致 Goroutine 阻塞，则调度程序可以上下文切换一个新的 Goroutine 来运行。一旦 Goroutine 可以再次运行，它就可以重新排队并最终在 M 上进行上下文切换。

3.2.2 协程调用机制原理

3.2.2.1 异步系统调用

go 语言处理异步的网络请求，使用的是类似于网络轮询的机制(epollo)。

通过使用网络轮询器进行网络系统调用，调度器可以防止 Goroutines 在进行这些系统调用时阻塞 M。 这有助于保持 M 可用于执行 P 的 LRQ 中的其他 Goroutine，而无需创建新的 M。这有助于减少 OS 上的调度负载。

当 g1 在 m1，且想要完成一次网络请求的时候，会将 g1 迁移到 networker poller 进行异步等待，此时 m1 可以处理其他的 goroutine，直到 g1 收到了网络请求，g1 会被再次放入 m1 的本地可执行队列中，等待下一次调用。

3.2.2.2 同步系统调用

当 goroutine 想要完成无法异步完成的系统调用的时候，进行系统调用的 Goroutine 将阻塞 M1,此时，go 语言为了解决此类场景对 P 的占用，会将被阻塞的 M1 带着进行系统调用的 G1 一同迁移出去，然后创建新的 M2 绑定到原先的 P 上，对剩下的 G 进行调用。(如果有多余的 M 可以直接拿来使用，减少新建的消耗，类似线程池)

当进行系统调用的 G1 完成了系统调用，G1 会回到队列，此时 M1 也不删除，作为后备，减少下一次此类场景出现对 M 的新建消耗。

3.2.2.3 工作窃取

每个 P 都有自己的 LRQ(本地队列)，但是每个 P 的本地队列的数目和每个 goroutine 所需要的执行时间是不一致的，为了减少 cpu 空闲的时间，我们要尽量避免 P 的 LRQ 为空，导致 cpu 浪费的场景，所以 goroutine 的调用机制还增加了工作窃取(work stealing)。

当 P 的本地队列没有 goroutine 的时候，他会先去别的 P 进行窃取，如果别的 P 有待执行的 G，那 P 就会窃取一半，如果别的也没有，那 P 就回去全局队列(GRQ)获取。

四.并发

4.1 协程的并发

4.1.1 并发与并行

并发：乱序执行一系列任务，并保证结果与顺序执行一致

并行：同时执行多条任务，意味着必须拥有多个硬件线程，同时运行多个 goroutine。

4.1.2 并发的两种工作负载

CPU-Bound：这是一种工作负载，它永远不会造成 Goroutines 自然地进入和退出等待状态的情况。这是一项不断进行计算的工作。例如将 Pi 计算到第 N 位的线程将受 CPU 限制。

IO-Bound：这是一种导致 Goroutines 自然进入等待状态的工作负载。这项工作包括通过网络请求访问资源，或对操作系统进行系统调用，或等待事件发生。需要读取文件的 Goroutine 将是 IO-Bound。我将包括同步事件（互斥体、原子），这会导致 Goroutine 作为该类别的一部分等待。

4.1.2.1 CPU-Bound

针对 CPU-Bound，在并发的使用上可以通过并行性来提高效率，如求 n 个数的和，但是由于协程切换有上下文切换的代价，所以 n 的大小，和用多少个协程来进行并行，也是情况而定，不是一定利用了多个内核线程程序就越快。

也不是所有的 cpu 工作负载用了并行都可以提高效率，如冒泡排序，顺序执行效率还高于并发执行。

4.1.2.2 IO-Bound

对于 IO-Bound，不需要并行性来获得性能的大幅提升。

效率检验可以使用 golang 自带的benchmark机制进行检验。

参考文档

others

https://baike.baidu.com/item/%E8%BF%9B%E7%A8%8B%E8%B0%83%E5%BA%A6/10702294?fr=aladdin

https://en.wikipedia.org/wiki/Completely_Fair_Scheduler

https://www.kernel.org/doc/html/latest/scheduler/sched-design-CFS.html

https://blog.csdn.net/XD_hebuters/article/details/79623130

golang

https://www.ardanlabs.com/blog/2018/08/scheduling-in-go-part1.html

https://www.ardanlabs.com/blog/2018/08/scheduling-in-go-part2.html

https://www.ardanlabs.com/blog/2018/12/scheduling-in-go-part3.html