Concurrency

Concurrency

Locks, isolation, and the bugs that only show up in production.

• Atomics, Memory Ordering & Lock-Free

  6 studies
  1. 1.Atomics, Memory Ordering & Lock-Free — Races, Barriers & When Locks WinInterview map for process-local concurrency: data races versus race conditions, atomics and CAS, memory orders, lock-free structures and ABA, and when a mutex still wins.
  2. 2.Data Races & Happens-Before — UB, Tools & Mental ModelsA data race is conflicting access with no happens-before edge. C++ and Rust call that undefined behavior. This page is the definition, the edges, and the tools that catch it.
  3. 3.Atomic Operations & CAS Loops — Progress GuaranteesAtomics are indivisible read-modify-write on one word. CAS loops build lock-free algorithms and accidental spinlocks. This page is the operations, the retry shape, and the progress words.
  4. 4.Memory Ordering — Relaxed, Acquire/Release, SeqCstAtomicity stops a torn word. Memory order controls which other accesses may move around that word. Relaxed, acquire/release, and seq_cst are the ladder, and a publish flag is the pattern to know.
  5. 5.Lock-Free Structures — Queues, Stacks & ABALock-free structures use CAS so some thread always makes progress. The teaching cases are the Treiber stack, the Michael-Scott queue, and an SPSC ring. ABA and reclamation are the part people skip.
  6. 6.When Locks Win — Contention, Fairness & Hybrid DesignsA short mutex often beats a CAS storm on one cache line. Locks cover multi-field invariants, fairness, and review. This page is when to keep them, when to shard, and when a hybrid is honest.

• Concurrency

  6 studies
  1. 1.Mutexes, Condition Variables, Deadlocks & Happens-BeforeMutex HB; CV while-loop (Mesa); Coffman + lock ordering; atomics ≠ compound atomicity; locks vs lock-free.
  2. 2.Mutex vs RWLockA mutex gives one thread exclusive access. An RWLock (shared mutex) lets many readers in at once or one writer. Reach for an RWLock only when reads far outnumber writes and each read section does real work (I/O, parsing, a long scan), so readers actually overlap. For short critical sections a plain mutex is usually faster: every RWLock reader still does an atomic update on the shared reader count, and that cache line ping-pongs between cores. Default to a mutex and measure before switching.
  3. 3.Condition Variables: Mesa vs HoareA condition variable lets a thread sleep until a predicate on shared state becomes true, always paired with the mutex that guards that state. Under Hoare semantics, signal hands the mutex straight to the woken waiter, so the predicate is guaranteed true when it runs. Under Mesa semantics (pthreads, Java, C++, Go, Rust, Python), signal is only a hint: the signaler keeps running, the waiter re-acquires the mutex later, and by then the predicate may be false again. So always wait in a while loop, never an if.
  4. 4.Deadlock Prevention & AvoidanceDeadlock needs Coffman’s four — mutual exclusion, hold-and-wait, no preemption, circular wait. Production systems break circular wait with lock ordering, avoid hold-and-wait with try-lock + backoff, or redesign with channels / actors so resources are not multi-locked.
  5. 5.Happens-Before & Memory VisibilityHappens-before (≺) is the relation that makes writes visible and ordered across threads. Mutex unlock ≺ later lock; volatile/atomic stores synchronize with later loads; thread start/join create edges. Without a happens-before edge, seeing stale/torn values is allowed.
  6. 6.Atomics vs LocksA lock protects an invariant that spans several fields and makes waiters block. An atomic does one read-modify-write on one machine word (load, store, fetch_add, compare-and-swap) without blocking anyone. Use atomics for single-word counters, flags and published pointers; use a lock as soon as two fields must change together, because making each field atomic does not make the group atomic. Neither removes contention on one hot word: atomics fail by retrying while the cache line bounces, locks fail by queueing.

• Distributed locks

  6 studies
  1. 1.Distributed Locks — Correctness, Leases & Fencing TokensDistributed locks need mutual exclusion, crash safety via leases, and fencing so stale holders cannot corrupt shared state. Prefer CAS/queues when you do not need a multi-step exclusive critical section.
  2. 2.Redis SET NX EX vs Redlock — Single-Instance Safety & the Kleppmann DebateAtomic SET NX EX is best-effort on one Redis; Redlock’s majority story is contested (Kleppmann). Use single Redis + fencing for soft work; etcd/ZK/DB CAS for correctness-critical paths.
  3. 3.ZooKeeper / etcd Lock Recipes — Ephemeral Nodes, Sessions & WatchesConsensus locks use ephemeral/lease-bound keys, sequential recipes, and watches; session timeout is the fence boundary. Prefer Curator / etcd concurrency APIs over hand-rolled nodes.
  4. 4.Fencing Tokens — Stopping Stale Lock Holders After PartitionA monotonic fencing token must be checked by storage; without it, TTL/lease locks are unsafe after GC pauses or partitions.
  5. 5.Lease Renewal, Clock Skew & Heartbeat Failure ModesRenew on monotonic timers; on renew failure stop writing immediately. Clock skew and GC pauses force lease-length tradeoffs—pair renewals with fencing.
  6. 6.Compare-And-Swap & Optimistic Coordination — When You Do Not Need a LockConditional writes (DynamoDB, etcd Txn, Redis WATCH, Postgres version columns) beat distributed locks under low contention; watch ABA and retry storms.