User-Level Threads

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

/*
 * Go's goroutine stack management strategy
 * 
 * Key innovation: Stacks start tiny (2KB) and grow as needed.
 * This allows millions of goroutines without exhausting memory.
 */
 
// Initial stack is just 2KB (compared to typical 8MB OS thread stack)
const MinStackSize = 2048
 
// Stack grows by copying to larger allocation
func growStack(g *goroutine) {
    // Current stack is full
    oldStack := g.stack
    oldSize := len(oldStack)
    
    // Double the size (up to a maximum)
    newSize := oldSize * 2
    if newSize > MaxStackSize {
        throw("stack overflow")
    }
    
    // Allocate new, larger stack
    newStack := allocateStack(newSize)
    
    // Copy old stack contents to new stack
    // This requires adjusting all pointers within the stack!
    copyAndAdjustStack(oldStack, newStack)
    
    // Update goroutine to use new stack
    g.stack = newStack
    
    // Old stack can be returned to pool or freed
    freeStack(oldStack)
}
 
/*
 * Stack copying is non-trivial:
 * - Must find all pointers into the stack
 * - Adjust them to point to new locations
 * - Handle edge cases (pointers from heap to stack, etc.)
 * 
 * Go uses "copyable stacks" with compiler support to identify
 * stack pointers. This is a sophisticated technique.
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

/*
 * Simplified Go scheduler logic
 */
 
// Main scheduling loop for each M (OS thread)
func schedule() {
    for {
        // 1. Find a goroutine to run
        gp := findrunnable()
        
        // 2. Execute the goroutine
        execute(gp)
        
        // 3. When goroutine yields/blocks, loop back
    }
}
 
func findrunnable() *g {
    // Check local run queue first (cache friendly)
    if gp := runqget(_p_); gp != nil {
        return gp
    }
    
    // Check global run queue
    if gp := globrunqget(_p_, 0); gp != nil {
        return gp
    }
    
    // Check network poller (ready I/O)
    if netpollinited() {
        if gp := netpoll(0); gp != nil {
            return gp
        }
    }
    
    // Work stealing: try to steal from other P's
    for i := 0; i < gomaxprocs; i++ {
        if gp := runqsteal(_p_, allp[i]); gp != nil {
            return gp
        }
    }
    
    // Nothing to do - park this M
    stopm()
    return nil
}
 
