[译] Go’s work-stealing scheduler

Go调度器的工作是在一个或多个处理器上运行的多个工作者OS线程上分发可运行的goroutine。在多线程计算中，调度中出现了两种范例：工作共享和工作窃取。

  • 工作共享：当处理器生成新线程时，它会尝试将其中的一些线程迁移到其他处理器，希望它们被闲置/未充分利用的处理器利用。
  • 工作窃取：未充分利用的处理器会主动寻找其他处理器的线程并“窃取”一些。

线程迁移在工作窃取中发生的频率比在工作共享中发生的频率低。当所有处理器都能运行时，不会迁移任何线程。并且，一旦有一个空闲的处理器，便考虑迁移。

Go从1.1开始，便有一个工作窃取调度器，由Dmitry Vyukov贡献。本文将深入解释什么是窃取工作调度器以及Go如何实现它。

调度基础

Go有一个M：N调度器，该调度器也可以利用多个处理器。任何时候，M个 goroutines 需要在N个OS线程上被调度，这些OS线程最多有 GOMAXPROCS 个处理器。Go调度器对goroutine，线程和处理器，有以下术语：

  • G：goroutine
  • M：操作系统线程（机器）
  • P：处理器

有一个特定于P的本地和全局goroutine队列。每个M应该分配给一个P。如果发生阻塞或系统调用，P可能没有M。在任何时候，最多有GOMAXPROCS个P。在任何时候，每个P只能运行一个M。如果需要，调度器可以创建更多M。

调度器基础

每一轮调度都只是简单地找到一个可运行的goroutine并执行它。在每一轮调度中，搜索均按以下顺序进行：

1
2
3
4
5
6
7
8

runtime.schedule() {
    // only 1/61 of the time, check the global runnable queue for a G.
    // if not found, check the local queue.
    // if not found,
    //     try to steal from other Ps.
    //     if not, check the global runnable queue.
    //     if not found, poll network.
}

一旦找到可运行的G，它将一直执行到被阻塞。

注意：看起来全局队列比本地队列有一个优势，但是每隔一段时间检查一次全局队列，对于避免M仅从本地队列进行调度直到没有本地排队的goroutine至关重要(防止M只调度本地排队的goroutine，直到本地队列没有要运行的goroutine，应该是为了防止有goroutine长时间等待而饿死)。

偷窃

当新的G被创建或已经存在的G成为可运行时，它将被推送到当前P的可运行goroutine列表中。当P完成执行G时，它将尝试从自己的可运行goroutine列表中弹出一个G。如果列表现在为空，则P选择一个随机的其他处理器（P）并尝试从其队列中窃取一半可运行的goroutine。

P2抢断P1

在上述情况下，P2无法找到任何可运行的goroutine。因此，它随机选择另一个处理器（P1）并将窃取三个goroutine到其自己的本地队列中。P2将能够运行这些goroutine，并且调度器的工作将更加公平地分布在多个处理器之间。

自旋线程

调度器始终希望向Ms分发尽可能多的可运行goroutine，以利用处理器，但与此同时，我们需要停止过多的工作以节省CPU和功耗。与此相反，调度器还应该能够扩展到高吞吐量和CPU密集型程序。

如果性能至关重要，则持续抢占不但昂贵，对高吞吐量程序的来说又是问题。OS线程不应经常在彼此之间切换可运行的goroutine，因为这会导致延迟增加。除了存在系统调用外，还需要不断阻塞和解除阻塞OS线程。这是昂贵的，并且增加了很多开销。

为了最大程度地减少交接，Go调度器实现了“旋转线程”。旋转线程会消耗一点额外的CPU能力，但会最大程度地减少操作系统线程的抢占。如果发生以下情况，则线程正在旋转：

  • 分配了P的M正在寻找可运行的goroutine。
  • 没有分配P的M正在寻找可用的P。
  • 如果有一个空闲的P并且没有其他自旋线程，则Scheduler还会在准备goroutine时释放一个附加线程并对其进行旋转。

随时有最多GOMAXPROCS个自旋的 M。当自旋的线程找到工作时，它将退出旋转状态。

如果存在未分配P的空闲M，则分配P的空闲线程不会阻塞。当创建新的goroutine或阻塞一个M时，调度器将确保至少有一个旋转的M。并避免过多的M阻止/取消阻止。

结论

Go调度器通过偷窃将它们调度到正确的处理器和未充分利用的处理器上，以及实现“旋转”线程来避免发生过多的阻塞/未阻塞转换，从而避免了OS线程的过多抢占。

调度事件可以由执行跟踪器跟踪。如果您碰巧认为自己的处理器利用率很低，则可以调查正在发生的情况。

参考