Mock 11 — Concurrency Heavy

Interview type: Concurrency / parallelism coding round Target role: Backend, systems, infrastructure, embedded, gaming, OS-adjacent Time limit: 60 minutes Format: ONE problem requiring real concurrency primitives (locks, condvars, channels, atomics) Hints policy: A hint on the primitive choice is acceptable; a hint on the race condition is borderline. Primary goal: Write code that is provably correct under concurrent access.

What This Mock Tests

Concurrency code is notoriously hard. The bar:

  • Identify what needs synchronization (shared mutable state)
  • Choose the right primitive (mutex vs RWLock vs channel vs atomic)
  • Avoid deadlocks, livelocks, starvation
  • Write a test that would catch the bug if present (not just one that passes by luck)

Scoring weights: Correctness (#5), Code Quality (#7), Language/Runtime (#12) are critical.

Pick One Problem

Problem A — Bounded Blocking Queue (with timeout)

q = BoundedQueue(capacity=10)
q.put(item)                       # blocks if full
q.put(item, timeout=5.0)          # returns False on timeout
item = q.get()                    # blocks if empty
item = q.get(timeout=5.0)         # returns None on timeout
q.close()                         # subsequent put → exception; get drains then returns None

Multiple producers, multiple consumers. Must be FIFO. Must support graceful close.

Problem B — Thread Pool (with shutdown semantics)

pool = ThreadPool(workers=4)
future = pool.submit(fn, arg)
result = future.result(timeout=5.0)   # blocks until done
pool.shutdown(wait=True)              # waits for all queued + running
pool.shutdown(wait=False)             # rejects new, returns immediately

Required: bounded work queue, graceful drain, future-based result delivery, exception propagation.

Problem C — Read-Write Lock (Writer-Preferred)

lock = RWLock()
with lock.read():
    # multiple readers concurrently
    ...
with lock.write():
    # exclusive; blocks new readers waiting for writer
    ...

Required: many readers OR one writer; writers must not starve.

Problem D — Dining Philosophers (Deadlock-Free)

5 philosophers, 5 chopsticks. Each alternates think/eat. Implement so no deadlock, no philosopher starves.

Expected Communication Style

  1. Restate with the explicit concurrency requirements (“multiple producers, multiple consumers, FIFO, graceful close”).
  2. Identify shared mutable state. This is the most important step.
  3. Identify the invariant. (“Queue size never exceeds capacity”; “no two writers active simultaneously”; “no two adjacent philosophers eat simultaneously”.)
  4. Choose primitives with rationale. (“I need to block on full/empty — that means condvar, not just a lock.”)
  5. Code the critical section minimally. Hold the lock only across the shared-state mutation; release before any potentially-blocking call.
  6. Write a concurrency test. Not just “does it work once” — stress with many threads, verify the invariant.
  7. Discuss failure modes: what happens if a producer dies holding the lock? If close is called during a put?

Solution Sketches

A. Bounded Queue:

class BoundedQueue:
    def __init__(self, capacity):
        self._capacity = capacity
        self._q = deque()
        self._lock = threading.Lock()
        self._not_full = threading.Condition(self._lock)
        self._not_empty = threading.Condition(self._lock)
        self._closed = False
    
    def put(self, item, timeout=None):
        with self._lock:
            if self._closed: raise QueueClosed()
            end = time.monotonic() + timeout if timeout else None
            while len(self._q) >= self._capacity:
                if self._closed: raise QueueClosed()
                remaining = end - time.monotonic() if end else None
                if remaining is not None and remaining <= 0: return False
                self._not_full.wait(timeout=remaining)
            self._q.append(item)
            self._not_empty.notify()
            return True
    
    def get(self, timeout=None):
        with self._lock:
            end = time.monotonic() + timeout if timeout else None
            while not self._q:
                if self._closed: return None
                remaining = end - time.monotonic() if end else None
                if remaining is not None and remaining <= 0: return None
                self._not_empty.wait(timeout=remaining)
            item = self._q.popleft()
            self._not_full.notify()
            return item
    
    def close(self):
        with self._lock:
            self._closed = True
            self._not_full.notify_all()
            self._not_empty.notify_all()

B. Thread Pool: N worker threads pulling from a shared bounded queue; each task wraps (fn, args, future). Workers set future’s result/exception. Shutdown sentinels (None) wake workers; wait=True joins all worker threads.

C. RWLock writer-preferred: Track reader_count, writer_active, waiting_writers. Reader acquires only if no writer active AND no waiting writers. Writer blocks while readers active; once it’s the chosen waiter, blocks all new readers.

D. Philosophers: asymmetric strategy — even-numbered grabs left then right, odd-numbered grabs right then left. Breaks the symmetry that causes circular wait → no deadlock. Alternative: use a hierarchical lock ordering (always grab lower-id chopstick first).

Common Failure Modes

  1. Used if instead of while around wait(). Spurious wakeups cause invariant violations.
  2. Released the lock before notifying, or notified before updating state. Wakes a consumer that finds the queue empty.
  3. Held the lock during a callback / blocking I/O. Other threads stall.
  4. Used notify() instead of notify_all() for close. Only wakes one waiter; others hang forever.
  5. RWLock without writer preference → writer starvation.
  6. Philosophers: all grab left → deadlock. Classic.
  7. Test that runs once and passes. Not a concurrency test. Need stress (1000+ iterations across many threads).
  8. Used concurrent.futures.ThreadPoolExecutor for Problem B without implementing the underlying logic. Some interviewers accept this; many want you to build it.

Passing Bar

  • Total score: 56/70 (average 4.0)
  • Code correctness verified under stress (≥ 10K operations across ≥ 8 threads)
  • Invariant explicitly stated and tested
  • No use of high-level concurrency abstractions that hide the primitive (e.g., queue.Queue for problem A)
  • Failure modes discussed

Follow-up Questions

For A:

  • Lock-free version. → Discuss MPMC ring buffer with CAS; show awareness of ABA problem.
  • Multi-priority. → Multiple internal queues, one per priority.
  • Persist across restart. → Append-only log; replay on startup.

For B:

  • Work-stealing pool. → Per-worker deque; idle workers steal from others.
  • Dynamic resizing. → Grow workers under load; shrink when idle.
  • Cancellable tasks. → Future.cancel() signals; worker checks flag.

For C:

  • Fair RWLock (FIFO). → Single waiting queue; reader batching possible but trickier.
  • Reader-preferred. → Easier to implement; writer starvation risk.
  • Async version with futures. → Same logic; futures replace condvar.

For D:

  • Variant where philosophers think for variable time. → Same algorithm.
  • Generalize to N philosophers and K chopsticks. → Open problem; resource allocation graphs.
  • Distributed version (philosophers on different machines). → Requires distributed deadlock detection.

Required Tests

  • Single-thread correctness
  • Multi-thread stress: many producers + consumers; assert no item lost, no item duplicated, no exception
  • Timeout correctness: put(timeout=0.1) returns False after 100ms when full
  • Close semantics: close during active put/get unblocks all waiters cleanly
  • Invariant assertion: assert size ≤ capacity throughout, etc.

Example stress test for A:

def test_stress():
    q = BoundedQueue(10)
    produced = []
    consumed = []
    def producer(start, count):
        for i in range(start, start + count):
            q.put(i)
            produced.append(i)
    def consumer():
        while True:
            x = q.get(timeout=1.0)
            if x is None: break
            consumed.append(x)
    threads = [threading.Thread(target=producer, args=(i*1000, 1000)) for i in range(10)]
    consumers = [threading.Thread(target=consumer) for _ in range(5)]
    for t in threads + consumers: t.start()
    for t in threads: t.join()
    q.close()
    for t in consumers: t.join()
    assert sorted(consumed) == sorted(produced)
    assert len(consumed) == 10_000

Required Discussion

  • The invariant your code maintains
  • The lock ordering (if multiple locks)
  • The worst-case latency (lock contention)
  • What happens under crash mid-operation
  • How you’d debug a deadlock if one were reported (jstack, py-spy dump, gdb)

Self-Evaluation Template

Mock 11 — Concurrency
Date: _______
Problem: _______
Time: ___ / 60 min

Scores (1–5):
___ Total /70

Stress test passed (≥ 10K ops)? Y/N
Invariant explicitly stated? Y/N
Failure modes discussed? Y/N
Any race condition found post-hoc? (List:)

Action item:

What to Do If You Fail

  • Race condition in submitted code: This is the #1 reason to repeat — concurrency bugs in production are catastrophic.
  • Couldn’t choose the right primitive: Read your language’s concurrency chapter (Phase 9). Understand condvar vs channel vs atomic before next attempt.
  • Stress test exposed a bug you didn’t anticipate: Lab 05 (stress harness) applied to concurrent code is your training.
  • Pass twice consecutively before Mock 12.