Threads, Scheduler Activations and the Failed Promise of User-Level Scheduling

A thread is a program counter and a stack. Everything else about it, whether it is scheduled by the kernel or by a library, is a design decision about who pays for the switch and who knows what the program wants. The user-level thread and the kernel thread are two endpoints of that decision, and the history of operating systems in the late 1980s and early 1990s is largely a record of attempts to hold both at once, ending in the choice of the endpoint that was less efficient and knew less.

Multiplexing M user threads onto N kernel threads

The standard user-level thread package keeps all thread state in user space and switches between threads with a saved register set and a stack pointer, both manipulated directly by the library. No kernel call occurs during a switch, so a switch saves and restores a register set and a stack pointer in user space rather than crossing into the kernel and back through a scheduler pass. The library can also make decisions the kernel cannot: it knows the dependency structure of the program, it knows when a thread is waiting for a lock held by a thread in the same address space, and it can implement priority inheritance or lock-free handoff at a granularity the kernel would find prohibitively fine.

The design constraint that produces the problem is the one blocking operation that the library cannot see coming. A user-level thread executing a read on a file descriptor enters the kernel, and the kernel blocks the kernel thread it is running on. From the library’s point of view, one of its n slots has disappeared while the thread that occupied it is still logically runnable elsewhere in the program. The library’s scheduler cannot reschedule it because the thread’s state is on a stack that the kernel has suspended.

The two documented escapes were both weak. The first is to wrap every potentially blocking call and use non-blocking variants, so the library learns about the wait before entering the kernel. This requires interposing on the entire system call interface, and it fails for operations whose non-blocking form does not exist or whose blocking happens deep in a library that issues its own calls. The second is to accept that a blocked call stalls the kernel thread and provide enough kernel threads that a few stalls do not matter, which is the M:N design that the Solaris thread library and others used. Under a workload where many threads block on I/O, the M:N layer oversubscribes kernel threads and its scheduling decisions interact unpredictably with the kernel’s.

The stacks

A second constraint is memory. A user-level thread’s stack must be allocated in the address space, and a typical default is large. Threads created in their thousands consume their stacks’ virtual address space; a 32-bit process with a 3 GB user address space and 1 MB per thread bottoms out at roughly three thousand threads before allocation fails. The traditional answer is to reduce the per-thread stack to a few tens of kilobytes, which is safe only if the thread’s call depth is bounded, and unbounded call depth in a program whose libraries are not stack-aware is exactly the case where the assumption fails. Guard pages turn the failure from a silent overwrite into a fault, and the fault occurs in a thread that has already consumed its address space, which is not a recoverable state.

What scheduler activations asked for

The scheduler activations design, published by Anderson, Bershad, Lazowska and Levy in 1992, is the clearest statement of what a kernel would have to provide to make user-level scheduling sound. Its premise is that the kernel’s job is to allocate processors and report events, and the application’s job is to decide what runs on them.

The mechanism is this: the kernel gives an address space a set of virtual processors, one per kernel-visible execution context. When the kernel needs to preempt a thread, it removes a virtual processor rather than suspending a thread, and it notifies the user-level scheduler with an activation upcall that carries the state of the preempted context on a fresh stack. The user-level scheduler then decides which thread to run on the processor it still has. When a thread blocks in the kernel, the kernel adds a virtual processor if the address space does not have enough, so that the blocked thread’s absence does not reduce the program’s parallelism. When the blocking operation completes, the blocked thread resumes on one of the virtual processors it is given.

The promise is that the kernel never makes a scheduling decision on the application’s behalf, and that the application never has to guess the kernel’s state. The upcall is the key structural element: it converts a kernel-side event into a user-side function call at a point where the application’s scheduler is running and can act.

The cost of a new kernel interface

Three properties of that design are why it never spread.

It requires the kernel to deliver an upcall into the address space at an arbitrary point, on a stack the kernel allocates. On a system without a way to run user code with a kernel-controlled stack, this is a new execution state, and the kernel’s own description of its thread state machine grows a case for it. Debuggers, profilers and signal handlers all have to be taught what a thread that is executing an upcall looks like.

