Building H2O — Concurrency en Go

Planteamiento del Problema

El problema Building H2O de LeetCode consiste en simular la formación de moléculas de agua a partir de átomos de hidrógeno y oxígeno. Cada molécula de H₂O necesita dos átomos de hidrógeno y un átomo de oxígeno.

Se nos proporcionan dos funciones callback:

• releaseHydrogen() — libera un átomo de H
• releaseOxygen() — libera un átomo de O

El reto es sincronizar los hilos para que siempre se formen moléculas completas sin condiciones de carrera.

Estrategia de Resolución

Para resolverlo necesitamos tres mecanismos de sincronización:

1. Semáforos para controlar cuántos átomos de cada tipo pueden estar activos simultáneamente
2. Una barrera reutilizable para que exactamente 3 hilos (2H + 1O) esperen hasta que todos hayan llegado
3. Un mutex con variable de condición para implementar la barrera

Implementación en Go

package main

import "sync"

type H2O struct {
	hSem chan struct{} // semaphore: capacity 2
	oSem chan struct{} // semaphore: capacity 1

	mu    sync.Mutex
	cond  *sync.Cond
	count int // threads currently at the barrier
	gen   int // barrier generation
}

func NewH2O() *H2O {
	h := &H2O{
		hSem: make(chan struct{}, 2),
		oSem: make(chan struct{}, 1),
	}
	h.cond = sync.NewCond(&h.mu)
	return h
}

// Reusable barrier for exactly 3 threads.
func (h *H2O) waitBarrier() {
	h.mu.Lock()
	g := h.gen
	h.count++

	if h.count == 3 {
		h.count = 0
		h.gen++
		h.cond.Broadcast()
		h.mu.Unlock()
		return
	}

	for g == h.gen {
		h.cond.Wait()
	}
	h.mu.Unlock()
}

func (h *H2O) Hydrogen(releaseHydrogen func()) {
	// Acquire hydrogen slot.
	h.hSem <- struct{}{}

	// Wait until 2H + 1O have arrived.
	h.waitBarrier()

	releaseHydrogen()

	// Release hydrogen slot.
	<-h.hSem    
}

func (h *H2O) Oxygen(releaseOxygen func()) {
	// Acquire oxygen slot.
	h.oSem <- struct{}{}

	// Wait until 2H + 1O have arrived.
	h.waitBarrier()

	releaseOxygen()

	// Release oxygen slot.
	<-h.oSem
}

Explicación del Código

Semáforos con Canales

Usamos canales con buffer como semáforos:

• hSem — buffer de capacidad 2, permite máximo 2 hidrógenos activos
• oSem — buffer de capacidad 1, permite máximo 1 oxígeno activo

Cada hilo adquiere un "slot" antes de entrar a la barrera (hSem <- struct{}{}) y lo libera al salir (<-hSem). Esto garantiza que nunca haya más de 2H y 1O compitiendo por formar una molécula.

Barrera Reutilizable

La función waitBarrier() implementa una barrera para exactamente 3 hilos usando un patrón clásico con sync.Cond:

1. El primer y segundo hilo que llegan incrementan count y se bloquean en cond.Wait()
2. El tercer hilo (el que completa el grupo) resetea count, incrementa gen y hace Broadcast() para despertar a todos
3. Los hilos despertados verifican que su generación ya pasó y continúan

Conclusión

Este problema demuestra cómo combinar semáforos (canales) con barreras reutilizables para resolver problemas clásicos de concurrencia. Es una solución elegante que respeta los principios de la synchronización en Go:

• Canales para control de acceso (semáforos)
• Mutex + Cond para coordinación grupal (barrera)
• Generaciones para hacer la barrera reutilizable

El patrón es aplicable a muchos otros problemas de concurrencia donde necesitas que un número fijo de goroutines se sincronicen en un punto antes de continuar.