Work-stealing scheduler in Go

divan0 July 18, 2017 at 19:57

Work-stealing scheduler in Go

Transfer

The task of the scheduler in Go is to distribute running goroutines between OS threads that can be executed by one or more processors. In multi-threaded computing, two planning paradigms have arisen: work sharing and work stealing.

Work-sharing : When a processor generates new threads, it tries to migrate them to other processors, in the hope that they will get to an idle or underloaded processor.
Work-stealing : An underloaded processor actively searches for threads of other processors and “steals” some of them.

Thread migration occurs less frequently with a work stealing approach than with work sharing . When all processors are busy, threads do not migrate. As soon as an idle processor appears, the migration option is considered.

Starting with version 1.1, the Go scheduler was implemented according to the work stealing scheme and was written by Dmitry Vyukov. This article explains in detail the work stealing device of schedulers and how it works in Go.

Planning Basics

The Go scheduler is made according to the M: N scheme and can use several processors. At any time, M goroutines should be distributed between N OS threads that run on a maximum of GOMAXPROCS processors. The Go Scheduler uses the following terminology for goroutines, threads, and processors:

G: goroutine
M: OS thread (M from Machine)
P: processor

Next, we have two queues specific to P. Each M must be assigned to its P. Ps may not have M if they are blocked or waiting for the end of the system call. At any moment, there can be a maximum of GOMAXPROCS processors - P. At any moment, only one M can be executed for each P. More than M can be created by the scheduler, if necessary.

Each planning cycle consists in searching for goroutine, which is ready to be launched and executed. With each cycle, the search comes in the following order:

runtime.schedule() {
    // только 1/61 от всего времени, проверить глобальную очередь G
    // если не найдено, проверить локальную очередь
    // если не найдено, то:
    //   попытаться украсть у других P
    //   если не вышло, проверить глобальную очередь
    //   если всё равно не вышло,  поллить (poll) сеть
}

Once a ready-to-execute G is found, it is executed until it is locked.

Note: It may seem that the global queue has an advantage over the local queue, but regular checking of the global queue is critical to avoid M using only goroutine from the local queue.

Theft (Stealing)

When a new G is created or an existing G becomes ready for execution, it is placed in the local queue of ready-to-execute goroutines of the current P. When P finishes executing G, it tries to pull (pop) G out of its queue. If the list is empty, P randomly selects another processor (P) and tries to steal half of the goroutines from its queue.

In the example above, P2 cannot find goroutines ready for execution. Therefore, he accidentally selects another processor (P1) and steals three gorutins in turn. P2 will now be able to start them and work will be more evenly distributed between processors.

Spinning threads

The scheduler always wants to distribute as many ready-to-execute goroutines as possible to many M in order to use all the processors, but at the same time, we must be able to suspend (park) very gluttonous processes in order to save CPU resources and energy. And at the same time, the scheduler must also be able to scale for tasks that really require a lot of processing power of the processor and great performance.

Constant preemption is both expensive and problematic for high-performance programs, where performance is the most critical. Goroutines do not have to constantly jump between OS threads, so this leads to increased latency. In addition to everything, when system calls are called, the thread must be constantly blocked and unlocked. This is expensive and leads to high overhead.

To reduce these goroutin jumps to and fro, the Go scheduler implements the so-called spinning threads. These threads use a little more processor power, but reduce the crowding out of the threads. A thread is considered looped if:

M assigned to P is looking for goroutine to run
M not assigned to P, searches for available P.
the scheduler also starts an additional thread and loops it when it is preparing a new goroutine and there is idle P and there are no other looped threads

At any given time, there can be a maximum of GOMAXPROCS looped M. When the looped stream finds work, it exits the looped state.

Idle threads assigned to any P are not blocked if there are other M not assigned to P. If a new goroutine is created or M is blocked, the scheduler checks and guarantees that there is at least one looped M. This ensures that all goroutines can be launched if possible and avoids unnecessary locks / unlocks of M.

conclusions

The Go scheduler does a lot of things to avoid excessive crowding out of threads, distributing them to underused processors by the “steal” method, and also by implementing “looped” threads to avoid frequent transitions from blocking to non-blocking state and vice versa.

Planning events can be monitored using execution tracer . You can get to the bottom of everything that happens inside the scheduler, especially if you think that in your case there is an inefficient use of processors.