The M:N Concurrent Model — A Complete Guide. From First Principles to Production Schedulers

May 9, 2026 · by 0xKiireguideioconcurrencyepollnetworkinglinuxevent-loopczigrust

Table of Contents

1. The Three Threading Models
2. Core Concepts and Terminology
3. User-Space Context Switching
4. The Scheduler: Policies and Data Structures
5. Work Stealing
6. Building an M:N Scheduler from Scratch in C
7. Go's Goroutine Scheduler (GMP Model)
8. Rust and Tokio: Async M:N
9. Erlang/BEAM: Process-Based M:N
10. Java Project Loom: Virtual Threads
11. Channels and Communication
12. Synchronization Primitives in M:N Runtimes
13. I/O Integration and Event Loops
14. Debugging and Observability
15. Performance Analysis and Tuning
16. Design Patterns for M:N Systems

---

Chapter 1: The Three Threading Models

To understand M:N threading, you must first understand what came before it and why each model was invented to solve the problems of its predecessor.

1.1 The N:1 Model — Green Threads

The earliest form of user-space concurrency mapped N user threads onto exactly 1 kernel thread. The programmer writes code with multiple logical threads; the runtime schedules them cooperatively on a single OS thread.

User space:   [Thread A] [Thread B] [Thread C] [Thread D]
                    \         |         |     /
                     \        |         |    /
                      [  Runtime Scheduler  ]
                              |
Kernel space:         [Kernel Thread 1]
                              |
                         [CPU Core 0]

Advantages:

• Extremely cheap context switching (no kernel involvement)
• No race conditions on shared state between user threads (single-threaded kernel thread)
• Low memory overhead (stack can be small)
• Simple to implement

Disadvantages:

• Blocking syscalls block everything: If Thread A calls read() on a socket with no data, the single kernel thread blocks. Thread B, C, and D all starve. This is catastrophic.
• True parallelism is impossible: Even on a 128-core machine, you use one core.
• Cooperative scheduling hazards: A thread that never yields starves all others.

Early Java (1.1–1.2) used green threads. Early Ruby (MRI) used a similar model with the Global Interpreter Lock.

1.2 The 1:1 Model — Native Threads

The natural response to N:1's limitations: map every user thread to exactly one kernel thread.

User space:   [Thread A]  [Thread B]  [Thread C]  [Thread D]
                  |            |            |            |
Kernel space: [KThread 1] [KThread 2] [KThread 3] [KThread 4]
                  |            |            |            |
              [CPU Core 0] [CPU Core 1] [CPU Core 2] [CPU Core 3]

Advantages:

• Blocking syscalls block only one thread — others continue
• True parallelism across cores
• OS scheduler handles preemption automatically

Disadvantages:

• Kernel thread is expensive: Each kernel thread requires a kernel stack (8 KB on Linux by default, but can grow to MB), kernel data structures, and scheduler bookkeeping.
• Context switching is expensive: A context switch requires entering kernel mode, saving/restoring kernel registers, TLB flushing on some architectures, and potentially cache disruption.
• Scale ceiling: Creating 10,000 threads for 10,000 concurrent connections consumes gigabytes of stack memory and brings the scheduler to its knees. The classic C10K problem.
• Thread creation latency: pthread_create is not free. Creating thousands of threads per second is impractical.

Linux pthreads, Windows threads, and Java threads (post-1.2) all use 1:1.

1.3 The M:N Model — The Synthesis

The M:N model maps M user-space threads (often called green threads, goroutines, fibers, or tasks) onto N kernel threads, where N is typically bounded by the number of CPU cores.

User space:   [G1][G2][G3][G4][G5][G6][G7][G8]...[G10000]
                  \  |  |  /        \  |  |  /
               [  Scheduler  ]    [  Scheduler  ]
                     |                   |
Kernel space:  [KThread 1]         [KThread 2]
                     |                   |
               [CPU Core 0]         [CPU Core 1]

The key insight: N (kernel threads) matches hardware parallelism; M (green threads) matches logical concurrency.

With 4 cores, N=4. M can be 10,000. Each kernel thread runs a scheduler loop that picks a green thread from a run queue and executes it. When a green thread needs to block (I/O, mutex), instead of blocking the kernel thread, the runtime intercepts the operation, parks the green thread, and lets the kernel thread run another green thread.

Advantages:

• True parallelism: N kernel threads run on N cores simultaneously
• Massive concurrency: M can be 10^6 goroutines/tasks without memory explosion (each green thread starts with a tiny stack, e.g., 2 KB in Go)
• Cheap green thread creation: No kernel syscall, just allocate a small stack and push to a run queue
• Non-blocking I/O transparent to the programmer: The runtime automatically converts blocking I/O calls to async operations with green-thread parking

Disadvantages:

• Runtime complexity: The scheduler is a sophisticated piece of engineering
• Debugging difficulty: Stack traces, deadlock detection, and profiling are harder
• FFI complications: Calling C code that blocks can pin a kernel thread
• Signal handling complexity: Signals are delivered to kernel threads, not green threads

1.4 Comparing the Models

Property	N:1	1:1	M:N
True parallelism	✗	✓	✓
Cheap creation	✓	✗	✓
Cheap context switch	✓	✗	✓
Blocking I/O safe	✗	✓	✓
Scales to millions	✓	✗	✓
Preemptive scheduling	✗ (usually)	✓	Both
Implementation complexity	Low	Low	High

---

Chapter 2: Core Concepts and Terminology

2.1 The Taxonomy of Lightweight Concurrency

The ecosystem around M:N concurrency has an unfortunately inconsistent vocabulary. Different communities use different words for the same concepts. Let's establish precise definitions.

Green Thread

A user-space thread — a unit of execution with its own stack and register state, scheduled by a user-space runtime rather than the OS kernel. The term comes from Java's early green thread implementation. Often used interchangeably with "fiber" or "coroutine," though there are subtle distinctions.

Fiber

A cooperatively scheduled green thread. Fibers explicitly yield control; they do not preempt each other. C++ 20's std::coroutine, Windows Fibers, and many game engines use this model. The key property: a fiber switch only happens at explicit yield points.

Goroutine

Go's term for its lightweight concurrent functions. Goroutines are M:N scheduled, preemptible (since Go 1.14 via signal-based preemption), and start with a 2KB stack that grows dynamically.

Coroutine

A generalisation of functions that can suspend and resume execution. Coroutines can be symmetric (coroutines transfer control to each other directly) or asymmetric (a coroutine yields to its caller). Python's async def, Kotlin's suspend fun, and C++20 coroutines are asymmetric. Coroutines are the mechanism; green threads are the abstraction.

Task / Future / Promise

In async/await runtimes (Tokio, Node.js, Python asyncio), the schedulable unit is a task — a state machine compiled from async functions. Tasks are polled (pulled) rather than pushed by the scheduler.

Virtual Thread

Java's Project Loom terminology for its M:N green threads, mounted on carrier threads (OS threads). The distinction from goroutines is mostly marketing; the concept is identical.

Process (Erlang-style)

Erlang uses "process" for its lightweight concurrent units, which have no shared memory — communication is exclusively via message passing. Each Erlang process has its own heap; GC is per-process.

2.2 The Anatomy of a Green Thread

A green thread needs to maintain enough state to be suspended and resumed. Minimally:

struct GreenThread {
    // Execution context
    ucontext_t  context;        // Saved registers + stack pointer
    void*       stack;          // Stack memory
    size_t      stackSize;

    // Scheduling state
    ThreadState state;          // RUNNABLE, RUNNING, WAITING, DEAD
    uint64_t    id;

    // Run queue linkage
    GreenThread* next;          // Intrusive linked list for run queue

    // Blocking information
    WaitChannel* waitChan;      // What is this thread waiting for?
    uint64_t     wakeTime;      // For sleep/timer-based waking

    // For work stealing
    int          preferredWorker; // Locality hint
};

The ucontext_t (or an equivalent hand-rolled structure) stores:

• Instruction pointer (where to resume)
• Stack pointer
• Callee-saved general-purpose registers
• Floating point / SIMD state (sometimes lazily saved)
• Signal mask (sometimes)

2.3 Stack Management

Stack management is one of the most interesting engineering challenges in M:N runtimes.

Fixed Stacks

The simplest approach: allocate a fixed-size stack (e.g., 64 KB) per green thread. Fast and simple, but wastes memory for threads that use little stack, and overflows for threads with deep recursion.

// Fixed stack allocation
void* stack = mmap(NULL, STACK_SIZE,
    PROT_READ | PROT_WRITE,
    MAP_PRIVATE | MAP_ANONYMOUS | MAP_STACK,
    -1, 0);

// Guard page at the bottom to catch stack overflow
mprotect(stack, PAGE_SIZE, PROT_NONE);

Segmented Stacks (Go ≤1.3, GCC split stacks)

The stack is divided into segments. When the stack is about to overflow, a new segment is allocated and linked to the old one. The function epilogue checks remaining stack space on every call.

; x86-64 segmented stack check (simplified)
; At the top of every function:
cmp  rsp, [fs:thread_local_stack_limit]
jb   .stack_overflow_handler          ; Branch if we'd overflow

; ... function body ...

.stack_overflow_handler:
    call __morestack                   ; Allocate new segment, re-call function

Problem: The "hot split" performance issue. If a function is called in a tight loop near a segment boundary, it repeatedly allocates and deallocates segments, causing catastrophic slowdown (10-100×).

Copying / Growing Stacks (Go ≥1.4)

Go's current approach: when the stack is about to overflow, copy the entire stack to a new, larger allocation. This requires that all stack pointers within the stack are updated (Go's garbage collector handles this since it knows all pointer locations).

Benefits: no hot-split problem, amortized O(1) growth. Costs: all interior stack pointers must be updated, complex interaction with the GC.

Stack Pools

Pre-allocate stacks and recycle them. Most production runtimes do this to amortize allocation cost:

struct StackPool {
    Stack* freelist[NUM_SIZE_CLASSES]; // Size classes: 4K, 8K, 16K, ...
    SpinLock lock;
};

Stack* stackGet(size_t minSize) {
    int sizeClass = sizeToClass(minSize);
    lock(&pool.lock);
    Stack* s = pool.freelist[sizeClass];
    if (s) pool.freelist[sizeClass] = s->next;
    unlock(&pool.lock);
    return s ? s : stackAlloc(classToSize(sizeClass));
}

2.4 The Run Queue

The run queue holds green threads that are ready to execute but not currently running. Design choices:

Global queue (simple): One queue for all N kernel threads. Simple but causes contention — every thread must lock the queue to push/pop.

Per-worker local queues (most production systems): Each kernel thread ("worker" or "P" in Go) has its own local queue. Green threads are pushed locally first. Only when the local queue is empty does the worker attempt to steal from other workers or pull from a global overflow queue.

// Per-worker run queue (lock-free ring buffer)
#define LOCAL_QUEUE_CAP 256

struct LocalQueue {
    _Atomic uint32_t head;   // Producers write here (work stealer)
    _Atomic uint32_t tail;   // Owner writes here
    GreenThread*     buf[LOCAL_QUEUE_CAP];
};

// Owner pushes to tail (only owner does this, no lock needed)
bool localQueuePush(LocalQueue* q, GreenThread* g) {
    uint32_t tail = atomic_load_explicit(&q->tail, memory_order_relaxed);
    uint32_t head = atomic_load_explicit(&q->head, memory_order_acquire);
    if (tail - head >= LOCAL_QUEUE_CAP) return false; // Full
    q->buf[tail % LOCAL_QUEUE_CAP] = g;
    atomic_store_explicit(&q->tail, tail + 1, memory_order_release);
    return true;
}

// Owner pops from tail (LIFO for cache locality)
GreenThread* localQueuePop(LocalQueue* q) {
    uint32_t tail = atomic_load_explicit(&q->tail, memory_order_relaxed);
    if (tail == atomic_load_explicit(&q->head, memory_order_relaxed))
        return NULL; // Empty
    tail--;
    atomic_store_explicit(&q->tail, tail, memory_order_relaxed);
    GreenThread* g = q->buf[tail % LOCAL_QUEUE_CAP];
    if (atomic_load_explicit(&q->head, memory_order_acquire) > tail) {
        // Stolen! Undo
        atomic_store_explicit(&q->tail, tail + 1, memory_order_relaxed);
        return NULL;
    }
    return g;
}

---

Chapter 3: User-Space Context Switching

The fundamental operation of any M:N scheduler is switching execution context from one green thread to another without involving the kernel. This chapter explores exactly how that works at the hardware level.

3.1 What Is a Context Switch?

A context switch saves the current thread's register state to memory and loads another thread's register state. For a kernel context switch, this is done by the OS scheduler in a privileged mode transition. For a user-space context switch, we do it entirely in user code.

The registers we must save depend on the calling convention. On x86-64 (System V ABI):

Caller-saved (scratch) registers — the function being switched away from is responsible for saving these if it needs them. The switch function doesn't need to save them:

• rax, rcx, rdx, rsi, rdi, r8, r9, r10, r11
• xmm0–xmm15 (SSE/AVX)

Callee-saved registers — the function being switched to must preserve these. The switch function must save and restore these:

• rbx, rbp, r12, r13, r14, r15
• rsp (stack pointer)

The instruction pointer (rip) is implicitly saved as the return address on the stack when we call the switch function.

3.2 The ucontext API (POSIX)

POSIX provides ucontext_t for portable context manipulation:

#include <ucontext.h>
#include <stdlib.h>
#include <stdio.h>

#define STACK_SIZE (64 * 1024)  // 64 KB

ucontext_t main_ctx, fiber_ctx;

void fiber_function() {
    printf("Fiber: Hello from fiber!\n");
    swapcontext(&fiber_ctx, &main_ctx);  // Yield back to main
    printf("Fiber: Resumed!\n");
    swapcontext(&fiber_ctx, &main_ctx);  // Done, back to main
}

