Go Runtime的调度器

以goroutine形式进行Go并发编程是一种非常方便的方法，但有没有想过他是如何有效地运行这些goroutine？下面从设计的角度，深入了解和研究Go运行时调度程序，以及如何在性能调试过程中使用它来解释Go程序的调度程序跟踪信息。

要了解为什么需要有一个运行时的调度以及它是如何工作的，先要回到操作系统的历史上，在这里将找到答案，因为如果不了解问题的根源。

操作系统的历史

1. 单用户（无操作系统）
2. 批处理 单编程 运行完成

多程序的目的是使CPU和I/O重叠。如何做到的呢？

• 多批次
  IBM OS / MFT（具有固定数量的任务的多重编程）
• 多批次
  IBM OS / MVT（具有可变数量的任务的多重编程）—在这里，每个作业仅获得其所需的内存量。即，随着作业的进出，内存的分区发生变化。
• 分时
  这是在作业之间快速切换的多道程序设计。决定何时切换以及切换到哪些作业称为调度。

现代大多数操作系统使用分时调度程序。

这些调度程序调度的是什么呢？
1 不同的程序正在执行（进程）
2 作为进程子集存在的CPU利用率（线程）的基本单位

这些都是有代价的。

因此，使用一个包含多个线程的进程效率更高，因为进程创建既耗时又耗费资源。随后出现了多线程问题：C10k问题是主要的问题。

例如，如果将调度程序周期定义为10毫秒（毫秒），并且有2个线程，则每个线程将分别获得5毫秒。如果您有5个线程，则每个线程将获得2ms。但是，如果有1000个线程怎么办？给每个线程10s（微秒）的时间片？你将花费大量时间进行上下文切换，但是无法完成真正的工作。

你需要限制时间片的长度。在最后一种情况下，如果最小时间片是2ms，并且有1000个线程，则调度程序周期需要增加到2s（秒）。如果有10,000个线程，则调度程序周期为20秒。在这个简单的示例中，如果每个线程都使用其全时切片，则所有线程一次运行需要20秒。因此，我们需要一些可以使并发成本降低而又不会造成过多开销的东西。

用户级线程
• 线程完全由运行时系统（用户级库）管理。
• 理想情况下，快速高效：切换线程不比函数调用贵多少。
• 内核对用户级线程一无所知，并像对待单线程进程一样对其进行管理。

在Go中，我们叫它“ Goroutine”（在逻辑上）

Goroutine

协程是轻量级线程，由Go运行时管理（逻辑上一个执行的线程）。要go在函数调用之前启动运行go关键字。

func main() {
    var wg sync.WaitGroup
    wg.Add(11)
    for i := 0; i <= 10; i++ {
   
        go func(i int) {
          defer wg.Done()
          fmt.Printf("loop i is - %d\n", i)
        }(i)
    }
    wg.Wait()
    fmt.Println("Hello, Welcome to Go")
}
运行结果

loop i is - 10
loop i is - 0
loop i is - 1
loop i is - 2
loop i is - 3
loop i is - 4
loop i is - 5
loop i is - 6
loop i is - 7
loop i is - 8
loop i is - 9
Hello, Welcome to Go

看一下输出，就会有两个问题。

1. 11个goroutine如何并发运行的？
2. goroutine以什么顺序运行？

这两个问题，又引发新的思考：

1. 如何将这些多个 goroutine 分布到在可用 CPU 处理器上运行的多个 OS 线程上。
2. 这些多个 goroutine 应该以什么顺序运行以保持公平性？

其余的讨论将主要围绕从设计角度解决 Go 运行时调度程序的这些问题。调度程序可能会瞄准许多目标中的一个或多个，对于我们的案例，我们将限制自己满足以下要求。

1. 应该是并行的、可扩展的、公平的。
2. 每个进程应可扩展到数百万个goroutine（10⁶）
3. 内存高效。（RAM很便宜，但不是免费的。）
4. 系统调用不应导致性能下降。（最大化吞吐量，最小化等待时间）

因此，让我们开始为调度程序建模，以逐步解决这些问题。

