FerrousPath

Nivel 4 · Experto· Lección 6 de 9 · 40 min

Estructuras de datos lock-free

Garantías de progreso, la pila de Treiber, el problema ABA, la recuperación de memoria con épocas y hazard pointers, y la linealizabilidad.

Garantías de progreso

Propiedad Garantía
Bloqueante Un hilo que tiene un cerrojo puede detener a todos (si el planificador lo desaloja, o si muere).
Obstruction-free Un hilo que se ejecuta solo termina en un número acotado de pasos.
Lock-free Algún hilo siempre termina en un número acotado de pasos. Hilos concretos pueden sufrir inanición.
Wait-free Todo hilo termina en un número acotado de sus propios pasos.

Lock-free no significa más rápido. Significa que ningún hilo puede impedir que el sistema progrese, algo valioso en manejadores de señales, contextos de interrupción, código de tiempo real y bajo mucha contención. Un mutex bien ajustado suele ganar en caudal. Mide.

La pila de Treiber

La estructura lock-free más simple (Treiber, 1986) es una pila enlazada cuya cabeza es un puntero atómico.

use std::ptr;
use std::sync::atomic::{AtomicPtr, Ordering};
use std::thread;

struct Node<T> {
    value: T,
    next: *mut Node<T>,
}

pub struct Stack<T> {
    head: AtomicPtr<Node<T>>,
}

// SAFETY: los valores se mueven entre hilos a través de la pila; los nodos son propiedad suya.
unsafe impl<T: Send> Send for Stack<T> {}
unsafe impl<T: Send> Sync for Stack<T> {}

impl<T> Stack<T> {
    pub const fn new() -> Self {
        Stack { head: AtomicPtr::new(ptr::null_mut()) }
    }

    pub fn push(&self, value: T) {
        let node = Box::into_raw(Box::new(Node { value, next: ptr::null_mut() }));
        let mut head = self.head.load(Ordering::Relaxed);
        loop {
            // SAFETY: `node` todavía no está compartido; somos su único dueño.
            unsafe { (*node).next = head };
            // Release: publica el contenido del nodo para quien cargue `head`.
            match self.head.compare_exchange_weak(head, node, Ordering::Release, Ordering::Relaxed) {
                Ok(_) => return,
                Err(actual) => head = actual,
            }
        }
    }

    /// Extrae todos los elementos de una vez. A salvo del problema ABA y del uso después de liberar,
    /// porque tras el swap este hilo es dueño de toda la lista separada.
    pub fn take_all(&self) -> Vec<T> {
        let mut node = self.head.swap(ptr::null_mut(), Ordering::Acquire);
        let mut out = Vec::new();
        while !node.is_null() {
            // SAFETY: la lista se separó de forma atómica; ningún otro hilo puede alcanzar estos nodos.
            let boxed = unsafe { Box::from_raw(node) };
            node = boxed.next;
            out.push(boxed.value);
        }
        out
    }
}

impl<T> Drop for Stack<T> {
    fn drop(&mut self) {
        self.take_all();
    }
}

fn main() {
    let stack = Stack::new();
    thread::scope(|s| {
        for t in 0..4u32 {
            let stack = &stack;
            s.spawn(move || for i in 0..1000 { stack.push(t * 1000 + i) });
        }
    });
    let mut all = stack.take_all();
    all.sort_unstable();
    println!("{} items, all distinct: {}", all.len(), all.windows(2).all(|w| w[0] != w[1]));
}

push es el bucle de CAS canónico: lee la cabeza, prepara el nodo, intenta cambiar la cabeza y reintenta si falla. Es correcto tal como está escrito.

Fíjate en lo que falta: un pop que extraiga un elemento. Ahí es donde vive la dificultad.

Por qué pop es difícil

La implementación evidente:

// ⚠ INCORRECTO (unsound) — no lo uses. Se muestra para explicar los errores.
pub fn pop(&self) -> Option<T> {
    loop {
        let head = self.head.load(Ordering::Acquire);
        if head.is_null() {
            return None;
        }
        let next = unsafe { (*head).next };            // (1) desreferencia
        if self.head.compare_exchange_weak(head, next, // (2) cambia la cabeza
            Ordering::AcqRel, Ordering::Relaxed).is_ok()
        {
            let node = unsafe { Box::from_raw(head) }; // (3) libera
            return Some(node.value);
        }
    }
}

