本文为 Go 团队调度器核心开发者的一篇设计文档,介绍了老版 Go 调度器存在的问题,解决的思路以及实践的具体操作方案等,对理解 Go 语言核心的调度器非常有帮助

久违的翻译系列,依旧不知道自己在乱翻些什么,直觉告诉我错漏、表达不清的地方应该不少,真心希望有相对专业的朋友读完原文和翻译后来指正

该文档需要 Go 语言和当前 goroutine 调度器实现的前置知识。


当前调度器存在问题

当前的 goroutine 调度器限制了 Go 编写并发编程的扩展性,尤其是在高吞吐服务器和并行计算的场合。Vtocc 服务器在 8 核的机盒上 CPU 的最高使用率达到 70%,检测文档显示 14% 的时间被消耗在 runtime.futex() 上。通常而言,调度器会阻止用户在性能关键的地方使用惯用的高粒度并发。

当前实现存在的问题:

  1. 单一全局互斥锁(Sched.Lock)与中心化状态。互斥锁保护所有与 goroutine 相关的操作(创造、完成、重调度等)。
  2. Goroutine(G)的移交(G.nextg)。Worker 线程(M 的)之间彼此频繁的移交可运行 goroutine,这可能会导致延迟增加以及额外的消耗。每一个 M 都必须能执行任意可运行的 G,尤其是创造了 G 的 M。
  3. 每单元 M 的内存缓存(M.mcache)。内存缓存以及其他缓存(栈分配)都与所有的 M 的运行代码联结,而实际上他们只需要与 M 正在运行的 Go 代码联结(阻塞在系统调用中的 M 不需要 mcache)。正在运行的 Go 代码的 M 与 M 的总量比率能高达 1:100.,毫无疑问这带来了额外的资源消耗(每个 MCache 能蚕食高达 2M 的空间),也使得数据本地化效果不佳。
  4. 频繁的线程阻塞/解阻塞。现在的系统调用中,worker 线程会频繁的阻塞和恢复,这也增加了额外的消耗。

设计

处理器

这里基本打算是将 P(Processors)的概念引入运行时,并在处理器上实现“工作偷取型”调度器。M 代表着系统级线程(当下)。P 代表运行 Go 代码所必需的一切资源。当 M 执行 Go 代码时,他持有一个与自身相联结的 P。当 M 空闲或执行系统调用时,他确实需要 P,P 的数量为 GOMAXPROCS。所有的 P 都存在一个数组中,这是实现执行对象(work)偷取机制的必要条件。GOMAXPROCS 的改变会引发“世界暂停/启动(stop/start the world)”来改变 P 数组的大小。

调度器的某些变量被去中心化后移到了 P 结构当中,某些 M 的变量(与激活 Go 代码执行有关)也被移到了 P 数据结构。

struct P
{
	Lock;
	G *gfree; // freelist, moved from sched
	G *ghead; // runnable, moved from sched
	G *gtail;
	MCache *mcache; // moved from M
	FixAlloc *stackalloc; // moved from M
	uint64 ncgocall;
	GCStats gcstats;
	// etc
	...
};
P *allp; // [GOMAXPROCS]

还有一个空闲 P 的无锁列表:

P *idlep; // lock-free list

M 想要开始执行 Go 代码时,它必须从列表中弹出一个 P,结束后将其放回列表。所以说当 M 执行 Go 代码时它必须要持有一个相联结的 P。这一机制取代了原本的 sched.atomic(mcpu/mcoumax)。

调度

当一个新的 G 产生或已存在的 G 变为可运行状态,它会被放入当前 P 的可运行 goroutine 列表中。P结束运行 G 之后首先会尝试从可运行 goroutine 列表中获取下一个运行对象,如果列表为空,P 会随机选择一个牺牲者(另一个 P)尝试从他那偷取一半可运行的 goroutine。

系统调用/ M 的暂停与启动

