Building H2O

medium concurrency semaphore synchronization

Problem

There are hydrogen and oxygen threads calling hydrogen() and oxygen(). To form water molecules, atoms must bond in groups of exactly two hydrogen and one oxygen. Every group of three threads must release together before any thread from the next molecule proceeds. Given an input string of H and O with twice as many H as O, output any ordering where every consecutive group of three contains exactly two H and one O.

Inputwater = "HOH"

Output"HHO"

Two H and one O are gathered, then released together as one molecule. "HOH" or "OHH" are equally valid.

water (H and O only, 2× as many H as O)

from threading import Semaphore

class H2O:
    def __init__(self):
        self.h = Semaphore(2)   # up to 2 H may enter
        self.o = Semaphore(0)   # O blocked until 2 H ready
        self.barrier = 0        # H arrived in current molecule

    def hydrogen(self, releaseHydrogen):
        self.h.acquire()
        releaseHydrogen()       # emit one "H"
        self.barrier += 1
        if self.barrier == 2:   # second H signals O
            self.o.release()

    def oxygen(self, releaseOxygen):
        self.o.acquire()
        releaseOxygen()         # emit one "O"
        self.barrier = 0
        self.h.release()        # refill 2 H permits
        self.h.release()

class H2O {
  constructor() {
    this.hPermits = 2;   // up to 2 H may enter
    this.oPermits = 0;   // O blocked until 2 H ready
    this.barrier = 0;    // H arrived in current molecule
  }
  hydrogen(releaseHydrogen) {
    this.hPermits--;          // acquire an H permit
    releaseHydrogen();        // emit one "H"
    this.barrier++;
    if (this.barrier === 2) this.oPermits++;  // signal O
  }
  oxygen(releaseOxygen) {
    this.oPermits--;          // acquire the O permit
    releaseOxygen();          // emit one "O"
    this.barrier = 0;
    this.hPermits += 2;       // refill 2 H permits
  }
}

import java.util.concurrent.Semaphore;

class H2O {
    private Semaphore h = new Semaphore(2); // up to 2 H may enter
    private Semaphore o = new Semaphore(0); // O blocked until 2 H
    private int barrier = 0;                // H in current molecule

    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        h.acquire();
        releaseHydrogen.run();   // emit one "H"
        if (++barrier == 2) o.release();  // second H signals O
    }

    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        o.acquire();
        releaseOxygen.run();     // emit one "O"
        barrier = 0;
        h.release(2);            // refill 2 H permits
    }
}

#include <semaphore.h>

class H2O {
    sem_t h, o;     // h starts at 2, o starts at 0
    int barrier = 0;
public:
    H2O() { sem_init(&h, 0, 2); sem_init(&o, 0, 0); }

    void hydrogen(function<void()> releaseHydrogen) {
        sem_wait(&h);
        releaseHydrogen();       // emit one "H"
        if (++barrier == 2) sem_post(&o);  // second H signals O
    }

    void oxygen(function<void()> releaseOxygen) {
        sem_wait(&o);
        releaseOxygen();         // emit one "O"
        barrier = 0;
        sem_post(&h); sem_post(&h);  // refill 2 H permits
    }
};

Explanation

Many threads call hydrogen() and oxygen() at once, but a water molecule needs exactly two H and one O. The job is to make threads wait for each other so they only proceed in valid groups of three. We do this with two semaphores, which are just permit-counters that block when they hit zero.

The H semaphore starts with 2 permits, so at most two hydrogen threads can enter at a time. The O semaphore starts at 0, so any oxygen thread is blocked immediately until something releases a permit to it.

Each hydrogen thread acquires an H permit, emits "H", and increments barrier. When the second H arrives (barrier == 2), it releases one O permit — the signal that two hydrogens are ready and an oxygen may now run.

The oxygen thread, once unblocked, emits "O", resets barrier to 0, and releases two H permits with self.h.release() twice. That refills the H semaphore so the next molecule's two hydrogens can enter, and the cycle repeats.

Example: with input "HOH", two H threads pass the Semaphore(2) and emit H, H; the second one releases O; the O thread then emits O and refills the permits — producing one valid molecule like "HHO".

Time: O(n) Space: O(1)