It makes the kernel’s scheduling policy dependent on the user library’s readiness to return processors. A library that fails to release a virtual processor when it should stalls the kernel scheduler’s accounting, and the kernel has no way to distinguish a buggy library from a library implementing a policy the kernel should not know about. The designers’ answer is that the contract is enforced by the library being correct, which is a weaker guarantee than the kernel enforcing it.

And it invalidates the assumption behind most of the rest of the system’s interfaces. Signals, in particular, are delivered to a process, and the choice of which thread handles one is made by the kernel in the kernel-thread model. Under user-level scheduling the kernel must deliver the signal to the address space and let the library pick the thread, which means the semantics of a perfectly ordinary system call change depending on a library’s design.

The published evaluations of the mechanism showed the expected benefit for workloads with frequent synchronization and fine-grained blocking. What stopped it was not the evaluation. It was that the interface is a commitment by every kernel and every library to a shared protocol, and neither side controlled the other.

The compromise that was actually shipped

The kernel thread model won by changing the price of what it offered. On multiprocessors, the kernel already had to schedule kernel threads to use the available processors; once the kernel’s scheduler was parallel and its context switch path was optimized, the gap between a user-level switch and a kernel-mediated one narrowed to a factor that few applications could justify building around. The dominant cost of interaction in the kernel model is the system call boundary and the scheduler’s locking, both of which were the subject of a great deal of work in that period. The exact figure varies by architecture and by kernel version, and the difference between a user-level switch and a kernel switch has narrowed in a way that eventually made the whole debate moot for most programs.

What was kept from the user-level tradition is the idea that blocking calls should be thread-aware. A kernel thread that blocks yields its processor to another thread, so the library’s problem disappears: there is no suspension of a slot, only another thread runnable elsewhere. The cost is the per-thread stack in the kernel, and the kernel’s stack requirement became the binding constraint on thread count. On Linux, the same task structure serves as process and thread, and the per-thread kernel stack is a small fixed allocation wired to the scheduler’s expectations, which is why thread creation eventually became cheap enough that libraries scaled to the tens of thousands.

The user-level scheduler’s advantage for fine-grained parallelism moved to a different layer entirely: the runtime for languages with their own schedulers runs many lightweight tasks on a fixed pool of kernel threads, and the reason it can do so soundly is that the runtime controls every blocking operation its tasks can perform. That control is the property the general-purpose library never had.

Why the blocking call was the whole story

The failure is concentrated in a single question: can the library know, before entering the kernel, that the call will block? A runtime that owns the I/O layer can answer yes, because its tasks call an interface that it implements. A library that augments a general-purpose system call interface has to guess, and the assumptions it makes about which calls block are documented in its own manual as a list, and a list is not a mechanism. The list is correct until a library adds a call, or until a platform makes an existing call block where it previously did not.

This is the same structural shape as the version-token conflict described in Optimistic Concurrency and the Conflict Check That Arrives Too Late: the check exists, it is correct when it runs, and it runs at the wrong point in the sequence to prevent the outcome. The user-level scheduler’s check for whether a call will block happens before the call. The kernel’s decision to block happens inside it. Nothing in the interface carries the answer from one to the other.

What survived

The activation model’s core insight survived in the form of the runtime: a scheduler that controls its threads’ entry and exit from the kernel, whether through non-blocking I/O and an event loop or through a poll mechanism that it invokes itself, can implement any policy it likes, because it owns the points where the kernel is entered. The failure was not the idea of user-level scheduling. It was the attempt to graft user-level scheduling onto an interface designed for a thread model the library could not observe.

The kernel thread model won on the axis that mattered, which was not the cost of a switch but the completeness of the interface. A user-level scheduler on an opaque system call interface has to know something it cannot know, and the design that removed the requirement to know it required a new kernel interface that no one was in a position to deliver.