Concurrency Problems

📘 Learn Concurrency Problems from zero

Concurrency problems reward a calm, disciplined process far more than cleverness. Use the same loop every time.

1. Read & restate. Say out loud what the threads are and what each must do. The decisive question is always: what state is shared, and what ordering must hold? Most "hard" concurrency problems become easy once you name these two things.
2. Pin the constraints. Number of threads, fixed vs. dynamic? Is output order required, or just correctness? Bounded resources (buffer size, N philosophers)? Termination condition? These dictate the primitive.
3. Brute force first — and make it correct, not fast. Start with one big lock (synchronized) around all shared state. A correct serialized version is your baseline; never optimize before it works. This also exposes exactly which sections actually contend.
4. Spot the pattern. Map the problem to a canonical shape: mutual exclusion (locks/atomics), signaling/ordering (semaphores, condition variables, latches), rendezvous (barriers), producer–consumer (blocking queues), or deadlock avoidance (lock ordering / arbiter). Name it before you code.
5. Optimize deliberately. Shrink critical sections, swap a global lock for fine-grained locks or lock-free atomics, partition work across a pool and reduce. Each step trades simplicity for throughput — justify it.
6. Edge cases & correctness checks. Spurious wakeups (always re-check the condition in a while loop, never an if), deadlock (hold-and-wait + circular wait), livelock, starvation/fairness, and clean shutdown. Reason about the worst interleaving, not the happy path.
7. Test. Run with many threads and high iteration counts; concurrency bugs are probabilistic. State your invariant ("at most N at the table," "H:O is 2:1 in every prefix") and argue why no interleaving breaks it.

Be encouraged: the primitive almost always falls out of step 4 once you've honestly answered step 1.

✨ Added by the guide to build intuition — not from the source course.

🎯 Guided practice

Worked example: Building H2O (Problem 12). Hydrogen and oxygen threads each call a hydrogen() / oxygen() method that takes a "release" runnable; you must release them in groups that form one water molecule — exactly 2 H and 1 O bonding together before any thread of the next molecule proceeds.

Step 1 — name the shared state and ordering. Two requirements jump out: (a) a ratio constraint — never let 3 H bond, or 2 O, in one group; and (b) a rendezvous — the three threads of one molecule must all arrive before any are released. That second word, "rendezvous," is the loudest signal.

Step 2 — match signal to technique. "A group of fixed size must all arrive, then proceed together" is the textbook trigger for a barrier (CyclicBarrier(3)): when the third thread arrives, all three cross. But the barrier alone can't enforce the 2:1 ratio — without admission control, three hydrogens could pile into the same barrier. So we add counting semaphores as admission gates: hSem with 2 permits and oSem with 1 permit. This pairing — a semaphore for "how many of each may enter," a barrier for "all bond at once" — is the canonical mutual-exclusion-plus-rendezvous combination.

Step 3 — outline the optimal.

1. Init Semaphore hSem = new Semaphore(2), Semaphore oSem = new Semaphore(1), CyclicBarrier barrier = new CyclicBarrier(3).
2. hydrogen(): hSem.acquire() → barrier.await() → releaseHydrogen.run() → hSem.release().
3. oxygen(): oSem.acquire() → barrier.await() → releaseOxygen.run() → oSem.release().

Emit the atom after barrier.await() returns, not before — that is the canonical accepted form, because the bond is printed only once the full molecule is confirmed present, so the output reads as one molecule at a time.

Why it's correct: the semaphores cap concurrent entrants at exactly 2 H and 1 O, so only one molecule's worth of threads can be past acquire() at a time. barrier.await() blocks until all three of that group are present — guaranteeing they bond as a set — and CyclicBarrier auto-resets the moment it trips. Permits are released only after await() returns, so a thread of the next molecule can't acquire until the current three have crossed. The invariant ("at most 2 H and 1 O between acquire and release") holds under every interleaving. The teaching point: when one constraint is "ratio/count" and another is "all-arrive-together," don't force one primitive to do both — layer a semaphore (admission) under a barrier (rendezvous).

✨ Added by the guide — work these before the full problem set.