User-Level vs Kernel-Level Threads

A thread is an independent sequence of execution sharing an address space with its siblings; it needs its own program counter, register set, and stack, bundled into a thread control block (TCB). The central design question is: where does the TCB live, and who switches between TCBs? If the answer is "a library linked into the user process, with no kernel involvement," we call these user-level threads. If the answer is "the kernel itself, which knows about and schedules each thread," we call these kernel-level threads. This is not a cosmetic distinction. The kernel is the only entity that can (a) preempt a running thread via a timer interrupt, (b) assign threads to physical CPU cores, and (c) block/unblock a thread on a system call like `read()`. If the kernel does not know a user-level thread exists, it can do none of these things for that thread individually — it only sees the one (or few) kernel-level entities that host the user threads. Conversely, every operation the kernel does perform on a thread's behalf — creating it, context-switching it, scheduling it — normally requires a trap into kernel mode, which costs far more than a user-space function call. The three canonical mapping models answer the question: how many user-level threads (M) map onto how many kernel-level threads (N)? 1. Many-to-one: all M user threads run on top of a single kernel thread. The user-space library does all scheduling; the kernel sees one schedulable entity. 2. One-to-one: each user thread has its own dedicated kernel thread, so M = N. The kernel scheduler directly manages every thread. 3. Many-to-many: M user threads are multiplexed over N kernel threads, with M ≥ N and typically N ≈ number of CPU cores. A two-level scheduler exists — one in user space (mapping user threads to a pool of kernel threads) and one in the kernel (mapping kernel threads to cores). A useful special case of many-to-many is the two-level model, where a few user threads are also allowed to bind permanently to their own kernel thread (for threads that must never be blocked behind others), while the rest float over the shared pool.

Thread creation. In the many-to-one model, creating a thread is a pure user-space operation: allocate a TCB and a stack, push it onto a ready queue maintained by the threading library — no system call, no kernel involvement, cost is roughly a memory allocation. In one-to-one, thread creation requires a system call (e.g., `clone()` on Linux, `pthread_create` which itself calls `clone()`) so the kernel can allocate its own kernel-level TCB, schedule the new thread, and set up whatever kernel bookkeeping (signal masks, scheduling class, CPU affinity) it needs.

Thread switching (yield or preemption). In many-to-one, when a running user thread yields or its user-space timer fires, the library's own scheduler runs entirely in user mode: save registers to the current TCB, pick the next runnable TCB, restore its registers. No mode switch, no kernel involvement — extremely fast (tens of nanoseconds). In one-to-one, a thread switch is a kernel operation, requiring at least a trap into kernel mode, saving/restoring more state (page tables if switching address spaces, kernel stack pointer), and going through the kernel scheduler — typically one to several microseconds, two to three orders of magnitude slower.

The blocking problem. This is where many-to-one breaks down. Suppose user thread T1, part of process P, calls a blocking system call such as `read()`. The kernel does not know about T1 — it only knows about the single kernel thread hosting P's user threads. When that kernel thread blocks on the I/O, the entire process — every user thread inside it — is descheduled, even though T2, T3, ... might have useful work to do. One-to-one avoids this entirely: T1's dedicated kernel thread blocks, but T2's kernel thread is independently schedulable, so the kernel simply runs it. Many-to-many mitigates the problem via mechanisms like scheduler activations or jacketing wrapper functions that convert a would-be blocking call into a non-blocking one at the user level (e.g., using `select`/`epoll` internally), so the library never lets a whole kernel thread get stuck behind one user thread's I/O.

