Scheduling, Threads, and Concurrency Runtimes

At 14:03:17.240, Mercury wakes task A after its storage read completes. All eight CPUs in the service quota are busy. A enters a run queue behind CPU subtasks created by other requests. At .252, the request’s 80 ms deadline expires, but its parent has not propagated cancellation. At .267, A finally runs on a different CPU, reloads cold data, acquires a response lock, and produces an answer the caller has already abandoned.

Nothing in that sequence is a long computation. The damage comes from three distinct intervals that a wall-clock duration can hide: blocked waiting for I/O, runnable waiting for a CPU, and running after useful completion became impossible. A runtime can make millions of tasks cheap to create while still having only eight CPUs on which useful instructions can execute.

This distinction matters when latency rises with concurrency, throughput falls after adding workers, blocked calls appear inside an async service, or several innocent pools multiply runnable work. The remedy begins by mapping tasks to their scheduling layers, sizing CPU execution separately from occupied waiting, and making cancellation and ownership explicit at every handoff.

Concurrency is a promise about overlap, not capacity

A process owns an address space and operating-system resources. An operating-system thread is usually the schedulable execution context the kernel runs on a CPU. A fiber, coroutine, or language task is a user-space unit that a runtime may multiplex over fewer threads. An event loop waits for readiness and dispatches callbacks or resumable tasks. Names vary across ecosystems, so diagnose the mapping rather than trusting the label.

Three counts answer different questions:

• Concurrency is the number of operations that have begun but not completed.
• Parallelism is the number of operations actually executing simultaneously.
• Arrival rate is new offered work per unit time.

A service can hold 20,000 concurrent sockets, run eight tasks in parallel, and receive 1,200 requests/s. Treating those values as interchangeable produces bad pool sizing and meaningless “threads per core” rules.

At any instant, an execution entity is approximately running, runnable, blocked, sleeping by design, or complete. Runtime-specific states are richer, but this partition separates the most important costs. Running consumes CPU. Runnable work wants CPU but has not received it. Blocked work waits for an event. A large blocked population can be healthy for an event-driven server; a growing runnable population is direct competition for finite execution slots.

Preemption and cooperation fail differently

With preemptive scheduling, a scheduler can interrupt an executing thread and run another. This prevents an ordinary compute loop from owning a CPU indefinitely, but it adds scheduling decisions, context switches, migrations, and cache disruption. Priority and fairness policies decide which runnable entity gets time; they do not create time.

With cooperative scheduling, a task runs until it completes, awaits, yields, or reaches another runtime-defined suspension point. Cooperation can make switches cheaper and keep state local. A task that performs a long computation, invokes blocking I/O, or never yields can stall unrelated work on the same executor. The runtime cannot schedule around an operation it cannot see as suspendable.

Many systems are hybrids. The kernel preempts runtime worker threads; the runtime cooperatively schedules tasks on them; a library maintains a separate blocking or CPU pool; the storage client and DNS resolver may introduce still more queues. “Async” describes an interface. The path remains async only while every potentially blocking boundary is either readiness-driven or isolated in a bounded blocking executor.

One request can occupy a thread or release it

A thread-per-request design gives each admitted request a thread for most of its lifetime. Its control flow and thread-local state are easy to inspect. When the request blocks, the thread stops running but still consumes stack, runtime metadata, and a place in the concurrency boundary. Enough waiting requests can exhaust the pool even while CPU usage is low.

An event-driven task runs until it registers I/O, leaves the worker, and resumes when readiness arrives. This lets a small worker set supervise many waiting operations. It does not reduce CPU service demand, downstream concurrency, buffer ownership, or queued work. If admission is unbounded, the design converts thread exhaustion into heap growth, queue age, and cancellation debt.

Four useful arrangements occupy the design space:

The right choice makes waiting, bounds, cancellation, and ownership inspectable for the dominant workload. Cheap task creation is not a decision criterion by itself.

Run queues are latency-bearing state

When a blocked thread becomes eligible to run, it does not necessarily run immediately. It becomes runnable and enters a scheduling structure associated with a CPU or scheduling domain. Selection policy, priority, affinity, load balancing, CPU availability, and competing work determine its dispatch time.

A context switch saves one execution context and restores another. The direct scheduler cost may be smaller than the indirect cost: displaced instructions and data, branch-predictor history, translation state, and NUMA locality. Chapter 10 established that placement governs memory access; task migration can break that placement after the data has been made local.

Migration is not inherently wrong. Moving work can prevent one CPU’s queue from growing while another idles. The question is whether balance gained exceeds locality lost. A stateful shard, per-core cache, or memory-bound task may benefit from affinity. A skewed affinity policy can strand capacity and worsen tails. Measure migrations and cache/NUMA evidence with correct goodput rather than optimizing a switch counter in isolation.

On contemporary Linux, ordinary fair scheduling is transitioning from older CFS selection toward EEVDF. The implementation uses virtual-time ideas to share CPU among runnable tasks, and exact behavior varies by kernel, policy, priority, cgroup controls, topology, and configuration. The portable lesson is narrower: equal-priority runnable tasks compete, and scheduler policy mediates that competition. Do not turn a kernel implementation detail into a universal runtime sizing formula.

