's blog
Posts Tags Categories About Bookmarks
's blog

Contents

Scalable Go Scheduler Design Doc 中文翻译

   393 words   2 minutes 

原文链接：https://golang.org/s/go11sched

以下是原文

Scalable Go Scheduler Design Doc

该文档假定您对Go 语言 和当前的 goroutine 调度程序实现有一定的了解。

当前调度程序的问题

当前的 goroutine 调度器限制了用 Go 编写的并发程序的可扩展性，特别是高吞吐量服务器和并行计算程序。 Vtocc 服务器在 8 核机器上最多可使用 70% 的 CPU，而性能分析显示 14% 用于runtime.futex(). 通常，调度程序可能会禁止用户在性能至关重要的情况下使用惯用的细粒度并发。

当前实现有什么问题：

  1. 单一全局互斥锁（Sched.Lock）和集中状态。互斥锁保护所有与 goroutine 相关的操作（创建、完成、重新调度等）。

  2. Goroutine (G) 切换 (G.nextg)。工作线程 (M’s) 经常在彼此之间切换可运行的 goroutine，这可能会导致延迟增加和额外开销。每个 M 必须能够执行任何可运行的 G，尤其是刚刚创建 G 的 M。

  3. 每个M内存缓存（M.mcache）。内存缓存和其他缓存（堆栈分配）与所有 M 相关联，而它们只需要与 M 正在运行的 Go 代码相关联（在 syscall 内部阻塞的 M 不需要 mcache）。运行的 Go 代码的M 与所有 M 之间的比率可以高达 1:100。这会导致过多的资源消耗（每个 MCache 最多可吸收 2M）和较差的数据局部性。

  4. 活跃的线程阻塞中或解除阻塞中。在存在syscalls的情况下，工作线程经常义阻塞和已解除阻塞。这增加了很多开销。

设计

Processors

总体思路是将 P（Processors）的概念引入运行时，并在Processors之上实现work-stealing scheduler。

M 代表操作系统线程（就像现在一样）。 P 表示执行 Go 代码所需的资源。 当 M 执行 Go 代码时，它有一个关联的 P。 当 M 空闲或在 syscall 中时，它不需要 P。

正好有 GOMAXPROCS P。所有 P 都组织成一个数组，这是工作窃取的要求。GOMAXPROCS 更改涉及stop/start the world以调整 P 数组的大小。

sched 中的一些变量被分散并移动到 P。M 中的一些变量被移动到 P（与 Go 代码的主动执行相关的变量）。

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 归还到列表中。因此，当 M 执行 Go 代码时，它必须有一个关联的 P。这种机制取代了 sched.atomic (mcpu/mcpumax)。

Scheduling

当一个新的 G 被创建或者一个已经存在的 G 变为可运行时，它会被放进到当前 P 的可运行 goroutines 列表中。当 P 执行完 G 时，它首先尝试从自己的可运行 goroutines 列表中取出一个 G；如果列表为空，则 P 选择一个随机牺牲者（另一个 P）并尝试从中窃取一半可运行的 goroutine。

Syscalls/M Parking and Unparking

当一个 M 创建一个新的 G 时，它必须确保有另一个 M 来执行 G（如果不是所有的 M 都处于忙碌中）。同样，当一个 M 进入 syscall 时，它必须确保有另一个 M 来执行 Go 代码。

有两种选择，我们可以立即阻塞和非阻塞M，或者使其部分自旋。这是性能和消耗不必要的 CPU 资源之间的内在冲突。这个想法是使用自旋且消耗CPU资源。但是，它不应该影响以 GOMAXPROCS=1 时 的运行程序（command line utilities, appengine,等）。

自旋分两层：

  • (1)一个空闲的 M 关联 P 自旋 ,寻找新的 G，
  • (2)一个 M 没关联 P 自旋,等待可用的 P。

最多有 GOMAXPROCS 个自旋 M((1)和(2))。当有类型 (2) 的空闲 M 时，类型 (1) 的空闲 M 不会阻塞。

当一个新的 G 被生成，或者 M 进入syscall，或者 M 从空闲到忙碌的转换时，它确保至少有 1 个自旋中 M（或者所有的 P 都忙碌中）。这确保了没有可运行的 G 可以以其他方式运行；同时避免过多的M 进行阻塞或解除阻塞。

自旋行为主要是被动的（OS驱动, sched_yield()），但可能包括一点主动自旋（循环消耗CPU）（需要调查和调整）。

Termination/Deadlock Detection

Termination/Deadlock Detection(解除/死锁检查)在分布式系统中更成问题。一般的想法是仅在所有 P 都空闲时进行检查（空闲 P 的全局原子计数器），这允许进行涉及每个 P 状态聚合的更昂贵的检查。

还没有细节。

LockOSThread

此功能不是性能关键的。

  1. 锁定的 G 变得不可运行（Gwaiting）。M 立即将 P 返回到空闲列表，唤醒另一个 M 并阻塞。

  2. 锁定的 G 变为可运行的（并到达 runq 的头部）。当前 M 将自己的 P 和锁定的 G 移交给与锁定的 G 关联的 M，并解锁它。当前 M 变为空闲。

Idle G

空闲的G;此功能不是性能关键的。

有一个（或单个?）空闲 G 的全局队列。寻找工作的 M 在几次不成功的窃取尝试后检查队列。

实施计划

目标是将整个事情分成可以独立审查和提交的最小部分。

  1. 引入 P 结构体（暂时为空）；实现 allp/idlep 容器（idlep 对于初学者来说是互斥保护的）；将 P 与运行 Go 代码的 M 相关联。仍然保留全局互斥锁和原子状态。

  2. 将 G freelist 移至 P。

  3. 将mcache移动到P。

  4. 将stackalloc移动到P。

  5. 将 ncgocall/gcstats 移至 P。

  6. 去中心化运行队列，实现工作窃取。消除 G 切换。仍在全局互斥锁下。

  7. 移除全局互斥体，实现分布式 termination detection，LockOSThread。

  8. 实施自旋，而不是提示进行阻塞/解除阻塞中.。

该计划可能行不通，有很多未探索的细节。

潜在的进一步改进

  1. 尝试LIFO调度，这将提高局部性。但是，它仍然必须提供一定程度的公平性并优雅地处理让出的 goroutine。

  2. 在goroutine第一次运行之前不要分配G和堆栈。对于一个新创建的 goroutine，我们只需要 callerpc、fn、narg、nret 和 args，也就是大约 6 个单词。这将允许创建大量运行到完成的 goroutine，显着降低内存开销。

  3. Without 3

  4. 更好的G-to-P局部性。尝试将未阻塞的 G 排入上次运行的 P 队列。

  5. P-to-M的更好的局部化。尝试在上次运行的同一 M 上执行 P。

  6. M创建节约。调度程序很容易被迫每秒创建数千个 M，直到操作系统拒绝创建更多线程。必须及时创建 M 直到 k*GOMAXPROCS，之后可以通过计时器添加新的 M。

散记

  • GOMAXPROCS 不会因为这项工作而消失。

原文结束

若翻译细节有错,还望指出

futex 了解 https://developer.aliyun.com/article/6043

Updated on 2022-08-04
Back | Home