Rethinking how scheduler threads sleep and wake

[SeanTAllen]

Revised; the original version of this document is in the edit history.

The arena allocator's suspend-and-drain work (PR #5768) made the cost of the runtime's wake machinery concrete. Every hard bug I fought there — lost-wakeup windows, seq_cst mark/re-check protocols, a pin-and-retire dance around wake-target teardown, lost-signal handling on macOS, a theoretical shutdown deadlock through a full pipe — exists for one reason: one scheduler thread must wake another, and a missed wake is a hang. Proving "never loses a wake," for every interleaving, on every platform, is where the complexity lives.

I mapped the machinery onto the code for this revision, and the tangle is wider than the wake paths. Going to sleep is as entangled as waking: the block/unblock bookkeeping lives in a local variable inside the steal loop; the active count is kept twice, the second copy only to cover lost signals; the active set must form an exact prefix of the scheduler array or unmute delivery breaks; the pinned-actor thread carries a full private copy of the suspend protocol, and scheduler 0 threads a private sleep loop through the shared one. Under the design below, all of this goes away rather than being ported.

This work is an expansion of #5768's suspend-and-drain step and lands in that PR: nothing merges until it is all done.

The shape of the design

The design rests on one principle: every decision a scheduler thread makes is computed from its own state plus the messages in its own mailbox. The whole design has two shared-state reads, a peek at the global inject queue by passive threads and an active-scheduler gauge read by the ASIO thread; everything else is local. This is the discipline the runtime imposes on user code — sole writer of your own state, coordination by messages — applied to the scheduler threads.

A scheduler thread is in one of three states: active, transitioning to passive, or passive. Active is today's loop: steal, run actors in batches, process the mailbox. There is no sleeping state. A passive thread runs no actors and steals nothing, but it is not asleep in any sense that matters: it is alive, no other thread does anything on its behalf, and it services its own mailbox and its own allocator inbox (where other threads deposit frees of memory it owns) on a cadence. The pause between services is just a pause. Nothing wakes a passive thread. A message sent to one is read at the next service.

The cadence is the tick: it starts around 10ms and stretches toward ~500ms the longer nothing happens. The tick bounds every latency in the system: an overloaded thread gets help within a tick, quiescence probes are answered within a tick, shutdown completes within a tick.

Going passive

A thread goes passive on its own, from the same local evidence today's suspend logic reads: its idle clock has run down (no work found for long enough), its mutemap is empty (no muted actors held), and its index is not below the minimum thread count. The index check is one comparison against a constant, and it is how the minimum stays staffed with zero coordination. Scheduler 0 has one extra condition: it goes passive only while ASIO has noisy events (subscriptions like a listening socket or a pending timer that keep the program alive on their own, so it cannot finish while they exist), and is otherwise the one thread that never goes passive, the quiescence backstop.

Today, only the highest-indexed active scheduler may suspend; that rule is what keeps the active set a prefix of the array. This design drops it: blocked is blocked, at any index. That is a deliberate break from today, and it is what makes activation self-correcting below.

