Contention, Deadlocks, Lock-Free Structures, and Data Parallelism

relay-service removes its last data race and becomes slower. In a modeled scaling run, one worker processes 48,000 records per second; two reach 71,000; four, 73,000; eight, 61,000. The median remains acceptable while p99 latency triples. CPU utilization is high, yet profiles show workers spending much of their time in synchronization and cache-coherence traffic.

Nothing in Rust’s race-freedom guarantees promises liveness or scalable throughput. Ownership can rule out an unprotected conflicting access while every worker waits forever. A mutex can protect the correct invariant while turning eight cores into an expensive queue. A lock-free queue can guarantee system-wide progress while repeatedly starving one producer. A parallel reduction can be data-race-free while changing floating-point answers between runs.

The review question is therefore broader than “is shared access legal?” Ask whether the system continues to make useful progress, which participant may be delayed, where capacity serializes, and whether the result is stable enough for its consumers. Those are separate contracts:

• safety: forbidden states or accesses do not occur;
• liveness: required events eventually have an opportunity to occur under stated assumptions;
• progress: the algorithm promises obstruction-free, lock-free, or wait-free completion at a named scope;
• scalability: useful throughput and latency respond acceptably as workers and load change;
• determinism: permitted schedules do not change an externally significant result.

Chapter 56 supplied the ordering graph for atomic visibility. The job here is to put time, scheduling, contention, and workload shape around that graph.

The controlling decision is deliberately conservative: choose the simplest mechanism that meets the required safety, progress, result, and capacity contracts under measured load. Concurrency sophistication that cannot repay its proof and operating cost is a regression, even when its benchmark headline is faster.

A race is not necessarily a data race

A data race is a memory-model violation: conflicting unsynchronized memory accesses, with at least one write. Safe Rust prevents many such programs. A race condition is broader: correctness depends on which valid operation wins.

Consider two operators concurrently requesting a transition from Open to different terminal states. A mutex or compare-exchange can make every access legal and ensure exactly one winner. The loser still needs a product-level result. If “cancel” wins before “commit,” billing and durable storage must agree about the outcome. If the API merely returns a generic conflict, callers may retry an irreversible action. The race is safe at the memory level but incomplete at the protocol level.

Review races as state-machine questions:

1. Which outcomes are legal when operations overlap?
2. Where is the linearization or commit point, if the contract has one?
3. What does each loser observe?
4. Can retries duplicate an external effect?
5. Does cancellation mean “requested,” “won,” or “cleanup finished”?

Adding SeqCst, a mutex, or a channel does not answer these questions. Synchronization orders transitions; the domain contract assigns meaning to the order.

Deadlock is a cycle; long waiting is evidence, not a diagnosis

For ordinary exclusive resources, a useful diagnostic graph has thread-to-resource edges for “waits for” and resource-to-thread edges for “held by.” A directed cycle is a deadlock candidate: every participant in the cycle needs another participant to release something first.

The diagram is a snapshot model, not a universal detector. Reader/writer locks have modes, condition variables temporarily release a mutex, channels wait on capacity or lifecycle, and callbacks can acquire resources not visible at the call site. Distributed waits add leases, network loss, and partial failure. A useful production graph names the resource mode and the operation holding or requesting it.

The classic two-lock failure is short:

// Path A: accounts -> journal
let accounts = accounts.lock().unwrap();
let journal = journal.lock().unwrap();

// Path B elsewhere: journal -> accounts
let journal = journal.lock().unwrap();
let accounts = accounts.lock().unwrap();

The code may run for months before timing aligns. Testing the absence of a hang cannot prove acyclicity. The scalable repair is usually a global partial order: assign every lock class or stable key an order and require all paths, including error recovery and destructors, to acquire in that order. When a callback can acquire an unknown lock, invoke it after releasing internal guards. When two independently owned subsystems cannot share an ordering discipline, move the cross-system operation into a message protocol or coordinator rather than nesting their locks.

Self-deadlock deserves explicit treatment. The standard mutex API does not promise a portable outcome when a thread locks a mutex it already holds; a second call may deadlock or panic. “It worked with a recursive mutex elsewhere” is not a Rust contract. Reentrant designs also make invariants harder because callbacks observe partially completed transitions. Prefer completing a protected transition before calling outward.

Livelock, starvation, and priority inversion fail differently

In livelock, participants run but repeatedly invalidate one another’s attempts. Two optimistic workers can both detect a conflict, back off identically, and collide again. A compare-exchange loop that continually loses is active but makes no local progress. Randomized or asymmetric backoff may help, but a bounded retry followed by a queued or locked slow path is easier to operate.

