workers? fixed N; sizing rationale ready (CPU ~cores,
IO-bound larger or separate pool)
queue? bounded, FIFO — bound implies a full-queue policy
results? future-like handle; wait or ignore
task throws? captured into the handle; NEVER kills a worker
priorities? out of scope (know the starvation story anyway)
primitives? mutex + condition variables (blocking design)
The design in ten lines
submitters -> [ bounded queue: mutex + not_empty + not_full ] -> N workers
worker loop: take -> run (CATCH ALL) -> complete handle
handle: PENDING -> DONE once; payload = value | exception;
waiter rethrows the exception in ITS OWN thread
queue waits: while (!predicate) wait(cv, mu) // never `if`
state changes: only under the queue mutex // kills missed wakeups
signals: push -> signal(not_empty, ONE)
take -> signal(not_full, ONE)
handle done: broadcast (all waiters may proceed)
Condvar discipline (the graded part)
1. predicate re-checked in a while loop (spurious wakeups are legal)
2. predicate only changed under the mutex (closes the missed-wakeup
window; wait releases + reacquires the lock atomically)
3. aim each signal at waiters who can progress; broadcast only when
the event satisfies everyone (handle completion)
4. in a blocking design the MUTEX is the memory-ordering story —
no hand-placed fences, and say why
Complexity and performance facts
submit / take O(1) + contention on one mutex
the ceiling lock handoff — fine at ms tasks, dominant at us
scaling shape work stealing: per-worker deques, steal when idle
(buys contention collapse, spends global FIFO)
The five report dimensions — what earns points here
Requirements & interface surfaced the failure questions unprompted:
bounded queue, throwing tasks, result handles
Core design & invariants condvar rules stated precisely; exception-
capture named as structural; one-shot handle
Extension probe (withheld — the mock tests you cold; answer
with: name the invariant, trace the break,
cost the fix)
Complexity honesty named the single-lock ceiling and when it
matters; sizing reasoned in words
Communication narrated lock scopes and signal targets
as you wrote them
Enjoying the preview?
Create a free account to unlock the rest of this course, the in-browser judge, and live AI mock interviews.