Error 1: uso después de liberar. El hilo A carga head y el planificador lo desaloja antes del paso (1). El hilo B extrae el mismo nodo y lo libera en (3). El hilo A se reanuda y desreferencia memoria liberada.

Error 2: ABA. La pila es A → B → C. El hilo 1 lee head = A, next = B, y se detiene. El hilo 2 extrae A, extrae B (liberándolo) y apila un nodo nuevo que el asignador coloca en la dirección A. La pila es ahora A → C. El hilo 1 se reanuda; su CAS ve head == A y tiene éxito, instalando B —un nodo liberado— como cabeza.

Los dos vienen de un mismo hecho: en una estructura lock-free, desenlazar un nodo no significa que nadie tenga todavía un puntero a él. Los lenguajes con recolector de basura nunca ven ninguno de los dos errores, porque un nodo no puede liberarse ni reutilizarse mientras está referenciado. En Rust necesitas un esquema de recuperación segura de memoria.

Recuperación de memoria

Recuperación basada en épocas

Los hilos anuncian cuándo están dentro de una región crítica («fijados»). Una época global solo avanza cuando todos los hilos fijados han observado la actual. Un nodo desenlazado en la época e se puede liberar cuando la época llega a e + 2, porque para entonces no puede quedar ningún hilo que estuviera fijado durante e.

  • Sobrecoste muy bajo en el camino de lectura: fijar y desfijar son un par de operaciones locales al hilo.
  • Un hilo fijado que se detiene retrasa toda la recuperación: en el peor caso, el uso de memoria no está acotado.

crossbeam-epoch lo implementa. Una pila de Treiber correcta con él:

// crate: crossbeam-epoch
use crossbeam_epoch::{self as epoch, Atomic, Owned};
use std::mem::ManuallyDrop;
use std::ptr;
use std::sync::atomic::Ordering::{Acquire, Relaxed, Release};

struct Node<T> {
    value: ManuallyDrop<T>,
    next: Atomic<Node<T>>,
}

pub struct Stack<T> {
    head: Atomic<Node<T>>,
}

impl<T> Stack<T> {
    pub fn new() -> Self {
        Stack { head: Atomic::null() }
    }

    pub fn push(&self, value: T) {
        let mut node = Owned::new(Node { value: ManuallyDrop::new(value), next: Atomic::null() });
        let guard = epoch::pin();
        loop {
            let head = self.head.load(Relaxed, &guard);
            node.next.store(head, Relaxed);
            match self.head.compare_exchange(head, node, Release, Relaxed, &guard) {
                Ok(_) => return,
                Err(e) => node = e.new, // recupera el nodo y reintenta
            }
        }
    }

    pub fn pop(&self) -> Option<T> {
        let guard = epoch::pin(); // mientras estemos fijados, los nodos que vemos no se liberarán
        loop {
            let head = self.head.load(Acquire, &guard);
            // SAFETY: `head` se leyó estando fijados, así que o es nulo o sigue reservado.
            let node = unsafe { head.as_ref() }?;
            let next = node.next.load(Relaxed, &guard);
            if self.head.compare_exchange(head, next, Release, Relaxed, &guard).is_ok() {
                // SAFETY: el CAS tuvo éxito, así que desenlazamos el nodo y somos el único hilo
                // que leerá su valor. La liberación se aplaza hasta que no quede ningún hilo fijado.
                unsafe {
                    guard.defer_destroy(head);
                    return Some(ptr::read(&*node.value));
                }
            }
        }
    }
}

fn main() {
    let s = Stack::new();
    std::thread::scope(|scope| {
        for t in 0..4 {
            let s = &s;
            scope.spawn(move || for i in 0..1000 { s.push(t * 1000 + i); s.pop(); });
        }
    });
    println!("empty afterwards: {}", s.pop().is_none());
}

Fijar arregla directamente el uso después de liberar, y arregla también el ABA: una dirección no puede reutilizarse mientras esté fijado algún hilo que todavía pudiera compararse con ella.

Hazard pointers