In starvation, the system makes progress while a particular participant does not. A lock-free algorithm allows this by definition: system-wide progress is not per-thread completion. Unfair scheduling, a hot shard, continual high-priority traffic, or readers that indefinitely delay a writer can all starve work. Rust’s standard synchronization APIs do not give a blanket fairness guarantee. If a deadline or tenant fairness matters, the design needs admission, queuing, quotas, or a documented scheduler property—not hope attached to a primitive name.

Priority inversion occurs when high-priority work waits for a resource held by lower-priority work that cannot run promptly, perhaps because medium-priority work consumes the CPU. It is a scheduler-and-resource interaction. Shortening the critical section helps but may not solve inversion. Platform priority inheritance, eliminating cross-priority sharing, ownership transfer to a dedicated worker, or priority-aware queues are possible remedies. Each depends on operating-system and runtime behavior outside Rust’s type system.

A timeout changes an infinite wait into a reported failure; it does not restore the half-completed operation. Every timeout needs a postcondition: was no change made, did the operation continue elsewhere, or must the caller reconcile? Timeouts without state and ownership semantics turn a liveness defect into duplication or corruption.

Measure queues around locks, not just code inside them

Contention is competition for a serial resource. It can occur at a mutex, an atomic cache line, an allocator, a bounded queue, a disk, a connection pool, or one executor worker. A low average guard hold time can coexist with a large aggregate wait if acquisition frequency is high. Conversely, a rare long hold may dominate p99 but barely affect throughput.

Instrument at least:

• acquisition count, total and distribution of wait time, and hold-time distribution;
• failed try_lock or CAS retries where those operations are meaningful;
• queue depth, enqueue delay, rejection, and service time;
• throughput and latency by worker count and offered load;
• per-shard traffic, not only the aggregate;
• CPU topology, affinity, build profile, target, toolchain, and workload version.

A compact heat map makes imbalance visible. This simulated sample is teaching data, not a benchmark result. Bars are normalized within each column; they do not compare milliseconds with counts.

Wait and hold instrumentation itself costs time and can perturb scheduling. Sample when necessary, keep clocks and aggregation out of the protected interval, and record the instrumentation mode with the result. A profiler that attributes time to Mutex::lock shows a symptom; it does not identify which invariant forced the lock or which key caused skew.

Scaling curves need a baseline. Compare one worker with N workers, but also compare the same total offered load with increasing concurrency and increasing load with fixed concurrency. Throughput saturation, latency blow-up, and fairness can appear at different points. Speedup should be judged against total work, not CPU utilization: retries and coherence traffic are busy work.

Striping changes one invariant into many

Lock striping or sharding maps keys onto multiple protected partitions. It reduces competition only when traffic spreads and operations usually touch one shard. The mapping function becomes part of the capacity model. A tenant with most traffic on one key still serializes, as the heat map shows.

Sharding introduces questions a single mutex avoided:

• Is an observation across shards allowed to be non-atomic?
• How are multi-key operations ordered?
• Can resharding preserve ownership and availability?
• Does a malicious or accidental key distribution create a hotspot?
• How are per-shard queue and wait metrics exposed?

The fixture’s ShardedCounter documents its snapshot as approximate because it locks and sums shards separately. That is adequate for an observation metric, not for deciding that every job has completed. If the consumer needs a coherent total, serialize the snapshot, maintain a different authoritative representation, or use a versioned protocol with a justified retry and wrap argument.

Multi-shard operations must acquire shards in a stable order derived from shard identifiers, not request order. Deduplicate identifiers before locking so the same shard is not acquired twice. If operations commonly span most shards, striping has preserved complexity while restoring global serialization; that is a simplification signal.

Read-copy-update is a lifecycle design, not a fast read trick

Read-copy-update (RCU) concepts separate readers from mutation: readers access a published version while writers construct and publish a replacement, then reclaim old versions only after no relevant reader can retain them. The appealing part is the read path. The hard part is reclamation.

An Arc-published immutable snapshot can provide a practical safe-Rust form of version lifetime: readers clone ownership, and the old value is dropped after the last clone. Publication still needs a synchronized container, and high-frequency Arc cloning creates reference-count traffic. Epoch or hazard-pointer schemes can reduce different costs but expand the proof to reader registration, quiescent states, thread failure, ABA, memory growth, and shutdown. They are established algorithms to obtain from a reviewed implementation, not a short unsafe recipe to invent during a latency incident.

RCU-style publication also changes semantics. Readers may observe different versions concurrently. A configuration read can often tolerate that; a debit spanning account and limit snapshots may not. State the consistency window and reclamation bound before comparing speed.

Lock-free names a progress guarantee, not a performance tier

Progress terminology should be used narrowly:

• obstruction-free: one operation completes if it eventually runs without interference;
• lock-free: in an infinite execution, the system as a whole continues completing operations under the algorithm’s assumptions;
• wait-free: each operation completes in a bounded number of its own steps under the stated model.

