Concurrency and Multithreading Questions
Principles and practical techniques for concurrent execution and safe access to shared state across threads or execution contexts. Covers synchronization primitives (locks, mutexes, semaphores, condition variables), atomic operations and memory ordering, avoiding deadlocks, race conditions, and livelocks, designing thread safe data structures, thread pools and work scheduling, and asynchronous or event driven execution models such as coroutines, futures and promises, and reactive streams. Also covers platform and language specific concurrency tools, for example java.util.concurrent and POSIX threads on backend systems, Grand Central Dispatch and OperationQueue on iOS, coroutines and structured concurrency on Android/Kotlin, and async/await models in other languages. Evaluations focus on reasoning about correctness under concurrent access, performance trade offs (throughput, latency, contention), and preventing blocking of latency sensitive execution paths (server request handlers, UI threads, game loops) to maintain responsiveness.
HardTechnical
47 practiced
Explain priority inversion and design strategies to avoid it in real-time systems. Describe priority inheritance as a solution, its implementation implications, and show a code sketch of a mutex wrapper that supports priority inheritance semantics.
Sample Answer
Priority inversion occurs when a high-priority task is blocked waiting for a resource (e.g., a mutex) held by a low-priority task, while one or more medium-priority tasks preempt the low-priority holder. The high-priority task ends up waiting longer than intended — violating real-time guarantees.Design strategies to avoid priority inversion- Avoid long critical sections; keep locks held briefly.- Use priority-aware locking protocols: Priority Inheritance (PI) or Priority Ceiling Protocol (PCP).- Use lock-free or wait-free algorithms where practical.- Partition work so high-priority tasks don't need shared resources with low-priority tasks.- Use real-time OS primitives (some kernels provide PI-enabled mutexes).Priority Inheritance (PI)- Principle: when a high-priority thread blocks on a mutex held by a lower-priority thread, the holder temporarily "inherits" the higher priority so it can run and release the mutex sooner. Once it releases, it reverts to its original priority.- Benefits: bounds blocking time and prevents medium-priority tasks from indefinitely delaying the low-priority holder.- Limitations: complexity with nested locks, chained inheritance (transitive boosts), interaction with deadlock avoidance, and requires support from scheduler or explicit priority management by the locking layer.- Implementation implications: - Must track waiting threads and compute the effective priority to apply to the owner. - Must restore owner priority safely (consider multiple nested boosts). - Requires ability to change thread priority at runtime (OS APIs like pthread_setschedparam or platform-specific calls). - Careful with priority ceiling: PCP can avoid transitive chains but is more restrictive.Code sketch (C++ / POSIX-like): a mutex wrapper that performs simple priority inheritance by boosting owner thread priority to the maximum waiting priority. This is illustrative (error checking and real-world corner cases omitted).Notes and caveats- This sketch is simplified: production code must handle nested locks, chained inheritance (transitive), race conditions, errors from sched calls, and privileges (changing priorities often requires elevated rights). Some OSes provide PI mutexes natively (POSIX mutexes with PTHREAD_PRIO_INHERIT) — prefer those to manual implementations.- Testing: verify priority boosts, chained blocking scenarios, and ensure no priority leaks (owner must always revert).- Alternatives: Priority Ceiling Protocol (prevents unexpected chains by raising thread priority to ceiling upon acquiring) or using real-time OS facilities that guarantee bounded blocking.
cpp
// C++ (POSIX-ish) illustrative sketch
#include <pthread.h>
#include <sys/types.h>
#include <map>
#include <set>
#include <mutex>
#include <thread>
class PI_Mutex {
pthread_mutex_t mtx;
std::mutex meta; // protect metadata
pthread_t owner = 0;
int owner_orig_prio = 0;
std::multiset<int> waiters; // store waiting priorities (higher number = higher priority)
int get_thread_priority(pthread_t t) {
sched_param sp; int policy;
pthread_getschedparam(t, &policy, &sp);
return sp.sched_priority;
}
void set_thread_priority(pthread_t t, int prio) {
sched_param sp{prio};
pthread_setschedparam(t, SCHED_FIFO, &sp); // error checks omitted
}
public:
PI_Mutex() { pthread_mutex_init(&mtx,nullptr); }
~PI_Mutex(){ pthread_mutex_destroy(&mtx); }
void lock() {
pthread_t self = pthread_self();
int self_prio = get_thread_priority(self);
{
std::unique_lock<std::mutex> lk(meta);
// if someone owns it, record our priority and boost owner
if (owner != 0) {
waiters.insert(self_prio);
int max_wait = *waiters.rbegin();
int owner_cur = get_thread_priority(owner);
if (max_wait > owner_cur) {
// boost owner
set_thread_priority(owner, max_wait);
}
}
}
pthread_mutex_lock(&mtx);
// we've acquired the mutex: become owner
std::unique_lock<std::mutex> lk(meta);
owner = self;
owner_orig_prio = self_prio; // store original (simplified)
// remove self from waiters if it was present
auto it = waiters.find(self_prio);
if (it != waiters.end()) waiters.erase(it);
}
void unlock() {
std::unique_lock<std::mutex> lk(meta);
if (owner != pthread_self()) {
// error: unlocking by non-owner (omitted)
}
// compute highest waiting priority (if any)
int new_prio = owner_orig_prio;
if (!waiters.empty()) new_prio = std::max(new_prio, *waiters.rbegin());
// restore owner (or set to next needed) before releasing
set_thread_priority(owner, owner_orig_prio);
owner = 0;
owner_orig_prio = 0;
lk.unlock();
pthread_mutex_unlock(&mtx);
}
};HardTechnical
46 practiced
Explain C++11 memory_order semantics: relaxed, acquire, release, acquire-release, and seq_cst. Provide a small code example that demonstrates a reordering that relaxed allows but acquire-release would prevent, and discuss performance trade-offs when choosing an ordering.
Sample Answer
Brief definitions:- relaxed: only atomicity, no synchronization or ordering with other operations.- acquire: for loads — prevents subsequent memory reads/writes from being reordered before the acquire load.- release: for stores — prevents prior memory reads/writes from being reordered after the release store.- acquire-release (acq_rel): for read-modify-write ops — combines both constraints.- seq_cst: strongest; provides a single total order for seq_cst operations consistent with program order (global sequential consistency).Example: writer wants to publish data then set a flag. With relaxed the store to flag may become visible before the data store (allowed reordering); acquire-release prevents that.Why: release on the writer makes prior stores (data) happen-before the release; an acquire load on the reader sees that and prevents reordering, guaranteeing visibility.Trade-offs:- relaxed is fastest (no fencing), useful when only atomicity/counting is needed and no cross-thread ordering required.- acquire/release give needed synchronization with lower overhead than seq_cst on many architectures.- seq_cst is simplest to reason about but may cost more (stronger fences or heavier CPU ordering), potentially reducing scalability.Choose the weakest ordering that still provides required correctness; prefer release/acquire for producer-consumer patterns, seq_cst only when global ordering is necessary.
cpp
#include <atomic>
#include <thread>
#include <cassert>
std::atomic<int> data{0};
std::atomic<bool> ready{false};
void producer_relaxed() {
data.store(42, std::memory_order_relaxed);
ready.store(true, std::memory_order_relaxed); // may be visible before data
}
void consumer_relaxed() {
while (!ready.load(std::memory_order_relaxed)) {}
// Could see ready==true but still read data==0 due to reordering
int v = data.load(std::memory_order_relaxed);
// v might be 0 here with relaxed semantics
}
void producer_release() {
data.store(42, std::memory_order_relaxed);
ready.store(true, std::memory_order_release); // publishes prior stores
}
void consumer_acquire() {
while (!ready.load(std::memory_order_acquire)) {}
int v = data.load(std::memory_order_relaxed);
// v must be 42: acquire pairs with release to synchronize
}MediumSystem Design
59 practiced
Design a scalable real-time metrics ingestion pipeline that must handle 100k events per second with low aggregation latency. Describe how you would use concurrency for ingestion, batching, worker pools, durable buffering, sharding, backpressure and fault tolerance across nodes.
Sample Answer
Requirements:- Ingest 100k events/sec, low aggregation latency (sub-second), durable, resilient, and backpressure-aware.High-level architecture:Clients → Load balancer → Ingress fleet (stateless collectors) → Durable buffer (partitioned Kafka / Pulsar) → Sharder → Worker pool (consumers) → In-memory aggregator / cache → Real-time store (Redis, materialized view) + Batch long-term store (S3, OLAP)Concurrency & ingestion:- Ingress collectors are multi-threaded async servers (Netty or async IO). Use event-loop + bounded thread-pool for parsing/validation, minimizing blocking.- Each collector writes events to durable partitioned buffer (Kafka topic) via async produce with batching (linger.ms, max.size).Batching & worker pools:- Consumers use consumer groups with N partitions = M workers. Each worker runs a pool of fixed-size threads to process batches pulled from a partition. Pull-based consumption enables efficient batching (e.g., 100–1000 events) to amortize processing and reduce commit overhead.Sharding:- Partition by customer_id or metric_id to keep related events co-located for correct aggregation. Use consistent hashing to distribute partitions across brokers and consumers. Number of partitions chosen to support concurrency: e.g., 1000 partitions → 100k eps with ~100 eps/partition.Durable buffering:- Kafka/Pulsar ensures durability, retention, replay and ordered per-partition processing. Store raw events to S3 for long-term.Backpressure:- Use pull-based consumers and monitor consumer lag. If lag grows, expose backpressure to collectors by: (1) returning 429 or retry-after, (2) throttling per-client at load balancer, (3) reducing producer throughput (client-side rate limits). Within pipeline, allow Kafka to throttle producers (acks/timeout) and apply dynamic scaling.Fault tolerance:- Consumer groups rebalance on node failure; partition ownership moves to other workers. Use idempotent processing (dedupe by event-id or use Kafka transactions) and exactly-once semantics where possible. Persist aggregator checkpoints (offsets and partial aggregates) to a durable store (Zookeeper/KV). Use health checks, auto-scaling, and graceful shutdown to drain partitions.Low-latency aggregation:- Combine two-tier aggregation: fast in-memory real-time aggregators per-partition (flush every 200–500ms) that push incremental deltas to a low-latency store (Redis/Timescale) and periodic compaction to long-term store. Use asynchronous flush and snapshots to avoid blocking.Monitoring & autoscaling:- Monitor throughput, consumer lag, processing latency. Autoscale consumers and ingress based on lag and CPU. Alert on sustained lag.Trade-offs:- Many partitions increase parallelism but add coordination overhead. Batching reduces per-event overhead but increases latency—tune batch size/linger for SLA. Exactly-once costs more; consider at-least-once with idempotent sinks if lower cost.This design uses concurrency at collectors and worker pools, durable buffering via Kafka, sharding by key for correct aggregation, batching to optimize throughput, backpressure mechanisms to protect system, and consumer rebalancing + idempotency for fault tolerance.
HardSystem Design
55 practiced
Design a distributed job scheduler that dispatches jobs to worker nodes running tasks concurrently. Explain how you will handle worker failures, job leasing, at-least-once vs exactly-once execution semantics, leader election, and how concurrency at the worker should be controlled.
Sample Answer
Requirements & constraints:- Functional: accept jobs, persist queue, dispatch to workers, report status, retries.- Non‑functional: scale to thousands of workers, low dispatch latency, durable state, tolerate worker/process failures.High-level architecture:- Scheduler service (leader-elected cluster) + persistent Job Store (e.g., Spanner/Postgres/Cassandra) + Worker nodes + Optional distributed lock/coordination (e.g., ZooKeeper/etcd/Consul) + Message bus (Kafka/RabbitMQ) for events.Core components:1. Job Store: authoritative state (job metadata, status, owner, leaseExpiry, attempts). Durable, supports transactions.2. Leader election: use etcd/raft to elect one active scheduler instance to perform dispatch decisions; others act hot-standby and can take over quickly.3. Dispatcher: leader scans Ready jobs, issues leases by updating Job.owner and leaseExpiry in Job Store (transactional).4. Delivery: publish LeaseAssigned event on message bus and/or push to worker endpoint.5. Worker: receives job, attempts execution, reports completion (SUCCESS/FAIL) with a lease token. Periodically heartbeats to renew lease before leaseExpiry.6. Monitor: detects lease expiry; if lease not renewed, marks job as Ready again and increments attempts.Worker failures & job leasing:- Lease model: scheduler assigns time-limited lease token to a worker. Worker must renew before expiry or return result with token. Lease prevents simultaneous work by different workers.- If worker crashes and lease expires, scheduler reclaims job and retries. Use exponential backoff and max-attempts to avoid livelock.At-least-once vs exactly-once:- At-least-once: default — simpler: allow retries on failure or timeout. Ensure idempotent tasks or make the system compensate (dedup keys, idempotency tokens).- Exactly-once (best-effort): combine idempotency + unique job IDs + transactional acknowledgement. Worker writes result into Job Store with lease token in a single transaction; job state transition to COMPLETED only if token matches current owner. For external side effects, require two-phase commit or use outbox pattern: worker writes intended side-effect to stable outbox and a separate reliable executor ensures side-effect runs once. True distributed exactly-once across arbitrary external systems is often impractical — prefer at-least-once with idempotency or exactly-once semantics for supported sinks.Leader election & high availability:- Use Raft (etcd/consul) for leader election and config storage. Leader runs dispatch loops; followers apply the same scheduling logic off-line for fast takeover. Persist schedule progress and leases so takeover can continue without duplicate dispatch.Controlling concurrency at workers:- Worker exposes concurrency config (maxThreads, maxCPU, queue size). Scheduler respects resource tags and per-worker capacity when leasing jobs. Maintain token-bucket or semaphore per worker in Job Store so dispatcher never grants leases exceeding capacity. Support task priorities and fair-share.Data flow summary:Client -> Job Store (create job) -> Leader Dispatcher assigns lease -> message bus -> Worker executes -> Worker writes result with lease token -> Job Store updates CLOSED or reschedules on failure.Trade-offs:- Short leases reduce failover latency but increase churn/renew overhead.- Central Job Store simplifies consistency but can be bottleneck; partition jobs by key to scale.- Exactly-once complexity vs practicality: prefer idempotency and monitoring.Observability, metrics, and testing:- Metrics: queue length, leases active, retry rates, worker heartbeats.- Chaos testing (kill workers, partition scheduler) to validate lease/retry behavior.This design provides fault-tolerant dispatching with clear lease semantics, HA leader election, and practical guidance for achieving exactly-once behavior where feasible.
MediumTechnical
66 practiced
Compare async/await, callbacks, and promises/futures across JavaScript, Python asyncio, Java CompletableFuture, and Kotlin coroutines. Discuss error propagation, cancellation, composition, and debugging implications for each model.
Sample Answer
High-level summary: callbacks, promises/futures, async/await, and coroutines provide increasing levels of composability and readability. Behavior differences across JS, Python asyncio, Java CompletableFuture, and Kotlin coroutines matter for error propagation, cancellation, composition, and debugging.Error propagation- Callbacks (JS/Python style): errors must be passed explicitly (err-first) or handled in each callback; easy to lose stack context and leak errors.- Promises/Futures (JavaScript Promise, Java CompletableFuture): exceptions are captured and forwarded to rejection/exception channels; .catch/handle methods let you centralize handling. In Java, exceptions are wrapped (CompletionException) which can obscure original cause unless unwrapped.- async/await (JS, Python asyncio, Kotlin suspend functions, Java via CompletableFuture.thenCompose + join): exceptions thrown inside await propagate like synchronous throws to the surrounding async function, making try/catch natural. In Python and Kotlin the original traceback is preserved; JS preserves stack for recent engines but microtask scheduling can split traces.- Kotlin coroutines: throw behaves like structured code; exceptions in parent vs child follow CoroutineExceptionHandler rules; supervisor jobs change propagation.Cancellation- Callbacks: no standard cancellation primitive; requires custom flags or abort tokens.- Promises (JS): native Promise has no built-in cancellation (AbortController is external). CompletableFuture supports cancel(true) but cooperative cancellation is required; may interrupt threads but not guarantee resource cleanup.- Python asyncio: Tasks support cancel() which raises CancelledError inside coroutine; code must handle cleanup (try/finally, shields).- Kotlin coroutines: Job cancellation is cooperative and integrated—suspending functions check for cancellation; structured concurrency ensures child coroutines are cancelled when parent scope is cancelled.- Java CompletableFuture: cancellation propagates only if you chain and check isCancelled; lacks structured concurrency, so leaks possible.Composition- Callbacks: nested, inversion of control, leads to callback hell.- Promises/Futures: then/thenCompose/thenCombine (JS Promise.all, Java CompletableFuture.allOf/thenCompose) allow flat composition and parallel patterns.- async/await / coroutines: composition reads sequentially while allowing concurrency via explicit constructs (Promise.all, asyncio.gather, coroutine async builders, Kotlin async/await). Kotlin structured concurrency encourages scoped composition and automatic cancellation of children.Debugging and observability- Callbacks: hard to trace; stacks are fragmented; breakpoints and async stack-traces limited.- Promises/Futures: better—rejection handlers and chain-aware traces exist but can still lose origin of error across microtasks; Java CompletableFuture stack traces can be noisy due to wrapping.- async/await / coroutines: source-like stack traces are easier to reason about. Python 3.11+ improved exception groups and tracebacks for asyncio. Kotlin offers coroutine debug probes and "debug mode" that records coroutine names and parents; stack traces may be synthetic when suspended. Java CompletableFuture debugging remains lower-level; tools like async-profiler help but lack coroutine-level semantics.- Logging/tracing: use structured spans (OpenTelemetry), include context IDs, and attach cancellation/reason metadata.Practical guidance- Prefer structured concurrency (Kotlin coroutines, Python trio/curio or using asyncio with careful scopes) to avoid leaks.- Use language-native patterns: JS—Promises + async/await + AbortController for cancellation; Python—asyncio Tasks with try/finally and gather(return_exceptions=True) when needed; Java—use CompletableFuture carefully, prefer higher-level frameworks (Project Loom fibers, or wrappers providing structured lifecycles); Kotlin—use CoroutineScope, SupervisorJob where appropriate and rely on cancellation being cooperative.- Always handle errors at boundaries, unwrap wrapped exceptions, and add observability (context, timeouts, cancellation reasons) to simplify debugging.
Unlock Full Question Bank
Get access to hundreds of Concurrency and Multithreading interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.