Part 1: Available Here

In this part, we will look at how the go scheduler works under the hood to schedule goroutines in a fair and efficient manner.

Note: This part is completely optional and not required for doing multithreaded programming in go. It is intended to give a deeper understanding of how go handles the threads internally.

Prerequisites:

1. Written a basic program utilizing goroutine.

Table of Contents:

1. States of a goroutine
2. The M:N scheduler
3. Go scheduler — under the hood
4. Work stealing
5. Blocking calls
6. System calls and handoff
7. Fairness and preemption

States of a Goroutine:

Before, talking about the scheduler, let’s understand what are the lifecycle states of a goroutine.

1. Runnable State: A Goroutine enters the runnable state when it is created using the go keyword or after being unblocked from a previously blocked state, such as waiting on a mutex or IO operation.
2. Running State: The Goroutine’s code is actively running on a kernel thread, making progress in its computations.
3. Blocked State: A Goroutine transitions to the blocked state when it is waiting for external events, such as data on a channel, acquiring a lock, or waiting for I/O operations.

The M:N Scheduler:

As we saw in the previous part, mapping the goroutines to actual OS level threads is handled by a middle man called as go scheduler. Go scheduler follows a model where N goroutines are multiplexed into M OS level threads.

When the program starts, The go scheduler will dynamically allocate a pool of OS threads for itself. This is determined by the number of cores your CPU has multiplied by the number of hardware threads per core.

OS threads = number of CPU cores x hardware threads per core

Usually most modern day processors have 8 cores and 2 hardware threads per core. So, 8 x 2 = 16 OS threads will be created. This number can be controlled by setting the environment variable GOMAXPROCS by the developer.

The number of goroutines can be infinite depending on the memory usage and availability.

Go Scheduler — Under The Hood:

P (Processor): Represents a logical processor. Each processor is associated with an OS thread (M) and has its own Local Run Queue. Processors manage the execution of goroutines.

Operating System Threads (M): Actual operating system threads. The number of threads is determined by the runtime and is usually based on the available CPU cores.

There is also a Global Run Queue that can be shared by all the Processors.

When a new Goroutine is created using the go keyword or through other means, a corresponding Goroutine (G) structure is created to represent it. The Goroutine is initially in the “runnable” state, meaning it is eligible for execution.

The goroutine is added to either the local run queue or the global run queue depending on the availability. The local run queue has a size of 256 goroutines. If the local run queue is full, the goroutine will be added to the global run queue.

This is the goroutine structure g for reference.

type g struct {
    // Stack and stack-related fields
    stack       stack   // Goroutine stack
    stackguard0 uintptr // Stack growth barrier

    // Goroutine scheduler state
    status       uint32 // Goroutine status (e.g., _Gidle, _Grunnable, _Grunning, _Gsyscall)
    goid         int64  // Goroutine ID
    gopc         uintptr
    ctxt         unsafe.Pointer // Context for saving and restoring registers during a context switch
    racectx      uintptr
    pret         *sudog // Previous Goroutine in the run queue
    sched        gobuf  // Scheduler state
    sysblocktraced uint32 // Whether the Goroutine is traced for syscalls or not
    sysblock     uint32 // Goroutine is in a syscall

    // Other fields
    // ... (additional fields for various purposes)
}

type stack struct {
    lo uintptr
    hi uintptr
}

type sudog struct {
    // SudoG (Suspended Goroutine) structure
    g *g

    // ... (other fields for synchronization and waiting)
}

type gobuf struct {
    // Context for saving and restoring registers during a context switch
    // ... (registers, stack pointers, etc.)
}

// Various Goroutine status constants
const (
    _Gidle     = iota // Goroutine is not executing
    _Grunnable        // Goroutine is ready to run
    _Grunning         // Goroutine is currently running
    _Gsyscall         // Goroutine is in a syscall
    // ... (other status constants)
)

Work Stealing:

Each processor executes the goroutines in its local queue using the OS thread. If the local queue becomes empty, the processor can take half the goroutines of some other processor. This is known as work stealing and can help to distribute the load evenly.

If all the processor local queues are empty, the can take goroutines from the global run queue for execution.

Blocking Calls:

When some blocking operation like IO or network operation is made, the goroutine is descheduled and placed in blocking state so that other goroutines have a chance to execute.

For example, the goroutines waiting for a network request will be added to a Network Queue, which will be monitored by a background thread for completion. Once it completes, the goroutine will be back to runnable state again.

The processors can read from the network queue if there are no goroutines available in the local or global queues.

System Calls and Handoff:

What happens when a goroutine makes a system call and blocks the underlying OS thread. In this case, the processor will be assigned a new OS thread. This is known as Handoff.

Handoff’s are really expensive and are only done if the go scheduler knows that the system call will take a long time.

The go scheduler will monitor the old thread and when it comes back, it tries its best to assign it to the same processor it was running before. Otherwise, the goroutine is added to the global run queue.

Fairness and Preemption:

In order to prevent some goroutines from hogging up the CPU, the go scheduler can stop the execution of a goroutine if it wants and schedule an another goroutine instead. This is called preemption.

In general, If a goroutine takes more than 10ms, it will be preempted and added to the global queue. It will continue once all the other goroutines before it are completed or preempted.

To maintain fairness, the order in which the processors execute the goroutines is,

1. Local Queue
2. Global Queue
3. Network Queue

That’s it. We are done with the go scheduler. In the next part, we will continue with goroutines and communication between them using channels.

“How do you ever know for certain that you are doing the right thing?”
― Anthony Doerr, All the Light We Cannot See