int main() {
    char* stack = malloc(STACK_SIZE);

    // Set up the fiber context
    getcontext(&fiber_ctx);
    fiber_ctx.uc_stack.ss_sp   = stack;
    fiber_ctx.uc_stack.ss_size = STACK_SIZE;
    fiber_ctx.uc_link          = &main_ctx; // Return to main when done
    makecontext(&fiber_ctx, fiber_function, 0);

    printf("Main: Switching to fiber\n");
    swapcontext(&main_ctx, &fiber_ctx);     // Switch to fiber

    printf("Main: Back from first yield\n");
    swapcontext(&main_ctx, &fiber_ctx);     // Resume fiber

    printf("Main: Fiber finished\n");
    free(stack);
    return 0;
}

Output:

Main: Switching to fiber
Fiber: Hello from fiber!
Main: Back from first yield
Fiber: Resumed!
Main: Fiber finished

swapcontext saves the current context (registers + stack pointer) into the first argument and loads the context from the second argument. It's essentially:

1. Push all callee-saved registers onto the current stack
2. Save the current rsp into ctx_from->uc_mcontext.gregs[REG_RSP]
3. Save the return address (rip) as well
4. Load rsp from ctx_to->uc_mcontext.gregs[REG_RSP]
5. Pop all callee-saved registers from the new stack
6. Return (which jumps to the saved rip)

3.3 Hand-Rolled Context Switching in Assembly

ucontext has overhead from saving signal masks (a syscall!). Production runtimes implement their own context switch in assembly. Here's a minimal x86-64 implementation:

; context.asm — Minimal x86-64 context switch
; Calling convention: switch_context(from_ctx, to_ctx)
;   rdi = from_ctx (pointer to Context struct)
;   rsi = to_ctx   (pointer to Context struct)
;
; Context layout (offsets must match C struct):
;   0:  rbx
;   8:  rbp
;   16: r12
;   24: r13
;   32: r14
;   40: r15
;   48: rsp
;   56: rip  (return address)

section .text
global switch_context

switch_context:
    ; ── Save current context into *from_ctx ──
    mov  [rdi +  0], rbx
    mov  [rdi +  8], rbp
    mov  [rdi + 16], r12
    mov  [rdi + 24], r13
    mov  [rdi + 32], r14
    mov  [rdi + 40], r15

    ; Save stack pointer
    mov  [rdi + 48], rsp

    ; Save return address (the instruction after the call to switch_context)
    mov  rax, [rsp]          ; rax = return address (top of stack)
    mov  [rdi + 56], rax

    ; ── Load new context from *to_ctx ──
    mov  rbx, [rsi +  0]
    mov  rbp, [rsi +  8]
    mov  r12, [rsi + 16]
    mov  r13, [rsi + 24]
    mov  r14, [rsi + 32]
    mov  r15, [rsi + 40]

    ; Restore stack pointer
    mov  rsp, [rsi + 48]

    ; Jump to saved return address (push onto new stack, then ret)
    mov  rax, [rsi + 56]
    push rax
    ret                      ; "Return" to the saved rip of to_ctx

The matching C struct:

typedef struct {
    uint64_t rbx, rbp, r12, r13, r14, r15;
    uint64_t rsp;
    uint64_t rip;
} Context;

extern void switch_context(Context* from, Context* to);

// Initialize a new context to start at 'func' with the given stack
void context_init(Context* ctx, void (*func)(void), void* stack, size_t stack_size) {
    // Stack grows downward; place the initial stack pointer at the top
    uint64_t* sp = (uint64_t*)((char*)stack + stack_size);

    // The "return address" for the initial call — if the function returns,
    // it returns to thread_exit (which cleans up)
    *--sp = (uint64_t)thread_exit;

    // The first "return" from switch_context jumps here
    *--sp = (uint64_t)func;

    ctx->rsp = (uint64_t)sp;
    ctx->rip = (uint64_t)func;

    // Callee-saved registers: initialize to 0
    ctx->rbx = ctx->rbp = ctx->r12 = ctx->r13 = ctx->r14 = ctx->r15 = 0;
}

This context switch is ~10 nanoseconds on modern hardware — compared to ~1–5 microseconds for a kernel context switch. That's 100–500× faster.

3.4 ARM64 Context Switch

For completeness, the ARM64 (AArch64) equivalent:

// context_arm64.S — AArch64 context switch
// Callee-saved registers on AArch64: x19-x28, x29 (fp), x30 (lr), d8-d15

.global switch_context
.type switch_context, %function