The transition itself is the middle state. The thread broadcasts "I'm blocked" to every scheduler, stops stealing, and finishes its run queue (empty by construction at this point in version one). It flushes its allocator debts (frees of other threads' memory it has not yet delivered to their inboxes), drains its own allocator inbox, publishes passive, and starts the cadence. The thread stays counted as blocked the whole time it is passive, which is what lets quiescence trigger while threads are passive. (One wrinkle, matching today: scheduler 0 can go passive during a noisy stretch without ever having been counted as blocked — its block gate and its passive gate have opposite polarities — and quiescence cannot start while ASIO is noisy anyway.) Today's code does the same; the comment in steal() claiming threads unblock first is wrong.

Broadcasts and the map

Block and unblock, today point-to-point messages to scheduler 0 alone, become broadcasts to every scheduler. Each scheduler keeps a private map of who is blocked, updated as it reads its own mailbox: the unblocked set is its steal list, the blocked set is its activation pool. Scheduler 0's quiescence counting becomes a tally over its own copies of the same messages; the aggregation logic is unchanged.

The maps lag each other slightly, and the lag is harmless: nothing correctness-critical reads a map, and mailbox FIFO order means a thread's "I'm unblocked" always arrives before any later consequence of it. The cost is a map per scheduler and broadcast traffic on every transition. Transitions happen at idle-clock rate, milliseconds apart, so the traffic is noise.

The global active count survives only as a gauge backing the public pony_active_schedulers(): each thread adjusts it by one at its own transitions, and nothing correctness-critical reads it.

The passive visit

Each tick, a passive thread runs a visit. It reads its mailbox to completion, under the same batch/reschedule predicate actor runs use; this is where quiescence probes get ACKed and where TERMINATE and ACTIVATE are found. It drains its allocator inbox (one load when the inbox is empty) and peeks at the head of the global inject queue: the shared queue no scheduler owns, where work lands when it comes from outside any scheduler's own run queue, ASIO events among it. Then: an ACTIVATE consumed, or work in inject, means go active; otherwise, pause again, backing off the tick.

The inject peek is the backstop that makes every race on advisory state (the maps, the gauge) harmless: work stranded in inject with nobody active is found within a tick. It is not new machinery. Today, scheduler 0 alone polls inject inside its private sleep loop while suspended; in this design every passive thread does the same, and the special case goes away.

Going active

Two triggers: asked, or noticed. Asked is an ACTIVATE message in the mailbox. Noticed is the visit finding work in inject, or, for the pinned-actor thread, work on its own queue (below). On going active, a thread broadcasts "I'm unblocked," bumps the gauge, and starts stealing; the broadcast updates every map and scheduler 0's quiescence tally. No other announcement is needed.

Activation is fully distributed. Any scheduler can activate any other; scheduler 0 has no special role in it. Activating means picking a blocked scheduler from the map, one the picker is not stealing from, and sending it ACTIVATE. Every targeting mistake is self-correcting: an ACTIVATE that lands on an already-active thread does nothing; two ACTIVATEs sent to the same target collapse in its mailbox; a thread activated for no reason finds no work, runs its idle clock down, and goes passive again on its own. A local "poked" bit per target debounces repeat sends until that target's next unblock broadcast arrives.

When to activate, the demand heuristic, is deliberately today's. A scheduler sends an ACTIVATE when, picking an actor to run, its own queue holds at least one more (depth two in hand), or when it holds muted actors (backpressure: more active threads means the overloaded receivers drain sooner). Both are purely local reads. It is a crude trigger; any momentary burst fires it. But it is today's proven behavior, and the trigger is one local predicate feeding one message, so swapping it later touches nothing else.

The ASIO thread is not a scheduler. It receives no broadcasts and holds no map. When it delivers an event and the gauge reads zero active schedulers, it sends ACTIVATE to a fixed target, scheduler 0. The choice is natural: scheduler 0 is only ever passive while ASIO has noisy events, which is exactly the situation this message exists for. A stale gauge read is covered by the inject peek.

The pinned-actor thread

The pinned-actor thread fits the model with one twist: it is the only thread whose queue other threads write; schedulers hand pinned actors over by pushing onto that queue. (I audited the rest: only the owner pushes to any queue in the scheduler array today.) So its passive visit checks its run queue, and work found there is its activation signal; no ACTIVATE message is involved.

It stays out of the map entirely: no broadcasts from it, since nobody steals from it and nobody activates it. That matches today, where it never participates in block counting; scheduler 0 counts it separately (one ACK expected beyond the scheduler roster in each quiescence round), unchanged, now answered from its mailbox on its tick. Its entire parallel copy of the suspend machinery goes away, and so does today's ugliest interaction: during a quiescence round, scheduler 0 busy-spin-wakes the pinned thread on every steal-loop iteration, solely to get the probe read. When a pinned actor's sends make ordinary actors runnable, the pinned thread ejects them to inject; if every scheduler is passive, the inject peek finds them within a tick.

One cost is accepted as the version-one starting point: a pinned actor made runnable while the pinned thread is idle waits for the thread's next tick, up to the backoff cap, where today the pushing scheduler spin-wakes it near-immediately. If the notify layer described under costs is added later, the sites that push onto this queue are the first place for it.

Quiescence and termination

The quiescence protocol is unchanged. When scheduler 0's tally shows every scheduler blocked, it probes them all (CNF) and collects their answers (ACK); it runs two clean rounds, with a check between them that ASIO activity can abort, and terminates on the second. A per-round token invalidates ACKs left over from earlier rounds, as today. The token also absorbs a thread taking work after it answered: its unblock bumps the token and the round restarts. What changes is delivery only. Passive threads answer probes from their mailbox within a tick, so the wake-the-world fan-outs, which exist solely because suspended threads never read their mail, are deleted. TERMINATE is likewise read on the tick, and blocked-while-passive accounting carries over exactly.

That leaves one thread with private wake machinery: the tracing thread, the dedicated thread that records runtime traces when tracing is compiled in. It keeps its own loop; its private wake signal and flag pair are replaced by the same timed wait every scheduler thread uses. It was never in the scheduler protocols, and it stays out of them.

What goes away

Today's suspend machinery has three platform arms: SIGUSR2 signals on Linux and the BSDs, a pthread condvar on macOS, kernel event objects on Windows. All go, and with them:

• the blocked-signal queueing, and the coupling to the standard library's signals package (users get SIGUSR2 back);
• the condvar arm's lock, its lost-signal discipline, and the marker that keeps scheduler 0 off its own lock;
• the shadow copy of the active count (lost-signal insurance) and its spin loops;
• the highest-active-only rule and the array-prefix invariant;
• the drain_requested flag and the wake-reason vocabulary added in the arena PR;
• the allocator's precise sleeping mark, its seq_cst mark/re-check protocol, the producer pins, and the retire spin; the allocator inbox goes back to a bare head pointer, because a passive thread drains it every visit and draining an empty inbox is one load;
• the wake-the-world fan-outs;
• scheduler 0's private sleep loop;
• the pinned thread's parallel suspend machinery, and the busy-spin that wakes it during quiescence rounds.

Most of the suspend-and-drain choreography in #5768 comes back out — a point in this design's favor, not against that PR: doing that work is what exposed the cost.

What this costs

• Every latency is tick-bounded: help, quiescence probes, shutdown, pinned dispatch. The worst case, at the backoff cap, is roughly half a second where today is near-immediate. The sharpest instance is the pinned thread, accepted above as the starting point. A wake-by-address notify layer — futex on Linux, WaitOnAddress on Windows, os_sync_wait_on_address on macOS (public API only, so recent macOS only), _umtx_op on FreeBSD — could later make any of these near-immediate without changing behavior. It is strictly a latency optimization, and it is not part of this design.
• Periodic servicing on an idle system costs CPU and, on battery hardware, power. The backoff shrinks the cost, and what remains lands on the longest-idle threads.
• A map per scheduler and the broadcast traffic, as above: noise at transition rates, but new memory and new messages.
• The scheduler sleep/wake path is among the most battle-tested code in the runtime, and I am replacing its foundation inside Replace the runtime allocator #5768; the runtime stress programs, systematic testing, and the thread sanitizer are the net.

Open questions

1. Tick values and the backoff curve. 10ms stretching toward 500ms is a guess; the real numbers come from measuring on the runtime stress programs and ubench.
2. The when-to-activate heuristic. Version one keeps today's, a deliberate choice. Picking a better one takes measurements, and measurements take a running implementation.
3. Systematic testing's mapping. Thread selection must span passive threads, since they do protocol work on the tick, and the timed wait maps to an always-eligible scheduling point. This needs its own derivation during implementation.
4. Steal skipping. Using the map to skip popping blocked threads' empty queues. The map exists either way, and the empty pops are nearly free; whether the skip is worth turning on is a measurement question.

The Verona precedent

There is precedent for threads that re-check the world for themselves instead of trusting the wake. Verona's entire suspend/resume synchronization surface (threadsync.h) is about 125 lines of code over a platform semaphore: a three-state lock, an intrusive waiter list, and one operation, unpause_all, that wakes every sleeper. A woken thread re-checks the world and pauses again if there is nothing to do.

The contrast that matters is the strategy. Verona keeps the no-lost-wake proof, shrunk into one auditable file. This design has no wakes to lose: a passive thread reads its mail on its own clock, and every message, every probe, and every piece of stranded work is found within a tick.

[SeanTAllen]

This was implemented.