De Java a Rust y Clojure: paradigmas de concurrencia

A lo largo del curso hemos razonado sobre corrección en programas concurrentes: linealizabilidad, consistencia secuencial, condiciones de progreso y estructuras lock-free. Todo ese análisis se ha hecho en Java. Sin embargo, los mismos problemas, y sus soluciones, se expresan de maneras radicalmente distintas en otros lenguajes. Esta práctica compara tres lenguajes que representan tres filosofías de diseño distintas ante el mismo problema: cómo lidiar con el estado compartido y el tiempo.

Una dimensión que el curso no ha explorado explícitamente es que las data races, ese fenómeno que en la Práctica 1 vimos producir resultados incorrectos, no son siempre un error. De hecho, algunas de las estructuras más eficientes que existen en la literatura explotan deliberadamente el comportamiento relajado de la memoria para lograr escalabilidad. Veremos un ejemplo concreto del libro de Herlihy & Shavit [HS08].

Contexto

Java: el modelo clásico de memoria compartida

Java nació en la era de los hilos del sistema operativo. Su modelo de concurrencia está basado en memoria compartida: todos los hilos viven en el mismo proceso y acceden al mismo heap. Cada hilo tiene su propia stack con variables locales, pero los objetos creados con new residen en el heap y son “visibles” para todos.

• Gestión de memoria: Heap compartido + stacks por hilo. Recolector de basura (GC) automático, evita fugas pero puede introducir pausas stop-the-world.

• Sincronización: Candados implícitos (synchronized) o explícitos (ReentrantLock). El programador protege secciones críticas manualmente.

• Volatile y fences: La palabra clave volatile garantiza visibilidad y establece barreras de memoria que impiden que el compilador o la CPU reordenen instrucciones. No garantiza atomicidad.

• Tipos atómicos: AtomicInteger, AtomicLong, AtomicReference, los mismos que usamos en las Prácticas 5 y 6 para operaciones CAS.

El modelo de memoria de Java (JMM), especificado en el JSR-133 [Manson et al., POPL 2005], define formalmente qué valores puede leer un hilo de una variable escrita por otro. El JMM es un ejemplo de modelo de memoria débil: el hardware moderno puede reordenar instrucciones y mantener cachés locales, y el JMM define exactamente cuándo esos reordenamientos son visibles, es el mismo tipo de modelo que estudia Herding Cats [Alglave et al., 2014].

Rust: concurrencia sin miedo (Fearless Concurrency)

Hola mundo en: https://github.com/gilde-valeria/gilde-valeria.github.io/blob/main/teaching/practicas/concurrencia-lenguajes/de-java-a-rust.org

Rust ataca el problema desde la raíz: el compilador rechaza programas con data races. Esto se logra sin un recolector de basura, a través de un sistema de tipos que rastrea en tiempo de compilación quién posee cada dato y cuándo se puede acceder a él.

• Gestión de memoria: Heap y Stack, sin GC. El sistema de Ownership (propiedad) y Borrowing (préstamo) garantiza que la memoria se libera exactamente cuando deja de usarse, sin pausas ni fugas.

• La regla de oro: En cualquier punto del programa, o existe una referencia mutable (&mut T), o existen múltiples referencias inmutables (&T), pero nunca ambas al mismo tiempo. Esta regla hace imposibles los data races, si el código compila, no tiene data races.

• Mutex acoplado al dato: Mutex<T> en Rust no solo protege el acceso, el dato vive dentro del Mutex. No puedes leer el dato sin antes adquirir el lock. En Java, el programador decide qué proteger; en Rust, el compilador lo impone.

• Compartir entre hilos: Arc<T> (Atomic Reference Counter), análogo a AtomicReference en Java, permite que múltiples hilos posean una referencia al mismo dato.

• Ordenamiento de memoria explícito: std::sync::atomic expone Ordering::SeqCst, Ordering::Acquire, Ordering::Release, el mismo vocabulario de barreras de memoria que Herding Cats formaliza.

Rust es el lenguaje preferido para programación de sistemas de bajo nivel donde el rendimiento y la ausencia de GC son críticos: sistemas operativos, drivers, contratos inteligentes en blockchain.

Clojure: estado, identidad y el tiempo

