Synchronization Primitives and Inter Task Communication Questions
Master synchronization mechanisms: semaphores (binary, counting), mutexes, condition variables, and message queues. Understand when to use each primitive and their trade-offs. Discuss potential issues: priority inversion, deadlock, race conditions, and how to prevent them. Explain interrupt-safe synchronization. Discuss critical sections and atomic operations.
EasyTechnical
66 practiced
Describe what a mutex (mutual exclusion) lock is, how it differs from a semaphore in terms of ownership and semantics, common API primitives (lock/unlock, try_lock), and SRE scenarios where mutexes are preferred (e.g., protecting shared in-memory state). Include a brief note on reentrancy and why it matters.
Sample Answer
A mutex (mutual exclusion) is a synchronization primitive that ensures only one thread/goroutine/process at a time can own a critical section protecting shared state. It provides exclusive ownership: the thread that locks the mutex must be the one to unlock it.Difference from a semaphore:- Ownership: mutexes have ownership semantics (lock/unlock by same owner); traditional counting semaphores do not enforce owner matching.- Semantics: mutex = binary exclusive lock. Semaphore = counter allowing N concurrent holders (N=1 approximates a mutex but without ownership rules).- Use-cases: mutex for protecting in-memory data structures; semaphore for rate-limiting or controlling concurrency degree.Common API primitives:- lock()/unlock() or acquire()/release()- try_lock(): attempt without blocking, returns success/failure- lock_with_timeout()/try_lock_for(): block up to timeout- is_locked(): diagnostic (not always safe)SRE scenarios where mutexes are preferred:- Protecting shared in-memory caches, maps, or runtime state (e.g., in a process managing leader election metadata)- Protecting update paths for connection pools, local counters, or in-process telemetry buffers- Short critical sections where contention is low; avoid holding during I/O to prevent blocking other threadsReentrancy note:- A reentrant (recursive) mutex allows the same owner to acquire the lock multiple times; non-reentrant mutex would deadlock if re-acquired. Reentrancy matters when lock-guarded functions call other lock-guarded functions or when signal handlers interact with locked code. Prefer non-reentrant for simpler reasoning and to catch accidental re-entry; use reentrant only when design requires it and track acquisition counts.
HardSystem Design
59 practiced
Design a concurrency-safe in-memory cache used by a web service that uses per-key locking to prevent a thundering herd on cache misses. Provide approaches such as lock striping, per-key lock objects with weak references to avoid memory leaks, lock pooling, and describe a garbage-collection strategy for unused locks.
Sample Answer
Requirements & constraints:- In-memory cache for a single service/process (or per-node) that prevents thundering herd: when many requests miss a key, only one fetches upstream while others wait.- High concurrency, low latency, bounded memory for lock structures, no memory leaks from per-key locks, and fast common-path reads.High-level design:- Cache store: thread-safe concurrent map (e.g., ConcurrentHashMap) holding value + metadata (expiry).- Lock manager: provides per-key synchronization primitive used only on cache miss.Approaches1) Lock striping (simple, low overhead)- Create N fixed ReentrantLocks (N ~ 256-4096) and map key -> stripe by hash % N.- Pros: bounded memory, simple, cheap.- Cons: coarse: unrelated keys collide and serialize, risking reduced parallelism under hotspots.2) Per-key lock objects with weak references (fine-grained)- Maintain a ConcurrentHashMap<Key, WeakReference<LockHolder>> where LockHolder contains a lightweight sync primitive (e.g., CompletableFuture / condition or ReentrantLock).- On cache miss: fetch or create LockHolder atomically (computeIfAbsent returning WeakReference to new LockHolder). Threads coordinate via LockHolder—first thread does upstream fetch and completes the result; others await it.- Use WeakReference so when no external strong refs to LockHolder remain (no threads waiting and key not present in map), GC can collect it.- To avoid races, store WeakReference in a ConcurrentHashMap and on get check .get(); if null, replace via compare-and-set.3) Lock pooling (reusable small pool of LockHolders)- Maintain an object pool of preallocated LockHolders (bounded) to reduce allocation churn. When a lock is needed, try to acquire from pool; when done, reset and return.- Combine with per-key map by storing pooled holder per-key while active, then returning to pool after use.Garbage-collection strategy for unused locks- Use WeakReferences + ReferenceQueue: when a WeakReference is enqueued, background janitor thread removes its map entry to avoid stale keys.- For languages with GC (Java): store WeakReference<LockHolder> in map and register to ReferenceQueue; janitor polls queue and removes mapping if it points to that reference.- Additionally, use TTL for lock entries: store last-used timestamp and periodically scan/map-scan limited to a small number per cycle to evict idle lock entries (helps in non-GC environments).- For extreme churn, combine lock pooling to cap allocations and avoid unbounded growth.Data flow on miss (per-key lock version)- Thread A checks cache -> miss -> asks lock manager for lock for key -> creates/acquires LockHolder -> detects it is the first (owner) -> fetch upstream -> write cache -> complete LockHolder (notify waiters) -> release and allow WeakReference to be collectable.- Threads B..N get same LockHolder, see fetch in-progress, wait on its completion and then read cached value.Scalability & trade-offs- Striping: simple, bounded memory, but may throttle parallelism. Good for moderate concurrency and memory-constrained environments.- Per-key locks: maximum parallelism, minimal wait for unrelated keys; requires careful GC management (WeakReferences + ReferenceQueue) or pooling to avoid leak/alloc churn.- Pooling reduces allocations but adds complexity (reset semantics, potential contention on pool).- For distributed caches, consider using singleflight (Go) / request coalescing or leader-election per-key (e.g., Redis-based lock) to extend pattern across nodes.Operational considerations- Monitor metrics: lock creation rate, contention (wait time), pool exhaustion, janitor activity, cache miss rate.- Set sensible timeouts for waiters to avoid stuck requests if upstream fetch hangs.- Add observability around eviction/GC to spot memory leaks.
MediumTechnical
68 practiced
Tail-latency spikes are correlated with mutex contention in a Linux service. Describe how you would profile and identify the hottest locks and critical sections across containers using tools like perf, eBPF, and flamegraphs, and propose mitigation strategies such as sharding, batching, lock elision, or move-to-thread-local.
Sample Answer
Start by reproducing spikes under a controlled load so you can correlate latency with CPU/mutex waits. Then iterate between low-overhead sampling (perf) and fine-grained tracing (eBPF/BCC/bpftrace) to find the hottest locks and critical sections, and visualize call stacks with flamegraphs.Profiling steps- Confirm correlation: enable histograms/metrics (latency percentiles) and record timestamps when requests block. Instrument app to emit simple lock acquisition timing if possible.- System-wide sampling: perf record -a -g -- sleep N or perf record -p <pid> -g while load runs. perf script | stackcollapse-perf.pl | flamegraph.pl -> flamegraph shows hot call paths.- Mutex-specific: use perf lock record && perf lock report to enumerate contended mutexes and owners.- eBPF tracing: use BCC tools (offcputime, profiile) or bpftrace one-liners to attach to kernel mutex tracepoints (sched:sched_wakeup, sched:sched_switch) or userspace pthread_mutex_lock/pthread_mutex_unlock to measure wait durations and emit stacks. Example bpftrace snippet: - Attach uprobe to pthread_mutex_lock, record timestamp on entry, on return compute delta; capture user stacks for long waits.- Across containers: run perf/eBPF on the host but target container pids (namespaces) or run lightweight sidecar in container; aggregate results centrally.Analysis & visualization- Generate flamegraphs of on-CPU stacks and off-CPU (blocked) stacks to separate CPU hotspots vs lock-wait hotspots.- Use perf lock report + stack traces to map contention to code locations and call contexts.Mitigations (apply incrementally, test performance/regressions)- Reduce critical-section work: move non-essential work outside the lock, avoid syscalls inside locks.- Sharding / partitioning: split a global lock into N shards keyed by independent keys to reduce contention.- Batching/coalescing: accumulate work (writes, syscalls) and perform in single lock hold.- Move-to-thread-local / per-CPU: use thread-local caches, per-CPU counters and periodic aggregation.- Lock elision / optimistic concurrency: replace exclusive locks with atomic/cas when operations are small; use RCU/read-copy-update for read-mostly paths.- Reader-writer locks: switch to RW-locks for read-heavy workloads.- Backoff & trylock: use trylock with exponential backoff to avoid convoying; detect and mitigate priority inversion.- Asyncify work: hand off work to dedicated worker threads to reduce main-thread contention.Operational considerations- Measure before/after with the same profiling chain and update SLO dashboards.- Roll out changes gradually (canary) and monitor tail-percentiles.- Add lightweight runtime metrics (lock wait time, trylock failures) for ongoing alerting.This combination of perf for sampling, eBPF for low-overhead tracing, and flamegraphs for visualization quickly reveals where to apply targeted fixes (sharding, batching, lock elision, or thread-localization) and how those changes affect tail latency.
MediumTechnical
63 practiced
Design an alert that detects elevated lock contention causing increased request latency for a web service. Specify which metrics you would collect (for example: mutex wait time histograms, syscall latency, queue sizes), how you would set thresholds, and include immediate runbook steps the on-call engineer should follow.
Sample Answer
Goal: detect when lock contention in-process (or across nodes) is driving increased request latency so on-call can triage and mitigate before SLOs are violated.Metrics to collect- Application-level: - Mutex/lock hold time histogram (per-lock and aggregated): buckets (µs→s) and p50/p95/p99. - Mutex wait time histogram (time spent waiting to acquire). - Lock acquisition rate (ops/sec per lock). - Number of goroutines/threads blocked on locks. - Per-request latency (p50/p95/p99) and request rate.- System-level: - CPU utilization, syscall latency (futex/syscall wait), context-switch rate. - Queue sizes (worker queues, connection queues). - GC pause times (if language has GC).- Distributed-level: - Distributed lock latency and retries (if using etcd/consul/redlock). - Error/timeout rates.Thresholds & alerting logic- Two-tier alerts: - Warning: aggregated lock wait p95 > 5× baseline AND request p95 increased by >20% vs 1h rolling baseline for 5m. - Critical: aggregated lock wait p99 > X ms (e.g., >200ms) OR number of blocked threads > 50 AND request p99 > SLO breach threshold for 2m.- Use rate-normalized measures (per-request or per-lock) to avoid noisy alerts during low traffic. Require sustained condition (3–5 minutes) to reduce flapping.- Correlate signals: fire only when both lock metrics AND latency metrics are anomalous.Immediate runbook (first 20 minutes)1. Acknowledge and gather context - Link to dashboard showing lock histograms, per-lock breakdown, request latency, CPU, GC, syscalls, and recent deploys.2. Triage: is this real contention? - Check per-lock heatmap to identify top offending locks. - Confirm request rate hasn't spiked causing queuing. - Confirm recent deploys/rollouts; if so, roll back if suspicious.3. Mitigate - If single lock hotspot in one service instance: remove instance from LB (drain) to stop impacted traffic. - If contention across all instances: scale horizontally (add pods/hosts) if safe; increase worker pool to absorb backlog. - If GC or syscall stalls observed: reduce load or roll back offending binary. - If distributed lock (etcd/consul) showing high latency: fail fast to degrade gracefully or fallback to read-only mode.4. Short-term fixes - Toggle feature flags or reduce concurrency for the offending path. - Apply emergency config to use optimistic locking / longer timeouts where safe.5. Escalation - If not mitigated in 15–20m, escalate to service owner and devs who own lock code; open P1 with timeline and actions taken.6. Post-incident - Preserve traces, flamegraphs, and heap/CPU profiles from affected instances. - Run retrospective: identify root cause (hot lock, algorithmic regression, deployment), implement instrumentation (per-lock tags), and scheduling/lock redesign or sharding.Why this approach- Combining lock wait histograms with request latency reduces false positives.- Per-lock breakdown pinpoints root cause quickly.- Two-tier alerting and sustained windows balance sensitivity vs noise.
HardTechnical
64 practiced
Propose an adaptive backoff algorithm for high contention locks in a cloud environment that accounts for variable VM performance and noisy neighbors. Explain how you choose spin length versus blocking, how to apply exponential backoff with jitter, and which metrics you would collect to tune parameters automatically.
Sample Answer
Requirements & constraints:- Minimize wasted CPU on noisy VMs but keep low latency for short critical sections.- VMs have variable performance and interference (noisy neighbors).- Lock strategy must adapt per-host and per-lock.High-level approach:- Use hybrid spin-then-block with adaptive spin cap determined by sampled local metrics and recent lock latency history.- Apply exponential backoff with full jitter when spinning fails to avoid synchronized retries.- Continuously tune parameters via collected metrics and feedback loop.Algorithm (summary):1. On lock attempt: - Read local lightweight signals: recent lock hold-time mean/percentile, local CPU steal, load, and last-successful-spin-count. - Compute spin_limit = base_spin * f1(hold_time, cpu_steal, qps), bounded [min_spin, max_spin]. - Try spinning up to spin_limit iterations/CPU-cycles. - If still contested, enter exponential backoff with jitter and then block (futex/park) after some backoff threshold.Exponential backoff with jitter (pseudo):Choosing spin vs block:- Favor spinning when expected remaining hold-time < spin_cost. Estimate: spin_cost = spin_limit * cpu_cycle_cost; remaining_hold = EWMA of lock_hold_time; if remaining_hold < spin_cost * safety_factor, spin more; otherwise block.- Prefer spinning on low steal and low latency VMs; prefer blocking on high steal or preemptible instances.Adaptive tuning metrics to collect:- Per-lock: acquisition latency distribution (p50/p95/p99), hold-time distribution, success-after-n-spins histogram, contention rate (#contentions/sec).- Per-VM: CPU steal time, runqueue length, context-switch rate, loadavg, host-level latency spikes.- System: wakeups/sec, futex syscall rate, power/thermal events (if available).Automatic tuning loop:- Feed metrics into a controller that: - Calculates EWMA of hold-time and contention. - Adjusts base_spin and min/max_backoff periodically (e.g., every 10s) using simple rules: increase spin if p95 hold-time decreased and steal low; decrease spin if CPU-steal or futex wakeups high. - Use gradient-free optimizer (e.g., Bayesian or hill-climb) per lock class to maximize throughput subject to SLOs (p99 latency).Safety & trade-offs:- Bound spin to avoid CPU livelock; enforce global budget per core via cgroup if needed.- Use randomized jitter to prevent synchronization storms.- Fall back to conservative defaults if metrics are missing or noisy.Operational: expose tuning metrics in monitoring, set alerts on rising futex/wakeup rates and p99 latency. Run canary experiments (A/B) when changing default parameters.
python
def backoff_and_sleep(attempt):
# full jitter per AWS recommendation
base = min_backoff_ms * (2 ** attempt)
cap = max_backoff_ms
sleep_ms = random.uniform(0, min(base, cap))
sleep(sleep_ms/1000)Unlock Full Question Bank
Get access to hundreds of Synchronization Primitives and Inter Task Communication interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.