Parallelism. On a machine with C physical cores, many-to-one can never use more than 1 core for a given process, no matter how many user threads exist, because the kernel only ever sees one schedulable entity. One-to-one can use up to min(M, C) cores simultaneously, since the kernel independently schedules each kernel thread. Many-to-many can use up to min(N, C) cores, and by tuning N to match C, it captures nearly all the available parallelism while still allowing M to be huge (thousands to millions) because ULT creation/switching stays cheap. Below is pseudocode for a simplified many-to-one style user-level scheduler (the kind found inside a "green threads" library), followed by the parallel kernel-visible variant. ``` // ---- User-level thread library (many-to-one style) ---- struct TCB { id registers // saved PC, SP, general registers stack state // READY, RUNNING, BLOCKED, DONE } readyQueue = empty queue of TCB currentTCB = null function thread_create(function f): tcb = new TCB() tcb.stack = allocate_stack() tcb.registers.PC = f tcb.registers.SP = top_of(tcb.stack) tcb.state = READY enqueue(readyQueue, tcb) return tcb.id // Cooperative or timer-driven switch, ALL in user space function thread_yield(): if readyQueue is empty: return // nothing else to run prev = currentTCB save_registers(prev) // pure register save, no trap if prev.state == RUNNING: prev.state = READY enqueue(readyQueue, prev) next = dequeue(readyQueue) next.state = RUNNING currentTCB = next restore_registers(next) // jump into next thread // execution resumes here for 'prev' next time it's picked // The danger case: a "blocking" call must be intercepted function my_read(fd, buf, n): if would_block(fd): currentTCB.state = BLOCKED register_io_wait(fd, currentTCB) thread_yield() // let other user threads run // ... woken up later when data arrives, if the library // uses select()/epoll() under the hood (jacketing) return real_kernel_read(fd, buf, n) ``` ``` // ---- Kernel-level view (one-to-one) ---- // Each user thread creation issues a system call: function pthread_create(f): trap_into_kernel(CREATE_THREAD, f) // kernel allocates a kernel TCB, adds it to the // kernel's ready queue, schedules it on some core // A blocking read() in one-to-one: function read(fd, buf, n): trap_into_kernel(SYS_READ, fd, buf, n) // kernel marks THIS kernel thread's TCB as BLOCKED, // context-switches CPU to a different kernel thread — // sibling threads of the same process are unaffected ```

Thread creation cost. User-level thread creation is O(1) amortized user-space work: allocate a stack (often a fixed-size mmap or a slab-allocated block) and initialize a TCB struct — no system call. Kernel-level thread creation is O(1) work too, but with a constant factor dominated by a mode switch (trap in, trap out) plus kernel bookkeeping (scheduling entity setup, possibly a new kernel stack), which is measured in microseconds versus the tens-of-nanoseconds cost of a user-space allocation. The asymptotic complexity class is the same; the practical constant differs by 100×–1000×, which is exactly why systems that spawn huge numbers of short-lived threads (e.g., one goroutine per request) cannot afford one-to-one kernel threads at scale.

Thread switch cost. A user-level switch under many-to-one is a register save/restore in user space: O(1) with a small constant (no TLB flush needed if staying in the same address space, no privilege-level change). A kernel-level switch is also O(1) but must go through the kernel scheduler's data structures — for a run-queue based scheduler this is typically O(1) amortized (as in Linux's CFS red-black tree operations, O(log n) for the tree update, O(1) for picking next) — plus the fixed cost of the mode switch itself, which dominates for small n.

Correctness invariant — no lost or duplicated thread. Any correct threading model must preserve the invariant that every created thread is in exactly one of {READY, RUNNING, BLOCKED, TERMINATED} at all times, and the transition function is total: every event (creation, yield, timer interrupt, I/O completion, exit) maps the TCB to exactly one new state. In the many-to-one pseudocode above, `thread_yield` preserves this: it always dequeues before enqueuing, so a thread is never in the ready queue and running simultaneously, and never disappears from all queues while still alive. In the kernel-level model, the same invariant is enforced by the kernel scheduler's run queue plus wait queues, with the crucial addition that the kernel guarantees fairness at the level of kernel-visible entities — it can only reason about entities it sees, so a many-to-one process, having 1 visible entity, gets 1 entity's worth of scheduling no matter how many user threads it contains internally. This is precisely the theorem-like fact that explains the blocking problem: since the kernel scheduler operates on kernel TCBs, any state change requiring the kernel (blocking on I/O, preemption to another process) affects the entire set of user threads riding on that single kernel TCB.