Hola mundo en: https://github.com/gilde-valeria/gilde-valeria.github.io/blob/main/teaching/practicas/concurrencia-lenguajes/de-java-a-clojure.org

Clojure corre sobre la JVM, por lo que hereda el heap, los stacks y el recolector de basura de Java. Sin embargo, su filosofía de concurrencia es radicalmente distinta: en lugar de proteger el acceso a la memoria, elimina el estado mutable por defecto.

• Inmutabilidad por defecto: Las estructuras de datos de Clojure (listas, vectores, mapas) son persistentes e inmutables. Modificar un vector no destruye el original, crea una nueva versión compartiendo estructura con el anterior (persistent data structures).

• Separación de identidad y estado: Clojure distingue entre la identidad (la referencia, ej. ‘la cuenta de Alice’) y el estado (el valor en un momento dado, ej. ‘1 000 pesos’). Los ref, atom y agent son tipos de identidad con diferentes semánticas de actualización.

• Para qué se usa en la industria: Nubank lo usa para su core bancario. Se usa en motores de emparejamiento (matching engines), procesamiento de eventos en tiempo real, y pipelines de datos. El STM brilla cuando necesitas actualizar múltiples variables coordinadamente sin riesgo de deadlock.

Software Transactional Memory (STM)

Las propiedades que garantiza el STM de Clojure son análogas a las propiedades ACID de una base de datos, pero en memoria:

La diferencia crucial frente a los candados: con STM no es posible un deadlock causado por el orden de adquisición de locks, porque no existen locks explícitos. La resolución de conflictos la hace el runtime, no el programador.

Data Races útiles: cuando la relajación es correcta

En la Práctica 1 vimos que un contador compartido sin sincronización produce resultados incorrectos. En la Práctica 5 analizamos los modelos de consistencia que formalizan exactamente qué significa ‘incorrecto’. Sin embargo, Herlihy y Shavit argumentan que existen situaciones donde permitir intencionalmente que un hilo lea un valor ‘obsoleto’ o ‘inconsistente’ es no solo aceptable, sino la base de implementaciones correctas y eficientes.

El contador de Consistencia Quiescente

El siguiente ejemplo, adaptado directamente de Herlihy & Shavit, muestra un contador concurrente que no es linealizable ni secuencialmente consistente, pero sí es quiescentemente consistente, y eso es suficiente para muchas aplicaciones de alto rendimiento.

import java.util.concurrent.atomic.AtomicLong;

/**
 * Adaptado de Herlihy & Shavit, The Art of Multiprocessor Programming,
 * Capitulo 5. Contador con Consistencia Quiescente.
 *
 * ADVERTENCIA INTENCIONAL: fetch() puede devolver un valor desactualizado
 * mientras hay incrementos en vuelo. La "data race" es deliberada:
 * el hilo lector puede ver un valor que no refleja los incrementos locales
 * de los otros hilos. Si todos los hilos cesan (quiescence), el valor
 * sera correcto.
 *
 * Propiedad: Quiescent Consistency (no Linearizable, no Seq. Consistent).
 */
public class QCSCounter {
    private final AtomicLong globalCount = new AtomicLong(0);
    private final int threshold;

    // La "data race" util: cada hilo tiene su copia local (stack privado).
    // No hay sincronizacion entre el ThreadLocal y globalCount
    // durante los incrementos -- eso es intencional.
    private final ThreadLocal<Long> local =
        ThreadLocal.withInitial(() -> 0L);

    public QCSCounter(int threshold) { this.threshold = threshold; }

    public void increment() {
        long current = local.get() + 1;
        if (current >= threshold) {
            globalCount.addAndGet(current); // volcado atomico al global
            local.set(0L);
        } else {
            local.set(current); // sin sincronizacion -- data race deliberada
        }
    }

    // fetch() puede ser incorrecto durante ejecucion concurrente
    // (ignora los contadores locales de otros hilos).
    public long fetch() { return globalCount.get(); }
}

¿Por qué es más rápido?