1.每个Goroutine线程——用户级线程。

    1.并行和可扩展。
      * 并行
      * 可扩展
    2. 每个进程不能扩展到数百万个goroutine（10⁶）

2.M:N线程——混合线程

M个内核线程执行N个“ goroutine”

M个内核线程执行N个“ goroutine”

代码和并行的实际执行需要内核线程。但是创建成本很高，所以将 N 个 goroutine 映射到 M Kernel Thread。Goroutine 是 Go Code，所以我们可以完全控制它。此外，它在用户空间中，因此创建起来很便宜。

但是因为操作系统对 goroutine 一无所知。每个 goroutine 都有一个 state 来帮助Scheduler根据 goroutine state 知道要运行哪个 goroutine。与内核线程相比，这个状态信息很小，goroutine 的上下文切换变得非常快。

• Running-当前在内核线程上运行的goroutine。
• Runnable-够程等待内核线程来运行。
• Blocked-等待某些条件的Goroutine（例如，在通道，系统调用，互斥体等上被阻止）

2个线程一次运行2个

因此，Go Runtime Scheduler通过将N Goroutine复用到M内核线程来管理处于各种状态的这些goroutine。

简单的MN排程器
在我们简单的M:N Scheduler中，我们有一个全局运行队列，某些操作将一个新的goroutine放入运行队列。M个内核线程访问调度程序以从“运行队列”中获取goroutine来运行。多个线程尝试访问相同的内存区域，我们将使用Mutex For Memory Access Synchronization锁定此结构。

简单的M:N

阻塞的goroutine在哪里？
可以阻塞的goroutine一些实例。

1. 在channel上发送和接收。
2. 网络I/O。
3. 阻止系统调用。

那么，我们将这些阻塞的goroutine放在哪里？

阻塞的goroutine不应阻塞底层的内核线程！（避免线程上下文切换成本）

通道操作期间阻止了Goroutine。
每个通道都有一个recvq（waitq），用于存储被阻止的goroutine，这些goroutine试图从该通道读取数据。
Sendq（waitq）存储试图将数据发送到通道的被阻止的goroutine 。

通道操作期间阻止了Goroutine。

通道操作后的未阻塞的goroutine被通道放入“运行”队列。

通道操作后接触阻塞的goroutine

系统调用呢？

首先，让我们看看阻塞系统调用。一个阻塞底层内核线程的系统调用，所以我们不能在这个线程上调度任何其他 Goroutine。

隐含阻塞系统调用降低了并行级别。

不能在 M2 线程上调度任何其他 Goroutine，导致CPU 浪费。

我们可以恢复并行度的方法是，当我们进入系统调用时，我们可以唤醒另一个线程，该线程将从运行队列中选择可运行的 goroutine。

现在，当系统调用完成时，超额执行了Groutine计划。为了避免这种情况，我们不会立即运行Goroutine从阻止系统调用中返回。但是我们会将其放入调度程序运行队列中。

避免过度预定的调度

因此，当我们的程序运行时，线程数大于内核数。尽管没有明确说明，线程数大于内核数，并且所有空闲线程也都由运行时管理，以避免过多的线程。

初始设置为10,000个线程，如果超过则程序崩溃。

非阻塞系统调用---在集成运行时轮询器上阻塞 goroutine ，并释放线程以运行另一个 goroutine。

例如在非阻塞 I/O 的情况下，例如 HTTP 调用。第一个系统调用 - 遵循先前的工作流程 - 不会成功，因为资源尚未准备好，迫使 Go 使用网络轮询器并停放 goroutine。

这是部分 net.Read功能的实现。

