Green Threads and the Cost of a User-Space Context Switch

A kernel thread is a schedulable entity the operating system knows about. It has an entry in the task table, a kernel stack, a saved register set the kernel maintains on every switch, and a priority that the kernel’s scheduler recomputes as load changes. Creating one costs a clone call and the allocation of both stacks. Switching between two of them costs a trap into the kernel, a scheduler decision, a page-table switch if they land on different processes, and a trap back out.

A green thread, or user-space thread, is a schedulable entity that only the language runtime knows about. It has a saved register set in ordinary memory, a stack the runtime allocated, and an entry in a runtime data structure. Switching between two of them is a function call that saves a handful of registers, swaps the stack pointer, and returns into a different place. No trap, no scheduler policy from the kernel, no page-table change if the stacks live in the same address space.

The distinction matters because the two costs differ by more than a constant factor, and because the second design changes what a blocking call is allowed to mean.

What must survive a switch

A running thread’s state is the set of registers the compiler might have used. On x86-64 that is sixteen general-purpose registers, the instruction pointer, the stack pointer, and a set of flags. Floating-point and vector state live in separate registers: sixteen 128-bit XMM registers under the System V ABI, with wider state available. The ABI’s convention is that most of them are caller-saved. A switch routine therefore saves a modest fixed set, not the entire processor state.

The kernel must save more, because the kernel’s own state is involved. When a thread traps into the kernel, the kernel stack holds the return frame of the system call; the thread’s user registers are already saved on that stack by the trap. Switching to another thread means switching kernel stacks, which means updating the per-CPU current-task pointer, the stack canary, and on some configurations the address-space identifier. All of that happens behind a single switch_to in the scheduler, and its cost is in the hundreds of cycles rather than the tens, before any cache effects.

Cache effects dominate. Two threads on the same core compete for L1; two threads on different cores force the working set to migrate. A switch between green threads that share an address space still evicts whatever the previous thread had in the instruction cache at the point where it resumed, because the new thread resumes somewhere else entirely. The cost is not the register save; it is the refill of instruction and data caches afterwards. That cost is present in both designs, which is why the practical advantage of green threads shows up in creation and destruction and in scheduling decisions, not in the raw switch.

Creation is where the difference is starkest. A kernel thread’s stack is mapped lazily but the mapping and the task structure are real; creating one is a syscall that allocates kernel memory and cannot be done in bulk cheaply. A green thread’s stack can be a segment of a larger arena, allocated by bumping a pointer. Runtimes that create a goroutine per request rely on this: allocation of a small stack is a few instructions in the common case.

The stack problem

The hard part of green threads is not the switch; it is the stack.

A stackful green thread needs its own stack, because it can suspend in the middle of an arbitrary call chain and must later resume there with the frames intact. Stack sizes are a guess. Too small and deep recursion overflows; too large and ten thousand threads consume ten thousand stacks. The standard resolutions are a fixed small initial stack with a growth check on entry to each function, or segmented stacks with a check at every call. The first is what Go uses: a goroutine starts with a small stack, and a function prologue compares the stack pointer against a bound and calls a runtime routine that copies the stack elsewhere when it does not fit. Copying is possible because the runtime knows where all the pointers are, which requires precise stack maps emitted by the compiler. A runtime without that information cannot move a stack and must either reserve a large one or abandon the approach.

Segmented stacks, where each stack segment is separately allocated and linked, avoid the copy but make every call site pay for the check and make pointer arithmetic on stack addresses unsafe. Both schemes exist in shipping runtimes, and both are the reason stackful concurrency is considered a runtime feature rather than a library one.

Stackless designs avoid the problem by not having per-task stacks at all. A coroutine compiled into a state machine keeps its locals in a heap-allocated frame and resumes by jumping to a numbered state. The task’s memory is proportional to its live variables, not to its call depth. The price is that suspension is only legal at points the compiler marked, and calls through a function the compiler cannot see cannot be suspended. The trade between these two designs is taken up in stackful and stackless coroutines compared.

M to N, and the syscall problem

The scheduler that runs green threads must decide how many kernel threads to use. One kernel thread per core is the usual choice, giving an M-to-N arrangement: M green threads multiplexed onto N kernel threads. The alternative, one kernel thread total, throws away multicore parallelism; one kernel thread per green thread is the kernel-thread design again with extra steps.

M-to-N brings a constraint that does not exist in the pure event loop. A green thread that calls a blocking system call blocks its carrier thread, and with it every other green thread scheduled on that carrier. There are three responses. The first is to forbid blocking calls and provide only non-blocking equivalents, which is what an async runtime does. The second is to detect the call and move the carrier’s other tasks elsewhere; this requires the runtime to intercept the call, which means either a language-level API or a library shim, and interception that works for read may not work for a third-party library that calls read internally. The third lets the carrier block and spawns a replacement carrier so the total stays at N runnable threads. Go takes this route: the runtime knows the system call is in progress because it made it, and hands the P, the logical processor holding the run queue, to another thread while the caller is inside the kernel.

That handoff is the reason the runtime needs its own notion of a processor separate from the OS thread. The scheduler’s unit of parallelism must be able to outlive the thread executing it.

func spawnMany() []int {
    results := make(chan int, 100000)
    for i := 0; i < 100000; i++ {
        go func(n int) {
            // A few hundred bytes of stack is enough for this frame.
            total := 0
            for j := 0; j <= n; j++ {
                total += j
            }
            results <- total
        }(i)
    }
    out := make([]int, 100000)
    for i := range out {
        out[i] = <-results
    }
    return out
}

The code above creates a hundred thousand tasks whose stacks are runtime-allocated. The equivalent with pthread_create would allocate a hundred thousand kernel stacks, and the process would spend its time in the kernel rather than doing the arithmetic.

Preemption without a signal

Cooperative green threads yield only at explicit points. A task that loops without allocating, calling, or suspending never yields, and on an M-to-N runtime it pins its carrier. With N carriers, N such tasks stop the program.

The event loop discussed in readiness notification and the single-threaded event loop accepts this limitation because handlers are supposed to be short. A general-purpose runtime cannot, because user code is arbitrary. The usual answer is asynchronous preemption: the runtime arranges for a signal to be delivered to a carrier that has been running too long, and the signal handler saves the task’s state and re-enters the scheduler. Go uses a signal delivered to the thread and a check at the resumption point. The mechanism is delicate, because the handler must not touch anything that could be mid-update, and it is the reason a runtime with green threads needs a signal handler installed even for programs that never mention concurrency.

The alternative, preemption at safepoints, requires the compiler to emit a check on every loop back-edge and every function return, which costs a few instructions per iteration and gives deterministic points at which a task can be stopped. Runtimes that already need stack maps and write barriers at those points pay little extra; runtimes that compile to plain machine code without runtime metadata cannot do it at all.

Where the design shows through

Green threads do not remove the operating system; they hide it. Every green thread that blocks in the kernel still consumes a kernel thread, every carrier still competes for a core with every other process, and every stack still occupies memory. What the runtime buys is a scheduling decision that costs tens of cycles instead of hundreds, a task creation that costs an allocation instead of a syscall, and a program whose concurrency is limited by memory rather than by the kernel’s task limits.

What it costs is a runtime that must intercept blocking, must manage stacks, must sometimes preempt asynchronously, and must therefore be present in the compiled output of every function. That last requirement is why green threads tend to come with a whole language rather than as a library, and why the runtimes that bolt them on later spend most of their effort on the interception problem described in blocking calls inside an asynchronous runtime.