了解 Go 调度器

无意中看到GopherCon上的一个演讲，The Scheduler Saga。觉得讲的很好，这篇文章作为笔记记录下来了。

Go 调度器初探

什么是 Go 调度器？

Go调度器在幕后管理Go程序的运行。

Go调度器负责运行创建的goroutines，暂停、恢复阻塞在channel，mutex上的goroutines，协调阻塞在系统调用，网络 IO，gc任务上的goroutines。

Go调度器管理着成千上万的goroutines。

为什么需要调度器？

因为Go使用的goroutines是用户级线程。

关于用户级的线程goroutines和操作系统线程的对比：

• goroutines和由操作系统调度的内核级线程类似，但是goroutines是由Go运行时管理的。
• goroutines比操作系统线程更加轻量级，消耗的资源更少。
• goroutines需要绑定到操作系统线程上运行。

什么时候调度？

当有会影响goroutines执行的操作时会触发调度，如：goroutines的创建，阻塞（channel, mutex, system call（系统调用阻塞会导致整个线程阻塞））。

Go运行时将调度器切换到线程上执行，并且调度器可能在同一个线程上同时调度两个不同的gorotuines。

调度目标

将goroutines调度到操作系统线程上运行。

• 使用更少的系统线程（系统线程的创建是昂贵的）
• 支持高并发（Go程序需要支持运行成千上万个goroutines）
• 完全并行（在N核机器上应该能并行N个gorotuines)

Go 调度器设计思想

如何将goroutines调度到操作系统线程上：

• 如何分配goroutines到操作系统线程上。
• 何时创建操作系统线程。

可运行的 goroutines 队列

需要调度的可运行的goroutines需要放到一个在堆上分配空间的队列里。这个队列就是可运行的goroutines队列。

不理想的设计

1:N 一个操作系统线程对应多个Goroutine

缺点：

• 没有并发性（如果一个goroutine阻塞了线程，其他goroutine也不能运行）。
• 没有并行性（只能利用单核CPU）。

1:1 一个操作系统对应一个Goroutine

和使用goroutines的初衷相违背（使用goroutines是为了创建更少的操作系统线程，因为操作系统线程的创建，销毁是昂贵的）。

理想的设计 M:N

复用操作系统线程

当需要时才创建操作系统线程，并管理这些操作系统线程进行复用。

• 当所有线程都不是空闲的，但是有goroutine要运行时才创建线程。

• 将不用的线程休眠不再占用cpu资源，并加到空闲线程的列表中。

操作系统线程从可运行的goroutines队列中获取goroutine运行。

到这我们已经重用了操作系统线程，并且提供了并发和并行支持。但是仍然存在两个问题：

• 多个线程需要访问同一可运行的goroutine队列，此时会产生全局锁争用，调度只能线性调度，效率低下。
• 创建的操作系统线程数量没有限制，仍然有可能创建成千上万个操作系统线程，太多操作系统线程切换代价非常大，数据竞争严重。

限制操作系统线程的数量

限制访问可运行的goroutine队列的操作系统线程数量（正在运行goroutine的线程，正在执行系统调用的线程不计入到限制的数量中）。

限制为多少呢？

• 太多线程会导致数据竞争严重。
• 太少无法利用多核优势。

限制为 CPU 的核数获取最大的并行。

到这里我们限制了操作系统的线程数，减少了数据竞争，保持了并行性。但是随着CPU的核心数越来越多，创建的操作系统线程也越来越多，同时访问可运行的全局队列的操作系统线程也越来越多，数据竞争又变得严重了。

限制操作系统线程数为CPU核数最大化的利用了CPU是没有问题的。问题在于全局的可运行的goroutines队列。

分布式的可运行的 goroutine 队列

在N个CPU核心上使用N个可运行的goroutines队列。

一个线程绑定一个可运行的goroutines队列，对队列中的goroutine进行插入，删除操作。

和之前一样重用线程。

如果本地队列是空的那么随机挑选一个其他线程上的队列，窃取一半的goroutines过来运行。这样可以使线程之间的工作负载均衡。

此时的模型已经可以按照CPU的核心数扩展了，并且线程之间不会太多的数据竞争。线程的工作负载也通过工作窃取的方式均衡了。

继续看下面的情况：

队列传递

• 使用某种机制将阻塞线程上队列传递到其他线程上（通过监控线程检测线程是否已经阻塞一段时间了，接管阻塞线程上的队列并将其传递到其他的线程上）。为什么不让线程在进入系统调用前自己主动将可运行队列交给别的线程呢？（如果这样的话，线程可能在不是必要交出队列的时候交出，阻塞系统调用时需要交出，而非阻塞系统调用时不必交出队列，比如网络 IO）。

• 必要时挂起，唤醒或新建操作系统线程来接管阻塞线程上的队列。

• 线程限制为CPU核数针对的线程是正在运行goroutine的线程数，而不是创建的goroutine的数量。

终于我们得到了最终的调度模型，可以适应CPU核数的增长，线程不会产生对队列的数据竞争。通过工作窃取的方式实现了线程的负载均衡，通过队列传递的方式避免了阻塞线程上的队列中的goroutine饥饿。

但是调度的时间点是协作式的，go程序触发调度。

为了避免这种情况，Go调度器实现了抢占式调度。通过运行一个叫做sysmon的线程来检测运行时间大于10ms的goroutine，并在适当的时候将其调度走。那么将它调度到哪里呢？它使其他运行的goroutines饥饿，所以不想把它放到本地队列，这似乎有点不公平。那么放到一个全局队列呢？Go调度器有一个额外的全局队列用来放可运行的goroutines。全局队列运行的优先级比较低，线程访问全局队列的频率比较低，所以数据竞争不是很大的问题。

一些小细节

线程自旋

• 没有goroutine运行的线程在休眠之前会自旋找goroutine来运行，查找全局队列，轮询网络，试图获取gc任务，工作窃取。
• 这消耗CPU时间片，但是可以使得线程负载均衡，获取更大的并行度，充分利用CPU。

结构体 P 和可运行的 goroutines 队列

• 每个CPU核心对应队列存储在P结构体中，P是在堆上分配的空间。
• P还存储了线程运行goroutine所需的其他资源，例如内存缓存。
• 线程通过P来运行goroutines，当线程阻塞时，整个P会被传递给其他线程。

局限性

• 先进先出的队列，没有优先级调度。
• 没有强抢占式调度。
• 没有考虑系统的局部性，无法充分利用CPU缓存。