switch_context:
    // Save to *x0 (from_ctx)
    stp  x19, x20, [x0, #0]
    stp  x21, x22, [x0, #16]
    stp  x23, x24, [x0, #32]
    stp  x25, x26, [x0, #48]
    stp  x27, x28, [x0, #64]
    stp  x29, x30, [x0, #80]   // x29=frame pointer, x30=link register
    mov  x2,  sp
    str  x2,  [x0, #96]        // Save stack pointer

    // Optionally save float regs (d8-d15)
    stp  d8,  d9,  [x0, #104]
    stp  d10, d11, [x0, #120]
    stp  d12, d13, [x0, #136]
    stp  d14, d15, [x0, #152]

    // Load from *x1 (to_ctx)
    ldp  x19, x20, [x1, #0]
    ldp  x21, x22, [x1, #16]
    ldp  x23, x24, [x1, #32]
    ldp  x25, x26, [x1, #48]
    ldp  x27, x28, [x1, #64]
    ldp  x29, x30, [x1, #80]
    ldr  x2,  [x1, #96]
    mov  sp,  x2

    ldp  d8,  d9,  [x1, #104]
    ldp  d10, d11, [x1, #120]
    ldp  d12, d13, [x1, #136]
    ldp  d14, d15, [x1, #152]

    ret                        // Return to x30 (link register) = saved rip equivalent

3.5 The Cost of Context Switches

Even user-space context switches are not free. What makes them slow:

Register save/restore: ~10–20 cycles for the minimal set (no FPU). With FPU/SIMD state: ~50–100 cycles.

Cache effects: When thread A yields and thread B runs, thread B's data is likely not in L1/L2 cache. The first few memory accesses will be cache misses. This cache pollution cost is often larger than the mechanical register swap. This is why LIFO scheduling (run the most recently suspended thread next) can improve cache utilization.

TLB effects: If threads share the same address space (which they do in M:N runtimes), TLB entries remain valid. This is a significant advantage over process context switches.

Branch predictor pollution: The switch displaces branch predictor history. Minor but non-zero.

Practical measurements on a modern x86-64 machine:

• Bare switch_context call: ~8–15 ns
• Cold cache miss after switch: adds ~50–200 ns depending on working set
• Go's runtime.Gosched(): ~100–200 ns total
• pthread context switch (voluntary): ~2–5 µs
• pthread context switch (involuntary): ~5–20 µs

---

Chapter 4: The Scheduler — Policies and Data Structures

The scheduler is the heart of an M:N runtime. It decides which green thread runs next, how to distribute work across kernel threads, and how to handle blocking operations.

4.1 Scheduler Topology

A production M:N scheduler has several components:

┌─────────────────────────────────────────────────────────┐
│                    Global State                          │
│  globalQueue (overflow)   │  allThreads (for GC/debug)  │
│  idleWorkers              │  newThreadChan               │
└───────────────────────────┴─────────────────────────────┘
          │                              │
    ┌─────┴──────┐                ┌──────┴─────┐
    │  Worker 0  │                │  Worker 1  │
    │ (OS Thread)│                │ (OS Thread)│
    │            │                │            │
    │ localQueue │                │ localQueue │
    │ [G3][G7]   │                │ [G1][G5]   │
    │            │                │            │
    │  current:  │                │  current:  │
    │    G9      │                │    G2      │
    └────────────┘                └────────────┘

Key components:

Worker (P in Go): A kernel thread actively running green threads. There are exactly GOMAXPROCS workers (Go) or tokio::runtime::Builder::worker_threads (Tokio).

Local run queue: Per-worker, holds green threads ready to run. Accessed without locks by the owning worker; stolen from by other workers using lock-free operations.

Global run queue: Overflow queue when local queues are full. Protected by a mutex.

Idle list: Workers that have found no work sleep here. New green threads wake idle workers.

Network poller: Integration with epoll/kqueue/io_uring that wakes parked threads when I/O is ready.

4.2 Scheduling Policies

FIFO (First In, First Out)

The simplest policy. Runnable threads go to the back of the queue; the scheduler picks from the front.

Enqueue: [G1] → [G2] → [G3] → [G4]  (newest at back)
Dequeue:  G1  (oldest first)

Good for fairness (no starvation), bad for cache locality (a thread's data is cold by the time it runs again).

LIFO (Last In, First Out)

The most recently suspended thread runs next. Used by Go's local queues (push/pop from the same end).

Enqueue: push G5 onto top: [G5][G4][G3][G2][G1]
Dequeue: pop G5 from top

Excellent cache locality — the thread that just ran likely has warm caches. Risk of starvation if a thread always yields immediately.

Work Stealing

Each worker prefers its local queue (LIFO). When empty, it steals from another worker's queue (FIFO, taking from the opposite end to reduce contention). This is the de-facto standard policy and is covered in detail in the next chapter.

Priority Scheduling

Some runtimes (e.g., real-time systems) assign priorities to green threads. Not common in general-purpose M:N runtimes due to priority inversion complexity.

4.3 Scheduling Points

A scheduling point is a moment where the scheduler may switch to a different green thread. In a purely cooperative scheduler, these must be explicit. In a preemptive scheduler, they can happen at any time.

Cooperative scheduling points:

• Explicit yield() call
• Channel send/receive
• Mutex lock (when already locked)
• I/O operation
• sleep()
• Green thread creation (sometimes)

Preemptive scheduling points (added in Go 1.14):

• Signal delivery (Go uses SIGURG)
• Function prologues (checked by the compiler)
• Safe points inserted by the compiler/JIT

Preemption solves a critical problem: a tight compute loop with no I/O or yield calls would otherwise starve other green threads. Here's the problem:

// This goroutine would starve all others without preemption
go func() {
    for {
        sum := 0
        for i := 0; i < 1_000_000; i++ {
            sum += i  // No function call = no preemption point (old Go)
        }
    }
}()

Go's solution since 1.14: the signal handler for SIGURG checks if a goroutine has been running too long. If so, it sets a flag in the goroutine's stack, and the goroutine is preempted at the next safe point (a point where the GC can scan the stack).

4.4 The Scheduler Loop

The main scheduler loop on each worker thread:

void scheduler_loop(Worker* w) {
    while (true) {
        GreenThread* g = NULL;

        // 1. Try local queue first (LIFO for cache locality)
        g = localQueuePop(&w->localQueue);
        if (g) goto execute;

        // 2. Try to drain some from global queue
        // (check every ~61 iterations to ensure fairness)
        if (w->schedTick % 61 == 0) {
            g = globalQueuePop();
            if (g) goto execute;
        }

        // 3. Check network poller (non-blocking)
        g = netpollCheck(0);  // timeout=0: don't block
        if (g) goto execute;

        // 4. Try to steal from another worker
        g = stealFromOther(w);
        if (g) goto execute;

        // 5. Block on network poller (now we really have no work)
        g = netpollCheck(-1);  // timeout=-1: block until event
        if (g) {
            globalQueuePush(g);  // Others may have stolen work; don't assume local
            continue;
        }

        // 6. Park this worker (sleep, waiting for work)
        workerPark(w);
        // When woken, go back to top
        continue;

    execute:
        w->current = g;
        g->state = RUNNING;
        switch_context(&w->schedulerCtx, &g->context);
        // After switch_context returns: g has yielded/finished
        w->current = NULL;
        postSchedule(w, g);  // Put g back in queue or mark as dead
    }
}

The %61 check for the global queue is a technique borrowed from Go. If workers only checked local queues, newly created goroutines pushed to the global queue might never run. The prime number 61 spreads the global checks to avoid synchronisation bursts.

4.5 Goroutine State Machine

A green thread's lifecycle:

            spawn()
               │
               ▼
          ┌──────────┐
          │ RUNNABLE │◄──────────────────────────────┐
          └────┬─────┘                               │
               │ scheduler picks it                  │
               ▼                                     │
          ┌──────────┐    yield() /                  │
          │ RUNNING  │──── I/O / mutex ──► WAITING   │
          └────┬─────┘                      │        │
               │ returns                   │ event   │
               ▼                           └─────────┘
          ┌──────────┐
          │   DEAD   │
          └──────────┘

State transitions:

• RUNNABLE → RUNNING: Scheduler picks this thread and switches to it
• RUNNING → RUNNABLE: yield() or preemption (goes back to run queue)
• RUNNING → WAITING: Blocks on I/O, mutex, channel, sleep
• WAITING → RUNNABLE: I/O ready, mutex unlocked, channel has data, timer fires
• RUNNING → DEAD: Function returns

---

Chapter 5: Work Stealing

Work stealing is the scheduling algorithm that makes M:N runtimes efficient on multi-core machines. Without it, the naive approach would have workers sitting idle while other workers are overloaded.

5.1 The Problem: Load Imbalance

Imagine 4 workers and 8 green threads, initially:

Worker 0: [G1][G2][G3][G4][G5][G6][G7][G8]
Worker 1: (empty)
Worker 2: (empty)
Worker 3: (empty)

Without work stealing, Worker 0 does all the work while 1, 2, 3 are idle. We have 4 cores but use 1.

5.2 The Work Stealing Algorithm

The algorithm, originally from Cilk (MIT, 1994):

1. Each worker has a deque (double-ended queue)
2. Owner (the worker that owns the deque) pushes and pops from the bottom (LIFO)
3. Stealers pop from the top (FIFO) — opposite end from the owner

Why opposite ends? Reduces contention. The owner accesses the bottom without needing CAS operations in the common case. Stealers access the top with a CAS.

Owner pushes/pops here:      Stealers steal from here:
         ▼                              ▼
   [Bottom] ←───────────────────────► [Top]
    G8 G7 G6 G5 G4 G3 G2 G1

The stealing policy:

• A thief picks a victim (usually at random, or round-robin)
• Steals half the victim's deque (not just one item — amortises the overhead)

5.3 Lock-Free Work-Stealing Deque (Chase-Lev)

The Chase-Lev deque (2005) is the standard lock-free implementation used by Go, Tokio, and many other runtimes:

// Chase-Lev work-stealing deque
// "Dynamic Circular Work-Stealing Deque" — Chase & Lev, 2005
#define INITIAL_CAP 64

typedef struct {
    _Atomic(int64_t)  top;    // Stealers access this
    _Atomic(int64_t)  bottom; // Owner accesses this
    _Atomic(GreenThread**) buf; // The circular buffer
    int64_t           capacity;
} ChaseLevDeque;

// Owner pushes a task (single producer)
void deque_push(ChaseLevDeque* d, GreenThread* g) {
    int64_t b    = atomic_load_explicit(&d->bottom, memory_order_relaxed);
    int64_t t    = atomic_load_explicit(&d->top,    memory_order_acquire);
    GreenThread** buf = atomic_load_explicit(&d->buf, memory_order_relaxed);

    if (b - t > d->capacity - 1) {
        // Grow the deque
        buf = deque_grow(d, buf, b, t);
    }

    buf[b % d->capacity] = g;
    atomic_thread_fence(memory_order_release);
    atomic_store_explicit(&d->bottom, b + 1, memory_order_relaxed);
}

// Owner pops its own task (single consumer from bottom)
GreenThread* deque_pop(ChaseLevDeque* d) {
    int64_t b = atomic_load_explicit(&d->bottom, memory_order_relaxed) - 1;
    GreenThread** buf = atomic_load_explicit(&d->buf, memory_order_relaxed);
    atomic_store_explicit(&d->bottom, b, memory_order_relaxed);
    atomic_thread_fence(memory_order_seq_cst);

    int64_t t = atomic_load_explicit(&d->top, memory_order_relaxed);
    GreenThread* g = NULL;

    if (t <= b) {
        // Non-empty
        g = buf[b % d->capacity];
        if (t == b) {
            // Last item: race with stealers
            int64_t expected = t;
            if (!atomic_compare_exchange_strong_explicit(
                    &d->top, &expected, t + 1,
                    memory_order_seq_cst, memory_order_relaxed)) {
                g = NULL;  // Stealer got it
            }
            atomic_store_explicit(&d->bottom, b + 1, memory_order_relaxed);
        }
    } else {
        // Empty
        atomic_store_explicit(&d->bottom, b + 1, memory_order_relaxed);
    }
    return g;
}

// Stealer takes a task from the top (multiple producers possible)
GreenThread* deque_steal(ChaseLevDeque* d) {
    int64_t t = atomic_load_explicit(&d->top, memory_order_acquire);
    atomic_thread_fence(memory_order_seq_cst);
    int64_t b = atomic_load_explicit(&d->bottom, memory_order_acquire);

    if (t >= b) return NULL; // Empty

    GreenThread** buf = atomic_load_explicit(&d->buf, memory_order_consume);
    GreenThread* g = buf[t % d->capacity];

    int64_t expected = t;
    if (!atomic_compare_exchange_strong_explicit(
            &d->top, &expected, t + 1,
            memory_order_seq_cst, memory_order_relaxed)) {
        return NULL; // Lost the race to another stealer
    }
    return g;
}

5.4 Stealing Strategy

When should a worker steal, and from whom?

Random victim: Pick a random other worker. Simple, avoids hot-spots. Used by Go.

Round-robin: Try workers in order. Predictable, good when workers have similar load.

Steal half: When stealing, take half the victim's queue. This is more efficient than stealing one at a time — it amortises the CAS overhead and reduces future stealing.

// Steal up to half from victim's local queue
int stealHalf(LocalQueue* dst, LocalQueue* src) {
    int32_t head = atomic_load_explicit(&src->head, memory_order_acquire);
    int32_t tail = atomic_load_explicit(&src->tail, memory_order_relaxed);
    int32_t n    = tail - head;
    int32_t steal = n - n/2;  // Steal half, round up

    if (steal <= 0) return 0;

    for (int32_t i = 0; i < steal; i++) {
        GreenThread* g = src->buf[(head + i) % LOCAL_QUEUE_CAP];
        dst->buf[(dst->tail + i) % LOCAL_QUEUE_CAP] = g;
    }

    int32_t expected = head;
    if (!atomic_compare_exchange_strong_explicit(
            &src->head, &expected, head + steal,
            memory_order_acq_rel, memory_order_acquire)) {
        return 0;  // Another stealer raced us
    }

    atomic_fetch_add_explicit(&dst->tail, steal, memory_order_release);
    return steal;
}

5.5 Work Stealing and Cache Topology

On NUMA (Non-Uniform Memory Access) systems, stealing from a remote NUMA node is more expensive than stealing locally. Some runtimes use NUMA-aware stealing:

1. First try to steal from workers on the same socket
2. Only if that fails, steal from remote sockets

GreenThread* stealFromOther(Worker* w) {
    int numWorkers = getNumWorkers();

    // Phase 1: Try workers on the same NUMA node first
    for (int i = 0; i < numWorkers; i++) {
        Worker* victim = &workers[(w->id + i) % numWorkers];
        if (victim == w) continue;
        if (victim->numaNode != w->numaNode) continue;  // Skip remote NUMA

        GreenThread* g = deque_steal(&victim->deque);
        if (g) return g;
    }

    // Phase 2: Try remote NUMA nodes
    for (int i = 0; i < numWorkers; i++) {
        Worker* victim = &workers[(w->id + i) % numWorkers];
        if (victim == w) continue;

        GreenThread* g = deque_steal(&victim->deque);
        if (g) return g;
    }

    return NULL;
}

---

Chapter 6: Building an M:N Scheduler from Scratch in C

Theory is best understood through implementation. In this chapter we build a minimal but complete M:N scheduler in C: multiple OS threads, a shared run queue, user-space context switching, and basic I/O integration.

6.1 Data Structures

// scheduler.h
#pragma once
#include <stdint.h>
#include <stddef.h>
#include <stdbool.h>
#include <stdatomic.h>
#include <pthread.h>
#include <ucontext.h>

#define MAX_WORKERS     16
#define STACK_SIZE      (128 * 1024)  // 128 KB per green thread
#define LOCAL_QUEUE_CAP 256
#define GLOBAL_QUEUE_CAP 4096

// ── Green thread states ──────────────────────────────

typedef enum {
    GT_RUNNABLE,
    GT_RUNNING,
    GT_WAITING,
    GT_DEAD,
} GTState;

// ── Green thread (G) ─────────────────────────────────

typedef struct GreenThread GreenThread;
struct GreenThread {
    ucontext_t      ctx;            // Execution context
    void*           stack;          // Stack memory
    GTState         state;
    uint64_t        id;
    GreenThread*    next;           // Intrusive list link
    int             workerHint;     // Preferred worker (-1 = any)

    // For blocking
    int             waitFd;         // fd we're waiting on (-1 = none)
    short           waitEvents;     // POLLIN / POLLOUT

    // Function + arg
    void            (*fn)(void*);
    void*           arg;
};

// ── Per-worker local queue (ring buffer) ─────────────

typedef struct {
    _Atomic uint32_t head;
    _Atomic uint32_t tail;
    GreenThread*     buf[LOCAL_QUEUE_CAP];
} LocalQueue;

// ── Worker (M — one per OS thread) ──────────────────

typedef struct {
    pthread_t       tid;
    int             id;
    ucontext_t      schedulerCtx;   // Scheduler coroutine context
    GreenThread*    current;        // Currently running green thread
    LocalQueue      localQ;
    uint64_t        schedTick;
} Worker;

// ── Global scheduler state ────────────────────────────

typedef struct {
    // Workers
    Worker      workers[MAX_WORKERS];
    int         numWorkers;

    // Global run queue (protected by lock)
    pthread_mutex_t   globalLock;
    GreenThread*      globalHead;
    GreenThread*      globalTail;
    int               globalLen;

    // Green thread ID counter
    _Atomic uint64_t  nextID;

    // Stack pool
    pthread_mutex_t   stackLock;
    void*             stackPool[64];
    int               stackPoolLen;

    // Idle workers (sleeping, waiting for work)
    pthread_mutex_t   idleLock;
    pthread_cond_t    idleCond;
    int               idleCount;

    // Shutdown flag
    _Atomic bool      shutdown;
} Scheduler;

extern Scheduler sched;
extern __thread Worker* currentWorker;  // Thread-local current worker

// ── Public API ────────────────────────────────────────

void    scheduler_init(int numWorkers);
void    scheduler_run(void);
void    scheduler_shutdown(void);
uint64_t go(void (*fn)(void*), void* arg);
void    yield(void);
void    sleep_ms(int ms);

6.2 Implementation

// scheduler.c
#include "scheduler.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <time.h>
#include <assert.h>

Scheduler sched;
__thread Worker* currentWorker = NULL;

// ── Stack pool ────────────────────────────────────────

static void* stackAlloc(void) {
    pthread_mutex_lock(&sched.stackLock);
    if (sched.stackPoolLen > 0) {
        void* s = sched.stackPool[--sched.stackPoolLen];
        pthread_mutex_unlock(&sched.stackLock);
        return s;
    }
    pthread_mutex_unlock(&sched.stackLock);

    // Allocate with guard page
    void* mem = mmap(NULL, STACK_SIZE + 4096,
                     PROT_READ | PROT_WRITE,
                     MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (mem == MAP_FAILED) {
        perror("mmap stack");
        abort();
    }
    // Guard page at the bottom
    mprotect(mem, 4096, PROT_NONE);
    return (char*)mem + 4096;
}

static void stackFree(void* stack) {
    pthread_mutex_lock(&sched.stackLock);
    if (sched.stackPoolLen < 64) {
        sched.stackPool[sched.stackPoolLen++] = stack;
        pthread_mutex_unlock(&sched.stackLock);
        return;
    }
    pthread_mutex_unlock(&sched.stackLock);
    munmap((char*)stack - 4096, STACK_SIZE + 4096);
}

// ── Green thread entry trampoline ─────────────────────

static void greenThreadEntry(void) {
    Worker* w = currentWorker;
    GreenThread* g = w->current;

    // Call the user function
    g->fn(g->arg);

    // Done — mark dead and yield back to scheduler
    g->state = GT_DEAD;
    // Switch back to scheduler context
    swapcontext(&g->ctx, &w->schedulerCtx);
    // Should never reach here
    abort();
}

// ── Green thread creation ─────────────────────────────

GreenThread* greenThreadCreate(void (*fn)(void*), void* arg) {
    GreenThread* g = calloc(1, sizeof(GreenThread));
    if (!g) abort();

    g->id    = atomic_fetch_add(&sched.nextID, 1);
    g->fn    = fn;
    g->arg   = arg;
    g->state = GT_RUNNABLE;
    g->stack = stackAlloc();
    g->waitFd = -1;
    g->workerHint = -1;

    // Set up the ucontext
    getcontext(&g->ctx);
    g->ctx.uc_stack.ss_sp   = g->stack;
    g->ctx.uc_stack.ss_size = STACK_SIZE;
    g->ctx.uc_link          = NULL;  // We handle return manually
    makecontext(&g->ctx, greenThreadEntry, 0);

    return g;
}

// ── Local queue operations ────────────────────────────

static bool localQueuePush(LocalQueue* q, GreenThread* g) {
    uint32_t tail = atomic_load_explicit(&q->tail, memory_order_relaxed);
    uint32_t head = atomic_load_explicit(&q->head, memory_order_acquire);
    if (tail - head >= LOCAL_QUEUE_CAP) return false;
    q->buf[tail % LOCAL_QUEUE_CAP] = g;
    atomic_store_explicit(&q->tail, tail + 1, memory_order_release);
    return true;
}

static GreenThread* localQueuePop(LocalQueue* q) {
    uint32_t tail = atomic_load_explicit(&q->tail, memory_order_relaxed);
    uint32_t head = atomic_load_explicit(&q->head, memory_order_relaxed);
    if (tail == head) return NULL;
    tail--;
    atomic_store_explicit(&q->tail, tail, memory_order_relaxed);
    GreenThread* g = q->buf[tail % LOCAL_QUEUE_CAP];
    if (head > tail) {
        // Lost to a stealer — undo
        atomic_store_explicit(&q->tail, tail + 1, memory_order_relaxed);
        return NULL;
    }
    return g;
}

static GreenThread* localQueueSteal(LocalQueue* src, LocalQueue* dst) {
    // Steal half from src into dst
    uint32_t head = atomic_load_explicit(&src->head, memory_order_acquire);
    uint32_t tail = atomic_load_explicit(&src->tail, memory_order_relaxed);
    uint32_t n    = tail - head;
    uint32_t steal = n - n / 2;
    if (steal == 0) return NULL;

    for (uint32_t i = 0; i < steal; i++) {
        GreenThread* g = src->buf[(head + i) % LOCAL_QUEUE_CAP];
        uint32_t dtail = atomic_load_explicit(&dst->tail, memory_order_relaxed);
        dst->buf[dtail % LOCAL_QUEUE_CAP] = g;
        atomic_store_explicit(&dst->tail, dtail + 1, memory_order_release);
    }

    uint32_t expected = head;
    if (!atomic_compare_exchange_strong_explicit(
            &src->head, &expected, head + steal,
            memory_order_acq_rel, memory_order_relaxed)) {
        // Race: undo our dst writes by rolling back tail
        uint32_t dtail = atomic_load_explicit(&dst->tail, memory_order_relaxed);
        atomic_store_explicit(&dst->tail, dtail - steal, memory_order_relaxed);
        return NULL;
    }

    // Return the first stolen item to run now
    uint32_t dtail = atomic_load_explicit(&dst->tail, memory_order_relaxed) - 1;
    atomic_store_explicit(&dst->tail, dtail, memory_order_relaxed);
    return dst->buf[dtail % LOCAL_QUEUE_CAP];
}

// ── Global queue ──────────────────────────────────────

static void globalQueuePush(GreenThread* g) {
    g->next = NULL;
    pthread_mutex_lock(&sched.globalLock);
    if (sched.globalTail) sched.globalTail->next = g;
    else                  sched.globalHead = g;
    sched.globalTail = g;
    sched.globalLen++;
    pthread_mutex_unlock(&sched.globalLock);
}

static GreenThread* globalQueuePop(void) {
    pthread_mutex_lock(&sched.globalLock);
    GreenThread* g = sched.globalHead;
    if (g) {
        sched.globalHead = g->next;
        if (!sched.globalHead) sched.globalTail = NULL;
        sched.globalLen--;
        g->next = NULL;
    }
    pthread_mutex_unlock(&sched.globalLock);
    return g;
}

// ── Enqueue a green thread for execution ──────────────

void enqueue(GreenThread* g) {
    g->state = GT_RUNNABLE;
    Worker* w = currentWorker;

    // Prefer local queue if we're on a worker
    if (w && localQueuePush(&w->localQ, g)) {
        // Wake an idle worker if available
        pthread_mutex_lock(&sched.idleLock);
        if (sched.idleCount > 0) {
            pthread_cond_signal(&sched.idleCond);
        }
        pthread_mutex_unlock(&sched.idleLock);
        return;
    }

    // Overflow to global queue
    globalQueuePush(g);

    // Wake idle worker
    pthread_mutex_lock(&sched.idleLock);
    if (sched.idleCount > 0) pthread_cond_signal(&sched.idleCond);
    pthread_mutex_unlock(&sched.idleLock);
}

// ── Find next green thread to run ────────────────────

static GreenThread* findRunnable(Worker* w) {
    GreenThread* g;

    // 1. Local queue (LIFO)
    g = localQueuePop(&w->localQ);
    if (g) return g;

    // 2. Global queue (every 61 ticks for fairness)
    if (w->schedTick % 61 == 0) {
        g = globalQueuePop();
        if (g) return g;
    }

    // 3. Steal from another worker
    for (int i = 1; i < sched.numWorkers; i++) {
        int victim = (w->id + i) % sched.numWorkers;
        g = localQueueSteal(&sched.workers[victim].localQ, &w->localQ);
        if (g) return g;
    }

    // 4. Global queue (last resort)
    g = globalQueuePop();
    return g;
}

// ── The scheduler loop ────────────────────────────────

static void schedulerLoop(Worker* w) {
    while (!atomic_load(&sched.shutdown)) {
        w->schedTick++;

        GreenThread* g = findRunnable(w);

        if (!g) {
            // No work — park this worker
            pthread_mutex_lock(&sched.idleLock);
            sched.idleCount++;

            // Double check while holding lock
            g = globalQueuePop();
            if (g) {
                sched.idleCount--;
                pthread_mutex_unlock(&sched.idleLock);
                goto run;
            }

            struct timespec ts;
            clock_gettime(CLOCK_REALTIME, &ts);
            ts.tv_nsec += 10 * 1000000;  // 10ms timeout
            if (ts.tv_nsec >= 1000000000) { ts.tv_sec++; ts.tv_nsec -= 1000000000; }
            pthread_cond_timedwait(&sched.idleCond, &sched.idleLock, &ts);
            sched.idleCount--;
            pthread_mutex_unlock(&sched.idleLock);
            continue;
        }

    run:
        w->current = g;
        g->state = GT_RUNNING;

        // Switch to the green thread
        swapcontext(&w->schedulerCtx, &g->ctx);

        // We're back — the green thread yielded or finished
        w->current = NULL;

        if (g->state == GT_DEAD) {
            // Free resources
            stackFree(g->stack);
            free(g);
        }
        // If GT_RUNNABLE: already re-enqueued by yield()
        // If GT_WAITING: will be re-enqueued when its event fires
    }
}

// ── Worker OS thread entry ────────────────────────────

static void* workerThread(void* arg) {
    Worker* w = (Worker*)arg;
    currentWorker = w;
    schedulerLoop(w);
    return NULL;
}

// ── Public API ────────────────────────────────────────

void scheduler_init(int numWorkers) {
    if (numWorkers > MAX_WORKERS) numWorkers = MAX_WORKERS;
    memset(&sched, 0, sizeof(sched));
    sched.numWorkers = numWorkers;

    pthread_mutex_init(&sched.globalLock, NULL);
    pthread_mutex_init(&sched.stackLock,  NULL);
    pthread_mutex_init(&sched.idleLock,   NULL);
    pthread_cond_init (&sched.idleCond,   NULL);

    for (int i = 0; i < numWorkers; i++) {
        Worker* w = &sched.workers[i];
        w->id = i;
        memset(&w->localQ, 0, sizeof(w->localQ));
    }
}

void scheduler_run(void) {
    // Start worker threads (all but the current thread)
    for (int i = 1; i < sched.numWorkers; i++) {
        pthread_create(&sched.workers[i].tid, NULL,
                       workerThread, &sched.workers[i]);
    }
    // Main thread becomes worker 0
    currentWorker = &sched.workers[0];
    schedulerLoop(&sched.workers[0]);
}

void scheduler_shutdown(void) {
    atomic_store(&sched.shutdown, true);
    pthread_mutex_lock(&sched.idleLock);
    pthread_cond_broadcast(&sched.idleCond);
    pthread_mutex_unlock(&sched.idleLock);
    for (int i = 1; i < sched.numWorkers; i++) {
        pthread_join(sched.workers[i].tid, NULL);
    }
}

uint64_t go(void (*fn)(void*), void* arg) {
    GreenThread* g = greenThreadCreate(fn, arg);
    enqueue(g);
    return g->id;
}

void yield(void) {
    Worker* w = currentWorker;
    if (!w || !w->current) return;
    GreenThread* g = w->current;
    g->state = GT_RUNNABLE;
    enqueue(g);
    // Switch back to scheduler
    swapcontext(&g->ctx, &w->schedulerCtx);
}

void sleep_ms(int ms) {
    // Simple busy-wait sleep (real impl would use timerfd/kqueue)
    struct timespec ts = {ms / 1000, (ms % 1000) * 1000000L};
    // A real impl would park the goroutine and register a timer callback
    nanosleep(&ts, NULL);
}

6.3 Using the Scheduler

// example.c
#include "scheduler.h"
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

// Fibonacci with cooperative concurrency
void fib_worker(void* arg) {
    long n = (long)arg;
    long a = 0, b = 1;
    for (long i = 0; i < n; i++) {
        long c = a + b;
        a = b;
        b = c;
        if (i % 10000 == 0) yield();  // Cooperative yield
    }
    printf("fib(%ld) last = %ld\n", n, a);
}

void counter(void* arg) {
    int id = (int)(intptr_t)arg;
    for (int i = 0; i < 5; i++) {
        printf("Counter %d: tick %d\n", id, i);
        yield();
    }
}

void spawn_many(void* arg) {
    int n = (int)(intptr_t)arg;
    for (int i = 0; i < n; i++) {
        go(counter, (void*)(intptr_t)i);
    }
    printf("Spawned %d goroutines\n", n);
}

int main(void) {
    // 4 OS threads, each with work-stealing
    scheduler_init(4);

    go(spawn_many,   (void*)8);
    go(fib_worker,   (void*)100000L);
    go(fib_worker,   (void*)200000L);

    scheduler_run();   // Run until all work is done
    scheduler_shutdown();
    return 0;
}

Compile and run:

gcc -O2 -pthread -o scheduler scheduler.c example.c && ./scheduler

---

Chapter 7: Go's GMP Model

Go's scheduler is the most widely studied M:N implementation. Understanding it deeply will give you intuition applicable to any M:N runtime.

7.1 The Three Actors: G, M, P

Go's scheduler operates with three types of entities:

G (Goroutine): The green thread. Starts with a 2KB stack that can grow (via stack copying) to 1GB by default. Contains the goroutine's function, arguments, deferred functions, stack, and scheduler metadata.

M (Machine): An OS thread. There can be more Ms than Ps when goroutines block in cgo or syscalls. Ms execute goroutines.

P (Processor): The logical CPU — a scheduling context. There are exactly GOMAXPROCS Ps. A P holds the local run queue and other per-P resources. An M must hold a P to run goroutines. If M blocks in a syscall, it releases its P so another M can use it.

┌──────────────────────────────────────────────────────────┐
│  Global Run Queue: [G12][G13][G14]                       │
│  Network Poller: [G7(reading socket), G9(writing socket)]│
└──────────────────────────────────────────────────────────┘

 P0 (local queue: [G3][G5])        P1 (local queue: [G8][G11])
    │                                    │
    M0 (running G1)                   M1 (running G6)
    │                                    │
 [OS Thread]                        [OS Thread]
    │                                    │
 [CPU Core 0]                      [CPU Core 1]

 M2 (blocked in syscall, no P)
    │
 [OS Thread] ← parked, waiting for syscall return

7.2 The GMP State Machine

Key state transitions:

Goroutine creation (go statement):

1. Runtime calls newproc()
2. A G struct is acquired from a pool (or allocated)
3. Stack is assigned (from stack cache or pool)
4. G is pushed to current P's local queue
5. If there are idle Ps, wake an M to run it

Goroutine scheduling:

1. M calls schedule() in a loop
2. Checks P's local queue (every ~61 iterations, also check global queue for fairness)
3. If no local work, tries to steal from another P
4. If still no work, blocks until signaled

Goroutine blocking (e.g., channel receive):

1. gopark() is called — changes G state to waiting
2. Records what G is waiting for (channel, mutex, timer, etc.)
3. Switches to schedule() via mcall() — moves execution to the M's stack and calls schedule()
4. M finds a new G to run

Goroutine unblocking:

1. Event fires (channel has data, timer expired)
2. goready() is called, G moves to RUNNABLE
3. G is pushed to local queue (or global if local is full)
4. If an M is idle, wake it

Syscall entry:

// Before syscall: runtime.entersyscall()
// 1. Save goroutine state (stack, PC)
// 2. Set G state to Gsyscall
// 3. Detach P from M (handoff P to another M)

// After syscall: runtime.exitsyscall()
// 1. Try to get P back
// 2. If no P available, park M and put G in global queue

7.3 Work Stealing in Go

Go's stealing implementation in findRunnable() (simplified from src/runtime/proc.go):

func findRunnable() (gp *g, inheritTime bool) {
    _p_ := getg().m.p.ptr()

top:
    // 1. Check for GC work (high priority)
    if gcBlackenEnabled != 0 {
        gp := gcController.findRunnableGCWorker(_p_)
        if gp != nil { return gp, false }
    }

    // 2. Check local run queue
    if gp, inheritTime := runqget(_p_); gp != nil {
        return gp, inheritTime
    }

    // 3. Check global run queue (every 61 ticks)
    if _p_.schedtick%61 == 0 && sched.runqsize > 0 {
        lock(&sched.lock)
        gp := globrunqget(_p_, 1)
        unlock(&sched.lock)
        if gp != nil { return gp, false }
    }

    // 4. Check the network poller
    if netpollinited() && atomic.Load(&netpollWaiters) > 0 &&
        atomic.Load64(&sched.lastpoll) != 0 {
        if list := netpoll(0); !list.empty() {
            gp := list.pop()
            injectglist(&list)   // Put the rest in global queue
            return gp, false
        }
    }

    // 5. Try to steal from another P
    procs := uint32(gomaxprocs)
    ranTimer := false
    const stealTries = 4
    for i := 0; i < stealTries; i++ {
        if i == stealTries-1 {
            // Last try: include timers
            ranTimer = checkTimers(pp, 0)
        }
        for enum := stealOrder.start(fastrand()); !enum.done(); enum.next() {
            p2 := allp[enum.position()]
            if _p_ == p2 { continue }

            // Try stealing from p2
            if gp, tnow, w, newVal := runqsteal(_p_, p2, i == stealTries-1); gp != nil {
                return gp, false
            }
        }
    }

    // 6. Park this M
    // ... (complex logic involving race-free parking)
}

Key insights from the real code:

• GC worker goroutines have highest priority
• Timer checking is interleaved with stealing
• The steal order is randomised each time to avoid hot-spots
• Network poller is checked non-blockingly first, then blockingly when parking

7.4 Goroutine Preemption

Pre-Go 1.14, goroutines were only preempted at function call boundaries. A tight loop like:

func spin() {
    for {}  // Never preempted in old Go!
}

Would prevent GC and starve other goroutines on that P.

Since Go 1.14, Go uses signal-based preemption:

1. The sysmon goroutine (a special OS-level goroutine running without a P) monitors all Ps
2. If a P has been running the same G for >10ms, it sends SIGURG to the M running that P
3. The signal handler checks if the goroutine can be safely preempted at its current PC
4. If safe, it injects an asyncPreempt call — the goroutine "calls" this function which yields to the scheduler

// The injected preemption (runtime/preempt.go, simplified)
func asyncPreempt() {
    // Save all registers (must save caller-saved too, unlike normal context switch)
    var regs asm.Regs
    asm.SaveAllRegs(&regs)

    // Check if we should preempt
    gp := getg()
    if gp.preempt {
        mcall(preemptPark)  // Park this goroutine
    }

    // Restore registers and return
    asm.RestoreAllRegs(&regs)
}

7.5 The sysmon Thread

sysmon (system monitor) is a special goroutine that runs on its own OS thread (without a P) and performs maintenance:

• Retract P from blocked goroutines: If a goroutine is in a syscall and its P hasn't been retracted, do it after 20µs
• Preempt long-running goroutines: Send SIGURG to M if G has run >10ms
• Poll network: Ensure the netpoller is checked even when all workers are busy
• Force GC: Trigger GC if too much time has passed
• Scavenge heap: Return unused memory to the OS

func sysmon() {
    for {
        delay := usleep_lo  // Start with 20µs sleep
        if idle > 50 {      // Increase to 10ms if consistently idle
            delay = 10 * 1000
        }
        usleep(delay)

        // Retract Ps from goroutines stuck in syscalls
        lastpoll := int64(atomic.Load64(&sched.lastpoll))
        now := nanotime()
        if netpollinited() && lastpoll != 0 && lastpoll+10*1000*1000 < now {
            atomic.Cas64(&sched.lastpoll, uint64(lastpoll), uint64(now))
            list := netpoll(0) // non-blocking
            if !list.empty() {
                injectglist(&list)
            }
        }

        // Retract Ps and preempt goroutines
        if retake(now) != 0 {
            idle = 0
        } else {
            idle++
        }
    }
}

7.6 Goroutine Stacks: The Copying Collector

When a goroutine's stack is about to overflow, Go copies the entire stack to a larger allocation. This requires updating all interior stack pointers.

The garbage collector already tracks all pointers — it uses stack maps (bitmaps generated by the compiler) that identify which words on the stack are pointers. When copying a stack:

1. Allocate a new stack (twice as large)
2. Copy old stack contents to new stack
3. Adjust all frame pointers (using stack maps)
4. Adjust all Goroutine-internal pointers (e.g., deferred function arguments)
5. Update the goroutine's stack bounds

Before copy:
Stack: [low_addr ..................... high_addr]
        frame0    frame1    frame2    frame3
        
After copy (2× size):
Stack: [new_low ....................................... new_high]
        frame0    frame1    frame2    frame3    (new free space)
        
All pointers within stack updated to new_low + original_offset

This is why Go can't have references from the heap to goroutine stacks — such references would become dangling after a stack copy. (Go's escape analysis ensures that objects that would be stack-addressed but escape to the heap are allocated on the heap instead.)

---

Chapter 8: Rust and Tokio — Async M:N

Rust's M:N story is different from Go's. Instead of runtime goroutines, Rust uses zero-cost async/await — the compiler transforms async functions into state machines, and a runtime (Tokio, async-std, smol) executes them.

8.1 Async Functions as State Machines

When you write:

async fn fetch_data(url: &str) -> Result<String, reqwest::Error> {
    let response = reqwest::get(url).await?;
    let body = response.text().await?;
    Ok(body)
}

The compiler generates roughly:

// Conceptual desugaring (actual codegen is more complex)
enum FetchDataState {
    Start { url: String },
    AwaitingGet { future: reqwest::RequestFuture },
    AwaitingText { future: reqwest::TextFuture },
    Done,
}

impl Future for FetchDataStateMachine {
    type Output = Result<String, reqwest::Error>;

    fn poll(mut self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output> {
        loop {
            match &mut *self {
                FetchDataState::Start { url } => {
                    // Start the GET request
                    let fut = reqwest::get(url);
                    *self = FetchDataState::AwaitingGet { future: fut };
                    // Fall through to poll the new state
                }
                FetchDataState::AwaitingGet { future } => {
                    match Pin::new(future).poll(cx) {
                        Poll::Pending  => return Poll::Pending,  // Not ready yet
                        Poll::Ready(r) => {
                            let response = r?;
                            let fut = response.text();
                            *self = FetchDataState::AwaitingText { future: fut };
                        }
                    }
                }
                FetchDataState::AwaitingText { future } => {
                    match Pin::new(future).poll(cx) {
                        Poll::Pending  => return Poll::Pending,
                        Poll::Ready(r) => {
                            *self = FetchDataState::Done;
                            return Poll::Ready(Ok(r?));
                        }
                    }
                }
                FetchDataState::Done => panic!("polled after completion"),
            }
        }
    }
}

Key insight: no stack is allocated. The state machine holds only the variables that need to survive across await points. A goroutine-style runtime keeps an actual stack per goroutine; Rust's async keeps a tiny enum. This is why Rust's async is called "zero-cost" — the overhead is exactly what the explicit state machine would cost, nothing more.

8.2 The Waker Mechanism

How does a task know when to be re-polled? The Waker:

use std::sync::Arc;
use std::task::{RawWaker, RawWakerVTable, Waker};

// A Waker is a reference-counted pointer to a task handle
// When called, it tells the runtime to re-schedule the task

struct TaskWaker {
    task: Arc<Task>,
}

impl TaskWaker {
    fn wake(self: Arc<Self>) {
        // Re-enqueue the task for polling
        self.task.runtime.enqueue(self.task.clone());
    }
}

// The Future::poll signature:
// fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output>
//
// Context holds the Waker. When a future can't make progress, it:
// 1. Registers the Waker with the event source (epoll, channel, timer)
// 2. Returns Poll::Pending
//
// When the event fires, the event source calls waker.wake()
// Which enqueues the task back onto the runtime's run queue

8.3 Tokio's Architecture

Tokio uses a multi-threaded M:N runtime with work stealing:

                 ┌─────────────────────┐
                 │   tokio::runtime    │
                 │                     │
                 │  io_driver (epoll)  │
                 │  timer_wheel        │
                 │  global_queue       │
                 └──────────┬──────────┘
                            │
          ┌─────────────────┼─────────────────┐
          │                 │                 │
   ┌──────┴──────┐  ┌───────┴─────┐  ┌────────┴────┐
   │  Worker 0   │  │  Worker 1   │  │  Worker 2   │
   │             │  │             │  │             │
   │ local_queue │  │ local_queue │  │ local_queue │
   │ [T2][T5]    │  │ [T1][T3]    │  │ [T4][T6]    │
   │             │  │             │  │             │
   │ running: T8 │  │ running: T7 │  │ running: T9 │
   └─────────────┘  └─────────────┘  └─────────────┘
         │                 │                 │
      [OS Thread]      [OS Thread]      [OS Thread]

Building a Tokio application:

use tokio::io::AsyncReadExt;
use tokio::net::{TcpListener, TcpStream};
use tokio::sync::Semaphore;
use std::sync::Arc;

// Tokio handles 10,000 concurrent connections with ~4 OS threads
#[tokio::main(flavor = "multi_thread", worker_threads = 4)]
async fn main() -> Result<(), Box<dyn std::error::Error>> {
    let listener = TcpListener::bind("0.0.0.0:8080").await?;
    let semaphore = Arc::new(Semaphore::new(10_000)); // Max 10K concurrent conns

    println!("Listening on :8080");

    loop {
        let (stream, addr) = listener.accept().await?;
        let permit = semaphore.clone().acquire_owned().await?;

        tokio::spawn(async move {
            let _permit = permit;  // Released when this task ends
            if let Err(e) = handle_connection(stream).await {
                eprintln!("Error from {}: {}", addr, e);
            }
        });
    }
}

async fn handle_connection(mut stream: TcpStream) -> Result<(), std::io::Error> {
    let mut buf = vec![0u8; 4096];
    loop {
        let n = stream.read(&mut buf).await?;  // Non-blocking via epoll
        if n == 0 { break; }                    // EOF

        // Process request (could await other things here)
        let response = process(&buf[..n]).await;
        stream.write_all(&response).await?;
    }
    Ok(())
}

async fn process(data: &[u8]) -> Vec<u8> {
    // Could call database, other services, etc.
    // All non-blocking, all cooperative
    data.to_vec()  // Echo for simplicity
}

8.4 Blocking Tasks and spawn_blocking

A crucial concern in async Rust: CPU-bound or blocking work must not run on async worker threads, because it prevents the event loop from making progress. Tokio provides spawn_blocking:

use tokio::task;

async fn mixed_workload() {
    // CPU-bound work: run on a separate thread pool
    let result = task::spawn_blocking(|| {
        // This can block as long as it wants — it's on a blocking thread
        let mut sum = 0u64;
        for i in 0..100_000_000 {
            sum += i;
        }
        sum
    }).await.unwrap();

    println!("Sum: {}", result);

    // I/O-bound work: stays on async worker
    let content = tokio::fs::read_to_string("file.txt").await.unwrap();
    println!("File length: {}", content.len());
}

Tokio maintains two thread pools:

• Async workers: Small, fixed count (defaults to number of CPUs). Must never block.
• Blocking pool: Grows on demand (up to 512 threads by default). Used for spawn_blocking.

8.5 Rust vs Go: Philosophy Comparison

Aspect	Go	Rust/Tokio
Stack per task	Yes (2KB–1GB, copying)	No (state machine, stack only during poll)
Memory per idle task	~8KB typical	64–256 bytes (state machine size)
Blocking safety	Runtime detects + handles	Compiler/programmer responsibility
Syntax	go func() / natural	async/await
Startup cost	Fork-and-forget	Must build future, spawn
Preemption	Signal-based (Go 1.14+)	No (must use yield_now())
FFI blocking	Handled via handoff	Must use spawn_blocking

---

Chapter 9: Erlang/BEAM — Process-Based M:N

Erlang's BEAM virtual machine represents a radical approach: millions of isolated processes with no shared memory, communicating only through message passing. This is M:N scheduling taken to its logical extreme for fault tolerance.

9.1 The BEAM Process Model

% Spawn 1 million processes — each gets ~300 bytes overhead
lists:foreach(fun(I) ->
    spawn(fun() ->
        receive
            {ping, From} -> From ! pong
        end
    end)
end, lists:seq(1, 1_000_000)).

BEAM processes:

• Have their own heap (no shared memory between processes)
• Are scheduled by the BEAM scheduler, not the OS
• Have bounded reduction counts — each process gets 2000 "reductions" (roughly, function calls) before being preempted
• Communicate via message passing through a per-process mailbox

9.2 BEAM's Scheduler Architecture

BEAM uses N scheduler threads (one per CPU core by default) plus a small pool of I/O threads:

┌─────────────────────────────────────────────────────────────┐
│                     BEAM VM                                  │
│                                                             │
│  Scheduler 1      Scheduler 2      Scheduler 3              │
│  [Run Queue]      [Run Queue]      [Run Queue]              │
│  P1 P3 P7         P2 P5 P9         P4 P6 P8                │
│       │                 │                 │                 │
│  [OS Thread]      [OS Thread]      [OS Thread]              │
│                                                             │
│  Async I/O Pool (separate OS threads for file/DNS ops)      │
│  [Thread][Thread][Thread][Thread]                           │
│                                                             │
│  Timer Thread                                               │
│  [Thread]                                                   │
└─────────────────────────────────────────────────────────────┘

Key BEAM scheduler properties:

Reduction-based preemption: A "reduction" is roughly one function call. Each process gets 2000 reductions per scheduling slice. When reductions are exhausted, the process is preempted and sent to the back of the run queue. This ensures no process can starve others regardless of what it's computing.

Per-process GC: Because processes have isolated heaps, GC happens per-process. No global stop-the-world GC — each process is collected individually when its heap is full. This is a major factor in BEAM's legendary low-latency characteristics.

Work stealing: BEAM schedulers steal work from each other similarly to Go and Tokio.

9.3 OTP and Supervision Trees

Erlang's M:N model enables its famous fault-tolerance architecture:

% Supervisor: monitors workers, restarts on failure
-module(my_supervisor).
-behaviour(supervisor).

init([]) ->
    Children = [
        #{id => worker_1,
          start => {my_worker, start_link, [arg1]},
          restart => permanent,    % Always restart
          shutdown => 5000,
          type => worker},
        #{id => worker_2,
          start => {my_worker, start_link, [arg2]},
          restart => transient,    % Restart only on abnormal exit
          shutdown => 5000,
          type => worker}
    ],
    {ok, {#{strategy => one_for_one,  % Restart only failed child
            intensity => 5,           % Max 5 restarts
            period => 60},            % Per 60 seconds
          Children}}.

When worker_1 crashes, the supervisor spawns a fresh process. The isolation guarantee (no shared memory) means the crash cannot corrupt worker_2's state. The restart is fast — spawning a new BEAM process takes microseconds.

9.4 The receive Pattern and Mailboxes

Each Erlang process has a mailbox. receive blocks the process (not the OS thread — it parks the process and lets the scheduler run others):

% A simple stateful server process
-module(counter).
-export([start/0, increment/1, get/1]).

start() ->
    spawn(fun() -> loop(0) end).

loop(Count) ->
    receive
        {increment, N, From} ->
            From ! {ok, Count + N},
            loop(Count + N);
        {get, From} ->
            From ! {count, Count},
            loop(Count);
        stop ->
            ok   % Process terminates
    end.

% Client API
increment(Pid) ->
    Pid ! {increment, 1, self()},
    receive {ok, NewCount} -> NewCount end.

get(Pid) ->
    Pid ! {get, self()},
    receive {count, C} -> C end.

Under the hood, receive checks the mailbox (O(n) in mailbox size — a known weak point), and if empty, parks the process in a wait state. When a message arrives, the process is moved to the run queue.

9.5 Comparison: Erlang vs Go vs Rust

Property	Erlang/BEAM	Go	Rust/Tokio
Isolation	Full (per-process heap)	None (shared heap)	None (shared heap)
Communication	Message passing only	Channels + shared mem	Channels + shared mem
GC	Per-process, incremental	Stop-the-world (short)	None (ownership)
Fault tolerance	Built-in supervision	Manual	Manual
Max processes	~134 million tested	Millions	Millions (tasks)
Preemption	Reduction-based (hard)	Signal-based (Go 1.14+)	None (cooperative)

---

Chapter 10: Java Project Loom — Virtual Threads

Java's traditional model was 1:1: every Java thread was a platform (OS) thread. The C10K problem hit Java servers hard — 10,000 concurrent HTTP connections meant 10,000 OS threads.

Project Loom, released in Java 21 as a production feature, adds virtual threads: lightweight, M:N scheduled threads managed by the JVM.

10.1 Virtual Thread Basics

import java.util.concurrent.*;

// Old way: 10,000 OS threads (memory-intensive, slow)
ExecutorService old = Executors.newFixedThreadPool(200);  // Must limit!

// New way: 10,000 virtual threads (each ~1KB overhead)
ExecutorService vt = Executors.newVirtualThreadPerTaskExecutor();

// Spawn 100,000 virtual threads — works fine
try (var executor = Executors.newVirtualThreadPerTaskExecutor()) {
    for (int i = 0; i < 100_000; i++) {
        final int id = i;
        executor.submit(() -> {
            // This can block! Virtual thread parks; carrier thread continues.
            Thread.sleep(1000);
            System.out.println("Task " + id + " done on " + Thread.currentThread());
            return null;
        });
    }
}

Output shows tasks running on a small pool of carrier threads:

Task 0 done on VirtualThread[#23]/runnable@ForkJoinPool-1-worker-1
Task 1 done on VirtualThread[#24]/runnable@ForkJoinPool-1-worker-2
Task 2 done on VirtualThread[#25]/runnable@ForkJoinPool-1-worker-1

10.2 Carrier Threads and Mounting

Virtual threads run on carrier threads (platform threads). The JVM scheduler mounts a virtual thread onto a carrier thread when it's runnable, and unmounts it when it blocks:

Virtual Thread lifecycle:
  NEW → RUNNABLE → MOUNTED (running on carrier) → UNMOUNTED (parked) → RUNNABLE → ...

Mounting event: virtual thread selected from run queue, copied onto carrier's stack
Unmounting event: virtual thread calls blocking operation (I/O, sleep, synchronized)

The JVM intercepts blocking operations:

• Thread.sleep() → park virtual thread, let carrier run another
• InputStream.read() → park virtual thread, register with I/O poller
• Lock.lock() (java.util.concurrent) → park virtual thread, add to lock wait queue
• synchronized block → pins the virtual thread (cannot unmount while in synchronized)

Pinning is the current limitation: code in synchronized blocks cannot be unmounted. A blocking operation inside synchronized blocks the carrier thread. This is why Project Loom recommends migrating synchronized to ReentrantLock:

// BAD: pins the virtual thread
synchronized (lock) {
    database.query();   // Blocks; pins carrier thread
}

// GOOD: virtual thread can be unmounted
lock.lock();
try {
    database.query();   // Blocks; virtual thread parks, carrier continues
} finally {
    lock.unlock();
}

10.3 Structured Concurrency

Java 21+ also introduces structured concurrency — a disciplined approach where subtasks' lifetimes are bounded by the parent scope:

import java.util.concurrent.StructuredTaskScope;

String fetchWithTimeout(String userId) throws Exception {
    try (var scope = new StructuredTaskScope.ShutdownOnFailure()) {
        // Both subtasks are scoped to this try block
        StructuredTaskScope.Subtask<String> profile =
            scope.fork(() -> fetchProfile(userId));   // Virtual thread
        StructuredTaskScope.Subtask<String> orders  =
            scope.fork(() -> fetchOrders(userId));    // Virtual thread

        scope.join()           // Wait for both
             .throwIfFailed(); // Propagate any exception

        // Both completed successfully
        return combineResults(profile.get(), orders.get());
    }
    // When try block exits: scope cancelled, all subtasks terminated
    // Lifetime of subtasks cannot outlive parent scope
}

This eliminates the classic bug where spawned tasks outlive their parent and access freed resources.

---

Chapter 11: Channels and Communication

Channels are the primary communication primitive in M:N runtimes. They allow green threads to exchange data safely without explicit locks.

11.1 Channel Taxonomy

Unbuffered channels (rendezvous): Sender blocks until receiver is ready, and vice versa. Guarantees synchronisation at every message. Used when coordination matters more than throughput.

Buffered channels: A queue of fixed capacity. Sender only blocks when the buffer is full. Receiver only blocks when the buffer is empty. Decouples sender and receiver speeds.

Unbounded channels: Never block the sender (until OOM). Risk: fast producers overwhelm slow consumers (backpressure problem).

One-shot channels: Send exactly one value. Common for async results/futures.

Select / select!: Wait on multiple channels simultaneously, handling whichever is ready.

11.2 Implementing an Unbuffered Channel

// Synchronous (rendezvous) channel
// Sender and receiver must both be ready simultaneously

typedef struct {
    GreenThread*    sender;    // Parked sender (NULL if none waiting)
    GreenThread*    receiver;  // Parked receiver (NULL if none waiting)
    void*           value;     // The value being transferred
    bool            closed;
    pthread_mutex_t lock;      // Brief critical section only
} Channel;

// Send blocks until a receiver is ready
void chan_send(Channel* ch, void* value) {
    pthread_mutex_lock(&ch->lock);

    if (ch->receiver) {
        // A receiver is already waiting — hand off directly
        GreenThread* recv = ch->receiver;
        ch->receiver = NULL;
        recv->waitResult = value;     // Put value in receiver's result slot
        pthread_mutex_unlock(&ch->lock);
        enqueue(recv);                // Wake the receiver
        return;
    }

    // No receiver — park this sender
    GreenThread* g = currentWorker->current;
    g->waitValue = value;
    ch->sender = g;
    g->state = GT_WAITING;
    pthread_mutex_unlock(&ch->lock);

    // Yield to scheduler — will be woken when receiver arrives
    swapcontext(&g->ctx, &currentWorker->schedulerCtx);
}

// Receive blocks until a sender is ready
void* chan_recv(Channel* ch) {
    pthread_mutex_lock(&ch->lock);

    if (ch->sender) {
        // A sender is already waiting — grab the value
        GreenThread* send = ch->sender;
        void* value = send->waitValue;
        ch->sender = NULL;
        pthread_mutex_unlock(&ch->lock);
        enqueue(send);               // Wake the sender
        return value;
    }

    // No sender — park this receiver
    GreenThread* g = currentWorker->current;
    ch->receiver = g;
    g->state = GT_WAITING;
    pthread_mutex_unlock(&ch->lock);

    swapcontext(&g->ctx, &currentWorker->schedulerCtx);
    return g->waitResult;            // Set by the sender
}

11.3 Implementing a Buffered Channel

typedef struct {
    void**          buf;
    uint32_t        cap;
    _Atomic uint32_t head;
    _Atomic uint32_t tail;
    _Atomic uint32_t count;

    // Waiting lists
    GreenThread*    sendWaiters;  // Parked senders (when full)
    GreenThread*    recvWaiters;  // Parked receivers (when empty)
    pthread_mutex_t lock;
    bool            closed;
} BufferedChan;

bool bchan_send(BufferedChan* ch, void* value) {
    pthread_mutex_lock(&ch->lock);

    if (ch->closed) {
        pthread_mutex_unlock(&ch->lock);
        return false;  // Send on closed channel
    }

    // Is there a waiting receiver? Short-circuit the buffer
    if (ch->recvWaiters) {
        GreenThread* recv = ch->recvWaiters;
        ch->recvWaiters = recv->next;
        recv->waitResult = value;
        pthread_mutex_unlock(&ch->lock);
        enqueue(recv);
        return true;
    }

    // Is there space in the buffer?
    if (atomic_load(&ch->count) < ch->cap) {
        uint32_t tail = atomic_load(&ch->tail);
        ch->buf[tail % ch->cap] = value;
        atomic_store(&ch->tail, tail + 1);
        atomic_fetch_add(&ch->count, 1);
        pthread_mutex_unlock(&ch->lock);
        return true;
    }

    // Buffer full — park sender
    GreenThread* g = currentWorker->current;
    g->waitValue = value;
    g->next = ch->sendWaiters;
    ch->sendWaiters = g;
    g->state = GT_WAITING;
    pthread_mutex_unlock(&ch->lock);
    swapcontext(&g->ctx, &currentWorker->schedulerCtx);
    return true;
}

void* bchan_recv(BufferedChan* ch) {
    pthread_mutex_lock(&ch->lock);

    // Buffer has data?
    if (atomic_load(&ch->count) > 0) {
        uint32_t head = atomic_load(&ch->head);
        void* value = ch->buf[head % ch->cap];
        atomic_store(&ch->head, head + 1);
        atomic_fetch_sub(&ch->count, 1);

        // Wake a waiting sender (there's now space)
        if (ch->sendWaiters) {
            GreenThread* sender = ch->sendWaiters;
            ch->sendWaiters = sender->next;
            // Put sender's value in newly freed buffer slot
            uint32_t tail = atomic_load(&ch->tail);
            ch->buf[tail % ch->cap] = sender->waitValue;
            atomic_store(&ch->tail, tail + 1);
            atomic_fetch_add(&ch->count, 1);
            pthread_mutex_unlock(&ch->lock);
            enqueue(sender);
        } else {
            pthread_mutex_unlock(&ch->lock);
        }
        return value;
    }

    if (ch->closed) {
        pthread_mutex_unlock(&ch->lock);
        return NULL;
    }

    // No data — park receiver
    GreenThread* g = currentWorker->current;
    g->next = ch->recvWaiters;
    ch->recvWaiters = g;
    g->state = GT_WAITING;
    pthread_mutex_unlock(&ch->lock);
    swapcontext(&g->ctx, &currentWorker->schedulerCtx);
    return g->waitResult;
}

11.4 Go Channels in Practice

Go channels are the idiomatic coordination mechanism:

// Fan-out: distribute work to multiple workers
func fanOut(jobs <-chan Job, numWorkers int) []<-chan Result {
    results := make([]<-chan Result, numWorkers)
    for i := 0; i < numWorkers; i++ {
        resultCh := make(chan Result, 100)
        results[i] = resultCh
        go func(out chan<- Result) {
            for job := range jobs {  // Range over channel until closed
                out <- process(job)
            }
            close(out)
        }(resultCh)
    }
    return results
}

// Fan-in: merge multiple channels into one
func fanIn(channels ...<-chan Result) <-chan Result {
    out := make(chan Result, 100)
    var wg sync.WaitGroup

    merge := func(ch <-chan Result) {
        defer wg.Done()
        for r := range ch {
            out <- r
        }
    }

    wg.Add(len(channels))
    for _, ch := range channels {
        go merge(ch)
    }

    go func() {
        wg.Wait()
        close(out)
    }()
    return out
}

// Pipeline: chain stages
func pipeline(input []int) <-chan int {
    // Stage 1: generate
    gen := func(nums []int) <-chan int {
        out := make(chan int)
        go func() {
            for _, n := range nums { out <- n }
            close(out)
        }()
        return out
    }

    // Stage 2: square
    sq := func(in <-chan int) <-chan int {
        out := make(chan int)
        go func() {
            for n := range in { out <- n * n }
            close(out)
        }()
        return out
    }

    return sq(sq(gen(input)))  // Double-square pipeline
}

11.5 Select: Waiting on Multiple Channels

// Timeout with select
func fetchWithTimeout(url string, timeout time.Duration) (string, error) {
    resultCh := make(chan string, 1)
    errCh    := make(chan error, 1)

    go func() {
        resp, err := http.Get(url)
        if err != nil { errCh <- err; return }
        body, err := io.ReadAll(resp.Body)
        if err != nil { errCh <- err; return }
        resultCh <- string(body)
    }()

    select {
    case result := <-resultCh:
        return result, nil
    case err := <-errCh:
        return "", err
    case <-time.After(timeout):
        return "", fmt.Errorf("timeout after %v", timeout)
    }
}

// Done channel pattern for cancellation
func longRunning(ctx context.Context) error {
    for {
        select {
        case <-ctx.Done():            // Cancellation signal
            return ctx.Err()
        default:
            if err := doOneUnit(); err != nil {
                return err
            }
        }
    }
}

---

Chapter 12: Synchronization Primitives in M:N Runtimes

Synchronisation primitives in M:N runtimes must be goroutine-aware — blocking operations must park green threads, not OS threads.

12.1 Green-Thread Mutex

A standard pthread_mutex_t blocks the OS thread, which blocks all green threads on that worker. A green-thread-aware mutex parks just the waiting goroutine:

// Go's sync.Mutex simplified implementation concept
// (actual implementation uses lock-free fast path + semaphore slow path)

type GreenMutex struct {
    state int32  // 0=unlocked, 1=locked, locked|waiter_count
    sema  uint32 // Semaphore for goroutine parking
}

func (m *GreenMutex) Lock() {
    // Fast path: try CAS from 0 to 1
    if atomic.CompareAndSwapInt32(&m.state, 0, 1) {
        return  // Got the lock immediately
    }
    // Slow path: spin briefly, then park
    m.lockSlow()
}

func (m *GreenMutex) lockSlow() {
    var waitStartTime int64
    starving := false
    awoke := false
    iter := 0

    old := m.state
    for {
        // Spin a few times (only useful on multi-core)
        if old & (mutexLocked|mutexStarving) == mutexLocked &&
           runtime_canSpin(iter) {
            // ... spinning logic ...
            runtime_doSpin()
            iter++
            old = m.state
            continue
        }

        new := old
        if old & mutexStarving == 0 {
            new |= mutexLocked  // Try to acquire
        }
        new += mutexWaiterShift // Increment waiter count

        if atomic.CompareAndSwapInt32(&m.state, old, new) {
            if old & (mutexLocked|mutexStarving) == 0 {
                break  // Acquired the lock
            }
            // Park this goroutine
            runtime_SemacquireMutex(&m.sema, queueLifo, 1)
            // Woken up — try again
        }
        old = m.state
    }
}

The runtime_SemacquireMutex call parks the goroutine using the runtime's semaphore implementation, which places the goroutine in a wait queue and calls gopark() — switching back to the scheduler without blocking the OS thread.

12.2 Green-Thread RWMutex

// sync.RWMutex: multiple concurrent readers OR one writer
var mu sync.RWMutex
var data map[string]string

// Multiple goroutines can read simultaneously
func read(key string) string {
    mu.RLock()
    defer mu.RUnlock()
    return data[key]
}

// Only one goroutine can write at a time
func write(key, value string) {
    mu.Lock()
    defer mu.Unlock()
    data[key] = value
}

12.3 WaitGroup — Waiting for Multiple Goroutines

// sync.WaitGroup: wait for a collection of goroutines
func processAll(items []Item) []Result {
    results := make([]Result, len(items))
    var wg sync.WaitGroup

    for i, item := range items {
        wg.Add(1)
        go func(idx int, it Item) {
            defer wg.Done()
            results[idx] = process(it)
        }(i, item)
    }

    wg.Wait()  // Blocks until all goroutines call Done()
    return results
}

12.4 Once — Lazy Initialization

// sync.Once: run initialization exactly once, even with concurrent callers
var (
    instance *Database
    once     sync.Once
)

func GetDatabase() *Database {
    once.Do(func() {
        instance = connectToDatabase()  // Called exactly once
    })
    return instance
}

12.5 Semaphores for Rate Limiting

// Use a buffered channel as a semaphore
type Semaphore chan struct{}

func NewSemaphore(n int) Semaphore {
    return make(Semaphore, n)
}

func (s Semaphore) Acquire() { s <- struct{}{} }
func (s Semaphore) Release() { <-s }

// Limit concurrent database connections
var dbSem = NewSemaphore(10)

func queryWithLimit(query string) Result {
    dbSem.Acquire()
    defer dbSem.Release()
    return db.Query(query)
}

// Tokio equivalent (Rust):
use tokio::sync::Semaphore;

let sem = Arc::new(Semaphore::new(10));

async fn limited_query(sem: Arc<Semaphore>, query: &str) -> Result<Rows> {
    let _permit = sem.acquire().await?;  // Park if no permits available
    db.query(query).await
    // _permit dropped here → permit released
}

12.6 Atomic Operations

For lock-free communication between goroutines, sync/atomic provides atomic operations:

import "sync/atomic"

type Stats struct {
    requestCount int64
    bytesReceived int64
    errors        int64
}

func (s *Stats) RecordRequest(bytes int64) {
    atomic.AddInt64(&s.requestCount, 1)
    atomic.AddInt64(&s.bytesReceived, bytes)
}

func (s *Stats) RecordError() {
    atomic.AddInt64(&s.errors, 1)
}

func (s *Stats) Read() (int64, int64, int64) {
    return atomic.LoadInt64(&s.requestCount),
           atomic.LoadInt64(&s.bytesReceived),
           atomic.LoadInt64(&s.errors)
}

---

Chapter 13: I/O Integration and Event Loops

The true power of M:N systems comes from integrating non-blocking I/O. When a green thread needs to read from a socket, instead of blocking the OS thread, it parks itself and registers the socket with the I/O poller.

13.1 The epoll Integration Pattern

Linux's epoll watches multiple file descriptors and reports which are ready. The M:N runtime bridges epoll and the green thread scheduler:

// netpoll.c — Integration between epoll and green thread scheduler

#include <sys/epoll.h>
#include <unistd.h>
#include <fcntl.h>

#define MAX_EVENTS 256

static int epollFd = -1;
static int wakeupPipe[2];  // To interrupt blocked epoll_wait

// Map from fd → waiting green thread
#define FD_TABLE_SIZE 65536
static GreenThread* fdWaiters[FD_TABLE_SIZE];
static pthread_mutex_t fdLock = PTHREAD_MUTEX_INITIALIZER;

void netpollInit(void) {
    epollFd = epoll_create1(EPOLL_CLOEXEC);
    pipe2(wakeupPipe, O_NONBLOCK | O_CLOEXEC);

    struct epoll_event ev = {
        .events = EPOLLIN,
        .data.fd = wakeupPipe[0]
    };
    epoll_ctl(epollFd, EPOLL_CTL_ADD, wakeupPipe[0], &ev);
}

// Called by a green thread that wants to wait for fd to be readable
void netpollWait(int fd, uint32_t events) {
    Worker* w = currentWorker;
    GreenThread* g = w->current;

    pthread_mutex_lock(&fdLock);
    fdWaiters[fd] = g;
    pthread_mutex_unlock(&fdLock);

    struct epoll_event ev = {
        .events   = events | EPOLLONESHOT,
        .data.fd  = fd
    };
    epoll_ctl(epollFd, EPOLL_CTL_ADD, fd, &ev);
    // (or EPOLL_CTL_MOD if already registered)

    // Park this goroutine
    g->state = GT_WAITING;
    g->waitFd = fd;
    swapcontext(&g->ctx, &w->schedulerCtx);
    // We're back: fd is ready
}

// Called by the scheduler (or a dedicated netpoll goroutine) to check for events
GreenThread* netpollCheck(int64_t timeoutNs) {
    struct epoll_event events[MAX_EVENTS];
    int timeout_ms = (timeoutNs < 0) ? -1
                   : (timeoutNs == 0) ? 0
                   : (int)(timeoutNs / 1000000);

    int n = epoll_wait(epollFd, events, MAX_EVENTS, timeout_ms);

    GreenThread* first = NULL;
    GreenThread* last  = NULL;

    for (int i = 0; i < n; i++) {
        int fd = events[i].data.fd;

        if (fd == wakeupPipe[0]) {
            // Drain the wakeup pipe
            char buf[256];
            while (read(wakeupPipe[0], buf, sizeof(buf)) > 0);
            continue;
        }

        pthread_mutex_lock(&fdLock);
        GreenThread* g = fdWaiters[fd];
        fdWaiters[fd] = NULL;
        pthread_mutex_unlock(&fdLock);

        if (g) {
            g->state = GT_RUNNABLE;
            g->next  = NULL;
            if (!first) first = g;
            else        last->next = g;
            last = g;
        }
    }
    return first;  // Linked list of woken goroutines
}

// Wake the epoll_wait thread (when new work arrives and it's sleeping)
void netpollBreak(void) {
    write(wakeupPipe[1], "x", 1);
}

13.2 Wrapping Blocking I/O

With netpollWait, we can wrap blocking syscalls to be goroutine-friendly:

// Goroutine-safe read — parks goroutine until data is available
ssize_t green_read(int fd, void* buf, size_t count) {
    // Try non-blocking read first
    int flags = fcntl(fd, F_GETFL);
    fcntl(fd, F_SETFL, flags | O_NONBLOCK);

    for (;;) {
        ssize_t n = read(fd, buf, count);
        if (n >= 0) return n;

        if (errno == EAGAIN || errno == EWOULDBLOCK) {
            // No data yet — park goroutine until fd is readable
            netpollWait(fd, EPOLLIN);
            continue;  // Try again after wakeup
        }

        return -1;  // Real error
    }
}

// Goroutine-safe write — parks goroutine if socket buffer full
ssize_t green_write(int fd, const void* buf, size_t count) {
    int flags = fcntl(fd, F_GETFL);
    fcntl(fd, F_SETFL, flags | O_NONBLOCK);

    size_t written = 0;
    while (written < count) {
        ssize_t n = write(fd, (const char*)buf + written, count - written);
        if (n > 0) {
            written += n;
            continue;
        }
        if (n < 0 && (errno == EAGAIN || errno == EWOULDBLOCK)) {
            netpollWait(fd, EPOLLOUT);
            continue;
        }
        return -1;
    }
    return written;
}

13.3 io_uring: The Modern I/O Interface

Linux 5.1+ offers io_uring, a high-performance async I/O interface that can be used to eliminate the overhead of per-operation syscalls:

// io_uring based async I/O for M:N runtimes
#include <liburing.h>

struct IOUring {
    struct io_uring ring;
    // Map from user_data → parked goroutine
    GreenThread*    completions[4096];
    uint64_t        nextTag;
};

// Async read using io_uring
ssize_t uring_read(IOUring* uring, int fd, void* buf, size_t count) {
    struct io_uring_sqe* sqe = io_uring_get_sqe(&uring->ring);

    uint64_t tag = uring->nextTag++;
    GreenThread* g = currentWorker->current;
    uring->completions[tag % 4096] = g;

    io_uring_prep_read(sqe, fd, buf, count, 0);
    io_uring_sqe_set_data64(sqe, tag);
    io_uring_submit(&uring->ring);

    // Park goroutine
    g->state = GT_WAITING;
    swapcontext(&g->ctx, &currentWorker->schedulerCtx);

    // Woken by completion handler — result in g->waitResult
    return (ssize_t)(intptr_t)g->waitResult;
}

// Completion handler (runs in scheduler loop)
void uringPollCompletions(IOUring* uring) {
    struct io_uring_cqe* cqe;
    unsigned head;
    io_uring_for_each_cqe(&uring->ring, head, cqe) {
        uint64_t tag = io_uring_cqe_get_data64(cqe);
        GreenThread* g = uring->completions[tag % 4096];
        if (g) {
            g->waitResult = (void*)(intptr_t)cqe->res;
            g->state = GT_RUNNABLE;
            enqueue(g);
        }
    }
    io_uring_cq_advance(&uring->ring, head);
}

io_uring allows batching multiple I/O operations into a single syscall via the submission queue, dramatically reducing per-operation overhead — critical for high-throughput servers doing millions of I/O operations per second.

---

Chapter 14: Debugging and Observability

Debugging M:N concurrent programs is harder than debugging sequential programs. The non-deterministic scheduling makes bugs intermittent and hard to reproduce.

14.1 Goroutine Dumps

Go can dump all goroutine stacks at any time:

import (
    "runtime"
    "fmt"
    "os"
    "os/signal"
    "syscall"
)

func init() {
    // Ctrl+\ dumps all goroutine stacks
    go func() {
        c := make(chan os.Signal, 1)
        signal.Notify(c, syscall.SIGQUIT)
        for range c {
            buf := make([]byte, 1 << 20)  // 1MB buffer
            n := runtime.Stack(buf, true) // true = all goroutines
            fmt.Fprintf(os.Stderr, "=== Goroutine Dump ===\n%s\n", buf[:n])
        }
    }()
}

Typical output:

goroutine 1 [running]:
main.main()
    /home/user/main.go:42 +0x1f4

goroutine 18 [chan receive, 3 minutes]:
main.worker()
    /home/user/worker.go:17 +0x6a
created by main.startWorkers in goroutine 1
    /home/user/main.go:29 +0x39

goroutine 42 [IO wait]:
net.(*netFD).Read(...)
    /usr/local/go/src/net/fd_posix.go:56
net.(*conn).Read(...)
    /usr/local/go/src/net/net.go:185

The state in brackets tells you why a goroutine is paused:

• [running]: Currently executing
• [chan receive]: Waiting for channel data
• [chan send]: Blocked sending (buffer full or no receiver)
• [IO wait]: Waiting for I/O (epoll)
• [semacquire]: Waiting for a mutex/semaphore
• [sleep]: In time.Sleep
• [select]: Blocked in a select statement

14.2 Race Detector

Go's race detector (go run -race) instruments all memory accesses and reports unsynchronised concurrent accesses:

// This code has a data race
var counter int

func unsafeIncrement() {
    go func() { counter++ }()  // Race!
    go func() { counter++ }()  // Race!
}

Running with `-race`:

==================
WARNING: DATA RACE
Write at 0x00c0001b4050 by goroutine 7:
  main.unsafeIncrement.func1()
      /home/user/main.go:8 +0x34

Previous write at 0x00c0001b4050 by goroutine 6:
  main.unsafeIncrement.func1()
      /home/user/main.go:7 +0x34

Goroutine 7 (running) created at:
  main.unsafeIncrement()
      /home/user/main.go:8 +0x5e
==================

How it works: The race detector adds instrumentation that records each memory access with a vector clock — a logical timestamp that can determine if two accesses are concurrent and one is a write.

14.3 pprof: CPU and Memory Profiling

Go's pprof package can profile goroutine scheduling and CPU usage:

import (
    "net/http"
    _ "net/http/pprof"
    "runtime/pprof"
    "os"
)

func main() {
    // Enable HTTP profiling endpoint
    go http.ListenAndServe(":6060", nil)

    // Or collect to file
    f, _ := os.Create("cpu.prof")
    pprof.StartCPUProfile(f)
    defer pprof.StopCPUProfile()

    // ... your program ...
}

// Then analyse:
// go tool pprof http://localhost:6060/debug/pprof/goroutine
// go tool pprof http://localhost:6060/debug/pprof/heap
// go tool pprof http://localhost:6060/debug/pprof/profile?seconds=30

The goroutine profile shows where goroutines are blocked — invaluable for finding deadlocks and contention hotspots.

14.4 Deadlock Detection

A deadlock occurs when goroutines are waiting for each other in a cycle. Go's runtime detects deadlocks when all goroutines are blocked:

fatal error: all goroutines are asleep - deadlock!

goroutine 1 [chan receive]:
main.main()
    /home/user/main.go:5 +0x28

goroutine 6 [chan receive]:
main.producer()
    /home/user/main.go:11 +0x30

However, Go cannot detect partial deadlocks — if only some goroutines are deadlocked but others are still running. Tools like goleak can detect goroutine leaks in tests:

// Using goleak in tests
import "go.uber.org/goleak"

func TestMyFunction(t *testing.T) {
    defer goleak.VerifyNone(t)  // Fails if any goroutines leaked

    // Run test
    result := myFunction()
    assert.Equal(t, expected, result)
    // goleak checks: are there goroutines that didn't exist before this test?
}

14.5 Tokio Console

For Rust/Tokio, the tokio-console tool provides a live view of async task scheduling:

// Cargo.toml
[dependencies]
tokio = { version = "1", features = ["full"] }
console-subscriber = "0.2"

// main.rs
#[tokio::main]
async fn main() {
    console_subscriber::init();  // Enable tokio-console
    // ... rest of program
}

Running tokio-console shows:

• All active tasks with their poll counts
• Tasks blocked waiting for I/O
• Tasks busy in CPU-bound code
• Wakeup counts (a task woken very frequently may be spinning)

---

Chapter 15: Performance Analysis and Tuning

15.1 The Scheduler's Effect on Throughput

The scheduler adds overhead to every green thread switch. For a system doing millions of short tasks per second, scheduling overhead can dominate:

// Benchmark: scheduling overhead per goroutine
func BenchmarkGoroutineRoundtrip(b *testing.B) {
    ch := make(chan struct{})
    go func() {
        for range ch { ch <- struct{}{} }
    }()

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        ch <- struct{}{}
        <-ch
    }
}
// Result: ~200 ns per roundtrip = ~5M goroutine switches/second/core

For comparison:

• Goroutine switch (Go): ~100–300 ns
• Task switch (Tokio): ~80–200 ns (context switch amortised across many polls)
• OS thread switch (pthread, voluntary): ~2–5 µs
• OS thread switch (preemptive): ~5–20 µs

15.2 Backpressure and Bounded Queues

An unbounded run queue is dangerous: if producers create green threads faster than workers can execute them, memory grows without bound:

// Pattern: bounded semaphore to limit concurrent goroutines
type Pool struct {
    sem chan struct{}
    wg  sync.WaitGroup
}

func NewPool(maxConcurrent int) *Pool {
    return &Pool{sem: make(chan struct{}, maxConcurrent)}
}

func (p *Pool) Submit(fn func()) {
    p.sem <- struct{}{}  // Blocks if pool is full
    p.wg.Add(1)
    go func() {
        defer func() {
            <-p.sem
            p.wg.Done()
        }()
        fn()
    }()
}

func (p *Pool) Wait() { p.wg.Wait() }

15.3 Cache-Aware Task Sizing

Green thread tasks should be large enough to amortise scheduling overhead but small enough to stay in cache:

// Bad: millions of tiny goroutines — scheduling overhead dominates
func badParallel(data []int) []int {
    results := make([]int, len(data))
    var wg sync.WaitGroup
    for i, v := range data {
        wg.Add(1)
        i, v := i, v
        go func() {  // One goroutine per element — too fine-grained!
            defer wg.Done()
            results[i] = v * v
        }()
    }
    wg.Wait()
    return results
}

// Good: chunk the work — goroutine per CPU, not per element
func goodParallel(data []int) []int {
    results := make([]int, len(data))
    numCPU  := runtime.NumCPU()
    chunkSz := (len(data) + numCPU - 1) / numCPU

    var wg sync.WaitGroup
    for i := 0; i < numCPU; i++ {
        start := i * chunkSz
        end   := min(start + chunkSz, len(data))
        if start >= len(data) { break }

        wg.Add(1)
        go func(s, e int) {
            defer wg.Done()
            for j := s; j < e; j++ {
                results[j] = data[j] * data[j]
            }
        }(start, end)
    }
    wg.Wait()
    return results
}

15.4 GOMAXPROCS Tuning

GOMAXPROCS controls the number of OS threads (Ps) in Go. The default is runtime.NumCPU(). Tuning cases:

CPU-bound workloads: Default is optimal. More Ps than cores adds context switch overhead.

I/O-bound workloads: Default is also good — goroutines park during I/O, Ps pick up other goroutines.

Mixed with C extensions (cgo): cgo calls can block OS threads. If cgo blocks frequently, increase GOMAXPROCS or use a larger thread pool.

Container environments: If running in a container with CPU limits (e.g., 0.5 CPUs), runtime.NumCPU() may report host CPU count. Use uber-go/automaxprocs to set GOMAXPROCS based on actual CPU quota:

import _ "go.uber.org/automaxprocs"  // Auto-sets GOMAXPROCS for containers

---

Chapter 16: Design Patterns for M:N Systems

16.1 The Worker Pool Pattern

type WorkerPool struct {
    jobs    chan func()
    results chan error
    wg      sync.WaitGroup
}

func NewWorkerPool(workers, queueDepth int) *WorkerPool {
    p := &WorkerPool{
        jobs:    make(chan func(), queueDepth),
        results: make(chan error, queueDepth),
    }

    for i := 0; i < workers; i++ {
        p.wg.Add(1)
        go func() {
            defer p.wg.Done()
            for job := range p.jobs {
                if err := func() (err error) {
                    defer func() {
                        if r := recover(); r != nil {
                            err = fmt.Errorf("panic: %v", r)
                        }
                    }()
                    job()
                    return nil
                }(); err != nil {
                    p.results <- err
                }
            }
        }()
    }

    return p
}

func (p *WorkerPool) Submit(job func()) {
    p.jobs <- job
}

func (p *WorkerPool) Shutdown() {
    close(p.jobs)
    p.wg.Wait()
    close(p.results)
}

16.2 The Circuit Breaker Pattern

Prevent cascading failures by stopping calls to a failing service:

type CircuitBreaker struct {
    state        int32  // 0=closed, 1=open, 2=half-open
    failures     int32
    threshold    int32
    timeout      time.Duration
    lastFailTime int64
    mu           sync.Mutex
}

func (cb *CircuitBreaker) Call(fn func() error) error {
    state := atomic.LoadInt32(&cb.state)

    switch state {
    case 1: // Open
        elapsed := time.Since(time.Unix(0, atomic.LoadInt64(&cb.lastFailTime)))
        if elapsed < cb.timeout {
            return errors.New("circuit breaker open")
        }
        // Try half-open
        atomic.StoreInt32(&cb.state, 2)
        fallthrough

    case 0, 2: // Closed or half-open
        err := fn()
        if err != nil {
            fails := atomic.AddInt32(&cb.failures, 1)
            atomic.StoreInt64(&cb.lastFailTime, time.Now().UnixNano())
            if fails >= cb.threshold {
                atomic.StoreInt32(&cb.state, 1) // Trip to open
            }
            return err
        }
        // Success: reset
        atomic.StoreInt32(&cb.failures, 0)
        atomic.StoreInt32(&cb.state, 0)
        return nil
    }
    return nil
}

16.3 The Actor Pattern

Erlang-style isolated actors with message passing:

type Message struct {
    Type    string
    Payload interface{}
    ReplyTo chan<- interface{}
}

type Actor struct {
    mailbox chan Message
    state   interface{}
    handler func(state interface{}, msg Message) interface{}
}

func NewActor(initialState interface{},
              handler func(interface{}, Message) interface{}) *Actor {
    a := &Actor{
        mailbox: make(chan Message, 100),
        state:   initialState,
        handler: handler,
    }
    go a.run()
    return a
}

func (a *Actor) run() {
    for msg := range a.mailbox {
        a.state = a.handler(a.state, msg)
    }
}

func (a *Actor) Send(msg Message) {
    a.mailbox <- msg
}

func (a *Actor) Ask(msgType string, payload interface{}) interface{} {
    reply := make(chan interface{}, 1)
    a.Send(Message{Type: msgType, Payload: payload, ReplyTo: reply})
    return <-reply
}

// Example: counter actor
func main() {
    counter := NewActor(0, func(state interface{}, msg Message) interface{} {
        n := state.(int)
        switch msg.Type {
        case "increment":
            return n + 1
        case "get":
            msg.ReplyTo <- n
            return n
        case "reset":
            return 0
        }
        return n
    })

    counter.Send(Message{Type: "increment"})
    counter.Send(Message{Type: "increment"})
    counter.Send(Message{Type: "increment"})
    fmt.Println("Count:", counter.Ask("get", nil))  // 3
}

16.4 The Scatter-Gather Pattern

Dispatch work to multiple goroutines and collect results:

func scatterGather[T, R any](
    items []T,
    fn func(T) (R, error),
    maxConcurrent int,
) ([]R, []error) {
    type indexed struct {
        idx int
        val R
        err error
    }

    sem := make(chan struct{}, maxConcurrent)
    out := make(chan indexed, len(items))
    var wg sync.WaitGroup

    for i, item := range items {
        wg.Add(1)
        go func(idx int, it T) {
            defer wg.Done()
            sem <- struct{}{}        // Acquire semaphore
            defer func() { <-sem }() // Release on done

            val, err := fn(it)
            out <- indexed{idx: idx, val: val, err: err}
        }(i, item)
    }

    go func() {
        wg.Wait()
        close(out)
    }()

    results := make([]R, len(items))
    errs    := make([]error, len(items))

    for r := range out {
        results[r.idx] = r.val
        errs[r.idx]    = r.err
    }

    return results, errs
}

// Usage
urls := []string{"https://a.com", "https://b.com", "https://c.com"}
bodies, errs := scatterGather(urls, func(url string) (string, error) {
    resp, err := http.Get(url)
    if err != nil { return "", err }
    defer resp.Body.Close()
    b, _ := io.ReadAll(resp.Body)
    return string(b), nil
}, 10)  // Max 10 concurrent

---

Appendix A: M:N Runtime Comparison Table

Runtime	Language	Green thread	Stack	Preemption	I/O model	Work stealing
Go runtime	Go	Goroutine	2KB–1GB, copying	Signal (SIGURG)	netpoll (epoll/kqueue)	Yes (Chase-Lev)
Tokio	Rust	Task (state machine)	Stack only during poll	No (cooperative)	io_uring / epoll	Yes
BEAM	Erlang	Process	Fixed per process	Reduction count	Dedicated async threads	Yes
Project Loom	Java	Virtual thread	Small, fixed	JVM-driven	NIO integration	Yes (ForkJoinPool)
GHC	Haskell	Spark / thread	Small	Allocation sites	Event manager	Yes
libuv	C (Node.js)	N/A (event loop)	OS thread stack	N/A (single-threaded)	epoll / IOCP / kqueue	No
Boost.Fiber	C++	Fiber	User-set	No (cooperative)	User must integrate	No

---

Appendix B: Quick Reference — Go Concurrency Primitives

// Create goroutine
go func() { /* ... */ }()
go namedFunction(arg1, arg2)

// Channel creation
ch := make(chan T)          // Unbuffered
ch := make(chan T, n)       // Buffered capacity n

// Channel operations
ch <- value                 // Send (blocks if no receiver / buffer full)
value := <-ch               // Receive (blocks if no data)
value, ok := <-ch           // Receive with closed check
close(ch)                   // Signal no more sends (panics if already closed)
for v := range ch { ... }   // Receive until channel closed

// Select
select {
case v := <-ch1:    // ...
case ch2 <- v:      // ...
case <-time.After(d): // Timeout
default:            // Non-blocking
}

// Sync primitives
var mu sync.Mutex
mu.Lock(); defer mu.Unlock()

var rw sync.RWMutex
rw.RLock(); defer rw.RUnlock()   // Multiple concurrent readers
rw.Lock(); defer rw.Unlock()     // Exclusive write

var wg sync.WaitGroup
wg.Add(1); go func() { defer wg.Done(); /* ... */ }()
wg.Wait()

var once sync.Once
once.Do(func() { /* init exactly once */ })

// Context (cancellation)
ctx, cancel := context.WithCancel(context.Background())
ctx, cancel := context.WithTimeout(ctx, 5*time.Second)
ctx, cancel := context.WithDeadline(ctx, time.Now().Add(5*time.Second))
defer cancel()
select { case <-ctx.Done(): return ctx.Err() }

// Atomics
var n int64
atomic.AddInt64(&n, 1)
atomic.LoadInt64(&n)
atomic.StoreInt64(&n, 0)
atomic.CompareAndSwapInt64(&n, old, new)

---

Appendix C: Common Pitfalls

Goroutine Leaks

// BAD: goroutine leaks if nobody reads resultCh
func leaky() <-chan Result {
    resultCh := make(chan Result)  // Unbuffered!
    go func() {
        resultCh <- computeResult()  // Blocks forever if caller discards channel
    }()
    return resultCh
}

// GOOD: context-aware, can be cancelled
func notLeaky(ctx context.Context) <-chan Result {
    resultCh := make(chan Result, 1)  // Buffered: goroutine won't block
    go func() {
        select {
        case resultCh <- computeResult():
        case <-ctx.Done():
        }
    }()
    return resultCh
}

Closing Channels Twice

// Panics: close of closed channel
close(ch)
close(ch)  // panic!

// Safe: use sync.Once
var once sync.Once
safeClose := func() { once.Do(func() { close(ch) }) }

Loop Variable Capture

// BAD: all goroutines capture the same 'i' variable
for i := 0; i < 5; i++ {
    go func() {
        fmt.Println(i)  // Will likely print 5, 5, 5, 5, 5
    }()
}

// GOOD (Go 1.22+): loop variables are per-iteration by default
// GOOD (all versions): pass as argument
for i := 0; i < 5; i++ {
    go func(i int) {
        fmt.Println(i)  // Prints 0, 1, 2, 3, 4 in some order
    }(i)
}

Mutex Copied by Value

// BAD: copying mutex (sync.Mutex must not be copied after first use)
type Counter struct {
    sync.Mutex
    value int
}

func copyBad(c Counter) {      // Copies the mutex — race condition!
    c.Lock()
    defer c.Unlock()
    c.value++
}

// GOOD: use pointer receiver
func (c *Counter) Increment() {  // Pointer receiver — no copy
    c.Lock()
    defer c.Unlock()
    c.value++
}

---

This completes the M:N Concurrent Model guide. The concepts span from assembly-level context switching through production-grade work stealing, language runtime internals, and high-level design patterns. The M:N model is one of the most impactful ideas in modern systems programming — enabling programs that handle millions of concurrent operations on commodity hardware with predictable performance and minimal overhead.