These properties say neither fair nor low-latency. A lock-free stack can funnel every writer through one cache line, spend most cycles retrying, and starve one thread. A well-implemented mutex can outperform it under moderate contention by parking losers and handing execution to a useful owner. Conversely, a mutex may be unacceptable in an interrupt context or a hard progress domain. The requirement must come from the environment.

Memory reclamation is part of the algorithm. Removing a node from a lock-free structure does not prove that no reader still holds its address. ABA occurs when a location changes from A to B and back to a value that appears to be A while its identity or generation has changed. Tags consume finite bits and wrap; reference counting, epochs, and hazard pointers have distinct progress and memory-retention trade-offs. If a review says “the CAS succeeded, so free it,” the safety case is incomplete.

Do not expose a public type as “lock-free” merely because a target currently lowers an atomic operation to one instruction. The claim belongs to the complete algorithm, target availability, fallback behavior, allocator interaction, and reclamation path.

Work stealing balances unknown work and complicates observation

Static partitioning gives each worker a fixed range. It is excellent when item costs are predictable and locality matters. It performs poorly when one partition contains most expensive items. A work-stealing scheduler gives workers local queues and lets idle workers take tasks from others, improving utilization for irregular divide-and-conquer work.

Stealing is not free. Tasks have scheduling overhead; tiny tasks spend more time moving than computing. Steals can harm cache locality. Nested parallelism can oversubscribe other thread pools. Blocking inside a worker may strand capacity unless the library has a documented compensation mechanism. Thread-local assumptions become fragile because a logical operation may execute on different workers.

Rayon’s documented scheduler uses local deques and stealing, and its parallel iterators split work dynamically. That is an ecosystem contract for the reviewed version, not a language guarantee. Prefer high-level parallel operations when their semantics fit, isolate the pool when resource ownership requires it, and record crate versions. Do not depend on a particular steal order for correctness.

Granularity is a measured design parameter. Set a sequential cutoff for recursive algorithms; batch cheap items; keep blocking I/O out of a CPU pool; and test with skewed, empty, tiny, and oversized inputs. A parallel path should retain a cheap sequential fallback because one core, small input, constrained containers, and oversubscribed hosts are normal production cases.

Deterministic reduction requires algebra and policy

Parallel map is often straightforward because each input produces an independent output. Reduction combines partial results in an order chosen by partitioning and scheduling. The combine operation must have an identity and be associative for arbitrary tree reduction to preserve the mathematical answer. Commutativity is additionally useful when input order is not fixed.

Machine arithmetic complicates the algebra. Unsigned wrapping addition is associative modulo the integer width, but checked addition can report overflow at a different partial combination. Floating-point addition is not associative: rounding means (a + b) + c can differ from a + (b + c). String concatenation is associative but order-sensitive. “The type implements Sum” is not a determinism proof.

Choose a result contract:

• exact integer accumulation in a wider checked type;
• reproducible fixed partitioning and ordered combination;
• compensated or pairwise floating-point summation with a documented error bound;
• nondeterministic result within an accepted tolerance;
• stable item ordering after parallel computation.

The fixture uses scoped threads to square indexed chunks and stores each partial in its input slot. It then combines slots in chunk order with checked u128 arithmetic. This teaches ownership and reproducibility, not optimal scheduling:

pub fn deterministic_sum_of_squares(values: &[u32], workers: usize) -> Option<u128> {
    let workers = workers.max(1).min(values.len());
    let chunk_len = values.len().div_ceil(workers);
    let mut partials = vec![None; values.len().div_ceil(chunk_len)];

    std::thread::scope(|scope| {
        for (chunk, slot) in values.chunks(chunk_len).zip(&mut partials) {
            scope.spawn(move || {
                *slot = chunk.iter().try_fold(0_u128, |sum, value| {
                    let value = u128::from(*value);
                    sum.checked_add(value * value)
                });
            });
        }
    });

    partials.into_iter()
        .try_fold(0_u128, |sum, part| sum.checked_add(part?))
}

Production code must define empty-input behavior, panic propagation, cancellation, memory overhead, worker ownership, and the maximum input before allocating partials. A general pool or parallel iterator usually schedules better than spawning threads per call, but the library’s reduction-order contract still matters.

Test concurrency by separating claims

No single test proves concurrency correctness and performance. Use evidence lanes:

1. State and ordering argument: legal transitions, protected invariants, wait-for ordering, and happens-before edges.
2. Deterministic unit tests: barriers and channels arrange specific transitions without sleeps; tests assert outcomes and cleanup.
3. State-space exploration: a suitable concurrency model explores small interleavings; record modeled primitives and omissions.
4. Stress and fault injection: varied scheduling, worker failure, cancellation, queue saturation, and long runs find integration defects but cannot prove their absence.
5. Performance experiments: scaling, latency distributions, fairness, retries, cache traffic, and memory use under a recorded workload.

