Understanding Go scheduler

The Go scheduler is an essential part of the Go runtime responsible for managing goroutines, Go’s lightweight threads. Let’s break this down into simple concepts with clear code examples and easy words.

Prehumble: Concurrency in Go

Go is designed for concurrency. Its goroutines are lightweight threads managed by Go’s runtime instead of the operating system (OS). This runtime uses an M:N scheduler to multiplex M goroutines onto N OS threads.

The Scheduler

The scheduler is a part of the Go runtime that decides when and where goroutines run. It ensures:

1. Efficiency: Balancing CPU usage across cores.
2. Fairness: Ensuring all goroutines get CPU time.
3. Preemption: Stopping long-running goroutines to let others run.

The M:N Scheduler

The M:N model means:

• M goroutines run on N OS threads.
• The OS threads are distributed across the available CPU cores.

Example:

package main

import "fmt"

func main() {
    for i := 0; i < 5; i++ {
        go func(i int) {
            fmt.Printf("Goroutine %d\n", i)
        }(i)
    }
}

This spawns multiple goroutines, managed by Go’s M:N scheduler.

States of a Goroutine

A goroutine can be in one of these states:

1. Running: Actively executing.
2. Runnable: Ready but waiting for CPU time.
3. Waiting: Blocked, waiting for I/O or a timer.
4. Dead: Finished execution.

How Does the Scheduler Keep Track of Goroutines?

Goroutines are tracked using run queues:

1. Local run queues (per thread).
2. Global run queue (shared across threads).

Example: Runnable Goroutines

package main

import "time"

func worker() {
    for i := 0; i < 10; i++ {
        time.Sleep(100 * time.Millisecond)
        println("Working...")
    }
}

func main() {
    go worker() // Adds worker to the scheduler
    time.Sleep(1 * time.Second)
}

Fairness

Fairness ensures goroutines don’t starve for CPU time. The scheduler rotates between them, giving each a fair chance to execute.

How Fairness was Achieved in the Go Scheduler

1. Time slicing: Goroutines run for a fixed time before preemption.
2. Priority to the runnable queue: Ensures ready goroutines are prioritized.

Preemption

Preemption allows the scheduler to stop long-running goroutines to give others a chance.

Example:

package main

import (
    "time"
)

func longTask() {
    for {
        println("I might run forever, but I'll be preempted!")
    }
}

func main() {
    go longTask()
    time.Sleep(1 * time.Second)
}

Local Run Queues

Each thread (managed by a P, or Processor) has a local queue where most goroutines are scheduled.

M:P:N Threading Model

In Go:

• M: Goroutines.
• P: Processors (virtual CPUs).
• N: OS threads.

Work Stealing

If a processor’s local queue is empty, it “steals” work from another processor’s queue.

Network Poller

The network poller manages I/O. Goroutines waiting on network calls are offloaded, and the scheduler wakes them up when data is ready.

Cases Where All Queues are Empty

If local and global run queues are empty, the scheduler waits for:

1. New goroutines to be created.
2. I/O or timers to unblock waiting goroutines.

Fairness Hierarchy

1. Runnable goroutines: Always prioritized.
2. Blocked goroutines: Wait for events like I/O.
3. Sleeping goroutines: Woken up after timers expire.

Returning from a Handed-Off Syscall

When a goroutine finishes a syscall, it’s added back to the local or global queue for further execution.

Runtime APIs

The Go runtime provides APIs to interact with the scheduler:

1. runtime.Gosched(): Yields the processor, allowing other goroutines to run.
2. runtime.NumGoroutine(): Returns the number of active goroutines.

Example: runtime.Gosched()

package main

import (
    "fmt"
    "runtime"
)

func main() {
    go func() {
        for i := 0; i < 5; i++ {
            fmt.Println("Goroutine 1")
            runtime.Gosched() // Yield to another goroutine
        }
    }()
    
    go func() {
        for i := 0; i < 5; i++ {
            fmt.Println("Goroutine 2")
        }
    }()
    
    select {} // Block main from exiting
}