Parallelism bound. Formally, if a process has M user threads mapped onto N kernel threads on a machine with C cores, the maximum simultaneous progress is: ``` speedup_max = min(M, N, C) ``` For many-to-one, N = 1, so `speedup_max = 1` regardless of M or C — no parallel speedup is achievable even on a 64-core machine. For one-to-one, N = M, so `speedup_max = min(M, C)`, achieving full hardware parallelism once M ≥ C. For many-to-many with N chosen ≈ C, `speedup_max = min(M, C) = C` once M ≥ C, matching one-to-one's parallelism ceiling while keeping thread-creation/switch costs at the cheap user-space rate for the M-side operations.

Tradeoff honesty. Many-to-many is not free: it requires a genuinely two-level scheduler, careful handling of blocking system calls (jacketing, or scheduler activations — a kernel mechanism that upcalls into user space whenever a kernel thread is about to block or has become idle, so the user-level scheduler can rebalance). This complexity is why real systems mostly retreated to one-to-one at the OS level (Linux NPTL, Windows threads) and instead build many-to-many inside a user-space runtime (Go, Erlang/BEAM) that itself sits atop one-to-one kernel threads — pushing the two-level scheduling problem into a place where the runtime controls both ends.

Consider a process with 4 user-level threads (T1–T4) on a machine with 2 physical cores, and trace what happens when T1 issues a blocking `read()` call, under each model.

The key numeric contrast: under M:1, T1 blocking costs the process 100% of its parallel capacity even though 2 cores sit idle and 3 other threads are ready. Under 1:1, the same event costs the process 0% of its remaining capacity — the kernel simply continues scheduling K2, K3, K4 on the 2 available cores (running 2 at a time, rotating). Under M:N with proper jacketing, the runtime detects the impending block (often via non-blocking I/O and an event loop, e.g., Go's netpoller using `epoll`) before committing K1 to a real blocking syscall, so T1's block never stalls T2 — the practical goal being to approach 1:1's responsiveness while keeping M:1's cheap creation cost for the other three threads that never blocked.

Real production systems still make this exact tradeoff today. Linux and Windows expose one-to-one kernel threads as the OS-level primitive (`pthread_create` on Linux maps to a `clone()` syscall; Windows threads are kernel objects), because it is the simplest model that guarantees correctness under blocking I/O and full multicore parallelism, at the cost of per-thread overhead. Go's goroutine runtime implements a many-to-many scheduler entirely in user space: millions of goroutines can exist, multiplexed over a small, tunable pool of OS threads (`GOMAXPROCS`), with the Go runtime's netpoller handling I/O via non-blocking syscalls and `epoll`/`kqueue` so a blocked goroutine never stalls an OS thread. Erlang/OTP's BEAM VM takes the same many-to-many approach for its lightweight "processes," enabling systems like WhatsApp and telecom switches to run millions of concurrent lightweight units. Java's original "green threads" (pre-Java 1.2 on some platforms) used many-to-one and hit exactly the blocking-I/O wall described above, which is part of why the JVM moved to native (one-to-one) threads, and why Java's newer virtual threads (Project Loom) reintroduce an M:N-style model with careful integration into the JVM's own non-blocking I/O to avoid the classic pitfall. Database connection pools, thread-pool-based web servers (e.g., older Apache MPM prefork/worker models), and async-I/O frameworks (Node.js's single-threaded event loop, which sidesteps the whole question by minimizing thread count altogether) are all direct descendants of this same design fork. Understanding this tradeoff is prerequisite to reasoning about Context Switching costs and to the scheduling policies covered under CPU Scheduling Fundamentals, since a scheduler can only make decisions about the entities the kernel actually sees.

Ask the tutor: How would scheduler activations concretely change the pseudocode of the many-to-one blocking-call handler shown above?