Multiplexing Green Threads onto Kernel Threads

A kernel thread is an expensive object. Creating one costs a system call and a stack, typically reserved in the megabytes on 64-bit systems, and the scheduler that multiplexes them is in the kernel where the language runtime cannot see it. An M:N runtime replaces that with its own abstraction: M tasks, each with a small stack that grows on demand, multiplexed onto N kernel threads, where N is usually the number of usable cores and the runtime decides which task runs where.

The design exists because the two granularities want different things. Tasks want to be cheap enough to create per connection, per request, or per object. Kernel threads want to be few, because context switching between them is a transition into the kernel and each has a fixed stack cost. M:N scheduling decouples the two, and every complication in a modern runtime follows from that decoupling.

The three-level queue

A typical M:N scheduler has a global run queue, a per-worker run queue, and a parking mechanism for idle workers. A task that becomes runnable is pushed onto a queue; a worker pops and runs it until the task blocks, yields, or is preempted.

Per-worker queues are the important part. A single global queue requires an atomic operation on every push and pop and becomes a contention point as core counts rise. Per-worker queues make the common case a local push or pop with no synchronisation at all, and reserve atomics for the steal path. The Go runtime uses exactly this structure: a run queue per P (a scheduling context), plus a global queue for overflow, and workers that steal from others when their own queue drains.

The queue is usually a deque, and the worker that owns it takes from one end while thieves take from the other. The owner’s end is hot in cache because it was just touched; the thief’s end is cold anyway, so the steal pays the cache miss it was going to pay regardless. The ordering is deliberate: taking from opposite ends maximises the distance between the owner’s working set and the stolen task, which is the task least likely to be related to what the owner is doing.

Work stealing and the locality it trades away

The scheduler’s central assumption is that tasks created by a running task are likely to share data with it. So a newly created task is pushed onto the creator’s local queue, and if a worker is idle it takes it, so a fork-join computation keeps its subproblems near the core that generated them.

When a worker’s local queue is empty, it picks a victim and attempts to steal. In the Blumofe-Leiserson analysis, a worker steals from the far end of the victim’s deque, and the expected running time for a computation with T₁ total work and critical path T∞ is T₁/P + O(T∞) on P processors. The scheduling overhead does not multiply with the processor count; it is bounded by the critical path.

The bound assumes a specific work model: tasks that are spawned and later joined, with no blocking. Real runtimes add blocking, I/O, and priority, and each of those breaks the model in a specific way. A worker that blocks inside a task must either be replaced by a new kernel thread or must have its remaining tasks migrated, and both are costly. The same blocking hazard is what makes the cancel-safety classification in Cooperative Cancellation and the Cancel-Safety Contract a scheduling concern and not only a correctness one. Runtimes handle this by trying to avoid blocking calls in the runtime’s own primitives: a channel receive parks the task, not the worker, so the worker continues to other tasks and the blocked task is resumed by whoever completes the operation.

The stack problem

Green threads need stacks, and stack size is a genuine trade-off with no free setting.

A fixed, small stack per task bounds memory but overflows on deep recursion or large frames. A fixed, large stack reserves address space at scale: 100,000 tasks with 1 MiB each is about 100 GiB of reservation, most of it untouched, which is why operating systems use virtual memory to make reserved-but-untouched stacks cost nothing until they are used. A runtime that allocates stacks on a managed heap cannot rely on that trick, so it either segments the stack or copies it on growth.

Segmented stacks divide the stack into fixed-size chunks linked together, so growth allocates a new chunk and no copying occurs. The cost is that a call crossing a segment boundary is slower, and the runtime must be able to detect the crossing. Copying stacks grow by allocating a larger stack and copying the live frames; the copy is O(depth) and happens rarely, amortised to O(1) per frame if the growth is geometric, but a pointer into the old stack becomes invalid, which constrains what the runtime can do with interior pointers.

Both designs trade a rare expensive operation against a common cheap one, and the choice shows in the language’s restrictions. A copying stack requires the runtime to find and adjust every pointer into the moved region, which is only possible where the runtime has precise stack maps for each frame; that is why pointers to locals can survive a stack growth in a runtime that maintains them, and why a language whose state machine is itself moved by the compiler, without stack maps the runtime can consult, forbids holding a borrow to a local across a suspension point unless the value is pinned in place.

Preemption without cooperation

A cooperative scheduler only switches at explicit yield points. A task in a tight loop with no allocation and no call never yields, and on a machine with N workers, N such tasks saturate the runtime while everything else starves. This is not a theoretical concern; it is the failure mode that motivated asynchronous preemption in the Go runtime.

Asynchronous preemption requires a way to interrupt a running task at an arbitrary instruction. Go introduced one in version 1.14 by sending a signal (SIGURG on Unix) to the thread running the goroutine; the handler either preempts on the spot, by rewriting the saved program counter and stack pointer so the goroutine returns into the runtime’s preemption stub, when the interrupted instruction is an asynchronous safe point recorded in the function’s stack map, or marks the goroutine so that it yields at the next such point. Because the compiler records safe points at function entries and at loop back edges, a tight loop with no calls is preemptible, which was the case the mechanism was added to cover.

Erlang takes a different route: it counts reductions, where a reduction is roughly a function call or a small unit of work, and a process that exhausts its budget is descheduled. The count is decremented at function calls and at backward jumps in loops, so a process that loops without calling anything still yields. The advantage of the counting approach is that it needs no signal and no cooperation from the operating system; the disadvantage is that it only works where the runtime controls every instruction, which is the case for a bytecode VM and not for native code.

What the scheduler cannot fix

An M:N runtime can make tasks cheap, but it cannot make a task’s work parallel. Two tasks that both contend on the same mutex serialise regardless of how many workers exist, and the runtime’s own locks are subject to the same rule. A scheduler with N workers and a single hot lock has an effective parallelism of one, and adding workers increases contention rather than throughput.

Nor can the scheduler bound latency. A run queue is a queue: a task at the back waits for everything ahead of it. Fairness between tasks is a property of the queue discipline, and most M:N runtimes offer best-effort fairness rather than a guarantee. A long-running task that yields periodically still delays the tasks behind it by the length of its slice.

The runtime can, however, make the blocking case cheap, and that is where the design pays off. A server that holds a task per connection and blocks on a read has a memory cost of one stack per connection and a scheduling cost of zero while parked. That is the property that made the model dominant for network services, and it is the same property that makes the failure modes of unbounded concurrency so easy to reach: nothing in the runtime charges for a task that is merely parked, so nothing discourages creating a million of them.

The structural question of who owns a spawned task, and who waits for it, is not answered by the scheduler at all. That is a separate discipline, described in Structured Concurrency and the Task Scope.