Synchronization Primitives

A monitor is a lock protecting shared state plus a condition variable to wait on. The consumer locks, and while the queue is empty calls wait, which atomically releases the lock and sleeps. A producer adds an item under the lock and signals. Polling wastes CPU and adds latency; waiting costs nothing until woken.

At most one thread holds a given mutex, so critical sections guarded by that same lock never overlap, and a holder's writes become visible to the next holder. It promises nothing about acquisition order, fairness, deadlock freedom, or data guarded by another lock.

It has two modes: many threads may hold it in shared (read) mode at once, but exclusive (write) mode admits one holder and excludes all readers. It only beats a plain mutex when reads greatly outnumber writes and critical sections are long enough to repay its higher bookkeeping cost.

A semaphore is a counter of permits with two atomic operations: acquire, which takes a permit and blocks while none are free, and release, which returns one. A counting semaphore starts with N permits; a binary semaphore holds at most one.

A latch has separate roles — workers count down, a different thread waits — and is one-shot: zero is permanent. A barrier is symmetric and reusable: every participant calls await, all block until the Nth arrives, then all resume and the barrier re-arms. An iterative simulation needs the barrier.

Waking means "the state may have changed", not "your condition is true". Another thread can consume the state between the signal and your re-acquiring the lock, one condition may serve several predicates, and spurious wakeups are permitted. So: while (not predicate) wait — never if.

Under reader preference, new readers join while readers are already inside, so if reads arrive faster than they finish the reader count never reaches zero and a waiting writer never runs. Writer-preference blocks arriving readers once a writer is queued; fair or phase-fair policies queue both by arrival and alternate between them.

A mutex has an owner: only the thread that locked it may unlock it, which enables reentrancy, priority inheritance and error detection. A semaphore is an ownerless permit counter, so any thread may release. That makes it a signal, not a lock.

A spinlock makes a waiting thread loop on an atomic test until the lock frees, keeping its CPU and never involving the scheduler. A blocking lock parks the thread so the CPU runs something else, paying a context switch on both sleep and wake.

The rendezvous tags each round with a generation number; a released thread that loops back is recorded against the next generation, so its arrival can never be mistaken for a late arrival in the old one. The swap runs as the barrier action: once, on the thread that completes the round, after all have arrived and before any is released.

Waking one is safe only when every waiter on that condition waits for the same predicate and one unit of state satisfies exactly one waiter. Otherwise wake all: the single wake-up can reach a thread whose predicate is false, which consumes it and leaves the right thread asleep. Waking all is always correct but costs a thundering herd.

A reentrant lock lets the thread that already holds it acquire it again, tracking a hold count and only freeing the lock when the count returns to zero. A non-reentrant lock self-deadlocks on the second acquire. Reentrancy eases recursion and callbacks but lets code re-enter a critical section while invariants are broken.

Use three: an "empty slots" semaphore starting at capacity, a "filled slots" semaphore starting at zero, and a mutual-exclusion semaphore or lock for the buffer itself. Producers acquire empty then the lock; consumers acquire filled then the lock. Acquiring the lock first deadlocks.

Spin when the expected remaining hold time is shorter than the round trip of parking and waking, and when a spare core exists so the holder can still run. Long, unpredictable or blocking critical sections, and oversubscribed CPUs, favour parking.

The rendezvous can never complete, so leaving the others blocked is a permanent, silent hang. The barrier is marked broken and all current and future waiters fail immediately with a distinct error, so failure propagates to every participant instead of one loud error plus N−1 stuck threads.

A signal is not stored: if it fires when nobody is in the wait set, it vanishes. If the producer changes state and signals in the window after the waiter tests its predicate but before it is registered as waiting, the waiter sleeps forever. Prevention: test the predicate and wait under the same mutex that the producer holds while changing state and signalling.

A fair lock grants ownership in arrival order via a queue; an unfair lock lets a running thread barge in and take a just-released lock ahead of queued waiters. Barging gives much higher throughput because it avoids wake-up handoff gaps, at the price of a long starvation tail. Fairness pays when hold times are long and tail latency matters.

They bound how long you wait: the attempt returns success or failure instead of blocking indefinitely, so you can take a fallback path, stay responsive, or release locks you already hold and retry. The risks are livelock from lockstep retries and code that ignores the failure branch.

The reader takes no lock: it records a version counter, reads the data, then re-reads the counter. If it changed, or was odd (a write in progress), the read is discarded and retried. Readers must therefore tolerate momentarily inconsistent data — no side effects, no dereferencing possibly-freed pointers, no unbounded work before validation.

If two readers both try to upgrade, each waits for the other to release its shared hold, so neither can ever get exclusive mode — a deadlock with no cycle of distinct locks. Downgrading is safe because the holder already excludes everyone and simply relaxes. Restructure by releasing, re-acquiring exclusively, and re-validating, or by using a single-holder upgradeable mode.

Permit leaks on error paths (always release in a finally/defer), double releases that silently raise the cap, unbounded waiting instead of a timeout plus rejection, an unbounded queue of waiters hiding the overload, starvation under barging, and forgetting the cap is per instance, not global.

An atomic write takes the cache line exclusively, so hammering it makes every spinner steal the line from the holder and each other. Reading first (test-and-test-and-set) spins on a shared copy; backoff and adaptive limits cut the remaining traffic and stop pointless spinning.

The lock state is an ordinary word in user memory, so an uncontended acquire is one atomic compare-and-swap — a few nanoseconds, no kernel. Only when a thread must actually wait does it make a wait system call naming that address; the kernel queues it and the releaser wakes it.

Coarse locking is one lock for a whole structure: simple, but it serializes everything. Fine-grained locking splits protection into independent locks — striping hashes keys onto N locks — raising parallelism but adding multi-lock complexity and deadlock risk. A convoy forms when a holder is descheduled or blocks while holding, waiters pile up, and threads then advance in lockstep, collapsing throughput.

Measure first: read/write ratio, critical-section length, and core count. Mode separation only pays if reads dominate and sections are long enough to amortise the reader bookkeeping. Otherwise weigh a plain mutex, an immutable snapshot swapped atomically, sharded state, per-thread state with aggregation, or optimistic validated reads.

Start from Little's law: in-flight = throughput x latency. Pick the throughput you must sustain, multiply by measured service time, then check the number against the dependency's own capacity budget divided across replicas, and keep utilisation below saturation. Then measure and adjust.

Spinning assumes the lock holder is running in parallel. Under oversubscription the holder gets preempted, so spinners burn whole scheduling quanta waiting for a thread that cannot run — wasting the very CPU it needs. Fix by bounding spins and parking, or by not oversubscribing.

Under Hoare semantics the woken thread runs with the predicate still guaranteed true, so a single if would suffice — but it needs an extra context switch and lock handoff. Mesa semantics let the signaller continue, so the predicate can be falsified before the waiter runs, forcing a while loop. Every mainstream platform is Mesa. Signalling inside versus just after the critical section is a performance choice, not a correctness one — provided the state change happened under the lock.

Each step costs the slowest worker, not the average, so per-step time tracks the maximum of N samples and grows as N and variance grow. The rendezvous itself is serial work, capping speedup by Amdahl's law. Restructure toward pipelining, work-stealing, or asynchronous/relaxed-consistency iteration when stragglers dominate.