Nivel 5 · Investigación· Lección 8 de 9 · 45 min
Memoria débil y teoría de la concurrencia
Modelos de memoria formales — consistencia secuencial, TSO, el modelo de C++/Rust, pruebas de fuego (litmus tests), valores surgidos de la nada, linealizabilidad y model checking con loom.
El nivel 4 enseñó los órdenes de memoria de forma operacional. Esta lección examina la teoría que hay debajo: cómo se definen los modelos de memoria, qué se puede y qué no se puede demostrar sobre ellos, y cómo se enuncia formalmente la corrección de los objetos concurrentes.
La consistencia secuencial y por qué el hardware la abandona
La consistencia secuencial de Lamport (1979): el resultado de cualquier ejecución es como si todas las operaciones se hubieran ejecutado en algún orden total coherente con el orden del programa de cada hilo. Es el modelo que todo el mundo lleva en la cabeza: «los hilos se entrelazan».
Ningún multiprocesador moderno la implementa para los accesos normales a memoria, porque prohíbe dos cosas que hacen rápidos a los procesadores: los búferes de escritura (una escritura se encola localmente antes de llegar a la caché) y la ejecución fuera de orden. Los compiladores también la rompen: reordenar dos escrituras independientes es inobservable para un solo hilo, pero visible para otro.
Un modelo de memoria especifica qué comportamientos no secuencialmente consistentes se permiten. Hay tres clases que conviene no mezclar:
| Nivel | Ejemplos | Lo define |
|---|---|---|
| Hardware | x86-TSO, Armv8, RISC-V RVWMO, POWER | Las especificaciones de los fabricantes; formalizadas por Sewell, Alglave, Maranget y otros |
| Lenguaje | C/C++11 y posteriores, Rust (que adopta el de C++20), Java | El estándar del lenguaje |
| IR del compilador | LLVM | Sigue en su mayor parte a C++ |
El modelo del lenguaje debe ser lo bastante débil para compilarse con eficiencia a todas las plataformas y permitir optimizaciones, y lo bastante fuerte para programar contra él.
Pruebas de fuego (litmus tests)
Los modelos de memoria se estudian con programas diminutos que preguntan «¿está permitido este resultado?». Todas las variables empiezan en 0.
Store buffering (SB)
Hilo 1 Hilo 2
x := 1 y := 1
r1 := y r2 := x
¿Puede ser r1 = r2 = 0 ?
SC: no. x86-TSO: sí. Arm, POWER: sí. Rust: sí con Relaxed o con Release/Acquire; no con SeqCst.
Load buffering (LB)
Hilo 1 Hilo 2
r1 := x r2 := y
y := 1 x := 1
¿Puede ser r1 = r2 = 1 ?
Cada hilo parece leer un valor que el otro escribe más tarde. TSO: no. Las arquitecturas Arm y POWER lo permiten (los loads pueden satisfacerse tarde); los compiladores pueden producirlo reordenando el load y el store independientes. Rust con Relaxed: permitido.
Paso de mensajes (MP)
Hilo 1 Hilo 2
data := 42 r1 := flag
flag := 1 r2 := data
¿Puede ser r1 = 1 y r2 = 0 ?
TSO: no (los stores se mantienen en orden). Arm, POWER: sí. Rust: sí, si flag es Relaxed (y entonces además es una carrera de datos si data no es atómico: UB); no con un store Release y un load Acquire. Es el patrón de publicación del nivel 4.
Lecturas independientes de escrituras independientes (IRIW)
Hilo 1 Hilo 2 Hilo 3 Hilo 4
x := 1 y := 1 r1 := x; r2 := y r3 := y; r4 := x
¿Puede ser r1 = 1, r2 = 0, r3 = 1, r4 = 0 ? (los dos lectores discrepan sobre el orden de las escrituras)
TSO: no. POWER: sí; Armv8 lo prohíbe. Rust: permitido con loads Acquire; prohibido solo con SeqCst. Es el caso canónico en el que el orden total único de SeqCst da algo que AcqRel no puede dar.
El modelo de hardware, en una línea cada uno:
- x86-TSO (Sewell et al., 2010): cada núcleo tiene un búfer de escritura FIFO; los loads leen primero del búfer propio. Solo hay reordenación store→load. Es la razón de que tanto código lock-free incorrecto «funcione en mi máquina».
- Arm / RISC-V / POWER: los loads y los stores a direcciones distintas pueden reordenarse casi de cualquier manera si no hay dependencias ni barreras.
Las herramientas herd y diy generan y ejecutan miles de pruebas de este tipo contra modelos formales y contra chips reales.
El modelo de C++/Rust, de forma axiomática
El modelo del lenguaje (Boehm y Adve, 2008; formalizado por Batty et al., POPL 2011) es axiomático: en lugar de describir cómo avanza una máquina, define qué ejecuciones candidatas son consistentes.
Una ejecución es un grafo. Los nodos son eventos —lecturas, escrituras, actualizaciones (RMW)—, cada uno con una posición, un valor y un orden. Las aristas son relaciones:
sb(sequenced-before): el orden del programa dentro de un hilo.rf(reads-from): enlaza cada lectura con la escritura cuyo valor devuelve.mo(modification order): un orden total sobre las escrituras a cada posición atómica.sw(synchronises-with): de una escritura release a la lectura acquire que lee de ella; de un unlock a un lock; spawn; join.hb(happens-before): el cierre transitivo desb ∪ sw.sc: un orden total sobre todos los eventosSeqCst.
Una ejecución candidata es consistente si cumple una lista de axiomas, como: hb es acíclica; una lectura no lee de una escritura que ocurre después de ella, ni de una oculta por una escritura posterior que ocurre antes de la lectura (coherencia); los RMW son atómicos (ninguna escritura se interpone en mo entre el valor leído y el valor escrito); sc es coherente con hb y con mo.
Entonces:
- Se enumeran todas las ejecuciones consistentes del programa.
- Si alguna de ellas contiene una carrera de datos —dos accesos no atómicos en conflicto que
hbno ordena—, el programa tiene comportamiento indefinido. - En caso contrario, los comportamientos del programa son exactamente esas ejecuciones.
Dos teoremas lo hacen utilizable:
DRF-SC. Si toda ejecución SC de un programa está libre de carreras de datos y el programa solo usa atómicos
SeqCsty cerrojos, entonces todas sus ejecuciones son SC.
El Rust seguro está libre de carreras de datos. (Por el sistema de tipos,
Send/Syncy la corrección de las bibliotecas: RustBelt.)
Juntos: en Rust seguro con mutex y SeqCst puedes razonar por entrelazado. La memoria débil es algo que eliges, un Ordering cada vez.
Dos fallos famosos
SeqCst estaba mal
Los axiomas originales de C++11 para SeqCst, cuando se mezclaban con accesos más débiles a la misma posición, eran a la vez demasiado fuertes para implementarse con eficiencia en POWER y Arm y demasiado débiles para garantizar lo que los programadores esperaban. Lahav, Vafeiadis, Kang, Hur y Dreyer, «Repairing Sequential Consistency in C/C++11» (PLDI 2017), encontraron el problema y propusieron RC11; el arreglo se adoptó en C++20, que es el modelo al que se remite Rust.
Valores surgidos de la nada
Hilo 1 Hilo 2
r1 := x (relaxed) r2 := y (relaxed)
y := r1 (relaxed) x := r2 (relaxed)
¿Puede ser r1 = r2 = 42 ?
Nada en el programa escribe 42. Y sin embargo, las reglas axiomáticas, leídas al pie de la letra, admiten una ejecución en la que cada lectura «justifica» la escritura de la otra en un ciclo causal. Ningún hardware ni compilador la produce, y si estuviera permitida no podría demostrarse nunca ningún invariante sobre valores, y la propia seguridad de tipos fallaría (el 42 podría ser un puntero falsificado).
El arreglo evidente —prohibir los ciclos en sb ∪ rf, como hace RC11— prohíbe también el resultado de load buffering de arriba, que los compiladores reales sí producen cuando reordenan un load y un store independientes. Así que el arreglo simple cuesta rendimiento en Arm y POWER o prohíbe optimizaciones estándar.
Una semántica que permita el load buffering y las optimizaciones estándar a la vez que prohíbe los valores surgidos de la nada lleva siendo un problema abierto bastante más de una década. La respuesta más influyente es la semántica de promesas (promising semantics; Kang, Hur, Lahav, Vafeiadis y Dreyer, POPL 2017; «Promising 2.0», PLDI 2020): un modelo operacional en el que un hilo puede prometer una escritura futura, siempre que pueda certificar que será capaz de cumplir la promesa ejecutándose en aislamiento. Los ciclos que se justifican a sí mismos no se pueden certificar. Los estándares no la han adoptado; el texto de C++ dice, en la práctica, «las implementaciones no deberían hacer esto».
Modelos operacionales y axiomáticos
| Axiomático | Operacional | |
|---|---|---|
| Se define como | Predicados de consistencia sobre grafos de ejecución completos | Un sistema de transiciones con estado adicional (búferes, marcas de tiempo, vistas, promesas) |
| Sirve para | Pruebas de fuego, exploración exhaustiva de programas pequeños | Lógicas de programas, demostraciones por simulación, intérpretes |
| Ejemplos | C++11, RC11, los modelos «cat» de herd | x86-TSO, la semántica de promesas, ORC11, lo que implementa Miri |
La emulación de memoria débil de Miri es operacional: cada posición atómica guarda un búfer de los stores recientes, y un load puede devolver uno más antiguo, sujeto a la vista del hilo (un registro, parecido a un reloj vectorial, de lo que ya ha observado).
Demostrar que el Rust concurrente es correcto
¿Qué es «correcto»? Para un objeto concurrente, el criterio estándar es la linealizabilidad (Herlihy y Wing, 1990): toda historia concurrente es equivalente a una secuencial que respeta el orden en tiempo real de las operaciones que no se solapan. De forma equivalente —y esta es la forma que se usa en las demostraciones—, la implementación refina contextualmente una especificación atómica: ningún cliente puede distinguirlas (Filipović et al., 2010). Con memoria débil incluso esto requiere cuidado, puesto que el «orden en tiempo real» deja de ser simple.
Lógicas de programas para memoria débil. La lógica de separación se ha adaptado a los modelos no SC:
- RSL y FSL (Vafeiadis y Narayan, 2013; Doko y Vafeiadis): lógica de separación relajada para release/acquire y para los accesos relajados.
- GPS (Turon, Vafeiadis y Dreyer, 2014): estado fantasma, protocolos y separación para release/acquire.
- iGPS e iRC11: esas lógicas reconstruidas dentro de Iris, que es lo que usa RustBelt Meets Relaxed Memory (Dang, Jourdan, Kaiser y Dreyer, POPL 2020). Volvió a demostrar los resultados de RustBelt con ORC11, un modelo relajado con release/acquire y accesos relajados, y volvió a verificar
Arc. El esfuerzo de demostración descubrió un error real:Arc::get_mutusaba un loadRelaxeddonde hacía faltaAcquire, lo que admitía una carrera de datos. Se corrigió en la biblioteca estándar.
Merece la pena fijarse en el patrón. Dos veces —la restricción Sync de MutexGuard y el orden de Arc::get_mut— la verificación formal de la biblioteca estándar encontró errores que la revisión, las pruebas y años de uso en producción no habían encontrado.
Model checking
Las demostraciones son caras. El model checking sin estado explora exhaustivamente las ejecuciones de una prueba:
loom(proyecto Tokio): sustituyestd::syncystd::threadpor las versiones de loom bajocfg(loom); loom ejecuta la prueba con todos los entrelazados, usando reducción dinámica de orden parcial para saltarse los equivalentes, y modela los comportamientos débiles de los atómicos según el modelo de C11 (con algunas cotas y limitaciones: en particular, el tratamiento deSeqCstes aproximado, y no puede producir comportamientos de load buffering).shuttle(AWS): planificación aleatoria con garantías probabilísticas (PCT); escala a pruebas más grandes que la búsqueda exhaustiva.- GenMC (Kokologiannakis y Vafeiadis): un model checker exhaustivo paramétrico en un modelo de memoria axiomático (RC11, IMM). El trabajo para manejarlo desde Miri lleva a los programas de Rust una exploración de memoria débil correcta y completa.
- CDSChecker, RCMC, Nidhugg: el linaje de investigación.
// Una prueba con loom (crate: loom; se ejecuta con RUSTFLAGS="--cfg loom" cargo test --release)
#[cfg(loom)]
#[test]
fn message_passing_is_safe() {
use loom::sync::atomic::{AtomicBool, AtomicUsize, Ordering::*};
use loom::sync::Arc;
loom::model(|| {
let data = Arc::new(AtomicUsize::new(0));
let flag = Arc::new(AtomicBool::new(false));
let (d, f) = (data.clone(), flag.clone());
let t = loom::thread::spawn(move || {
d.store(42, Relaxed);
f.store(true, Release); // cámbialo a Relaxed y loom encuentra la ejecución que falla
});
if flag.load(Acquire) {
assert_eq!(data.load(Relaxed), 42);
}
t.join().unwrap();
});
}
Cuestiones abiertas
- Una semántica a nivel de lenguaje que prohíba los valores surgidos de la nada, permita todas las optimizaciones que se pretenden y se compile con eficiencia a todas las arquitecturas, y demostraciones de la corrección de la compilación a los modelos de Arm y RISC-V.
- La especificación y la verificación de algoritmos lock-free con recuperación segura de memoria bajo memoria débil.
- Criterios parecidos a la linealizabilidad y técnicas de refinamiento que sean correctos bajo memoria débil.
- La interacción de la memoria débil con el modelo de aliasing de Rust: las suposiciones de
noaliasen código concurrente. - Los accesos de tamaños mezclados y los atómicos compartidos con otros procesos o con el hardware (E/S mapeada en memoria), que el modelo del lenguaje excluye.
- Model checking escalable: explorar programas realistas, no pruebas de diez líneas.
Lista de lecturas
- Adve y Gharachorloo, «Shared Memory Consistency Models: A Tutorial» (1996): sigue siendo el mejor comienzo.
- Sewell et al., «x86-TSO: A Rigorous and Usable Programmer’s Model for x86 Multiprocessors» (CACM 2010).
- Boehm y Adve, «Foundations of the C++ Concurrency Memory Model» (PLDI 2008).
- Batty et al., «Mathematizing C++ Concurrency» (POPL 2011).
- Lahav et al., «Repairing Sequential Consistency in C/C++11» (PLDI 2017).
- Kang et al., «A Promising Semantics for Relaxed-Memory Concurrency» (POPL 2017).
- Alglave, Maranget y Tautschnig, «Herding Cats» (TOPLAS 2014).
- Herlihy y Wing, «Linearizability: A Correctness Condition for Concurrent Objects» (TOPLAS 1990).
- Dang et al., «RustBelt Meets Relaxed Memory» (POPL 2020).
- Kokologiannakis y Vafeiadis, «GenMC: A Model Checker for Weak Memory Models» (CAV 2021).
- Bos, Rust Atomics and Locks: para la práctica que esta teoría explica.
Ejercicios
- Para cada una de SB, LB, MP e IRIW, escribe el programa en Rust con atómicos e indica, para cada elección de orden, si el modelo del lenguaje permite el resultado débil.
- Dibuja el grafo de ejecución (
sb,rf,mo,sw) del resultado débil de MP con accesos relajados. Muestra que hacer release/acquire los accesos a la bandera crea un caminohbque el resultado contradice. - Ejecuta la prueba SB en un bucle de diez millones de iteraciones en tu máquina y cuenta los resultados
(0, 0). Después prueba la prueba MP en una máquina Arm (un teléfono o una Raspberry Pi). - Escribe la prueba con loom de arriba, cambia
ReleaseporRelaxedy lee la traza que falla. - Explica por qué el ejemplo de los valores surgidos de la nada amenaza la seguridad de tipos, y no solo la corrección funcional.
- Indica los puntos de linealización de un contador lock-free construido sobre
fetch_add, y delpushde la pila de Treiber. Después explica por qué «punto de linealización» es más difícil de definir con memoria relajada.
Comprueba lo que has entendido
Elige una respuesta para ver la explicación.
1.¿Qué afirma el teorema DRF-SC?
2.En la prueba de fuego de store buffering, ¿por qué pueden leer 0 los dos hilos en x86?
3.¿Qué es el problema de los valores surgidos de la nada (out-of-thin-air)?