Sincronización entre hilos

📐 Fundamento

Sección crítica (o región crítica): un fragmento de código que accede a estado compartido y por lo tanto no debe ejecutarse simultáneamente por más de un hilo.

Ejemplo del cap 2 (race condition):

contador++;     // ← sección crítica

Aunque parece una instrucción, son tres operaciones (leer, sumar, escribir). Si dos hilos las intercalan, se pisan.

Requisitos de un buen esquema de sincronización:

1. Exclusión mutua. Solo un hilo a la vez en la sección crítica.
2. Progreso. Si nadie está en la sección y varios quieren entrar, alguien (no nadie) entra eventualmente.
3. Espera acotada. Ningún hilo espera infinitamente — eventualmente todos pasan (sin starvation).

Lo que NO querés:

• Race condition — dos hilos pisándose, comportamiento dependiente del orden.
• Deadlock — todos esperan algo que nadie puede dar.
• Starvation — un hilo nunca obtiene su turno aunque siempre haya turnos.
• Livelock — hilos en movimiento pero sin progreso (como dos personas tratando de pasarse en un pasillo y bailando lateralmente).

Atomicidad. La operación es atómica si se ejecuta "todo o nada" — sin posibilidad de que otro hilo la vea a medio hacer. La CPU moderna ofrece instrucciones atómicas (CAS, compare-and-swap) que son la base de toda primitiva de sincronización superior.

📐 Fundamento

Antes de las primitivas correctas, vale ver intentos ingenuos:

Intento 1: variable booleana (mal)

bool ocupado = false;

void entrar() {
    while (ocupado) { /* espera */ }
    ocupado = true;
    // sección crítica
    ocupado = false;
}

Falla. Dos hilos pueden ver ocupado=false al mismo tiempo, los dos pasan el while, los dos ponen ocupado=true, los dos entran. Race condition adentro de la propia "solución".

Intento 2: deshabilitar interrupciones (mal)

void entrar() {
    cli();   // deshabilita interrupciones
    // sección crítica
    sti();   // las habilita
}

Falla. En multinúcleo, deshabilitar interrupciones en un núcleo no detiene otros núcleos. Y en modo usuario, cli no es siquiera permitido.

Intento 3: algoritmo de Peterson (correcto pero impráctico)

Hay algoritmos puramente en software (Peterson, Dekker, Lamport) que resuelven exclusión mutua para 2 o N hilos sin hardware especial. Funcionan, pero:

• Asumen modelos de memoria fuertes que las CPU modernas no respetan (necesitan memory barriers).
• Son busy-wait (hilo gasta CPU haciendo while).
• Difíciles de generalizar.

Conclusión: la sincronización correcta requiere soporte del hardware (instrucciones atómicas) y del SO (poner hilos a dormir cuando esperan).

📐 Fundamento

Mutex = abreviatura de "mutual exclusion". Es la primitiva más usada.

Operaciones:

• lock(m) — adquirir la cerradura. Si ya está tomada, bloquearse hasta que se libere.
• unlock(m) — liberar.

Garantías: solo un hilo posee la cerradura a la vez.

Ejemplo en C con pthreads:

#include <pthread.h>

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
int contador = 0;

void *incrementar(void *arg) {
    for (int i = 0; i < 1000000; i++) {
        pthread_mutex_lock(&lock);
        contador++;                  // ← protegido
        pthread_mutex_unlock(&lock);
    }
    return NULL;
}

Ahora dos hilos lanzados con incrementar dan siempre 2,000,000. La race condition desapareció.

Mismo código en Python:

import threading

lock = threading.Lock()
contador = 0

def incrementar():
    global contador
    for _ in range(1_000_000):
        with lock:
            contador += 1

with lock: es azúcar sintáctica equivalente a lock.acquire(); ...; lock.release(). Garantiza que se libera incluso si hay excepciones.

Implementación interna del mutex. El SO usa instrucciones atómicas como CAS (compare-and-swap):

CAS(addr, esperado, nuevo):
    si memoria[addr] == esperado:
        memoria[addr] = nuevo
        devolvé true
    sino:
        devolvé false

