User-Level Threads and the M:N Scheduling Problem

A kernel thread costs a task descriptor, a kernel stack, and a trap on every scheduling decision. For a server that wants tens of thousands of concurrent tasks, mostly blocked on network input, that cost is the binding constraint: the tasks are cheap in terms of what they do and expensive in terms of what the kernel must maintain for each of them. The response is to let a runtime schedule its own threads, using a small number of kernel threads as execution vehicles.

Two Levels of Scheduling

In the M:N model, M logical threads are multiplexed over N kernel threads. The runtime owns the M logical threads entirely: their stacks, their saved register state, their run queue. The kernel owns the N kernel threads and knows nothing about the M. A logical thread runs when the runtime switches a kernel thread onto it, and the switch is a user-space operation that saves registers to a runtime structure and loads another set.

The benefit is that the switch no longer crosses the kernel boundary. There is no trap, no kernel stack change, and no scheduler invocation. The register save is the same handful of stores the kernel would do, performed by a small assembly routine or by the compiler’s support for stack switching. The cost of creating a logical thread drops from a kernel allocation to a runtime allocation, and a stack can start small.

The cost is that the kernel’s view and the runtime’s view can disagree. The kernel schedules N threads on the assumption that they are the units of work. If one of them blocks in a system call, the kernel deschedules it and the logical threads it was running are stuck: they are runnable from the runtime’s perspective and have no vehicle. The runtime must either create another kernel thread to compensate, or ensure that its logical threads never make blocking calls.

The Blocking Call Is the Whole Problem

Everything else in the design follows from how blocking calls are handled. The straightforward approach is to give each logical thread the ability to make a blocking call by having the runtime detect it and hand off. Detection requires either wrapping every call that might block, which is fragile because a library can call a blocking function internally, or converting the calls to non-blocking form and having the runtime poll.

The conversion approach is what modern runtimes do. Sockets are placed in non-blocking mode. A logical thread that would block registers its interest with an event notification mechanism, records why it is waiting, and yields to the runtime scheduler. The runtime’s event loop waits for readiness on any of the registered descriptors and wakes the corresponding logical threads. The kernel thread that was running the blocked logical thread is now free to run another.

This works for descriptors and for a few other pollable objects. It does not work for a call that blocks inside the kernel on something that has no file descriptor: a page fault on a file-backed mapping that requires disk I/O, a read from a file on a local filesystem, a call into a library that takes a lock held by a thread that is itself blocked. For these, the runtime’s only options are to run the call on a separate kernel thread dedicated to blocking operations, or to accept that the vehicle is lost and create a replacement.

The replacement strategy is what causes thread explosion. If the runtime creates a new kernel thread whenever one blocks, a workload that makes many concurrent blocking calls creates many kernel threads, and the M:N design degrades to 1:1 with extra bookkeeping. Runtimes bound this with a pool of blocking-capable threads and a queue of work for them, so the number of kernel threads is capped at a configured value and the logical threads that need a blocking call wait for a slot.

Stack Management

A logical thread’s stack can be small because the runtime can grow it. The technique is a segmented or copied stack. In the copied variant, the thread starts with a small stack, and when the stack pointer approaches the limit the runtime allocates a larger stack, copies the contents, adjusts every pointer into the old stack that the runtime can find, and resumes on the new one. Finding the pointers is the hard part: a pointer into the stack may be held in a register, in a callee’s frame, or in a structure the runtime cannot see.

The consequence is that the runtime must be able to identify all live pointers into a stack, which requires cooperation from the compiler. A runtime that cannot do this uses a fixed maximum stack size per logical thread, chosen small enough that the total for M threads fits in memory. That is the design used by runtimes that cannot move stacks, and it makes the maximum depth of a logical thread a static property rather than a dynamic one.

Segmented stacks avoid the copying by allocating stack segments as needed and chaining them, with the return path switching segments. The cost is that every function call must check whether the current segment has room, which is a comparison and a conditional branch on a hot path. The check is cheap but not free, and it is paid on every call rather than only at the point of growth.

