Scheduling in Go

This is a note about how Go scheduler implementation.

Device Resource

The first thing important is the number of CPU within your device, if you are a win10 user like me, just pop up the teask manager, switch to the performance tab, and you will got the answer.

According to the above panel, there are 4 Cores and 8 Logical processors in my computer, and it will report to Go program that up to 8 virtual cores are available for task scheduling.

Let’s give it a test :

$ go run scheduling_1.go in
8

G, P, M Model

The scheduling mechanism in Go is combine with three main characters, Goroutine, Processor, and Machine. I’ll call it GPM model for short in this note.

• Goroutine (G)
  The task unit for scheduling, like a application-level thread. A Goroutine maintains its executing state, but only can be executed while attach to a Processor.
• Processor (P)
  Processor act as a executor of Foroutine, it owns the executing resource via binding with a virtual (logical) core. In addition to the Goroutine being executed, each Processor also associate with a local run queue, which is “LRQ”.
• Machine (M)
  Machine is actually a OS thread that still managed by the OS, and it must be placed on a core for executing. Also, each Machine individually attached to a Processor, it’s how the performance of scheduler affected by the number of cores.

Image from https://www.ardanlabs.com/blog/2018/08/scheduling-in-go-part2.html

• LRQ & GRQ (cooperating scheduler)
  As the note mention above, LRQ stands for local run queue, which belongs to each processor in order to manage the goroutines assigned to be executed.
  Another one is GRQ, global run queue, which exist for the unassigned goroutines. The mechanism of collaberating between LRQ and GRQ would be described later.

Scheduler

Go scheduler is not a preemptive scheduler but a cooperating scheduler. Being a cooperating scheduler means the scheduler needs well-defined user space events that happen at safe points in the code to make scheduling decisions. The followings are the opportunities for scheduling:

• The use of the keyword go
  This is how we create a new goroutine, scheduler gain an opportunity when a new goroutine was created.
• Garbage collection
  Since the GC runs using its own set of Goroutines, those Goroutines need time on an M to run, scheduler needs a opportunitt to handle that
• System calls
  Including async and sync system calls, go has different way to deal with them. With async type like network request, a network poller would be used, goroutine that might block is moved to net poller, let the proccesor can execute the next one.
  With sync type like file I/O, the current pair of G and M will be seperated from G, P, M model. Meawhile, a new machine would be created in order to keep the original G, P, M model working, and the block goroutine would be take back while system call finished.
• Synchronization and Orchestration
  If an mutex, or channel operation call will cause the Goroutine to block, the scheduler can context-switch a new Goroutine to run. Once the Goroutine can run again, it will be re-queued automatically.

Policies

Go have some mechanism to make workloads of processors are as average as possible, so the goroutines could be finished earlier. I’ll break it into two parts, assign policies and obtain policies.

Assign policies

When a new goroutine is created, it was marked runnable (like the runnable state of a thread) and look for a processor’s LRQ to attach on.

Obtain policies

While a processor finish the holding goroutine and its LRQ is empty, it will try to obtain some tasks from other places, called work stealing. The following is the order:

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.
}

When to use

Through the understanding of the scheduler, we can further think whether to use concurrent or parallel to improve performance.If a task is CPU bound, like file reading/writing and massive calculation, excessive context-switch and thread create need to be avoided.

On the other hand, for the I/O bound task like network requests and socket communication, most of the time concurrency will perform better than parallel. For the lightweight testing framework I am currently developing, because of the large number of network requests required to implement userstory, I chose Go with more concurrent features.

References

Scheduling In Go : Part II - Go Scheduler