Introducción

Etimología: del griego ‘ατομον’ (átomos). Indivisible.
En concurrencia, una operación atómica es aquella que no puede observarse parcialmente: o sucede completa, o no sucede. Estas operaciones permiten que varios hilos trabajen sobre las mismas variables de forma segura.
Estas operaciones deben estar soportadas por la arquitectura del procesador para el que se genera el código ejecutable. Sobre estas primitivas se construyen abstracciones de nivel superior como los mutex.
A lo largo de este tema usaremos Rust como lenguaje de referencia.
Modelo de memoria adoptado. Rust adopta el modelo de memoria para atómicas de C++20 (heredado y revisado desde C++11). Aunque es un modelo complejo y con defectos conocidos y corregidos a lo largo del tiempo, tiene la ventaja de ser probado, estándar y con herramientas que ayudan a entenderlo y usarlo correctamente. Puedes usar la documentación de C++ como guía incluso si no programas en C++.

En el resto del tema, veremos por qué surgen los problemas (reordenación por compilador y hardware), qué garantías necesitamos expresar (relación happens-before), y cómo se materializan mediante órdenes de memoria (SeqCst, Acquire/Release, Relaxed). Finalmente, repasaremos la API de atómicas en Rust, sus tipos, el enumerado Ordering y algunos ejemplos de uso.

Origen de los problemas.

Reordenación del compilador

Los compiladores reordenan para eliminar dependencias de datos y código muerto. Esto puede cambiar el orden de los eventos o hacer que algunos no ocurran nunca. Ejemplo:
```
x = 1;
y = 3;
x = 2;
```
puede transformarse en
```
x = 2;
y = 3;
```

Fíjate que:
1. Se ha invertido el orden de eventos
2. Se ha eliminado uno de ellos.
Desde un punto de vista de monohilo el estado final coincide.
En código multihilo podríamos estar asumiendo que a x se le asignara un 1 antes de que a y se le asignara un valor.
El beneficio de reordenar (eficiencia) choca con la necesidad de confiar en el orden observado entre hilos.

Reordenación del hardware

Las CPUs disponen de memoria cache, normalmente de dos tipos: de datos y de instrucciones.

$ lscpu
...
Caches (sum of all):
L1d:                   256 KiB (8 instances)
L1i:                   256 KiB (8 instances)
L2:                    8 MiB (8 instances)
L3:                    11 MiB (1 instance)

Cuando una CPU accede a un dato, mira en su cache si lo tiene y si lo tiene no comprueba en la RAM si ambos valores coinciden.
El resultado final es que el hardware no puede garantizar que los eventos que ocurren en un orden en un hilo ocurren en el mismo orden en otro hilo.
Y para garantizar que sea así (mismo orden en ambos hilos) debemos dar instrucciones a la CPU para que tenga en cuenta ciertas consideraciones.

Supongamos el siguiente código:
```
initial state: x = 0, y = 1

THREAD 1        
y = 3;          
x = 1;          

THREAD 2
if x == 1 {
    y *= 2;                        
}
```
¿Qué posibles salidas tiene este código?
- y = 3: El hilo 2 hizo la comparación antes de que el hilo 1 terminara.
- y = 6: El hilo 2 hizo la comparación después de que el hilo 1 terminara.
- y = 2: El hilo 2 vio x = 1 pero no y = 3 y sobreescribe y = 3.

Arquitecturas strongly-ordered vs. weakly-ordered.

Hay que tener en cuenta que esta reordenación depende del hardware (CPU).
Para garantizar órdenes concretos debemos dar instrucciones explícitas a la CPU.
Cada CPU proporciona distintas garantías.
Podemos distinguir CPUs por el tipo de orden que imponen:
1. strongly-ordered, p.e. x86_64
2. weakly-ordered, p.e. ARM.
El hardware impone un orden base pero el programa puede pedir garantías adicionales (o más débiles).

Pedir garantías más fuertes a un hardware que ya, de por sí, es fuertemente ordenado tiene un coste nimio o incluso cero.
Las garantías más débiles solo proporcionarán ganancias de rendimiento en un hardware débilmente ordenado.
Es muy probable que pedir garantías demasiado débiles a un hardware fuertemente ordenado “funcione” (aunque el programa sea estrictamente incorrecto).
En consecuencia, un programa concurrente debería probarse en hardware débilmente ordenado.

Acceso a datos vs. acceso atómico

