N-of-M Barrier Synchronization
Hydrogen and Oxygen threads must pair into water, exactly 2 H + 1 O before any can release. The pattern: two semaphores controlling H/O entry + a CyclicBarrier of 3 ensuring all three threads of a molecule are present before any prints.
The setup
This shows up on LeetCode as "Building H2O". The picture is simple. Many threads are running. Some of them are "hydrogen", some are "oxygen". They want to print themselves, but with one rule: a hydrogen or oxygen thread can only print as part of a complete water molecule. A molecule needs exactly two hydrogens and one oxygen, all three printing as a group, before the next molecule can start.
So if four hydrogens and four oxygens show up in some random order, the right output is something like HHO HHO HHO HHO. The threads have to figure out, on their own, how to form those groups of three.
The job is to write hydrogen() and oxygen() so that:
- Two hydrogens and one oxygen always print together as one molecule, in any internal order.
- A third hydrogen does not get to print until the previous molecule has fully finished.
- Nobody busy-waits.
A picture of one round
Two things have to happen at the same time:
- Cap who is allowed in. At most two hydrogens and one oxygen can be inside the "trying to form a molecule" zone. The third hydrogen waits at the door.
- Release them as a group. Once all three are in, all three are released together. None of them prints alone.
The pattern: a gate plus a meeting point
The clean way to solve this is to use two pieces, each one doing one job.
One primitive per concern
- A counting gate per type, to control how many can enter. This is what a semaphore does. Set the hydrogen gate to allow 2 at a time and the oxygen gate to allow 1 at a time. Extra threads of either type wait at the door.
- A meeting point that only releases everyone once all three have arrived. This is what a barrier does. A barrier of size 3 makes each thread block until the other two have also reached it, then lets all three through together.
After the three threads pass the meeting point and print, the gates refill and the next batch can come in.
The gates handle "how many of each type", the barrier handles "release them together". Each piece is small and easy to reason about. Trying to do both with one shared counter and a mutex is where the bugs come from.
Why this pattern is worth remembering
The same shape comes up any time a system has to wait for a fixed mix of things before moving forward.
- Quorum voting in distributed systems. A leader election in Raft or Paxos waits for replies from a majority of nodes before declaring a winner. That is "N of M" in a different costume.
- Batch processing. A training loop collects K samples before running a gradient step. The collector is the gate; the step is the barrier.
- Build pipelines. A package step waits until 3 compile jobs and 1 link job all finish before it runs. Same gate + barrier shape, with different counts.
Once you have done H2O, every problem of the form "wait for exactly N of A and M of B, then release them together" solves the same way.
The trap interviewers watch for The shortcut answer is "I will use one shared counter and a mutex". It can be made to work, but only after you have hand-rolled all the things the gate and barrier give you for free: counting per type, blocking when full, signaling when the count is right, waking the right threads, resetting for the next molecule. Each one is a place to introduce a bug. The composed answer (gate + barrier) splits the problem into two named primitives that each do one thing.
A short follow-up worth knowing
If the interviewer asks "what happens if one thread dies between entering the gate and reaching the meeting point?", the answer is that the barrier breaks. The other two threads of that molecule are stuck waiting forever unless the barrier knows how to fail them.
Java's CyclicBarrier handles this with BrokenBarrierException: when one party fails, the barrier marks itself broken, the other waiters throw, and the barrier resets so the next batch can start clean. In Go you do not get this for free, you have to track each batch yourself with a counter and a condition variable, and reset on failure.
Implementations
Two semaphores cap concurrent entries (2 H, 1 O). Once all three threads enter, the CyclicBarrier of 3 unblocks them simultaneously. After printing, semaphores are released → next molecule's H/O can enter.
1 import java.util.concurrent.Semaphore;
2 import java.util.concurrent.CyclicBarrier;
3
4 class H2O {
5 private final Semaphore hSem = new Semaphore(2);
6 private final Semaphore oSem = new Semaphore(1);
7 private final CyclicBarrier barrier = new CyclicBarrier(3);
8
9 public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
10 hSem.acquire();
11 try { barrier.await(); }
12 catch (Exception e) { Thread.currentThread().interrupt(); return; }
13 releaseHydrogen.run();
14 hSem.release();
15 }
16
17 public void oxygen(Runnable releaseOxygen) throws InterruptedException {
18 oSem.acquire();
19 try { barrier.await(); }
20 catch (Exception e) { Thread.currentThread().interrupt(); return; }
21 releaseOxygen.run();
22 oSem.release();
23 }
24 }Key points
- •Pattern: rate-limiting semaphore + barrier
- •Hydrogen semaphore = 2 permits; Oxygen semaphore = 1 permit; both refill after barrier
- •CyclicBarrier(3) ensures the 2 H + 1 O appear together before any prints
- •After barrier, semaphores reset, next molecule's H and O begin