El costo de AtomicLong.incrementAndGet() bajo alta contención es alto: todos los núcleos intentan invalidar la misma línea de caché (cache line bouncing). El contador quiescente distribuye el trabajo: cada hilo escribe en su propia memoria (su stack, a través del ThreadLocal) y solo ocurre contención en el volcado al global, que sucede una vez cada threshold incrementos. El costo de 1 000 incrementos pasa de \(O(1{,}000)\) operaciones atómicas a \(O(1{,}000/\mathit{threshold})\) operaciones atómicas.

Esta es exactamente la idea detrás del SloppyCounter de la Práctica 5 y del árbol de difracción de Shavit: relajar la consistencia para ganar escalabilidad. La pregunta correcta no es ‘¿hay una data race?’ sino ‘¿qué modelo de consistencia necesita mi aplicación?’

Ejemplos Aplicados

¿Qué es un Smart Contract?

La conexión con el curso es directa: una blockchain debe garantizar que el estado global (el registro de balances) sea linealizable — cada transacción debe parecer que ocurrió en un único instante de tiempo real. Si no fuera linealizable, sería posible gastar el mismo saldo dos veces (el famoso double-spend problem).

¿Por qué Rust? Redes como Solana o Polkadot usan Rust para sus contratos inteligentes porque: (1) compila a WebAssembly (Wasm) o bytecode determinista, (2) no tiene Garbage Collector (las pausas GC son inaceptables cuando cada instrucción cuesta gas), y (3) el sistema de tipos garantiza ausencia de data races en tiempo de compilación — propiedad crítica cuando el contrato maneja valor real.

Contrato inteligente de tokens en Rust

use std::collections::HashMap;
use std::sync::{Arc, Mutex};
use std::thread;

/// Estado del contrato: un mapa de direcciones a balances.
/// El dato vive DENTRO del Mutex -- no se puede acceder sin el lock.
/// Arc permite que multiples hilos (transacciones) compartan la referencia.
struct TokenContract {
    balances: Mutex<HashMap<String, u64>>,
}

impl TokenContract {
    fn new() -> Self {
        let mut state = HashMap::new();
        state.insert("Alice".to_string(), 1000);
        state.insert("Bob".to_string(),    500);
        TokenContract { balances: Mutex::new(state) }
    }

    /// Punto de linearizacion: el momento en que lock() retorna.
    fn transfer(&self, from: &str, to: &str, amount: u64) -> bool {
        let mut b = self.balances.lock().unwrap();
        let from_bal = b.get(from).copied().unwrap_or(0);
        if from_bal < amount {
            println!("[RECHAZADA] {} no tiene fondos", from);
            return false;
        }
        *b.entry(from.to_string()).or_insert(0) -= amount;
        *b.entry(to.to_string()).or_insert(0)   += amount;
        println!("[OK] {} -> {} : {} tokens", from, to, amount);
        true
        // El Mutex se libera automaticamente al salir del scope (drop).
        // Equivale al bloque finally { lock.unlock(); } de Java,
        // pero garantizado por el compilador.
    }

    fn balance(&self, addr: &str) -> u64 {
        self.balances.lock().unwrap().get(addr).copied().unwrap_or(0)
    }
}

fn main() {
    let contract = Arc::new(TokenContract::new());
    let mut handles = vec![];

    for _ in 0..3 {
        let c = Arc::clone(&contract);
        handles.push(thread::spawn(move || {
            c.transfer("Alice", "Bob", 100);
        }));
    }
    for h in handles { h.join().unwrap(); }

    println!("Balance Alice: {}", contract.balance("Alice"));
    println!("Balance Bob:   {}", contract.balance("Bob"));
}

Transacciones bancarias en Clojure (STM)

El problema clásico de los candados para transferencias bancarias: para transferir de la cuenta \(A\) a la cuenta \(B\), hay que bloquear \(A\), luego bloquear \(B\). Si otro hilo bloquea \(B\) primero y luego \(A\), hay deadlock. Clojure elimina este problema completamente: no existen locks explícitos.

(ns banco.core)

;; 'ref' crea una identidad coordinable via STM.
;; @cuenta-alice dereferencia el ref para leer el valor actual.
(def cuenta-alice (ref 1000))
(def cuenta-bob   (ref  500))

