Cairn
guides · cross-cutting lens, not tied to one category

↩ back to Guides

Busy-Waiting vs. Blocking

This site's eleven Concurrency entries split into two families by how a process behaves while it can't yet proceed, with four entries straddling the line. Peterson's, Dekker's, and Lamport's bakery algorithm spin on a shared flag; Dining Philosophers and Readers-Writers retry a failed admission check the same way, just over forks or a reader/writer count instead of a flag. All five are busy-waiting in the strict sense this page measures: always runnable, always burning CPU while it waits. The Treiber Stack's, the Michael-Scott Queue's, Hazard Pointers', and Epoch-Based Reclamation's own compare-and-swap retry loops never block either, so by that same CPU-cost test they count as busy-waiting too — but none of the four spins on an unmet condition the way the other five do; each only retries after actually losing a race, and (per each page's own Complexity section) none of them ever holds anything the way a lock is held, so none can suffer the specific preemption pathology measured below. The Producer-Consumer Problem is the one page built on something else entirely: Dijkstra's counting semaphore, which blocks — it takes the waiting process off the scheduler entirely until another process wakes it. That page's own intro names the busy-waiting/blocking split among the six entries that existed before the Treiber Stack, but never measures what it actually costs to be on the wrong side of it. This page does, with a real two-thread benchmark, then shows the one property a browser demo can still make visible even though it can't literally block its own UI thread the way the benchmark blocks a real OS thread.

Two ways to wait

Busy-waiting means checking a condition in a loop: read the shared flag, and if it's not yet what you need, read it again, immediately, with no gap. The scheduler has no way to tell this apart from real work — the process is runnable the entire time, and on whatever core it's assigned to, it gets scheduled time the identical way a process doing useful computation would. This is exactly what Peterson's, Dekker's, and Lamport's bakery algorithm do on their own shared flags, and it's what Dining Philosophers and Readers-Writers do too, one level up: a failed fork pickup or a failed admission check just returns, and the calling process tries again — Dining Philosophers' own acquire function literally comments // blocked — try again later at that exact check, which is polling, not an OS-level suspend.

Blocking means telling the scheduler the opposite: take this process off the run queue completely, and don't schedule it again until something specific happens. This is the primitive Dijkstra built the semaphore to support — wait() on an empty semaphore doesn't loop, it suspends, and signal() is what wakes the suspended process back up. Producer-Consumer's waitEmpty and waitFull are exactly this: a producer that finds the buffer full isn't spinning on a check, it has been removed from the scheduler's attention until a consumer's own signal() puts it back.

What it actually costs: CPU, not just time

Both styles of waiting take roughly the same wall-clock time to notice a wakeup. They do not cost the same amount of CPU. A real benchmark makes the gap exact: two Node worker_threads, sharing one Int32Array flag over a SharedArrayBuffer. One worker busy-waits — a tight loop re-reading the flag with Atomics.load, never sleeping. The other blocks for real, with Atomics.wait — an actual OS-level suspend, not JavaScript pretending to suspend. The main thread lets each run for a fixed window, then flips the flag; each worker reports its own process.cpuUsage() for the time it spent waiting. Three real wait windows, three trials each:

wall-clock waitspin: CPU usedblock: CPU usedratio
~70ms~70.0ms~0.23ms~300x
~972ms~972.1ms~0.29ms~3,350x
~2,972ms~2,970.5ms~0.37ms~8,000x

The pattern isn't just "spinning uses more CPU," it's why the gap keeps widening rather than holding at some fixed multiple. A spinning worker's CPU time tracks its wall-clock wait almost exactly 1:1 — it never once stops working, so the two numbers are nearly the same number measured two ways. A blocked worker's CPU time barely moves between a 70ms wait and a 3-second one, because that tiny cost isn't the waiting at all — it's the one-time overhead of actually being suspended and woken, paid once regardless of how long the suspension lasts. Multiply a cost that scales with duration against a cost that doesn't, and the ratio between them is just the duration, rescaled.

Try it

The benchmark above blocks a real OS thread, which a browser deliberately won't let this page do to its own UI thread — Atomics.wait is disallowed outside a worker, specifically so a page can't freeze itself that way. The demo below can't reproduce the literal mechanism, but it can reproduce the one consequence that actually matters here: does the waiter consume the thread's own attention while nothing has changed? Spin-wait runs a real busy-loop on this page's own JavaScript thread for one second — watch the heartbeat counter below stop advancing for the full second, and try clicking Ping while it's spinning. Yield-wait waits the same one second with setTimeout instead, handing control back to the browser immediately; the heartbeat keeps ticking right through it, and Ping answers at once.

heartbeat: 0
Click Spin-wait, watch the heartbeat freeze, then try Ping mid-freeze — it queues but can't run until the loop returns. Click Yield-wait and try Ping again — it answers immediately.

Which of the site's own eleven entries uses which

entrywait stylewhat the waiting process does
Peterson's algorithmbusy-waitspins re-reading the other process's flag and turn
Dekker's algorithmbusy-waitspins, backing off and retrying on turn
Lamport's bakery algorithmbusy-waitspins comparing tickets against every other process
Dining Philosophersbusy-waitretries a failed two-fork pickup from scratch
Readers-Writersbusy-waitretries a failed admission check
Treiber Stackbusy-retry (CAS)retries push/pop's compare-and-swap after losing a race — never spins on an unmet condition, never holds anything to be preempted out of
Michael-Scott Queuebusy-retry (CAS)retries enqueue/dequeue's compare-and-swap after losing a race, same as the Treiber Stack — now over two independently-raced pointers instead of one
Hazard Pointersbusy-retry (CAS)retries the Treiber Stack's own pop loop after a failed re-validation, plus one bounded hazard-array scan per successful retire — no unmet condition to spin on, nothing held across a preemption
Epoch-Based Reclamationbusy-retry (CAS)retries the Treiber Stack's own pop loop the identical way, plus a bounded pin/unpin pair and a straggler check per successful retire — no unmet condition to spin on, nothing held across a preemption
Harris Linked Listbusy-retry (CAS)retries insert's link CAS or delete's mark/unlink CAS after losing a race — no unmet condition to spin on, nothing held across a preemption
Producer-Consumerblockingsuspends on a counting semaphore until signaled

Pitfalls

The literal 0.2–0.4ms figure above is this one benchmark's own constant, not a universal one. It's the overhead of Node's worker-thread scheduler suspending and waking a thread, not a kernel-level futex measurement — real OS block/wake costs on Linux are typically in the low microseconds, smaller than what's measured here by roughly two more orders of magnitude. What generalizes is the shape: spin cost scales with wait length, block cost doesn't. The exact constant is specific to this VM and this runtime.

A spinning waiter only wastes its own core if there's a free core to waste it on. This VM has 2 cores. A third thread that wants to spin has to share a core with something else, and the OS can only reclaim a spinning thread's slice at the next scheduler timer tick — not the instant it has nothing useful left to do, the way a blocked thread's slice is reclaimed immediately on the syscall that blocks it. A busy-waiter can measurably delay unrelated work sharing its core; a blocked one never costs anyone else anything.

None of this makes busy-waiting simply wrong. When the expected wait is shorter than the cost of actually suspending and rewaking a thread — the block side's own constant overhead, measured above — a brief spin can cost less than blocking would, which is exactly why real OS kernels still use spinlocks for their own shortest internal critical sections. Where that crossover actually sits isn't something this page's own benchmark can measure honestly: worker-thread creation overhead swamped every wait window tried below roughly 70ms in testing here, so the crossover is stated as the standard structural reason real systems reach for both tools, not as a number this page verified itself.