Implement a thread-safe one-shot **trigger** (a one-time event signal) in Python, then critique a buggy fragment a candidate proposed for it. The trigger wraps an internal boolean flag that is initially `False`. It exposes two methods: - `wait()` — blocks the calling thread until the trigger has fired. If the trigger has *already* fired, `wait()` must return immediately. - `fire()` — flips the flag to `True` (once) and wakes **every** thread currently blocked in `wait()`. Many threads may call `wait()` and `fire()` concurrently, so every access to the shared flag must be correctly synchronized. ### Constraints & Assumptions - Single-process, multi-threaded CPython using the standard `threading` module. - The trigger is **one-shot**: there is no `reset()` — once fired it never returns to the unfired state. `fire()` may be called more than once and is idempotent after the first fire. - A correct `wait()` must never block forever once a `fire()` has happened — including a `wait()` that arrives *after* the trigger already fired. - An unbounded number of threads may be parked in `wait()` simultaneously; `fire()` must release all of them. - Do **not** rely on the GIL for correctness; assume the implementation must be correct under the threading memory model (so it should still hold on a free-threaded, no-GIL build). - Memory/throughput are not the concern here — correctness under concurrency is. ### Clarifying Questions to Ask - Is the trigger strictly one-shot, or must it support `reset()` and re-firing? - Should `wait()` support an optional timeout, or always block indefinitely? - Must `fire()` be safe to call multiple times and from multiple threads simultaneously? - Should a `wait()` that arrives *after* `fire()` return immediately, or do only threads already blocked get woken? - Are we constrained to CPython with a GIL, or must the solution also be correct on a free-threaded (no-GIL) build? ### Part 1 — Implement the trigger Write a correct, thread-safe `Trigger` class satisfying the requirements above. Your `wait()` must not return before `fire()` has been observed, and a thread that calls `wait()` after the trigger has already fired must return without blocking. ```hint Primitive to reach for A bare `Lock` only gives mutual exclusion — it can't *wake* a sleeping thread, so it isn't enough on its own. What kind of synchronization object lets one thread block until another *signals* it, while still sharing a lock that guards the flag? Browse `threading` for the objects built to pair a lock with a wait/notify queue, or for a higher-level one that already packages "set once, all waiters pass." ``` ```hint The check-then-block gap The dangerous interleaving is on the *waiter* side: a thread checks the flag (sees `False`) and, *before* it actually parks, a firer sets the flag and notifies. If the notify lands in that gap, the waiter blocks forever (a lost wakeup). The waiter's "check predicate, then block" and the firer's "set flag, then notify" must each run while holding the **same** lock so they cannot interleave inside that window. ``` ```hint Re-check after waking A return from a condition-variable wait is not a promise that your flag is set: waits can return without a matching notify (spurious wakeups), and waking *every* blocked thread hands the lock back to them one at a time. Decide whether testing the flag *once* before blocking is enough, or whether the waiter must re-confirm the flag every time it wakes — and what loop construct that implies. ``` #### What This Part Should Cover - Chooses a primitive that can actually *wake* a blocked thread (a `Condition`, or the higher-level `Event`), not a bare `Lock`. - Protects both the flag read in `wait()` and the flag write in `fire()` under the *same* synchronization object, eliminating the check-then-block gap. - Handles the "fire-before-wait" case so late waiters return immediately, and releases *all* currently-parked waiters on fire (not just one). - Structures `wait()` as a `while` loop on the predicate so it cannot return on a stale or spurious wakeup. ### Part 2 — Critique the follow-up fragment Your interviewer proposes this body for `fire()`: ```python self.lock.acquire() self.lock.release() self.flag = True ``` Is this thread-safe? State yes or no and explain precisely *why*; describe a concrete interleaving of two threads that demonstrates the bug (e.g. a waiter that misses the trigger and blocks forever); and state the general rule it violates. ```hint What the lock actually guards A lock protects only the state accessed *while the lock is held* — it guards code regions, not a variable by proximity. Here the lock is acquired and immediately released, and *then* `self.flag = True` runs. Trace exactly which statements execute inside the critical section, and ask what protection the assignment still has once it sits after `release()`. ``` ```hint Don't lean on the GIL It's tempting to argue "the GIL serializes the assignment, so it's fine." The GIL makes the single store atomic, but it provides **no** ordering or wakeup guarantee relative to a waiter's check-then-block sequence. The bug is a missed-wakeup / ordering problem, not a torn-write problem — the GIL doesn't fix it. ``` #### What This Part Should Cover - A clear verdict that the fragment is **not** thread-safe, rooted in *which state the lock guards* — the assignment runs entirely outside the critical section, so the lock buys nothing. - A concrete missed-wakeup interleaving (a waiter that reads `False`, is preempted before parking, then blocks forever), not just "it could race." - Notes that the fragment also performs no notification at all, so even setting the flag could never wake a thread already parked in `wait()`. - Recognition that the GIL guarantees atomicity of the single store but not happens-before ordering or wakeup delivery across the check-then-block sequence. ### What a Strong Answer Covers These dimensions span both parts: - The unifying invariant: shared mutable state must be both *mutated* and *checked* while holding the lock that guards it, and for a wait/signal protocol the state change and the notification must be published together under that same lock — a lock guards code regions, not variables by association. - Memory-model discipline: correctness is argued from lock + condition guarantees, never from the GIL, so the design carries over to a free-threaded build. ### Follow-up Questions - Why must `wait()` re-check the predicate in a `while` loop rather than an `if`? - How would you add an optional `timeout` to `wait()` that returns a boolean indicating whether the trigger fired before the deadline? - How would you extend this into a *resettable* event (auto-reset vs manual-reset semantics, à la a Windows event object) without losing a concurrent fire? - If thousands of threads are parked in `wait()`, what are the performance implications of `notify_all()` versus `notify()`, and which is correct here?