(defn transferir
  "Transfiere cantidad de origen a destino de forma atomica.
   Si dos hilos colisionan, el STM reintenta automaticamente.
   No es posible deadlock: no hay locks, solo transacciones STM."
  [origen destino cantidad]
  (dosync                      ; abre la transaccion STM
    (let [saldo @origen]
      (if (>= saldo cantidad)
        (do
          ;; alter aplica una funcion al ref dentro de la transaccion.
          ;; Si hay conflicto al commit, dosync se reintenta.
          (alter origen  - cantidad)
          (alter destino + cantidad))
        (println "Fondos insuficientes")))))

;; 100 transferencias concurrentes de 5 pesos cada una
(defn simular []
  (let [fs (doall (repeatedly 100
                    #(future (transferir cuenta-alice cuenta-bob 5))))]
    (doseq [f fs] @f)
    (println "Alice:" @cuenta-alice)   ; esperado: 500
    (println "Bob:  " @cuenta-bob)     ; esperado: 1000
    (println "Total:" (+ @cuenta-alice @cuenta-bob)))) ; siempre 1500

(simular)

Tabla Comparativa

Ejercicios

Instrucciones:

• La práctica se resuelve en equipos de máximo 3 integrantes. Entrega un PDF con las respuestas teóricas y, para los ejercicios con código, una breve descripción de cada programa.

• Solo un integrante sube la práctica; los demás escriben un comentario privado con el nombre de quien entregó.

• El formato y el medio de entrega los indicará tu ayudante de laboratorio.

• Entornos: Java 21 LTS. Rust: instalar con
  curl –proto ’=https’ –tlsv1.2 -sSf https://sh.rustup.rs | sh
  Clojure: REPL en línea en https://tryclojure.org si no tienen instalación local.

Puntaje total: 100 Tiempo estimado: \(\approx\) 1 hr 30 min

Ejercicio 1 — Rust: el compilador como árbitro

[1hr / 50 puntos]

Este ejercicio tiene dos partes. En la primera intentarás escribir código incorrecto en Rust y observarás cómo el compilador lo rechaza. En la segunda extenderás el contrato inteligente del Listing [lst:rust] de la práctica.

Parte A: el rechazo del compilador (20 pts)

1. El siguiente código intenta replicar la race condition del contador de la Práctica 1 en Rust. Cópialo en un archivo race.rs, intenta compilarlo con rustc race.rs y pega el error del compilador en tu respuesta.

use std::thread;
 
fn main() {
    let mut counter: i64 = 0;   // variable en el stack del main
    let mut handles = vec![];
 
    for _ in 0..4 {
        // Intentamos pasar una referencia mutable a otro hilo
        handles.push(thread::spawn(|| {
            for _ in 0..1_000_000 {
                counter += 1;   // <- el compilador rechaza esto
            }
        }));
    }
    for h in handles { h.join().unwrap(); }
    println!("Contador: {}", counter);
}

1. Lee el mensaje de error del compilador. Identifica las frases clave y tradúcelas al vocabulario del curso: ?‘qué regla del sistema de Ownership/Borrowing se viola? ?‘Cómo se relaciona esa regla con la definición formal de data race (dos accesos concurrentes al mismo dato, al menos uno de escritura, sin sincronización)?

2. Corrige el código usando Arc<Mutex<i64>> para obtener el contador linealizable. Verifica que el resultado es siempre 4 000 000.

Parte B: extender el contrato (30 pts)

Extiende TokenContract del Listing [lst:rust] de la práctica añadiendo dos operaciones:

• mint(addr: &str, amount: u64) — crea amount nuevos tokens y los deposita en addr.

• burn(addr: &str, amount: u64) -> bool — destruye amount tokens de addr. Retorna false si la cuenta no tiene fondos suficientes.

1. Lanza 10 hilos concurrentes que ejecuten en un bucle de 100 iteraciones: cada hilo elige aleatoriamente entre transfer, mint y burn con montos pequeños. Al terminar todos, verifica que se cumple el siguiente invariante:

// suma_balances_actual == suma_balances_inicial + total_minted - total_burned
//
// Para verificarlo, rastrear total_minted y total_burned.
// Agregar contadores atomicos al SmartContract:
//   minted: AtomicU64
//   burned:  AtomicU64

1. Identifica el punto de linearización de mint() y de burn(). ?‘En qué línea exacta del código ocurre? ?‘Por qué el invariante se mantiene aunque haya 10 hilos modificando el estado simultáneamente?

Ejercicio 2 — Clojure: observar el STM en acción

[1hr min / 50 puntos]

En este ejercicio modificarás el código de Clojure para hacer observable el comportamiento interno del STM: cuántas veces reintenta transacciones, y qué pasa cuando introduces efectos secundarios dentro de un bloque transaccional.

Parte A: contando reintentos (25 pts)

1. Copia el código del Listing [lst:clj] de la práctica en un archivo (o en el REPL de https://tryclojure.org) y añade un contador de reintentos fuera del dosync:

(ns banco.core)
 
(def cuenta-alice (ref 1000))
(def cuenta-bob   (ref  500))
;; atom: actualizacion atomica sin coordinacion con otros refs
(def intentos (atom 0))
 
(defn transferir [origen destino cantidad]
  (dosync
    (swap! intentos inc)   ; <- DENTRO del dosync: corre en cada reintento
    (let [saldo @origen]
      (if (>= saldo cantidad)
        (do (alter origen  - cantidad)
            (alter destino + cantidad))
        nil))))
 
(defn simular [n monto]
  (reset! intentos 0)
  (let [fs (doall (repeatedly n
                    #(future (transferir cuenta-alice cuenta-bob monto))))]
    (doseq [f fs] @f)
    {:alice    @cuenta-alice
     :bob      @cuenta-bob
     :intentos @intentos
     :futuros  n}))
 
;; Ejecuta con distintos niveles de contencion:
(println (simular  10 10))
(println (simular 100 10))
(println (simular 500  5))

1. Ejecuta las tres llamadas a simular y registra los resultados. Para cada ejecución calcula:

   • Número de transferencias que realmente ocurrieron (cuántas veces cambió el saldo de Alice).

   • Número de intentos totales registrados.

   • Promedio de intentos por transacción exitosa.

2. ?‘Por qué el número de intentos aumenta con más hilos concurrentes? Explica en términos del protocolo STM: ?‘qué condición hace que una transacción se reintente? ?‘Puede haber livelock (todas las transacciones se reintenten indefinidamente)? ?‘El STM de Clojure garantiza progreso?

Parte B: efectos secundarios y pureza (25 pts)

1. Modifica transferir para añadir un println dentro del dosync:

(defn transferir-con-print [origen destino cantidad]
  (dosync
    (println "ejecutando transaccion")  ; efecto secundario en STM
    (let [saldo @origen]
      (if (>= saldo cantidad)
        (do (alter origen  - cantidad)
            (alter destino + cantidad))
        nil))))

1. Ejecuta (simular 50 10) usando esta versión. Cuenta cuántas veces se imprime "ejecutando transaccion" y cuántas transferencias realmente ocurrieron (cambios en el saldo). ?‘Son iguales? ?‘Por qué?

2. Relaciona tu observación con el principio: las funciones dentro de un dosync deben ser puras (sin efectos secundarios). ?‘Qué problema concreto introduce println dentro de la transacción? ?‘Cómo lo resolverías si realmente necesitaras registrar en un log cada transferencia exitosa?

Referencias

• Maurice Herlihy and Nir Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann, 2008. — Cap. 5 (Consistency, §5.3 Quiescent Consistency).

• Nir Shavit. Data structures in the multicore age. Commun. ACM, 54(3):76–84, 2011.

• Jeremy Manson, William Pugh, and Sarita V. Adve. The Java Memory Model. POPL 2005, pp. 378–391.

• Jade Alglave, Luc Maranget, and Michael Tautschnig. Herding Cats: Modelling, Simulation, Testing, and Data Mining for Weak Memory. ACM TOPLAS, 36(2):7:1–7:74, 2014.

• Paolo Viotti and Marko Vukolić. Consistency in Non-Transactional Distributed Storage Systems. ACM Comput. Surv., 49(1), 2016.

• The Rust Reference — Concurrency primitives. https://doc.rust-lang.org/std/sync/

• Rich Hickey. Clojure Refs and Transactions. https://clojure.org/reference/refs

← Volver al índice de prácticas