Problem 12 Building H2O

The invariant, and why a permit leak breaks it

Hydrogen and oxygen threads arrive in any order; you must let them through only in complete molecules — two H and one O bond together, and no extra hydrogen may slip ahead. Two mechanisms compose to enforce this: counting semaphores cap how many of each element can stage (2 H, 1 O), and a barrier of 3 makes the staged 2H+1O wait for each other before any of them "bonds" (prints). The old version released more permits than it took (oxygen did hSem.release(2) while each hydrogen also released), so the hydrogen permit count drifted upward and more than two H could pass between oxygens — the invariant silently broke.

Correct Java

import java.util.concurrent.Semaphore;
import java.util.concurrent.CyclicBarrier;

class H2O {
    private final Semaphore hSem = new Semaphore(2);   // at most 2 H staged
    private final Semaphore oSem = new Semaphore(1);   // at most 1 O staged
    private final CyclicBarrier barrier = new CyclicBarrier(3); // 2H + 1O assemble

    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        hSem.acquire();
        await();                       // wait for the full molecule
        releaseHydrogen.run();
        hSem.release();                // release ONLY my own permit
    }
    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        oSem.acquire();
        await();
        releaseOxygen.run();
        oSem.release();
    }
    private void await() {
        try { barrier.await(); }
        catch (Exception e) { Thread.currentThread().interrupt(); }
    }
}

The barrier auto-resets after every group of 3, so molecule after molecule forms correctly, and each thread releases exactly the one permit it acquired — the counts never drift.

Correct Go (buffered channels as semaphores + a reusable barrier)

Go has no built-in CyclicBarrier, so we build a tiny reusable one from a mutex + condition; the semaphores are buffered channels (a slot = a permit).

type H2O struct {
    h chan struct{} // cap 2
    o chan struct{} // cap 1
    mu sync.Mutex; cond *sync.Cond; count int
}
func New() *H2O { x := &H2O{h: make(chan struct{},2), o: make(chan struct{},1)}; x.cond = sync.NewCond(&x.mu); return x }

func (x *H2O) barrier() {            // releases in groups of 3
    x.mu.Lock(); x.count++
    if x.count%3 == 0 { x.cond.Broadcast() } else { for x.count%3 != 0 { x.cond.Wait() } }
    x.mu.Unlock()
}
func (x *H2O) Hydrogen(release func()) { x.h <- struct{}{}; x.barrier(); release(); <-x.h }
func (x *H2O) Oxygen(release func())   { x.o <- struct{}{}; x.barrier(); release(); <-x.o }

Why the counts do the real work — a worked leak

The whole design rests on one arithmetic fact: the barrier trips at exactly 3 arrivals, and the only way to get 3 arrivals is 2 H + 1 O — because hSem caps concurrent hydrogens at 2 and oSem caps oxygens at 1 (2 + 1 = 3). The semaphore counts are not a throttle for performance; they are what types the barrier's three slots. Break the count and a barrier of 3 will happily trip on the wrong composition. The old bug had oxygen call hSem.release(2) in addition to each hydrogen releasing its own — so hSem inflated past 2. Trace it:

Step 4 is the invariant break made concrete: with hSem > 2, three hydrogens satisfy the barrier's party count by themselves and "bond" into an HHH molecule with no oxygen present. The failure is silent — the program never throws, it just emits chemically impossible output. That is the signature of a count bug: correctness is decided by an integer you have to keep exactly right, and the barrier faithfully enforces whatever (wrong) grouping the counts allow.

Pitfalls

• Release only the permit you acquired. Cross-releasing (O releasing H's permits) inflates the count and lets the invariant break — the original defect.
• Without the barrier, the semaphores alone would let 2 H bond with no oxygen present; the barrier is what ties the triple together.
• BrokenBarrierException / interrupted await: if any party is interrupted at barrier.await(), Java's CyclicBarrier breaks — all other waiters throw BrokenBarrierException, and subsequent awaits fail until you reset() or replace the barrier. Production code must either fail the whole batch (propagate and stop admitting H/O) or reset() only when you know no threads are still mid-molecule. Do not swallow the exception and retry with a broken barrier.

try {
    barrier.await();
} catch (InterruptedException e) {
    Thread.currentThread().interrupt();
    // barrier is now broken for others — stop producing molecules
    throw e;
} catch (BrokenBarrierException e) {
    // peer failed; do not release() as if molecule formed
    throw new IllegalStateException("molecule assembly aborted", e);
}

When a barrier is the wrong tool

CyclicBarrier is the right primitive here precisely because the party count is fixed (always 3) and the rendezvous repeats molecule after molecule. Reach for something else when either assumption breaks: for a one-shot rendezvous with no reuse, CountDownLatch is lighter; when parties join or drop out dynamically, use Phaser (its register / arriveAndDeregister adjust the party count at runtime, which a barrier cannot). And never substitute a bare mutex + counter with no reset protocol — if the third thread never arrives, the first two are parked forever with no way to rearm the group.

Why not a single lock + counters, then? You can solve H2O with one mutex, an h/o counter, and a condition variable: a hydrogen blocks until h < 2, increments, and when h == 2 && o == 1 some thread signals the trio to proceed and resets the counters. It works — but you have just hand-rolled the semaphore-cap-plus-barrier out of raw parts, and the reset step (who zeroes the counters, and when, so a late thread from molecule k can't be counted into molecule k+1) is exactly the error-prone bookkeeping the barrier gives you for free with its automatic re-arm. Prefer the two composed primitives: the counts and the rendezvous are each expressed declaratively, so there is no reset protocol left to get wrong. Drop to the manual monitor only when the grouping rule is too irregular for a fixed party count (e.g. "bond whatever is staged every 100ms").

Where this pattern generalizes. H2O is one instance of assemble a fixed heterogeneous group of N before anyone proceeds: per-type semaphores type the members, a barrier of N does the rendezvous. The same shape appears in request batching (hold callers until a batch of N is staged, then flush together), phased parallel algorithms (every worker must finish iteration i before any starts i+1 — a barrier of worker-count), and staged pipelines that need a full crew before a stage runs. The tell that this pattern fits: the group size is fixed and known, and progress is all-or-nothing for the group. When the count varies at runtime, that fixed party count is exactly what forces you off a barrier and onto a Phaser or a manual monitor.

Takeaways

• Compose two primitives: semaphores bound how many stage; the 3-party barrier bonds the complete molecule.
• A self-resetting barrier (Java CyclicBarrier) handles molecule-after-molecule for free.
• Every acquire pairs with exactly one matching release — permit conservation is the whole game.

Re-authored for correctness for this guide (the prior version leaked semaphore permits, breaking the 2:1 ratio). Pattern: LeetCode 1117 "Building H2O". See also: Semaphore, Barriers, Condition Variables.