El acceso a datos convencional es, por defecto, no sincronizado; el compilador optimiza agresivamente asumiendo monohilo y el hardware puede propagar las escrituras de forma perezosa/inconsistente entre hilos. Resultado: con solo acceso a datos es imposible escribir código sincronizado correcto.
Necesitamos accesos atómicos para comunicar al compilador y al hardware que el programa es multihilo y para expresar relaciones de orden (happens-before), que el modelo de memoria formaliza. Esta idea enlaza con las secciones siguientes sobre ordenamientos (SeqCst, Acquire/Release, Relaxed).

Acceso a datos y modelo de orden de memoria

Modelo de orden de memoria y relación happens-before

El modelo de orden de memoria de C++ nos permite razonar sobre la causalidad del programa.
Esto lo hace introduciendo la relación “ocurre antes” (happens-before) entre partes del código y los hilos que las ejecutan.
La idea básica de la relación happens-before es que dentro de un mismo hilo, las acciones ocurren en el orden escrito: f(); g();.
Esto permite a compilador y hardware optimizar más cuando no existe relación “ocurre antes”, y ser más cuidadosos cuando sí existe.
La manera en la que comunicamos estas relaciones entre las diversas partes del código es a través de:
1. accesos atómicos, que establecen la relación “ocurre antes” entre hilos, y
2. accesos a datos normales, que quedan ordenados respecto a esos atómicos cuando están antes/después en el orden del hilo.
Con solo acceso a datos (no atómico) es imposible escribir código sincronizado correcto: no crea relaciones entre hilos. Necesitamos atómicos para indicar al compilador y al hardware que hay sincronización y, así, fijar el orden observado entre hilos.

El acceso a datos no basta

Es literalmente imposible escribir un código sincronizado correcto con solo acceso a datos.
Los compiladores lo optimizan asumiendo ejecución monohilo y el hardware puede propagar (hacer visibles a otros núcleos) esas escrituras de forma perezosa o inconsistente.

Acceso atómico

Cada acceso atómico se marca con un tipo de orden (ordering) que expresa la relación que establece con otros accesos.
En la práctica, esto “dice”:
- al compilador: qué reordenaciones debe evitar, y
- al hardware: cómo propagar las escrituras a otros hilos.

Reordenamientos y órdenes de memoria

Los reordenamientos/órdenes más importantes que usaremos son:
- Sequentially Consistent (SeqCst)
- Release (típicamente asociado a store)
- Acquire (típicamente asociado a load)
- Relaxed

Regla práctica:

Si dudas, empieza con SeqCst
En la mayoría de casos bastará Acquire/Release
Usa Relaxed solo cuando necesites solo atomicidad (sin orden entre hilos).

Sequentially Consistent

La más potente de todas
Implica todas las restricciones de los otros ordenamientos.
Una operación secuencialmente consistente no se puede reordenar.
Consecuencias:
1. Todo acceso del hilo que ocurre antes o después de un SeqCst permanece antes o después.
2. Un programa libre de condiciones de carrera y que solo usa accesos SeqCst tiene una única ejecución global (todos los hilos “ven” el mismo orden).
Uso recomendado:
- Opción apropiada si no estás seguro de la corrección con otras órdenes.
- Es preferible ir “más lento pero correcto” y, si procede, probar después con órdenes más débiles.
En la mayoría de casos no es necesario pues basta con usar acquire/release.

Acquire-Release

Se usan emparejadas.
El nombre les viene de que son apropiadas para las operaciones Acquire y Release de, p.e. un Mutex o Lock y por tanto definir secciones críticas.
Propiedades:
- Acquire: asegura que todo lo que viene después en el hilo no se mueva antes del Acquire. Operaciones previas podrían reordenarse hacia después del Acquire.
- Release: asegura que todo lo que viene antes en el hilo no se mueva después del Release. Operaciones posteriores podrían reordenarse hacia antes del Release.
Uso básico: acquire marca el inicio de la sección crítica; release marca el fin.
Nota sobre hardware:
- En arquitecturas strongly-ordered muchos accesos ya se comportan como Acquire–Release (coste adicional bajo o nulo); en weakly-ordered sí puede haber coste y diferencias visibles.

Relaxed

El más débil de todos:
- Garantiza atomicidad, no garantiza orden (no crea relaciones happens-before).
- Se puede reordenar libremente respecto a otros accesos.
Cuándo usarlo:
- Contadores u operaciones que solo requieren indivisibilidad (p. ej., fetch_add concurrente) y donde no importa el orden relativo entre hilos.
Consideraciones por arquitectura:
- En strongly-ordered suele no tener sentido (la semántica efectiva es ya más fuerte, similar a release–acquire).
- En weakly-ordered puede resultar más barato computacionalmente.

