Saltar a contenido

Week 10 - Channels, Lock-Free Patterns, and loom

10.1 Conceptual Core

  • Channel taxonomy:
  • MPSC (multi-producer, single-consumer): std::sync::mpsc, crossbeam_channel, tokio::sync::mpsc.
  • SPSC (single-producer, single-consumer): rtrb, ringbuf. Lock-free, often wait-free.
  • MPMC: crossbeam_channel, flume. Generally lock-free with backoff.
  • Broadcast: tokio::sync::broadcast. Many readers, lossy if slow.
  • Watch: tokio::sync::watch. Single-value, last-write-wins.
  • Lock-free vs wait-free:
  • Lock-free: at least one thread makes progress at any time.
  • Wait-free: every thread completes in bounded steps. Wait-free is much harder; most real-world "lock-free" code is lock-free, not wait-free.
  • The ABA problem: a CAS that compares a pointer can succeed even though the pointer was freed and re-allocated to the same address. Solutions: hazard pointers, epoch-based reclamation (crossbeam-epoch), or tagged pointers.

10.2 Mechanical Detail

  • crossbeam-epoch for safe lock-free memory reclamation. Read its source.
  • Loom: a model checker that exhaustively explores thread interleavings of programs written against its loom::sync::* shims. Used by Tokio and others to validate concurrent data structures. Read the loom user guide and the tokio test suite.
  • Cache effects: false sharing. Pad hot atomics to 64 bytes (or 128 on Apple Silicon) with crossbeam_utils::CachePadded.
  • Backoff strategies: exponential with jitter, then thread::yield_now(), then park. Read crossbeam_utils::Backoff.

10.3 Lab-"An SPSC Ring Buffer"

Implement a fixed-capacity SPSC ring buffer: - Two AtomicUsize indices (head, tail), each on its own cache line. - push and pop use Acquire/Release ordering pairs. - Validate under loom with at least 4 elements and 3 pushes/pops. - Benchmark against rtrb with criterion. You should be within 2× on x86_64.

10.4 Idiomatic & Clippy Drill

  • clippy::needless_lifetimes, clippy::missing_const_for_fn. Note that lock-free primitives often cannot be const fn due to atomic init constraints-explain when.

10.5 Production Hardening Slice

  • Add RUSTFLAGS="-Z sanitizer=thread" (nightly) to a CI job. Run your SPSC tests under TSan in addition to Loom. The two catch overlapping but distinct classes of bugs.

Comments