Concurrency, Synchronization & Deadlock Questions

Deadlock: a situation where two or more threads are permanently blocked because each is waiting for a resource held by another, so none can proceed.

Four Coffman conditions (all must hold for deadlock):

• Mutual exclusion: at least one resource is non-shareable (only one thread can use it at a time).
• Hold-and-wait: a thread holding at least one resource is waiting to acquire additional resources.
• No-preemption: resources cannot be forcibly taken from a thread; they are released only voluntarily.
• Circular-wait: a circular chain of threads exists where each thread waits for a resource held by the next.

Three practical strategies to prevent or recover from deadlocks:

1. Enforce a global lock ordering (prevention): define a consistent acquisition order for locks (e.g., always acquire Lock A then Lock B). This breaks circular-wait and is simple to implement; document the order and enforce in code and code reviews.
2. Use try-lock with timeout and backoff (avoidance/recovery): attempt lock acquisition with tryLock or timed wait; on failure, release held locks, sleep/back off, then retry. This prevents hold-and-wait and lets threads recover without global coordination.
3. Detect and recover (detection + recovery): periodically build a resource-allocation graph or use OS/thread library deadlock detection; when a deadlock is found, take action such as aborting or rolling back one thread/task, or preempting resources. Useful when strict lock ordering is impractical.

Bonus: Where possible prefer lock-free or immutable data structures to eliminate locking entirely.

Requirements & constraints:

• Low-latency local push/pop for producer worker
• Concurrent stealing by other workers with minimal contention
• FIFO/LIFO semantics favoring locality (LIFO for local)
• Scalability to many cores, NUMA-aware

High-level design:

• Each worker owns a double-ended deque (work deque) using a Chase–Lev lock-free design: owner pushes/pops at the bottom (LIFO) without CAS in the fast path; thieves steal from the top using CAS on head/tail indices.

Per-worker data structures:

• struct Deque { atomic<long> top; long bottom; Task[] buffer; } // top is atomic, bottom non-atomic for owner
• Worker: id, Deque*, rng for victim selection, local cache for stolen batch, optional NUMA affinity

Push/pop semantics (owner):

• push(task): write buffer[bottom++]; // fast non-atomic write
• pop(): if bottom==top → empty; decrement bottom; read task; if bottom <= top then do CAS on top to detect races and restore if failed; return task if success
• These use the Chase–Lev invariant: only owner modifies bottom, thieves modify top atomically.

Stealing (thief):

• choose victim (randomized / work-aware / affinity-first)
• atomically read top and bottom; if top < bottom, attempt CAS(&top, oldTop, oldTop+1) to claim task at index oldTop; on success return task
• To reduce contention, steal in batches (steal half or fixed chunk) using a single CAS sequence to claim a range, then pull tasks locally.

Atomicity and correctness:

• All concurrent steals synchronize via atomic CAS on top; owner vs thief race handled by CAS on top and owner detecting/top adjustment when bottom <= top; this preserves single-consumer semantics per task.

Strategies to minimize contention & maximize locality:

• Local LIFO favors recently spawned tasks and cache locality.
• Steal half/batch stealing reduces frequency of CAS operations and amortizes cost.
• Randomized victim selection with exponential backoff reduces hot-spot contention; prefer nearby/NUMA-local workers first.
• Task coarsening: fuse small tasks to reduce overhead.
• Work-stealing throttling: if global idle, expand stealing aggressive; otherwise backoff.
• Use per-worker caches and avoid global queues; maintain steal metrics to adapt victim selection.
• Optional: hierarchical stealing (steal within NUMA domain first, then cross-domain).

Edge cases:

• Resize buffer with careful synchronization: owner can resize; thieves must re-read indices.
• Starvation: periodic global balancing or work donation to avoid pathological imbalance.
• Long-running tasks: preempt or split tasks to expose parallelism.

Trade-offs:

• Chase–Lev is fast for owner but more complex; locks simpler but don't scale.
• Batch stealing increases latency for immediate load shift but reduces contention.

This design yields low-overhead local operations, atomic safe stealing via CAS, and practical heuristics (batching, affinity, randomized selection) for scalability and locality.