func execute(gp *g) {
    // Bind G to current M
    _g_.m.curg = gp
    gp.m = _g_.m
    
    // Switch to goroutine's stack and execute
    gogo(&gp.sched)
    
    // When goroutine returns here (via yield/block/exit)
    // it has been descheduled
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

/*
 * Go's preemptive scheduling (since Go 1.14)
 *
 * Before 1.14: Goroutines only yielded at function calls
 * A tight loop with no function calls could run forever:
 */
 
// This would starve other goroutines in Go < 1.14
func tightLoop() {
    sum := 0
    for i := 0; i < 1000000000; i++ {
        sum += i  // No function call = no yield point
    }
}
 
/*
 * Go 1.14+ introduced asynchronous preemption:
 * 
 * 1. A background sysmon goroutine monitors running time
 * 2. If a goroutine runs too long (>10ms), sysmon sends a signal
 * 3. The signal handler sets a flag on the goroutine
 * 4. At next safe point (even mid-function), goroutine yields
 *
 * Safe points are identified by the compiler:
 * - Between instructions that don't have complex invariants
 * - Not holding locks or in middle of allocation
 */
 
// Now this works fine - runtime will preempt after ~10ms
func tightLoopSafe() {
    sum := 0
    for i := 0; i < 1000000000; i++ {
        sum += i  // Runtime can now preempt here too!
    }
    
    // Other goroutines get their fair share
}
 
/*
 * Note: Preemption via signals (SIGURG on Linux) has overhead
 * but only when actually preempting. Normal scheduling remains
 * cooperative at natural yield points.
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

/*
 * How Go's netpoller works
 *
 * User perspective: conn.Read() blocks until data arrives
 * Reality: goroutine parks; fd registered with epoll; runtime continues
 */
 
func (fd *netFD) Read(p []byte) (n int, err error) {
    // Try non-blocking read first
    n, err = syscall.Read(fd.sysfd, p)
    
    if err == syscall.EAGAIN {
        // Would block - integrate with scheduler
        
        // 1. Register this fd with netpoller (epoll/kqueue)
        if err := fd.pd.waitRead(); err != nil {
            return 0, err
        }
        
        // 2. Park the current goroutine
        // Under the hood, waitRead() does:
        //   - fd.pd.rg = getg()  // Record waiting goroutine
        //   - gopark()           // Park goroutine (remove from run queue)
        
        // 3. When epoll says fd is readable, netpoller will:
        //   - Find the goroutine waiting on this fd
        //   - Call goready() to mark it runnable
        
        // 4. We wake up here, retry the read
        n, err = syscall.Read(fd.sysfd, p)
    }
    
    return n, err
}
 
/*
 * The netpoller runs as part of the scheduler:
 *
 * func findrunnable() *g {
 *     // ... check local queue ...
 *     
 *     // Check netpoller for ready I/O
 *     list := netpoll(0)  // Non-blocking poll
 *     for gp := list; gp != nil; gp = gp.schedlink {
 *         // This goroutine's I/O is ready - make it runnable
 *         injectglist(gp)
 *     }
 *     
 *     // ... continue scheduling ...
 * }
 */
 
// The beauty: user code looks synchronous
func fetch(url string) []byte {
    resp, _ := http.Get(url)  // Looks blocking, actually async
    defer resp.Body.Close()
    body, _ := ioutil.ReadAll(resp.Body)  // Same here
    return body
}
// This runs thousands of fetches concurrently without callback hell

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

package main
 
import (
    "fmt"
    "time"
)
 
// Goroutines: Go's green threads
func main() {
    // Create 100,000 goroutines - costs only ~200MB
    for i := 0; i < 100000; i++ {
        go worker(i)  // 'go' keyword spawns goroutine
    }
    
    time.Sleep(time.Second)
}
 
func worker(id int) {
    // Each goroutine has ~2KB initial stack
    // Stacks grow automatically as needed
    time.Sleep(100 * time.Millisecond)
    fmt.Printf("Worker %d done
", id)
}
 
/*
 * Go goroutine characteristics:
 * - M:N scheduling (GOMAXPROCS OS threads)
 * - 2KB minimum stack (growable to 1GB)
 * - Preemptive as of Go 1.14
 * - Integrated netpoller for async I/O
 * - Channels for communication
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

%% Erlang: Lightweight processes (green threads with isolation)
 
-module(example).
-export([spawn_many/0]).
 
%% Spawn 1 million processes - Erlang handles this easily
spawn_many() ->
    [spawn(fun() -> worker(I) end) || I <- lists:seq(1, 1000000)].
 
worker(Id) ->
    receive
        {ping, Sender} ->
            Sender ! {pong, Id},
            worker(Id);
        stop ->
            ok
    after 5000 ->
        io:format("Worker ~p timeout~n", [Id]),
        worker(Id)
    end.
 
%% Erlang process characteristics:
%% - Extremely lightweight (~300 bytes + heap)
%% - Millions of processes per VM (BEAM)
%% - Complete isolation (share nothing)
%% - Preemptive reduction-based scheduling
%% - Fault tolerance through supervision trees
%% - Message passing only (no shared state)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

// Java 21+: Virtual Threads (Project Loom)
// Green threads return to Java, done right
 
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
 
public class VirtualThreadsExample {
    public static void main(String[] args) throws Exception {
        // Create executor with virtual threads (NOT pooled!)
        try (ExecutorService executor = 
                Executors.newVirtualThreadPerTaskExecutor()) {
            
            // Submit 100,000 tasks - each gets its own virtual thread
            for (int i = 0; i < 100_000; i++) {
                final int id = i;
                executor.submit(() -> {
                    // Blocking calls are fine - they block the virtual
                    // thread, not the carrier OS thread
                    Thread.sleep(Duration.ofMillis(100));
                    System.out.println("Task " + id + " on " + 
                        Thread.currentThread());
                });
            }
        }
    }
}
 
/*
 * Virtual thread characteristics (Loom):
 * - M:N scheduling onto platform threads
 * - Blocking I/O automatically handled
 * - Compatible with existing Thread API
 * - sync-over-async: write blocking code, get async behavior
 * - Millions of virtual threads practical
 * - ThreadLocal works (but consider ScopedValue)
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

// Rust: Async tasks (a form of green threading)
 
use tokio;
 
#[tokio::main]
async fn main() {
    // Spawn 100,000 async tasks
    let mut handles = Vec::new();
    
    for i in 0..100_000 {
        let handle = tokio::spawn(async move {
            // .await points are where task can be suspended
            tokio::time::sleep(
                tokio::time::Duration::from_millis(100)
            ).await;
            
            println!("Task {} complete", i);
        });
        handles.push(handle);
    }
    
    // Wait for all tasks
    for handle in handles {
        handle.await.unwrap();
    }
}
 
/*
 * Rust async characteristics:
 * - Zero-cost futures (no heap allocation for simple futures)
 * - Explicit .await marks yield points
 * - Compile-time state machine generation
 * - Multiple runtimes: tokio, async-std, smol
 * - No implicit preemption - truly cooperative
 * - Send/Sync bounds for safe concurrency
 */