Size CPU execution and occupied waiting separately

Suppose a correct Mercury lookup consumes an estimated 4 ms of CPU service and waits 16 ms for I/O, for 20 ms mean wall-clock time. The target is 1,200 correct completions/s under an eight-logical-CPU quota.

CPU demand is:

[ D_{CPU} = \lambda S_{CPU} = 1{,}200\ \text{requests/s} \times 0.004\ \text{CPU-s/request} = 4.8\ \text{CPU cores} ]

where (\lambda) is the correct completion rate and (S_{CPU}) is CPU service demand per correct completion. This estimate assumes the request mix and service demand remain stable; retries and abandoned work must be counted separately.

At a chosen 70% utilization target, the modeled CPU ceiling is:

[ X_{target} = \frac{8\ \text{cores} \times 0.70}{0.004\ \text{CPU-s/request}} = 1{,}400\ \text{requests/s} ]

The 1,200/s objective consumes 4.8 cores on average, leaving modeled headroom for variance, runtime work, and failure. It does not prove p99 will fit; runnable bursts and skew still matter.

Little’s Law estimates average occupied requests at the declared boundary:

[ N = \lambda W = 1{,}200\ \text{requests/s} \times 0.020\ \text{s} = 24\ \text{requests} ]

A blocking design might provision 30 occupied threads by applying a 1.25 teaching headroom factor. That factor is a modeled policy choice, not a law. An async design can use eight CPU workers and release them during the 16 ms wait, but it still needs admission and downstream limits sized for roughly 24 average in-flight operations plus variance. Separating the two calculations prevents a common error: sizing CPU workers from wall-clock latency or sizing admitted I/O concurrency from core count.

CPU-bound work usually benefits from a runnable population near available parallel capacity, with small headroom for imbalance. I/O-bound concurrency is instead constrained by arrival rate, wait distribution, deadlines, buffers, downstream limits, and recovery cost. If work mixes both, split the execution classes or use cost-aware admission. One pool sized for the average can let long blocking operations convoy short CPU work.

The knee appears before the largest task count

The simulated Mercury sweep holds workload and environment constant:

Goodput gains only 0.5% from 24 to 32 in flight, while p99 crosses the 80 ms deadline. Beyond 32, more concurrency reduces goodput. The exact values are simulated, but the shape teaches a general search: sweep the bound, preserve the offered workload and correctness checks, and find the smallest region that keeps resources usefully occupied without moving wait beyond the objective.

Average CPU may still mislead. A quota can throttle the process while host CPU looks idle. One hot run queue can coexist with idle CPUs under affinity or skew. Short runnable bursts can dominate p99 while a one-minute utilization average remains comfortable. Preserve per-operation CPU demand, run-queue delay, queue age, completions, deadline success, and placement together.

Work stealing trades balance for locality

Work-stealing runtimes commonly give workers local queues and let idle workers take tasks from others. Local push/pop operations preserve affinity and reduce contention in the ordinary path. Stealing helps under uneven task duration or bursty submission, but it adds synchronization, moves work, and can separate tasks from warm caches or local memory.

Stealing works best when tasks are independent, movable, and coarse enough to amortize scheduler overhead. Tiny tasks can spend more time in enqueue, wakeup, steal, and bookkeeping than in useful work. Large tasks reduce overhead but increase imbalance and cooperative-scheduling stalls. A deque count cannot express either cost without task service distributions.

Measure the steal rate, failed steals, worker idle time, runnable delay, task duration distribution, migrations, and useful completions. A high steal count may indicate healthy balancing or pathological task fragmentation. A low count may indicate good locality or a stranded worker. The workload and outcome decide.

Priority is a resource contract

Priority can protect deadline-sensitive work, but only when the scarce resource and every dependency honor the distinction. A high-priority task waiting on a lock held by low-priority work experiences priority inversion. A high-priority request can also wait behind low-priority items in a runtime queue, connection pool, storage device, or downstream service even if the kernel schedules its thread first.

Fairness also needs a boundary. Fair CPU time by thread is not fair service by tenant when one request creates four threads. FIFO task order is not fair latency when task cost varies by 100×. Strict priority can starve background work until recovery becomes impossible. Weighted service, reserved concurrency, aging, per-tenant queues, and deadline-aware admission are policy tools; each requires an explicit promise and starvation bound.

Map the full resource chain before assigning priority:

admission → runtime queue → CPU → lock → connection pool → dependency

If one layer drops the class or reverses ownership, the priority promise is incomplete. Observe wait by class at each layer, not only thread priority.

Cancellation must reach owned work

A timeout stops one observer from waiting. A deadline states when useful completion is no longer expected. Cancellation asks owned work to stop. These are different events. If a parent request times out while its subtasks continue, the system consumes CPU, locks, connections, and queue slots for an outcome nobody can use.

Structured concurrency makes child lifetimes explicit: a parent scope owns its subtasks, joins or cancels them as a group, and does not silently return while work escapes. The principle transfers across languages even though APIs and guarantees differ. Cancellation remains cooperative at many boundaries. Code must reach a cancellation point, propagate the reason, release resources safely, and decide what happens to non-interruptible operations and already-committed effects.