M 创造一个新的 G 时必须确保有另一个 M 能运行 G(如果不是所有的 M 都处于忙碌状态)。同样的,当 M 陷入系统调用时也必须确保有另一个 M 来执行 Go 代码。

有两种选择,我们可以立即阻塞或解除 M 的阻塞,或者使用自旋,此处是一个性能和燃烧不必要 CPU 周期之间的固有冲突,而我们选择使用自旋并燃烧 CPU 周期。然而这不应该影响以 GOMAXPROCS=1 (通过命令行、app 引擎等方式设置)运行的程序。

自旋分两种:

  1. M 空闲,它的 P 自旋寻找新的 G
  2. M 没有相联结的 P,自旋等待可用的 P

最多有 GOMAXPROCS 个自旋的 M(包括1、2两种类型)。当存在类型 2 的空闲 M 时,类型 1 的空闲 M 不会阻塞。

当一个新的 G 产生,或者 M 陷入系统调用,又或者 M 从空闲状态变为忙碌状态,它确保至少有一个自旋的 M(除非所有的 P 都处于忙碌状态)。这保证了没有可运行的 G 会不被运行,并且避免了多余的 M 同一时刻阻塞/解除阻塞。自旋大多是被动的(yield 让渡给操作系统,sched_yield()),但可能包含一点主动的自旋(循环燃烧的 CPU)(待验证调整)

终止/死锁监测

终止/死锁监测在分布式系统中更成问题。通常而言,只在所有 P 都为空闲(依赖于空闲 P 的全局原子计数器)时才进行检查,这使得代价更昂贵的检查操作能够执行,包括每个 P 状态的聚合。

暂无详细计划。

系统线程锁

此功能不是性能关键。

  1. 上锁的 G 变为不可运行(Gwaiting)。M 立刻将 P 放回空闲列表,唤醒另一个 M 并阻塞
  2. 上锁的 G 变为可运行(并到达了 runq 的队头)。当前 M 将自身的 P 和上锁的 G 移交给与上锁 G 相联结的 M,并解除阻塞状态。当前 M 变为空闲状态

空闲 G

此功能不是性能关键。

空闲的 G 有一个全局队列,寻找执行对象的 M 在几次尝试偷取失败后会检查全局队列


实现计划

目标是将整件事分割成能够被独立审核和提交的最小部分。

  1. 引入 P 结构(当前为空);实现 allp/idelp 容器(idelp 对启动器是互斥保护的);将 P 与一个正在运行 Go 代码的 M 相联结。仍旧保留全局互斥和原子状态
  2. 将 G 的自由列表移动到 P。
  3. 将 mcache 移动到 P。
  4. 将栈分配移动到 P。
  5. 将 ncgocall/gcstats 移动到 P。
  6. 将运行队列去中心化,实现执行对象偷取机制。消除 G 移交。仍旧处于全局互斥条件下。
  7. 移除全局互斥,实现分布式终止探测,系统线程锁。
  8. 实现替代立刻阻塞/解除阻塞的自旋功能。计划有可能会失败,尚有太多未知的细节。

未来潜在的改进可能

  1. 尝试能够改进本地化的 LIFO 调度。然而还必须提供某种程度的公平,以及优雅处理移交 goroutine 的方案
  2. 知道 goroutine 第一次运行才分配 G 和栈空间。对一个新生成的 goroutine 我们只需要 callerpc、fn、narg、nret 以及 args,就这 6 个单词。这样就允许在内存消耗极低的条件下创建大量运行到完成的 goroutine 了。
  3. G 到 P 更好的本地化。尝试将一个未阻塞的 G 放入他上次运行的 P 当中
  4. P 到 M 更好的本地化。尝试在 P 上一次执行的 M 上继续执行 P。
  5. 控制节约 M 的创造。调度器很容易就会被迫每秒生成成千上万个 M 直到操作系统拒绝生成线程为止。M 必须被限制到最多生成 k*GOMAXPROCS 个,之后只能由定时器添加

随机笔记

  • GOMAXPROCS 不会因为本文项目而离开