Este problema aborda a sincronização de threads para simular a formação de moléculas de água (H2O). Temos dois tipos de threads: hidrogênio ('H') e oxigênio ('O'). O objetivo é garantir que as threads se combinem corretamente para formar moléculas de água, com dois átomos de hidrogênio e um de oxigênio, respeitando as restrições de concorrência.

Cada thread, ao chegar a um ponto de sincronização (barreira), deve aguardar até que os componentes necessários para formar uma molécula de água estejam disponíveis. Se um thread de oxigênio chegar e não houver dois threads de hidrogênio esperando, ele deve aguardar. Similarmente, se um thread de hidrogênio chegar e não houver um oxigênio e outro hidrogênio disponíveis, ele também deve esperar.

A regra principal é que a formação de uma molécula de água deve ser concluída antes que a próxima possa começar. Isso implica que os contadores de hidrogênio e oxigênio devem ser resetados após cada formação bem-sucedida.

Exemplo 1:

Entrada: "HOH" Saída: "HHO"

Exemplo 2:

Entrada: "OOHHHH" Saída: "HHOHHO"

Restrições:

• O comprimento total da string de entrada é 3*n*, onde 1 ≤ *n* ≤ 50.
• O número total de 'H' na entrada é 2*n*.
• O número total de 'O' na entrada é *n*.

Solução Utilizando Locks e Conditions

Uma abordagem eficiente para resolver este problema é utilizando locks (ReentrantLock) e conditions (Condition) do pacote java.util.concurrent.locks. Isso oferece um controle mais granular sobre a sincronização em comparação com os métodos wait(), notify() e notifyAll() da classe Object.

Manteremos contadores para os átomos de hidrogênio e oxigênio que estão aguardando para formar uma molécula. Usaremos um lock para proteger o acesso a esses contadores e a lógica de formação de moléculas.

Para cada tipo de átomo, utilizaremos uma Condition associada ao lock. A thread de hidrogênio esperará na hydrogenCondition se já houver dois hidrogênios aguardando. A thread de oxigênio esperará na oxygenCondition se já houver um oxigênio aguardando.

Quando um átomo é liberado (ou seja, seu método run() é chamado), seu respectivo contador é incrementado. Em seguida, verificamos se a condição para formar uma molécula de água (2 hidrogênios e 1 oxigênio) foi atendida. Se sim, resetamos os contadores e sinalizamos (usando signalAll()) ambas as condições. Isso acorda todas as threads que estavam esperando, permitindo que elas reavaliem suas condições de espera.

O uso de volatile para os contadores garante que as alterações feitas por uma thread sejam visíveis para as outras imediatamente.

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

class H2O {
    private final Lock moleculeLock = new ReentrantLock();
    private final Condition hydrogenWait = moleculeLock.newCondition();
    private final Condition oxygenWait = moleculeLock.newCondition();

    // Contadores voláteis para garantir visibilidade entre threads
    private volatile int pendingHydrogen = 0;
    private volatile int pendingOxygen = 0;

    public H2O() {
        // Construtor vazio
    }

    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        moleculeLock.lock();
        try {
            // Aguarda se já existirem 2 átomos de hidrogênio aguardando
            while (pendingHydrogen == 2) {
                hydrogenWait.await();
            }
            
            // Libera o átomo de hidrogênio e incrementa o contador
            releaseHydrogen.run();
            pendingHydrogen++;
            
            // Verifica se uma molécula pode ser formada
            checkAndFormMolecule();
        } finally {
            moleculeLock.unlock();
        }
    }

    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        moleculeLock.lock();
        try {
            // Aguarda se já existir 1 átomo de oxigênio aguardando
            while (pendingOxygen == 1) {
                oxygenWait.await();
            }
            
            // Libera o átomo de oxigênio e incrementa o contador
            releaseOxygen.run();
            pendingOxygen++;
            
            // Verifica se uma molécula pode ser formada
            checkAndFormMolecule();
        } finally {
            moleculeLock.unlock();
        }
    }
    
    private void checkAndFormMolecule() {
        // Se a combinação para uma molécula de água for completa
        if (pendingHydrogen == 2 && pendingOxygen == 1) {
            // Reseta os contadores para a próxima molécula
            pendingHydrogen = 0;
            pendingOxygen = 0;
            
            // Sinaliza todas as threads esperando para que possam tentar formar a próxima molécula
            hydrogenWait.signalAll();
            oxygenWait.signalAll();
        }
    }
}

Solução Utilizando Sincroinzação Padrão (synchronized, wait, notifyAll)

Uma alternativa é utilizar os mecanismos de sincronização intrínsecos do Java: o bloco synchronized e os métodos wait(), notifyAll(). Embora menos flexível que locks e conditions, esta abordagem também pode resolver o problema corretamente.

O princípio é semelhante: usamos um objeto this como monitor para o bloco synchronized. Dentro dele, verificamos as contagens de hidrogênio e oxigênio. Se as condições de espera forem atendidas (por exemplo, se já houver dois hidrogênios esperando), a thread chama wait() para liberar o monitor e entrar em estado de espera. Caso contrário, a thread executa sua ação (run()), icnrementa o contador arpopriado e, se uma molécula for formada, reseta os contadores e chama notifyAll() para acordar todas as threads em espera.

class H2O {
    private int hydrogenCount = 0;
    private int oxygenCount = 0;

    public H2O() {
        // Construtor vazio
    }

    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        synchronized (this) {
            // Aguarda se já houver 2 hidrogênios esperando
            while (hydrogenCount == 2) {
                wait();
            }
            
            // Libera o hidrogênio e incrementa o contador
            releaseHydrogen.run();
            hydrogenCount++;
            
            // Verifica se uma molécula completa foi formada
            if (hydrogenCount == 2 && oxygenCount == 1) {
                // Reseta contadores e notifica outras threads
                hydrogenCount = 0;
                oxygenCount = 0;
            }
            
            // Notifica todas as threads em espera
            notifyAll();
        }
    }

    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        synchronized (this) {
            // Aguarda se já houver 1 oxigênio esperando
            while (oxygenCount == 1) {
                wait();
            }
            
            // Libera o oxigênio e incrementa o contador
            releaseOxygen.run();
            oxygenCount++;
            
            // Verifica se uma molécula completa foi formada
            if (hydrogenCount == 2 && oxygenCount == 1) {
                // Reseta contadores e notifica outras threads
                hydrogenCount = 0;
                oxygenCount = 0;
            }
            
            // Notifica todas as threads em espera
            notifyAll();
        }
    }
}