Approach: use a bounded queue (capacity N) between producers and consumers. When queue is full, apply a backpressure policy: Blocking (producer waits), Dropping (drop/newest/oldest), or Signaling (notify upstream to slow rate or reduce batch size). Provide pseudocode for core queue plus examples of strategies and choice criteria.

# pseudocode / Python-like
class BoundedBuffer:
    def __init__(self, capacity):
        self.queue = []
        self.capacity = capacity
        self.lock = Lock()
        self.not_empty = Condition(self.lock)
        self.not_full = Condition(self.lock)

    # Blocking producer: waits until space available
    def produce_blocking(self, item):
        with self.not_full:
            while len(self.queue) >= self.capacity:
                self.not_full.wait()          # backpressure: block
            self.queue.append(item)
            self.not_empty.notify()

    # Dropping producer: drop item when full (drop_newest policy)
    def produce_dropping(self, item):
        with self.lock:
            if len(self.queue) >= self.capacity:
                return False                  # dropped
            self.queue.append(item)
            with self.not_empty:
                self.not_empty.notify()
            return True

    # Signaling producer: emit a signal/event to upstream controller
    def produce_signaling(self, item, signal_cb):
        with self.lock:
            if len(self.queue) >= self.capacity:
                signal_cb("SLOW_DOWN")       # asynchronous signal
                return False
            self.queue.append(item)
            with self.not_empty:
                self.not_empty.notify()
            return True

    def consume(self):
        with self.not_empty:
            while not self.queue:
                self.not_empty.wait()
            item = self.queue.pop(0)
            self.not_full.notify()
            return item

Key concepts:

• Blocking is simplest, ensures no data loss, keeps backpressure in-band. Use when correctness matters and producers can block (e.g., synchronous requests).
• Dropping sacrifices some data to preserve throughput and low latency. Use for best-effort telemetry or when stale items are worthless.
• Signaling lets a controller adjust producer rate (token-bucket, reduce batch size, or tell upstream services via HTTP gRPC). Use when producers are distributed and can adapt smoothly.

Trade-offs & selection:

• If data loss unacceptable -> Blocking.
• If latency-critical and occasional loss tolerable -> Dropping.
• If system has smart upstreams/auto-scaling -> Signaling combined with rate-limiters and metrics is preferred.

Testing:

• Unit tests for queue semantics (full/empty), concurrency tests with producers > consumers.
• Load tests to validate policy: measure throughput, latency, and loss rate under various producer/consumer speeds.
• Chaos tests: simulate consumer pauses, network partitions, and verify signaling leads to throttle or restart behavior.

Complexity:

• Operations O(1) amortized. Blocking/waiting cost depends on scheduler. Memory bounded by capacity.

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.

Brief approach: keep heavy computation or I/O off the main/UI thread using platform-specific concurrency primitives; marshal results back to the UI thread for safe updates. Use streaming/ incremental updates and debounce/throttle UI changes to avoid jank.

Browser (JavaScript)

• Off-main APIs: Web Workers, SharedArrayBuffer + Atomics, OffscreenCanvas for graphics, requestIdleCallback for low-priority work.
• Pattern: spin a Web Worker for CPU work; postMessage results back. Use transferable objects (ArrayBuffer) to avoid copies.
• UI update: onmessage handler runs on main thread — perform DOM updates there or use requestAnimationFrame to align with render.

Android

• Off-main APIs: Kotlin coroutines with Dispatchers.Default or Dispatchers.IO; ExecutorService / ThreadPool; WorkManager for background jobs.
• Pattern: launch coroutine on IO/Default, do work, then switch context with withContext(Dispatchers.Main) or use Handler/Looper to post updates.
• UI update: only on Main thread (Activity/Fragment); use LiveData/Flow observed on main to push updates safely.

iOS

• Off-main APIs: Grand Central Dispatch (DispatchQueue.global), OperationQueue, Swift async/await (Task, Task.detached).
• Pattern: DispatchQueue.global().async for background work; update UI inside DispatchQueue.main.async or use @MainActor/Task { @MainActor in ... }.
• UI update: UIKit/AppKit require main thread — update views/state on main.

Cross-cutting best practices

• Keep background tasks cancellable, limit concurrency, batch updates, and avoid long synchronous work on UI thread.
• Use incremental UI updates (diffing, virtualization) and measure with profiling (DevTools, Systrace, Instruments) to validate responsiveness.