CAS es una sola instrucción del hardware, atómica. El mutex (simplificado) hace:

lock(m):
    while not CAS(&m, UNLOCKED, LOCKED):
        // dormir o reintentar

Si la cerradura está libre, CAS triunfa y el hilo entra. Si está ocupada, fracasa y reintenta (o el SO duerme al hilo y lo despierta cuando se libere).

Costo del mutex:

• Contención baja (poca pelea): muy barato (~10-50 ns).
• Contención alta: hilos se duermen, hay context switches, costo aumenta mucho.

Regla práctica: las secciones críticas deben ser lo más cortas posible. Cuanto más tiempo retenés el lock, más esperan los demás.

// ❌ Sección crítica gigante, mata el rendimiento
pthread_mutex_lock(&lock);
hacer_calculo_pesado();    // 5 segundos
escribir_resultado();      // 1 µs
pthread_mutex_unlock(&lock);

// ✅ Solo lo compartido va adentro
hacer_calculo_pesado();    // sin lock
pthread_mutex_lock(&lock);
escribir_resultado();
pthread_mutex_unlock(&lock);

📐 Fundamento

Semáforo (Dijkstra, 1965): generalización del mutex. En lugar de "abierto/cerrado", lleva un contador entero.

Operaciones (notación clásica):

• P(s) o wait(s): si $s > 0$, decrementá y seguí. Si $s = 0$, bloqueá.
• V(s) o signal(s): incrementá $s$. Si hay hilos bloqueados, despertá uno.

(P y V vienen del holandés proberen y verhogen.)

Casos:

• Semáforo binario (valor 0 o 1): equivale a un mutex.
• Semáforo de conteo: para limitar número de accesos concurrentes. Por ejemplo, "máximo 5 conexiones a la base de datos".

Ejemplo: pool de recursos limitados.

#include <semaphore.h>

sem_t pool;
sem_init(&pool, 0, 5);   // 5 recursos disponibles

void *trabajador(void *arg) {
    sem_wait(&pool);     // toma uno (espera si no hay)
    usar_recurso();
    sem_post(&pool);     // devuelve
    return NULL;
}

Si hay 100 hilos y pool=5, solo 5 usan el recurso al mismo tiempo. Los otros 95 esperan en sem_wait.

Otro uso: señalización entre hilos. Un hilo espera, otro avisa.

sem_t listo;
sem_init(&listo, 0, 0);  // empieza en 0

// Hilo A
sem_wait(&listo);        // bloquea hasta que B avise
hacer_algo();

// Hilo B
preparar_datos();
sem_post(&listo);        // avisa a A

Mutex vs semáforo:

El semáforo es más flexible pero más fácil de mal usar. Los mutex son la opción default; los semáforos para casos específicos.

📐 Fundamento

A veces no querés solo "exclusión mutua" — querés esperar a que algo pase. Por ejemplo: "espero a que la cola no esté vacía".

Variable de condición = primitiva para que un hilo se duerma esperando una condición, y otro hilo lo despierte cuando la condición se cumpla. Siempre va asociada a un mutex.

Operaciones:

• cond_wait(c, m) — atómicamente: libera el mutex m, duerme al hilo, y al despertarse re-adquiere m.
• cond_signal(c) — despierta a uno de los esperando.
• cond_broadcast(c) — despierta a todos.

Patrón canónico:

pthread_mutex_lock(&m);
while (!condicion) {
    pthread_cond_wait(&c, &m);
}
// la condición se cumple acá
hacer_algo();
pthread_mutex_unlock(&m);

Notá:

• while, no if. Cuando despertás, la condición puede haber cambiado (otro hilo se adelantó). Volvé a verificar.
• El mutex se libera durante la espera y se readquiere al despertar — todo atómicamente.

Ejemplo: cola con bloqueo.

typedef struct {
    int datos[N];
    int cantidad;
    pthread_mutex_t lock;
    pthread_cond_t no_vacia;
    pthread_cond_t no_llena;
} Cola;

