Building H2O — Semaphores + CyclicBarrier

Problem#

A stream of threads represents atoms — each hydrogen thread calls hydrogen(releaseHydrogen), each oxygen thread calls oxygen(releaseOxygen). The callbacks just print the atom's letter. Threads arrive in arbitrary order, but water molecules need exactly 2 hydrogen + 1 oxygen at a time.

The input "OOHHHHHHOO" must produce valid H2O molecules (e.g. HHO HHO HHO), with atoms possibly interleaved but never grouped incorrectly.

Think Before Coding#

Work through these before looking at the solution:

1. What limits how many atoms of each kind can proceed at once? A semaphore caps a count — set the initial permits to encode the 2:1 stoichiometry of water directly. What initial count does hydrogen need? What does oxygen need?

2. Why does the initial permit count matter? If oxygenSemaphore starts at 0, the first oxygen thread blocks on acquire() immediately. Since nothing else ever calls release() on it before an acquire() succeeds, oxygen never reaches the barrier — and then hydrogen threads, waiting for the 3-party barrier to trip, also hang forever. The whole program deadlocks.

3. Why a CyclicBarrier instead of manual counting? A barrier releases all waiting threads at once, exactly when N parties have arrived — and being cyclic means it auto-resets after each trip, so the same object handles every molecule in the stream without any extra state.

Implementation#

package BuildingH2O;

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

public class BuildingH2O {
    // 2 permits = at most 2 hydrogen atoms "in flight" toward one molecule
    private final Semaphore hydrogenSemaphore = new Semaphore(2);
    // 1 permit = at most 1 oxygen atom "in flight" at a time
    private final Semaphore oxygenSemaphore   = new Semaphore(1);
    private final AtomicInteger moleculeCount = new AtomicInteger(0);

    // Barrier trips only when exactly 3 threads have arrived (2H + 1O, enforced by semaphores above)
    private final CyclicBarrier cyclicBarrier = new CyclicBarrier(3, () -> {
        int count = moleculeCount.incrementAndGet();
        System.out.print(" [molecule #" + count + " formed] ");
    });

    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        hydrogenSemaphore.acquire();          // block if 2 hydrogens already waiting
        try {
            cyclicBarrier.await();            // wait until full H2O triplet assembled
            releaseHydrogen.run();            // print "H"
        } catch (Exception e) {
            Thread.currentThread().interrupt();
        } finally {
            hydrogenSemaphore.release();      // free a slot for the next molecule's hydrogen
        }
    }

    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        oxygenSemaphore.acquire();            // block if an oxygen is already waiting
        try {
            cyclicBarrier.await();            // wait until full H2O triplet assembled
            releaseOxygen.run();              // print "O"
        } catch (Exception e) {
            Thread.currentThread().interrupt();
        } finally {
            oxygenSemaphore.release();        // free the slot for the next molecule's oxygen
        }
    }
}

Key Design Decisions#

Semaphore initial permits encode stoichiometry

hydrogenSemaphore(2) and oxygenSemaphore(1) encode the 2:1 ratio directly. The semaphores prevent, say, three hydrogen threads from all racing past their acquire() into the same molecule — the third would block until one of the first two releases after its molecule completes.

CyclicBarrier(3, action) — one action per molecule, not per thread

The barrier action runs once per trip, executed by whichever thread happens to complete the triplet. The action increments moleculeCount and prints the molecule marker. All three threads then continue past await() together.

Cyclic = auto-reset

After each group of 3 crosses the barrier, it resets automatically. The same instance handles molecule 1, 2, 3, … without any manual reset or new barrier allocation.

finally releases the semaphore

Releasing inside finally ensures the permit goes back even if releaseHydrogen.run() or cyclicBarrier.await() throws — so a future molecule's atom isn't left permanently blocked waiting on a permit that was never returned.

The deadlock bug: oxygenSemaphore(0) instead of (1)

Starting oxygen at 0 permits means the first oxygen thread blocks on acquire() and never reaches the barrier. The two hydrogen threads that did acquire their semaphore reach the barrier and wait for a third party that never arrives. Everything hangs. The fix is exactly new Semaphore(1).

Demo#

package BuildingH2O;

public class Demo {
    public static void main(String[] args) throws InterruptedException {
        BuildingH2O h2o = new BuildingH2O();
        String input = "OOHHHHHHOO";
        Thread[] threads = new Thread[input.length()];

        for (int i = 0; i < input.length(); i++) {
            char atom = input.charAt(i);
            if (atom == 'H') {
                threads[i] = new Thread(() -> {
                    try { h2o.hydrogen(() -> System.out.print("H")); }
                    catch (InterruptedException e) { Thread.currentThread().interrupt(); }
                });
            } else {
                threads[i] = new Thread(() -> {
                    try { h2o.oxygen(() -> System.out.print("O")); }
                    catch (InterruptedException e) { Thread.currentThread().interrupt(); }
                });
            }
        }

        for (Thread t : threads) t.start();
        for (Thread t : threads) t.join();
        System.out.println("\nDone.");
    }
}

What to observe#

The output must group atoms into valid H2O triplets — any interleaving of HHO is fine (e.g. HOH, OHH), but you should never see HHH or OO adjacent. The [molecule #n formed] markers confirm each triplet completed before the next started.

HH [molecule #1 formed] OHH [molecule #2 formed] OHH [molecule #3 formed] O
Done.

(Exact interleaving within each molecule varies by thread schedule; grouping is always correct.)

Common Mistakes#