Return to Mercury’s task A. If it belongs to the request, the parent owns its lifetime and passes the remaining 80 ms budget rather than granting a fresh timeout at the storage boundary. A semaphore, pool, queue, or admission budget bounds the fan-out before the task exists. The cancellation signal must cross both the runtime scope and any downstream protocol that can honor it. Success, failure, cancellation, and work that continues after abandonment remain distinct outcomes in telemetry.

Some work cannot stop promptly. Detaching it is legitimate only when ownership moves deliberately from the request to a durable workflow or the service lifecycle, with its own capacity bound and completion record. Otherwise “detached” means the request returned while retaining an unnamed claim on the system.

Cancellation safety is not the same as transaction rollback. A storage write may have committed before cancellation arrives. The concurrency model must preserve idempotency and outcome semantics rather than pretending interrupted waiting erased side effects.

Layered pools create invisible oversubscription

Mercury admits 24 requests. Each invokes a library operation that can split into four CPU-bound subtasks. The application exposes an eight-worker runtime and the library owns a pool with a maximum of 64 threads. At the logical layer, the request set can create:

[ 24\ \text{requests} \times 4\ \text{subtasks/request} = 96\ \text{runnable subtasks} ]

Against eight logical CPUs, that is 12 runnable tasks per CPU before runtime, telemetry, and kernel work. The application configuration still says “eight workers,” so a dashboard of that pool alone looks bounded.

Find the multiplication by drawing every handoff and annotating maximum active work, queue bound, and blocking behavior. Inventory runtime workers, blocking executors, library pools, parallel iterators, database connections, and downstream concurrency. Then record runnable delay and context switches while reducing one layer’s parallelism. If goodput holds and tail latency falls, the extra layer was coordination rather than capacity.

Oversubscription is sometimes useful: a small surplus hides short stalls and balances uneven work. It becomes harmful when runnable delay, cache disruption, lock pressure, or deadline waste grows faster than goodput. The decision is empirical and bounded, not “one thread per core” or “tasks are cheap.”

Scheduler evidence must align with the request path

Use a state timeline before changing runtime knobs:

Linux scheduler statistics can expose time tasks spend running and waiting to run when enabled, but interfaces and versions differ. Runtime queue time, loop lag, worker state, steal counts, and cancellation telemetry add the user-space view. Chapter 49’s population rules still apply: segment by operation, build, tenant, outcome, and operating state, and normalize by correct useful completions.

During overload, reject before creating an unbounded task graph. During partial failure, reduce downstream concurrency and suppress retry amplification. During recovery, reserve capacity for cache warm-up or backlog drain without allowing it to starve current work. Restart behavior matters: an apparently stable pool can synchronize connection establishment and wake thousands of tasks at once.

A runtime decision should fit on one page

Use this compact review rather than selecting by fashion:

Run the teaching model:

node examples/performance-engineering-system-design-handbook/part-02/scheduling-runtime/run.mjs
node examples/performance-engineering-system-design-handbook/part-02/scheduling-runtime/verify.mjs

Then perform three checks. First, recompute CPU demand and average in-flight work if the I/O wait rises from 16 ms to 46 ms while CPU service remains 4 ms; explain which bound should change and which should not. Second, inventory a real request path for every pool and compute the maximum runnable amplification from one admitted request. Third, design cancellation for a parent with two reads and one non-idempotent write; name the owner and outcome when the deadline expires after commit but before acknowledgment.

Before approving a concurrency boundary, ask: What is running, runnable, and blocked? Which unit of useful work sizes it? Where is the queue, and what is its age bound? Can one library multiply parallelism? What preserves locality? Which class can starve? Who owns every child after cancellation? What happens during dependency failure, restart, and backlog drain?

Choose the concurrency model that makes waiting, cancellation, bounds, and ownership explicit for the dominant workload. Increase concurrency only while it converts otherwise idle resources into correct goodput; stop when it mostly creates runnable delay, movement, and abandoned work. With scheduled execution visible, allocation, object lifetime, garbage collection, and warm-up become the next costs to separate because they pause or compete with these same workers.

Sources and evidence scope

• Linux EEVDF scheduler documentation describes the virtual-lag and virtual-deadline model used as Linux transitions ordinary fair scheduling. Exact selection behavior is kernel- and configuration-specific.
• Linux CFS scheduler documentation records the earlier virtual-runtime design and scheduling classes; it also notes the transition toward EEVDF.
• Linux scheduler statistics documentation defines versioned run and wait counters. Availability, overhead, and field versions must be verified on the target kernel.
• OpenJDK JEP 525 specifies the sixth preview of structured concurrency for JDK 26 and its scoped lifetime goals. The chapter relies on the ownership principle, not that preview API as a portable standard.
• All Mercury service demand, pool sizes, sweep results, and oversubscription values are modeled or simulated teaching evidence in examples/performance-engineering-system-design-handbook/part-02/scheduling-runtime/, not measurements of a kernel or language runtime.