n, err := syscall.Read(fd.Sysfd, p)
if err != nil {
  n = 0
  if err == syscall.EAGAIN && fd.pd.pollable() {
    if err = fd.pd.waitRead(fd.isFile); err == nil {
    continue
  }
}

一旦完成第一个系统调用并明确指出资源尚未准备好，goroutine将停放，直到网络轮询器通知它资源已准备好为止。在这种情况下，线程M将不会被阻塞。

Poller将基于操作系统使用select/kqueue/epoll/IOCP来了解哪个文件描述符已准备好，一旦文件描述符准备好进行读取或写入，它将把goroutine放回到运行队列中。

还有一个Sysmon OS线程，如果轮询时间不超过10毫秒，它将定期轮询网络，并将就绪G添加到队列中。

基本上所有的goroutine都被阻止在

现在，运行时具有具有以下功能的调度程序。

• 它可以处理并行执行（多线程）。
• 处理阻止系统调用和网络I/O。
• 处理阻止用户级别（在通道上）的调用。

但这不是可扩展的

使用Mutex的全局运行队列

如图所见，我们有一个Mutex全局运行队列，最终会遇到一些问题，例如

1. 缓存一致性保证的开销。
2. 在创建，销毁和调度Goroutine G时进行激烈的锁争用。

使用分布式调度器克服可扩展性的问题。

分布式调度程序—每个线程运行队列。

分布式运行队列调度程序

这样，我们可以看到的直接好处是，对于每个线程本地运行队列，我们现在都没有互斥体。仍然有一个带有互斥量的全局运行队列，在特殊情况下使用。它不会影响可伸缩性。

现在，我们有多个运行队列。

1. 本地运行队列
2. 全局运行队列
3. 网络轮训器

我们应该从哪里运行下一个goroutine？

在Go中，轮询顺序定义如下。

1. 本地运行队列
2. 全局运行队列
3. 网络轮训器
4. 工作偷窃（Work Stealing）

即首先检查本地运行队列，如果为空则检查全局运行队列，然后检查网络轮询器，最后进行窃取工作。到目前为止，我们对1,2,3有了一些概述。让我们看一下“窃取工作”。

工作偷窃

如果本地工作队列为空，请尝试“从其他队列中窃取工作”

“偷窃”工作

当一个线程有太多的工作要做而另一个线程处于空闲状态时，工作窃取解决了这个问题。在Go中，如果本地队列为空，窃取工作将尝试满足以下条件之一。

• 从全局队列中拉取工作。
• 从网络轮询器中拉取工作。
• 从其他本地队列中窃取工作。

到目前为止，运行时Go具有具有以下功能的Scheduler。

• 它可以处理并行执行（多线程）。
• 处理阻止系统调用和网络I/O。
• 处理阻止用户级别（在通道上）的调用。

但这不是有效的。

还记得我们在阻塞系统调用中恢复并行度的方式吗？

它的含义是，在一个系统调用中我们可以有多个内核线程（可以是10或1000），这可能会增加内核数。我们最终在以下期间产生了恒定的开销：

• 窃取工作时，它必须同时扫描所有内核线程（理想情况下并使用goroutine运行）本地运行队列，并且大多数都将为空。
• 垃圾回收，内存分配器都遭受相同的扫描问题。

使用M:P:N线程克服效率问题。

3.M：P：N（3级调度程序）线程化—逻辑处理器P简介

P — 处理器，可以将其视为在线程上运行的本地调度程序；

M:P:N线程

逻辑进程P的数量始终是固定的。（默认为当前进程可以使用的逻辑CPU）

将本地运行队列（LRQ）放入固定数量的逻辑处理器（P）中。

分布式三级运行队列调度程序

Go运行时将首先根据计算机的逻辑CPU数量（或根据请求）创建固定数量的逻辑处理器P。

每个goroutine（G）将在分配给逻辑CPU（P）的OS线程（M）上运行。

因此，现在我们在以下期间没有固定的开销：

• 窃取工作-只需扫描固定数量的逻辑处理器（P）本地运行队列。
• 垃圾回收，内存分配器也获得相同的好处。

带有固定逻辑处理器（P）的系统调用怎么样？

Go通过将系统调用包装在运行时中来优化系统调用-无论它是否阻塞

阻止系统调用包装器

Blocking SYSCALL方法封装在runtime.entersyscall（SB）
runtime.exitsyscall（SB）之间。
从字面上看，某些逻辑在进入系统调用之前执行，而某些逻辑在退出系统调用之后执行。进行阻塞系统调用时，此包装器将自动从线程M分离P，并允许另一个线程在其上运行。

阻塞系统调用切换P

这允许 Go 运行时在不增加运行队列的情况下有效地处理阻塞系统调用。

一旦阻止syscall退出，会发生什么？

• 运行时尝试获取完全相同的P，然后继续执行。
• 运行时尝试在空闲列表中获取一个P并恢复执行。
• 运行时将goroutine放到全局队列中，并将关联的M放回空闲列表。

自旋线程和理想线程（Spinning Thread and Ideal Thread）.

当M2线程在syscall返回后变成理想理想线程时。该理想的M2线程该怎么办。理论上，一个线程如果完成了它需要做的事情就应该被操作系统销毁，然后其他进程中的线程可能会被 CPU 调度执行。这就是我们常说的操作系统中线程的“抢占式调度”。

考虑上述syscall中的情况。如果我们销毁了M2线程，而M3线程即将进入syscall。此时，在创建新的内核线程并将其计划由OS执行之前，无法处理可运行的goroutine。频繁的线程前抢占操作不仅会增加OS的负载，而且对于性能要求更高的程序几乎是不可接受的。

因此，为了正确利用操作系统的资源并防止频繁的线程抢占操作系统上的负载，我们不会破坏内核线程M2，而是进行自旋操作并保存以备将来使用。尽管这似乎是在浪费一些资源。但是，与线程之间的频繁抢占以及频繁的创建和销毁操作相比，“理想的线程”仍然要付出更少的代价。

Spinning Thread —例如，在具有一个内核线程M（1）和一个逻辑处理器（P）的Go程序中，如果正在执行的M被syscall阻止，则“ Spinning Threads”的数目与该数目相同需要P的值以允许等待的可运行goroutine继续执行。因此，在此期间，内核线程的数量M大于P的数量（旋转线程+阻塞线程）。因此，即使将runtime.GOMAXPROCSvalue设置为1，程序也将处于多线程状态。

调度中的公平性如何？—公平选择下一步要执行的goroutine。

与许多其他调度程序一样，Go也具有公平性约束，并且由goroutine的实现所强加，因为Runnable goroutine应该最终运行

以下是Go Runtime Scheduler中的四个典型的公平性约束。

任何运行超过 10 毫秒的 goroutine 都被标记为可抢占（软限制）。但是，抢占仅在函数序言中完成。Go 目前在函数 prologues 中使用编译器插入的合作抢占点。

    无限循环——抢占（~10ms 时间片）——软限制

但是要小心无限循环，因为 Go 的调度程序不是抢占式的（直到 1.13）。如果循环不包含任何抢占点（如函数调用或分配内存），它们将阻止其他 goroutine 运行。一个简单的例子是：

package main
func main() {
    go println("goroutine ran")
    for {}
}

GOMAXPROCS = 1 go run main.go

直到Go（1.13）才可能打印该语句。由于缺少抢占点，因此主要的Goroutine可以占用处理器。

• 本地运行队列-抢占（〜10ms时间片）-软限制
• 通过每61个调度程序刻度检查一次全局运行队列，可以避免全局运行队列饥饿。
• Network Poller Starvation后台线程轮询网络偶尔会被主工作线程轮询。

Go 1.14有一个新的“非合作式抢占”。

有了Go，Runtime有了一个Scheduler，它具有所有必需的功能。

• 它可以处理并行执行（多线程）。
• 处理阻止系统调用和网络I / O。
• 处理阻止用户级别（在通道上）的调用。

这提供了大量的并发性，并且始终尝试实现最大的利用率和最小的延迟。

现在，我们总体上对Go运行时调度程序有了一些了解，我们如何使用它？Go为我们提供了一个跟踪工具，即调度程序跟踪，目的是提供有关行为的见解并调试与goroutine调度程序有关的可伸缩性问题。

调度程序跟踪

使用GODEBUG = schedtrace = DURATION环境变量运行Go程序以启用调度程序跟踪。（DURATION是以毫秒为单位的输出周期。）