Tema 7. Orden de memoria (preview)

Contenidos

1. Operaciones atómicas

1.1. Introducción (I).

  • Etimología: del griego ‘ατομον’ (átomos). Indivisible.
  • Las operaciones atómicas permiten que varios hilos trabajen con variables de manera segura.
  • Estas operaciones deben estar soportadas por la arquitectura del procesador para el que se genera el código ejecutable.
  • De hecho estas operaciones son el componente básico sobre el que se construyen abstracciones de nivel superior, p.e. Mutex.
  • A lo largo de este tema usaremos Rust como lenguaje de implementación.

1.2. Introducción (II).

  • Rust adopta el modelo de memoria para datos atómicos de C++20. Usa el anterior enlace como guía de consulta básica, incluso si programas en otro lenguaje que no sea C++.
  • No es que sea particularmente bueno, en realidad es complicado de entender y tiene algunos fallos.
  • La parte buena es que se trata de un modelo ya probado y dispone de herramientas que ayudan a su comprensión y uso.
  • La primera versión del mismo data de C++11 y a fecha de hoy ya ha tenido varias revisiones de fallos.

2. Origen de los problemas.

2.1. El compilador reordena instrucciones

  • Lo hace para eliminar:
    1. Dependencias entre datos
    2. Código muerto

  • Esto puede cambiar el orden de los eventos o incluso hacer que algunos no ocurran nunca, p.e. dado este código: 

    x = 1;
y = 3;
x = 2;

    El compilador puede decidir que este otro es mejor: 

    x = 2;
y = 3;

2.2. El compilador reordena instrucciones

  • Fíjate que:
    1. Se ha invertido el orden de eventos
    2. Se ha eliminado uno de ellos.
  • Desde un punto de vista de un solo hilo ambos códigos conducen al mismo estado.
  • Pero si nuestro código fuese multi-hilo, es posible que confiáramos que a x se le asignara un 1 antes de que a y se le asignara un valor.
  • Esto nos plantea una tesitura, la reordenación puede producir código más eficiente pero también es importante confiar en que nuestro programa hace lo que le hemos pedido.

2.3. Reordenación del hardware

  • Las CPUs disponen de memoria cache, posiblemente 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.

2.4. Reordenación del hardware

  • Supongamos el siguiente código: 

    initial state: x = 0, y = 1

THREAD 1        THREAD 2
y = 3;          if x == 1 {
x = 1;              y *= 2;
                }
  • Posibles salidas de 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.
  • Pero hay una tercera posiblidad aunque parezca imposible:
    y = 2
    El hilo 2 vio x = 1 pero no y = 3 y sobreescribe y = 3.