Deadlock tests need an external deadline so the test harness does not wait forever, but the deadline is only a detector. Model lock ordering directly where possible. Livelock tests should bound retries and assert fallback. Starvation tests need per-participant completion distributions, not aggregate throughput. Parallel results should be compared across worker counts and repeated schedules.

The file-backed lab contains four deterministic tests: a directed wait cycle, an acyclic graph, synchronized sharded updates, and worker-count-independent checked reduction. It deliberately contains no benchmark result. Numbers in a handbook cannot replace measurements on the reader’s workload and hardware.

Return to the stalled service

relay-service parses CPU-heavy records, updates per-tenant accounting, and emits accepted batches. Its first design question is not which concurrency primitive wins in the abstract, but where independence ends.

One mutex around the registry keeps the accounting transition coherent and recovery legible. It remains the baseline until wait and hold distributions, a call-path audit, and a scaling curve show that registry serialization—not parsing or output—is the binding limit. A bounded owner channel preserves one state owner while making overload and lifecycle explicit. It trades lock queues for a visible application queue, so the review must follow queue age, service time, request/reply cancellation, and shutdown all the way through.

Sharding the registry permits independent tenants to advance concurrently, but only if key traffic spreads and cross-tenant operations are rare. The evidence is therefore per-shard: key skew, heat, snapshot semantics, and a stable order for operations that touch more than one shard. Parallel parsing with a serialized commit draws the boundary elsewhere. Dynamic scheduling can balance expensive records while one owner preserves the accounting transition, but the cutoff, reduction policy, pool occupancy, and commit capacity must show that task overhead and pool interference do not recreate the bottleneck upstream.

A lock-free registry is not automatically a fifth and better design. It becomes a candidate only if the environment needs its progress property and the team can defend memory reclamation, fairness, portability, and maintenance. For this workload, parallel pure computation feeding one bounded, observable commit owner is the most credible next experiment: it spends concurrency where records are independent and keeps the irreversible transition legible.

The simplification threshold has been crossed when the proof, fallback, or instrumentation costs more than the measured bottleneck justifies. Remove parallelism when inputs are too small. Collapse shards when cross-shard invariants dominate. Replace retry loops with a mutex when progress is not special. Replace nested locks with ownership transfer when teams cannot sustain a global order.

Exercise: produce a liveness and scalability decision record

Given the relay-service workload above, produce an evidence-backed review of the mutex, bounded-channel, sharded, and parallel-iterator designs.

Your deliverable must contain:

1. one state account separating memory safety, domain races, and lifecycle outcomes;
2. a resource inventory and wait-for graph including locks, channel capacity, worker-pool slots, and shutdown joins;
3. an explicit lock/shard order and the callback or destructor paths that might violate it;
4. a contention heat map with wait, hold, acquisitions, p50/p95/p99, key skew, and queue age;
5. a progress statement for every retry loop, including starvation and fallback behavior;
6. a reclamation argument for any lock-free node; “CAS won” is not sufficient;
7. a reduction contract covering identity, associativity, overflow, floating-point tolerance, and output ordering;
8. a test plan separating model, deterministic orchestration, stress, faults, and performance;
9. scaling results at 1, 2, 4, 8, and 16 workers with fixed-load and increasing-load runs;
10. a decision naming the simplest design that meets the target and the evidence that would trigger reconsideration.

Reject a report that compares unbounded queues with bounded locks under different workloads, cites CPU utilization alone, or calls a structure lock-free without naming its algorithm and reclamation scheme. The conclusion may legitimately select one mutex. Sophistication is matching mechanism to contract, not maximizing concurrency vocabulary.

Part IX began with the question of which values can cross a thread boundary and ends with a stricter conclusion: legal sharing is only the first gate. The eight-worker result is not a demand for a more ingenious primitive. It is evidence that useful work has given way to waiting, retries, or coherence traffic. The next design must expose that queue, preserve the accounting result, and justify every new progress claim with the workload that needs it.

Part X changes the unit of scheduling from an OS thread to an async task. The same liveness discipline remains, but waiting becomes Pending, progress depends on wake, and a stalled participant may now occupy an executor rather than an operating-system thread.

Sources and version note

Mutex behavior and the lack of a portable recursive-lock outcome follow the current std::sync::Mutex documentation. Scoped partitioning follows std::thread::scope. Work-stealing and parallel-reduction statements are ecosystem behavior documented for Rayon 1.12.0 and its ParallelIterator::reduce; they are not Rust language guarantees. The fixture is dependency-free safe Rust 2024, targeted at Rust 1.97.0 with Rust 1.85.0 as MSRV. Scheduler fairness, mutex implementation, cache topology, and performance numbers remain platform- and workload-sensitive.