Cada hilo publica, en un hueco compartido, el puntero que está a punto de desreferenciar, y después vuelve a comprobar que el puntero sigue siendo alcanzable. Un hilo que quiere liberar un nodo recorre todos los huecos de hazard; los nodos que aparecen en ellos se guardan para más tarde.

  • Basura acotada: como máximo (hilos × hazards por hilo) nodos están alguna vez a la espera de recuperarse.
  • Cada acceso protegido cuesta un store y una barrera al estilo de SeqCst, así que las lecturas son más lentas que con épocas.

Crates: haphazard, seize (un esquema híbrido).

Otras estrategias

  • Conteo de referencias: un Arc en un hueco atómico (arc-swap), o contadores divididos/diferenciales. Simple; pone escrituras en el camino de lectura.
  • Punteros etiquetados / contadores de versión: empaquetar un contador en los bits sin usar del puntero (o usar un CAS de doble ancho) para que A tras la reutilización sea distinto del A original. Resuelve el ABA pero no el uso después de liberar; es adecuado cuando los nodos vienen de un pool que nunca se devuelve al asignador.
  • Evitar el problema. Las colas de un solo consumidor, las colas acotadas sobre un array (crossbeam::ArrayQueue) y las operaciones de «llévatelo todo» como el take_all de arriba no necesitan ningún esquema de recuperación.

Corrección: linealizabilidad

¿Cómo se enuncia siquiera que una pila concurrente es correcta? El criterio estándar (Herlihy y Wing, 1990) es la linealizabilidad: toda operación parece surtir efecto de forma atómica en un único instante —su punto de linealización— entre su invocación y su respuesta, y la historia secuencial resultante es legal para el tipo de datos.

En la pila de Treiber, el punto de linealización de un push o un pop con éxito es su CAS con éxito; para un pop que devuelve None, es el load que leyó nulo. Identificar esos puntos es el primer paso de cualquier argumento de corrección, y de cualquier demostración formal.

Pruebas

  • loom: sustituye los tipos de std::sync por los de loom, escribe pruebas pequeñas, y loom explora todos los entrelazados dentro de unos límites, incluidos los resultados de memoria débil. Indispensable.
  • Miri con muchas semillas (-Zmiri-many-seeds) para las carreras de datos y el uso después de liberar.
  • ThreadSanitizer y pruebas de estrés en hardware ARM con muchos núcleos.
  • Comprobadores de linealizabilidad que registran historias y buscan un orden secuencial válido.

Prefiere las implementaciones auditadas —crossbeam, parking_lot, dashmap, flume— a la tuya. Escribe la tuya para aprender, con todas las herramientas de arriba activadas.

Lecturas recomendadas

  • Herlihy y Shavit, The Art of Multiprocessor Programming: el libro de texto.
  • Michael y Scott (1996), «Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms».
  • Michael (2004), «Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects».
  • Fraser (2004), Practical Lock-Freedom: el origen de la recuperación basada en épocas.
  • Aaron Turon (2015), «Lock-freedom without garbage collection»: el diseño que hay detrás de crossbeam-epoch.

Ejercicios

  1. Añade is_empty y un pop a la primera pila protegiendo toda la estructura con un spin lock. Compara su rendimiento con Mutex<Vec<T>> con 1, 4 y 16 hilos.
  2. Reproduce sobre el papel el escenario ABA del pop incorrecto con tres nodos, escribiendo los pasos de cada hilo en una línea de tiempo.
  3. Implementa la cola de Michael–Scott con crossbeam-epoch. ¿Dónde están sus puntos de linealización?
  4. Escribe una prueba con loom para la primera pila con dos hilos que apilan, y comprueba que los dos valores están presentes.
  5. Implementa un búfer circular de un solo productor y un solo consumidor con dos índices AtomicUsize. ¿Por qué no necesita recuperación de memoria ni sufre el problema ABA?

Comprueba lo que has entendido

Elige una respuesta para ver la explicación.

  1. 1.¿Qué garantiza *lock-free*?

  2. 2.¿Qué es el problema ABA?

  3. 3.¿Por qué una pila lock-free no puede simplemente hacer Box::from_raw de un nodo en cuanto se extrae?

Términos clave de esta lección

¿Has terminado la lección y los ejercicios?