2.5. Reordenación del hardware

  • Hay que tener en cuenta que esta reordenación depende del hardware (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.

2.6. Consecuencias del HW Strongly/Weakly-Ordered

  • Pedir garantías mas fuertes a un hardware que ya, de por sí, es fuertemente ordenado tiene un coste nimio o incluso cero.
  • Las garantías mas débiles sólo proporcionarán ganancias de rendimiento en un hardware debílmente ordenado.
  • Es muy probable que pedir garantías que sean demasiado débiles a un hardware que es fuertemente ordenado funcione bien, aunque el programa sea estrictamente incorrecto.
  • Lo que nos lleva a que un programa concurrente debería ser probado en un hardware debílmente ordenado.

3. Acceso a Datos.

3.1. Modelo de orden de memoria

  • El modelo de orden de memoria propuesto en C++ intenta cerrar la brecha permitiéndonos hablar sobre la causalidad de nuestro programa.
  • Esto lo hace introduciendo una relación llamada "ocurre antes" entre las partes del código y los hilos que las ejecutan.
  • La idea básica de la relación "ocurre antes" es que todo lo que ocurre dentro de un mismo hilo ocurre en ese orden: f(); g();.
  • Esto permite al hardware y al software (compilador) llevar a cabo optimizaciones más agresivas cuando no existe una relación "ocurre antes" estricta…
  • …pero, al mismo tiempo, ser mas cuidadosos con las optimizaciones cuando sí existe una.
  • La manera en la que comunicamos estas relaciones entre las diversas partes del código es a través de:
    1. accesos a datos y
    2. accesos atómicos.
  • El acceso a datos es uno de los pilares de la programación y es, fundamentalmente, no sincronizado.
  • Los compiladores tratan de optimizarlo de manera agresiva bajo el supuesto de una ejecución mono-hilo.
  • Al mismo tiempo el hardware puede propagar los cambios hechos por el acceso a los datos a otros hilos de manera tan perezosa e inconsistente como quiera.

3.2. Consecuencias

  • Es literalmente imposible escribir un código sincronizado correcto con sólo el acceso a datos.
  • Necesitamos del acceso atómico a datos para indicarle al hardware y al software (compilador) que estamos ante un programa multi-hilo.

3.3. Acceso atómico

  • Cada acceso atómico se puede marcar con un tipo de orden que indica la relación que establece con otros accesos, es decir…
  • Le decimos al compilador y al hardware qué cosas no pueden hacer, lo cual significa para el:
    compilador:
    que ha de tener en cuenta la reordenación de instrucciones.
    hardware:
    cómo debe propagar las escrituras a otros hilos.

4. Reordenamientos

  • Los reordenamientos más importantes son:
    • Sequentially Consistent (SeqCst)
    • Release (se asocia a "Store")
    • Acquire (se asocia a "Load")
    • Relaxed

4.1. Sequentially Consistent

  • La más potente de todas.
  • Implica todas las restricciones de los otros ordenamientos y además…
  • Una operación secuencialmente consistente no se puede reordenar.
  • Esto implica que:
    1. Todos los accesos en un hilo que ocurren antes y después de un acceso SeqCst permanecen antes y después.
    2. Un programa libre de condiciones de carrera y que solo usa accesos SeqCst tiene la propiedad de que sólo existe una ejecución global de sus instrucciones en la que están de acuerdo todos los hilos.
  • Es la opción apropiada si no estás seguro de que la ejecución de tu código sea correcta con alguno de los otros ordenamientos.
  • Es mejor tener una ejecución más lenta pero correcta!
  • Además, siempre puedes probar con otro tipo de ordenamiento más adelante.
  • En la mayoría de casos no es necesario pues basta con usar acquire/release.

4.2. Acquire-Release

  • Se suelen usar 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.
  • Un acceso Acquire asegura que cualquier acceso tras él permanece tras él, pero cualquier operación previa puede reordenarse para que ocurra después.
  • De manera similar un acceso Release asegura que cualquier acceso antes de él permanece antes de él, pero cualquier operación posterior puede reordenarse para que ocurra antes.
  • Uso básico de acquire-release: adquirimos una posición de memoria indicando así el comienzo de la sección crítica y cuando hacemos el release marcamos el fin de la sección crítica.
  • En arquitecturas "strongly-ordered" la mayoría de accesos tienen una semántica "Acquire-Release", haciendo que sea una operación sin coste adicional, no así en arquitecturas "weakly-ordered".

4.3. Relaxed

  • Son los accesos más débiles de todos.
  • Sólo garantizan la atomicidad del acceso.
  • Se pueden reordenar libremente.
  • No crean relaciones "happens-before".
  • Se emplean en operaciones que queremos que ocurran de manera atómica pero nos da igual el orden en el que lo hagan, p.e. incrementar un contador por varios hilos usando una operación fetch_add con ordenamiento "Relaxed".
  • No tiene sentido en arquitecturas "strongly-ordered" (estas ya nos proporcionan una semántica "release-acquire" que es más estricta)
  • En arquitecturas "weakly-ordered" esta ordenación puede ser más barata computacionalmente.

5. Operaciones atómicas en Rust.

5.1. Operaciones atómicas en Rust (I).

  • Estas operaciones se implementan como métodos de los tipos de datos atómicos.
  • Tenemos acceso a estos tipos desde el módulo std::sync::atomic.
  • El nombre de estos tipos comienza con el prefijo Atomic (AtomicI8, AtomicBool, etc…).
  • Dado que son operaciones atómicas, estas permiten modificar una variable atómica a través de una referencia de solo lectura. Principio de mutabilidad interior.
  • Todos los tipos atómicos comparten el mismo API.
  • En este API a la operación de lectura de una variable se le llama Load y a la de escritura Store.

5.2. 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.

5.3. Ejemplo del API para un tipo atómico.

  • Veamos el caso para AtomicI32, para el resto es igual: 

    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".

  • 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> {
    // In reality, the load, comparison and store,
    // all happen as a single atomic operation.
    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)
    }
}

5.4. Ejemplos de uso.

6. 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.

Created: 2023-12-15 vie 13:36

Validate