Concurrency And Synchronization

What's being tested

Interviewers probe your ability to build correct, performant, and maintainable concurrent code: safe access to shared state under contention, choice of synchronization primitives, and reasoning about liveness (deadlock/starvation) and memory visibility. At Hudson River Trading, low-latency and high-throughput constraints make tradeoffs between simple correctness (coarse locks) and scalable designs (sharding, lock-free) particularly important. Expect to justify complexity vs. latency, show familiarity with the memory model, and describe measurable mitigations for contention and cache effects.

Core knowledge

Mutual exclusion (mutex): a blocking primitive that serializes critical sections. Use std::mutex/pthread_mutex_t; cost per lock is low for uncontended cases but grows with context switches and system calls.
Read-write locks (RWLock): allow concurrent readers, exclusive writers; useful for read-heavy workloads but can starve writers or increase writer latency under high read concurrency.
Atomic operations and CAS: compare-and-swap (CAS) via std::atomic or __sync_bool_compare_and_swap is the building block for lock-free algorithms; it offers O(1) semantics but may require retry loops under contention.
Lock-free vs wait-free: lock-free guarantees system progress; wait-free guarantees per-thread progress. Lock-free designs often use CAS loops; wait-free implementations are more complex and rare in production.
Memory model & happens-before: languages expose ordering (e.g., volatile in Java, memory_order in C++). Correctness depends on establishing happens-before for visibility; otherwise you get data races and undefined behavior.
Linearizability and correctness criteria: aim for linearizable operations when designing concurrent data structures so each operation appears atomic at some point between invocation and response.
Liveness hazards: deadlock often stems from inconsistent lock ordering; priority inversion and starvation appear with locks/condition variables and must be mitigated (timeouts, priority inheritance if available).
Condition variables and spurious wakeups: always use while loops to re-check predicates after wait(); treat wakeups as spurious and re-evaluate state.
Memory reclamation (ABA problem): lock-free structures need safe reclamation strategies: hazard pointers, epoch-based reclamation, or garbage collection to avoid ABA and use-after-free.
Contention mitigation patterns: sharding (partition data across locks/cores), per-thread counters with periodic aggregation, exponential backoff in CAS loops, and avoiding false sharing with padding to cache-line boundaries.

Tip: Benchmark with realistic contention patterns (perf, latency p99) and profile cache-misses and lock statistics before over-optimizing.

False sharing & cache effects: place frequently-updated fields on separate cache lines (align/pad) to prevent ping-ponging and degraded throughput on multi-core systems.
High-level strategies: prefer simpler locks when contention is low; switch to sharding or lock-free only if profiling shows lock-induced latency or blocking stalls throughput.

Worked example — "Implement a thread-safe LRU cache"

First 30s: clarify capacity, expected read/write ratio, eviction policy ties, required atomicity (single-key atomic vs. global), and persistence/serialization needs. Skeleton answer pillars: (1) data structures: unordered_map for lookup plus doubly-linked list for recency; (2) synchronization: naive global std::mutex for correctness first; (3) performance: sharded cache (N shards each with own map/list and mutex) to reduce contention; (4) eviction: per-shard LRU or global approximate LRU with periodic balancing. Flag tradeoff: a single global lock simplifies correctness and exact LRU but serializes all ops; sharding improves throughput but yields only per-shard LRU (approximate globally). Also mention memory reclamation for nodes if doing lock-free lists. Close by stating further work: measure p99 latency, add metrics (hit-rate, eviction-rate), tune shard count to number of cores, and consider read-mostly optimization with shared_mutex or hazard pointers if lock-free lookup is attempted.

A second angle — "Design a low-contention concurrent counter"

Frame: clarify accuracy (strictly consistent vs. eventual), update rate, and read frequency. Same core concepts apply: atomic increments vs. sharded counters. A basic solution uses std::atomic<uint64_t> for correctness but suffers on multicore under heavy writes. Better: use per-thread or per-core counters (an array indexed by thread-id) and aggregate reads occasionally; this reduces cache bouncing and increases throughput at the cost of slightly stale reads. You'd discuss padding to avoid false sharing and use relaxed memory ordering for increments, while using stronger ordering on aggregation. If exactness is required, combine per-shard counters plus a rare global CAS to reconcile. Emphasize measurement: quantify throughput improvement and staleness tradeoff.

Common pitfalls

Pitfall: assuming atomic++ scales — under high write contention, a single atomic variable becomes a hotspot and kills throughput; prefer sharding or per-thread accumulation.

Pitfall: forgetting spurious wakeups or relying on if around condition_variable::wait() — this yields missed signals and correctness bugs; always re-check the predicate in a loop.

Pitfall: over-promising lock-free correctness without addressing memory reclamation/ABA — a lock-free queue implementation that neglects safe node reclamation will have subtle, crash-prone bugs in production.

Connections

Concurrency interviewers may pivot to adjacent topics like distributed systems consistency (locks → distributed locks, leader election) or performance engineering (profiling, cache behavior, NUMA effects). They might also ask about language-specific models (Java Memory Model, C++ memory_order) or testing strategies for concurrent code (stress tests, fuzzing).