Operaciones atómicas en Rust.

Estas operaciones se implementan como métodos de los tipos de datos atómicos.
Están disponibles en el módulo std::sync::atomic.
Los tipos atómicos comienzan por el prefijo Atomic ([AtomicI8], [AtomicBool], etc.).
Al ser atómicas, permiten modificar una variable a través de una referencia de solo lectura (&self): principio de mutabilidad interior.
Todos los tipos atómicos comparten el mismo API. En este API la lectura se llama load y la escritura store.

Operaciones atómicas en Rust (II).

Las operaciones atómicas tienen un parámetro adicional de tipo “Orden de Memoria”.
El tipo de este parámetro es std::sync::atomic::Ordering.
Indica las garantías que tenemos sobre el orden relativo de las operaciones entre distintos hilos.

En Rust se implementa como un enumerado:

pub enum Ordering {
    Relaxed,
    Release,
    Acquire,
    AcqRel,
    SeqCst,
}

El orden más fácil de comprender es Relaxed, el cual solo nos garantiza el acceso atómico a la variable pero nada más.

Ejemplo del API para un tipo atómico.

Veamos el caso para AtomicI32 (análogo para el resto):

impl AtomicI32 {
    pub fn load(&self, ordering: Ordering) -> i32;
    pub fn store(&self, value: i32, ordering: Ordering);
    pub fn fetch_add(&self, v: i32, ordering: Ordering) -> i32;
    pub fn fetch_sub(&self, v: i32, ordering: Ordering) -> i32;
    pub fn fetch_or(&self, v: i32, ordering: Ordering) -> i32;
    pub fn fetch_and(&self, v: i32, ordering: Ordering) -> i32;
    pub fn fetch_nand(&self, v: i32, ordering: Ordering) -> i32;
    pub fn fetch_xor(&self, v: i32, ordering: Ordering) -> i32;
    pub fn fetch_max(&self, v: i32, ordering: Ordering) -> i32;
    pub fn fetch_min(&self, v: i32, ordering: Ordering) -> i32;
    pub fn swap(&self, v: i32, ordering: Ordering) -> i32; // "fetch_store"
    pub fn compare_exchange(&self, expected: i32, new: i32,
                            success_order: Ordering,
                            failure_order: Ordering) -> Result<i32, i32>;
}

Destacar “&self” y no “&mut self”, coherente con mutabilidad interior.

Una posible implementación de compare_exchange con este API podría ser (ignorando por ahora la ordenación de memoria):

pub fn compare_exchange(&self, expected: i32, new: i32) -> Result<i32, i32> {
    // En realidad, carga, comparación y escritura son UNA operación atómica.
    let v = self.load();
    if v == expected {
        // Value is as expected.
        // Replace it and report success.
        self.store(new);
        Ok(v)
    } else {
        // The value was not as expected.
        // Leave it untouched and report failure.
        Err(v)
    }
}

Ejemplos de uso.

Veamos algunos ejemplos de código sencillos de uso de estos tipos de datos:
Para ampliar tus conocimientos sobre este punto te recomiendo que veas el siguiente vídeo de la charla de Roy Margalit impartida en la conferencia de desarrolladores de y en Lenguaje ‘D’: If I Cannot Dissuade You from Using Atomics, at least Do It Safely.

Aclaraciones

En ningún caso estas transparencias son la bibliografía de la asignatura, por lo tanto debes estudiar, aclarar y ampliar los conceptos que en ellas encuentres empleando los enlaces web y bibliografía recomendada que puedes consultar en la página web de la ficha de la asignatura y en la web propia de la asignatura.

Introducción#

Origen de los problemas.#

Reordenación del compilador#

Reordenación del hardware#

Arquitecturas strongly-ordered vs. weakly-ordered.#

Acceso a datos vs. acceso atómico#

Acceso a datos y modelo de orden de memoria#

Modelo de orden de memoria y relación happens-before#

El acceso a datos no basta#

Acceso atómico#

Reordenamientos y órdenes de memoria#

Sequentially Consistent#

Acquire-Release#

Relaxed#

Operaciones atómicas en Rust.#

Operaciones atómicas en Rust (II).#

Ejemplo del API para un tipo atómico.#

Ejemplos de uso.#

Aclaraciones#