void poner(Cola *c, int x) {
    pthread_mutex_lock(&c->lock);
    while (c->cantidad == N)
        pthread_cond_wait(&c->no_llena, &c->lock);
    c->datos[c->cantidad++] = x;
    pthread_cond_signal(&c->no_vacia);
    pthread_mutex_unlock(&c->lock);
}

int sacar(Cola *c) {
    pthread_mutex_lock(&c->lock);
    while (c->cantidad == 0)
        pthread_cond_wait(&c->no_vacia, &c->lock);
    int x = c->datos[--c->cantidad];
    pthread_cond_signal(&c->no_llena);
    pthread_mutex_unlock(&c->lock);
    return x;
}

Esa es la cola productor-consumidor clásica. Productores llaman poner, consumidores sacar. Las dos colas (no_vacia, no_llena) son señales mutuas — quien pone avisa a quien saca, y viceversa.

📐 Fundamento

Un monitor es un constructo de lenguaje que encapsula un mutex + variables de condición de manera que es difícil olvidar adquirir/liberar.

Idea: todos los métodos de un objeto se ejecutan bajo un mutex implícito del propio objeto. Solo un hilo a la vez está "dentro" del monitor.

En Java:

class ContadorSeguro {
    private int valor = 0;

    public synchronized void incrementar() {
        valor++;
    }

    public synchronized int leer() {
        return valor;
    }
}

synchronized automáticamente toma el mutex del objeto al entrar y lo libera al salir. No tenés que llamar lock/unlock.

Variables de condición en Java:

synchronized void poner(int x) throws InterruptedException {
    while (cantidad == N) wait();    // libera mutex y duerme
    datos[cantidad++] = x;
    notifyAll();                      // avisa a todos
}

wait() y notifyAll() son los equivalentes a cond_wait y cond_broadcast.

Por qué los monitores son lindos: evitan el error #1 de mutex en C — olvidar unlock al salir por excepción o return temprano. En lenguajes como Java, C# o Python (with), eso pasa automáticamente.

Crítica: un monitor obliga a serializar todos los accesos al objeto, incluso los de solo-lectura. Eso es ineficiente. Read-write locks y lock-free son alternativas más sofisticadas para casos de alta lectura concurrente.

📐 Fundamento

Los locks tienen costo y peligro. Hay alternativas:

Operaciones atómicas

Para casos simples (incrementar contador, fijar bandera), las CPU modernas ofrecen instrucciones atómicas. C11 y C++11 las exponen:

#include <stdatomic.h>
atomic_int contador = 0;

// Sin lock, atómicamente:
atomic_fetch_add(&contador, 1);

Equivalente Java: AtomicInteger. Python: el módulo threading no expone atómicos directos pero queue.Queue y similares los usan internamente.

Estructuras lock-free

Estructuras de datos que no usan locks sino CAS y otros trucos:

• Cola lock-free (Michael & Scott, 1996).
• Stack lock-free (Treiber).
• Hashmaps concurrentes (ConcurrentHashMap en Java).

Ventajas: alta concurrencia, no hay deadlock. Desventajas: muy difíciles de escribir bien (errores sutiles, livelock posible).

Mensajes en lugar de memoria compartida

Cambiar el modelo: en lugar de hilos compartiendo memoria, procesos/actores que se mandan mensajes. Sin estado compartido, no hay race conditions (solo orden de mensajes).

• Erlang/Elixir — el actor model en su esencia.
• Go — goroutines + channels.
• Rust — channels en std::sync::mpsc.

// Go: dos goroutines comunicándose por channel
ch := make(chan int)
go func() { ch <- 42 }()
val := <- ch    // bloquea hasta recibir

Rob Pike (uno de los autores de Go) lo resumió: "Don't communicate by sharing memory; share memory by communicating."

Tendencia moderna: los lenguajes nuevos (Go, Rust, Elixir) prefieren mensajes. Los viejos (Java, C++) prefieren memoria compartida + locks. Las dos enfoques son válidos, con casos donde uno gana al otro.