The third approach is to give each logical thread a large stack reservation in a virtual address space that is sparse enough to afford it. A reservation of a few hundred kilobytes costs address space and no physical memory until touched, and it removes the need for growth, copying, and the per-call check. It works when the address space is large relative to the number of threads, which is the case on 64-bit machines up to a point. The guard-page and thread-local-block layout that a kernel thread’s stack uses is described in Thread Stacks, Guard Pages, and Thread-Local Storage, and the same layout constraints apply to a runtime’s stacks because the thread pointer register must still point at a valid block.

Handoff and Locality

The runtime’s scheduler decides which logical thread runs on which vehicle, and its decisions interact with the kernel’s. A logical thread that was running on a vehicle bound to one processor and is resumed on a vehicle bound to another pays the cost of a cold cache and a cold translation set. The runtime can bind its vehicles to processors and keep a logical thread on the same vehicle where possible, which turns the M:N scheduler into a per-processor work-stealing scheduler.

Work stealing is the usual structure. Each vehicle has a local queue of runnable logical threads. A vehicle that empties its queue takes work from another vehicle’s queue, typically from the opposite end of the queue from the one the owner uses, to reduce contention. The stolen thread migrates, and the migration cost is accepted because the alternative is an idle processor.

The interaction with the kernel scheduler is the source of a class of latency problems. The kernel may preempt a vehicle in the middle of running a logical thread, at a point the runtime did not choose. The runtime must be able to save the logical thread’s state at that point, which means the state must be recoverable from the vehicle’s own context, and the runtime must not hold a lock that another logical thread needs while it is preempted. Runtimes handle this by keeping runtime locks short and by making the preemption points explicit where possible.

Scheduler Activations and Why They Lost

The research answer to the coordination problem was scheduler activations: the kernel notifies the runtime when a vehicle blocks or is preempted, and the runtime decides which logical thread to run next. The kernel allocates a replacement vehicle when a logical thread blocks, and the runtime is told about the allocation. The runtime thus has complete information and the kernel retains control of processor allocation.

The design failed to be adopted widely for practical reasons. It requires a new kernel interface, which means every kernel and every runtime must implement the same contract. It requires the runtime to handle upcalls at arbitrary points, including while holding its own locks. And it does not compose with the existing thread interfaces, which assume that a thread is a kernel object.

What replaced it is the combination of non-blocking I/O and a runtime-managed pool of blocking threads. The kernel provides the event notification mechanism and the ability to make calls non-blocking; the runtime builds the scheduling on top. The kernel’s role shrinks to providing vehicles and readiness notifications, and the coordination problem is solved by avoiding the situations that require coordination.

The cost of that avoidance is visible in the programming model. A logical thread that calls a blocking function without the runtime’s knowledge stalls a vehicle, and a runtime that cannot intercept the call cannot prevent it. The common failure is a call into a library that uses a blocking primitive internally, which is invisible to the runtime and which degrades the M:N scheduling to 1:1 for the duration. The mitigation is to run such calls on the dedicated blocking pool, which requires the programmer to know which calls those are.

When the Model Is Worth It

The M:N design wins when the number of concurrent tasks is large, the tasks are mostly waiting, and the runtime controls the code that runs on them. A server handling many connections fits all three. A program that calls into arbitrary libraries fails the third condition and must fall back to the blocking pool, which caps the benefit.

The design loses when the tasks are CPU-bound, because then the number of runnable tasks is bounded by the number of processors and the runtime’s scheduling adds a layer with no benefit. It also loses when the tasks need kernel-level isolation, because a logical thread shares the address space with every other logical thread in the process, and the kernel cannot enforce a boundary between them. The isolation trade is the same one described in What Threads Share and What They Own, pushed one level further: the runtime’s threads share everything the kernel’s threads share, and the runtime adds no protection of its own.

The numbers that matter are the per-thread cost and the switch cost. A kernel thread’s kernel stack is a fixed allocation of a few pages; a logical thread’s stack can be a few kilobytes. A kernel switch costs a trap and, for a different address space, a translation-cache flush; a logical switch costs a register save and no trap. Those two ratios set the range where M:N is the right answer, and outside that range the simpler 1:1 mapping is both easier to reason about and no slower.