September 25, 2025

Building Water with Multithreading in Java: H2O Problem Explained

Introduction

Multithreading is one of the core concepts in computer programming where multiple threads run concurrently. Synchronizing these threads is crucial to avoid race conditions and ensure proper execution order.

A popular interview problem in this domain is the H2O problem, where the goal is to simulate the formation of water molecules using threads.

Problem Statement

We have two types of threads:

  • Hydrogen threads (H)

  • Oxygen threads (O)

The goal is to form water molecules (H₂O), which means each water molecule requires exactly 2 hydrogen threads and 1 oxygen thread.

The constraints are:

  1. No thread can “bond” until a complete molecule can form.

  2. Threads must pass the barrier in groups of three (2H + 1O).

  3. Threads from one molecule must bond before threads from the next molecule can start.

Essentially, we need synchronization to make sure water molecules are formed correctly in a multithreaded environment.

Intuition Behind the Solution

Think of this as a barrier problem:

  • We have hydrogen threads and oxygen threads arriving randomly.

  • A hydrogen thread must wait if there isn’t an oxygen thread and another hydrogen thread available.

  • An oxygen thread must wait if there aren’t two hydrogen threads available.

  • Once a complete molecule is ready (1 O + 2 H), all three threads “bond” together.

We can solve this using semaphores and barriers.

Key Concepts Used

1. Semaphore

A semaphore is a thread synchronization tool that allows a limited number of threads to access a resource at the same time.

  • Semaphore(n) allows n threads to acquire permits.

  • acquire() reduces the available permits.

  • release() increases the available permits.

In this problem:

  • Hydrogen semaphore allows 2 permits (max 2 H threads per molecule).

  • Oxygen semaphore allows 1 permit (max 1 O thread per molecule).

2. CyclicBarrier

A CyclicBarrier is a synchronization aid that allows a set of threads to wait for each other.

  • Once the required number of threads reach the barrier, all are released simultaneously.

  • Here, we use CyclicBarrier(3) because a molecule requires 3 threads (2 H + 1 O).

Step-by-Step Solution

Here’s the code:

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

class H2O {

    private Semaphore hydrogenSemaphore;
    private Semaphore oxygenSemaphore;
    private CyclicBarrier barrier;

    public H2O() {
        hydrogenSemaphore = new Semaphore(2); // max 2 hydrogen threads
        oxygenSemaphore = new Semaphore(1);   // max 1 oxygen thread
        barrier = new CyclicBarrier(3);       // wait for 3 threads to form a molecule
    }

    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        hydrogenSemaphore.acquire(); // acquire hydrogen slot

        try {
            barrier.await();  // wait until a molecule can form
        } catch (Exception e) {
            e.printStackTrace();
        }

        releaseHydrogen.run();  // release hydrogen (print H)
        hydrogenSemaphore.release(); // free hydrogen slot
    }

    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        oxygenSemaphore.acquire(); // acquire oxygen slot

        try {
            barrier.await(); // wait until 2 hydrogens are available
        } catch (Exception e) {
            e.printStackTrace();
        }

        releaseOxygen.run();  // release oxygen (print O)
        oxygenSemaphore.release(); // free oxygen slot
    }
}

How the Solution Works

  1. Hydrogen Threads:

    • Acquire a hydrogen permit.

    • Wait at the CyclicBarrier until 1 oxygen + 1 more hydrogen arrive.

    • Once all 3 threads arrive, the barrier releases them simultaneously.

  2. Oxygen Threads:

    • Acquire an oxygen permit.

    • Wait at the CyclicBarrier until 2 hydrogen threads arrive.

    • Once the barrier is complete, the oxygen and two hydrogen threads bond.

  3. Guarantees:

    • No partial molecule formation: threads wait at the barrier.

    • Threads from the next molecule don’t proceed until the current molecule completes.

    • Correct number of threads per molecule due to semaphores.

Example Output

If threads arrive in the order H H O H H O:

H H O H H O

This is valid because every 3 threads form a molecule.

Why This Approach Works

  • Semaphores control the maximum number of hydrogen and oxygen threads per molecule.

  • CyclicBarrier ensures all threads wait until a complete molecule is ready.

  • This combination guarantees safe and correct synchronization.

Alternative approaches might use locks + condition variables, but semaphores + barrier is simpler and cleaner.

Key Takeaways

  1. Think in terms of resources and limits: hydrogen and oxygen slots.

  2. Use a barrier for group synchronization: wait until all threads needed for a molecule arrive.

  3. Ensure atomic molecule formation: threads from one molecule must bond together before next molecule forms.

  4. This pattern is useful for thread grouping problems in general, not just H2O.

This approach is easy to learn, scalable, and safe for multithreading.

If you want, I can also make a visual diagram showing how threads wait at the barrier and release—this makes it even easier to understand.

Do you want me to make that diagram?

By