std::memory_order

std::memory_order especifica cómo los accesos de memoria, incluyendo accesos no atómicos regulares, deben ordenarse en torno a una operación atómica. En ausencia de restricciones en un sistema multinúcleo, cuando varios hilos leen y escriben simultáneamente en varias variables, un hilo puede observar que los valores cambian en un orden diferente del orden en que otro hilo los escribió. De hecho, el orden aparente de los cambios puede incluso diferir entre múltiples hilos de lectura. Algunos efectos similares pueden ocurrir incluso en sistemas uniprocesadores debido a las transformaciones del compilador permitidas por el modelo de memoria.

El comportamiento predeterminado de todas las operaciones atómicas en biblioteca proporciona un "orden secuencialmente consistente" (véase la discusión a continuación). Ese valor predeterminado puede afectar el rendimiento, pero las operaciones atómicas de la biblioteca pueden recibir un argumento std::memory_order para especificar las restricciones exactas, más allá de la atomicidad, que el compilador y el procesador deben imponer para esa operación.

[editar] Constantes

[editar] Descripción formal

La sincronización entre hilos y el orden de la memoria determinan cómo se ordenan las evaluaciones y los efectos secundarios de las expresiones entre diferentes hilos de ejecución. Se definen en los siguientes términos:

[editar] Secuenciado-antes/secuenciada-antes

El término secuenciado-antes se aplica en su mayoría a evaluaciones, donde usaremos el término en femenino, secuenciada-antes. Donde el género de la aplicación sea masculino, usaremos secuenciado-antes. El término en inglés es sequenced-before, que no tiene género. Aunque una traducción sin género podría ser "se secuencia antes", solamente se puede usar en tiempo presente.

Dentro del mismo hilo, la evaluación A puede ser secuenciada-antes que la evaluación B, como se describe en el orden de evaluación.

[editar] Conlleva dependencia

Dentro del mismo hilo, la evaluación A que está secuenciada-antes de la evaluación B también puede conllevar una dependencia a B (es decir, B depende de A), si alguno de los siguientes es verdadero:

[editar] Orden de modificación

Todas las modificaciones a cualquier variable atómica particular ocurren en un orden total que es específico de dicha variable atómica. Los siguientes cuatro requisitos se garantizan para todas las operaciones atómicas:

[editar] Secuencia de liberación

Después que una operación de liberación A se realiza en un objeto atómico M, a la subsecuencia continua más larga del orden de modificación de M que consiste de

se le conoce como la secuencia de liberación encabezada por A.

[editar] Ordenada-por-dependencia antes

Entre hilos, la evaluación A está ordenada-por-dependencia antes que la evaluación B si cualquiera de los siguientes es verdadero:

[editar] Intrahilos sucede-antes

Entre hilos, la evaluación A intrahilos sucede antes que la evaluación de B si cualquiera de los siguientes es verdadero:

[editar] Sucede-antes

Independientemente de los hilos, la evaluación A sucede-antes que la evaluación B si cualquiera de los siguientes es verdadero:

Se requiere que la implementación asegure que la relación sucede-antes sea acíclica, mediante la introducción de sincronización adicional si es necesario (solamente puede ser necesario si una operación de consumo está envuelta; véase Batty et al)

Si una evaluación modifica una ubicación de memoria, y la otra lee o modifica la misma ubicación de memoria, y si al menos una de las evaluaciones no es una operación atómica, el comportamiento del programa es indefinido (el programa tiene una carrera de datos) a menos que exista una relación sucede-antes entre estas dos evaluaciones.

[editar] Fuertemente sucede-antes

Independientemente de los hilos, la evaluación A fuertemente sucede-antes que la evaluación B si cualquiera de los siguientes es verdadero:

[editar] Efectos secundarios visibles

El efecto secundario A en un escalar M (una escritura) es visible con respecto al cálculo de valor B en M (una lectura) si se cumple lo siguiente:

Si el efecto secundario es visible con respecto al cálculo de valor B, entonces el subconjunto contiguo más largo de los efectos secundarios en M, en orden de modificación, donde B no sucede-antes, se le conoce como la secuencia visible de efectos secundarios (el valor de M, determinado por B, será el valor almacenado por uno de estos efectos secundarios). la sincronización entre hilos se reduce a prevenir las carreras de datos (estableciendo relaciones sudede-antes) y definiendo qué efectos secundarios se hacen visibles bajo qué condiciones. Nota: la sincronización entre hilos se reduce a prevenir las carreras de datos (estableciendo relaciones sudede-antes) y definiendo qué efectos secundarios se hacen visibles bajo qué condiciones.

[editar] Operación de consumo

La carga atómica con memory_order_consume o más rígida es una operación de consumo. Observa que std::atomic_thread_fence impone requisitos de sincronización más rígidos que una operación de consumo.

[editar] Operación de toma

La carga atómica con memory_order_acquire o más rígida es una operación de toma. La operación lock() en un Mutex también es una operación de toma. Observa que std::atomic_thread_fence impone requisitos de sincronización más rígidos que una operación de toma.

[editar] Operación de liberación

La carga atómica con memory_order_release o más rígida es una operación de liberación. La operación unlock() en un Mutex también es una operación de liberación. Observa que std::atomic_thread_fence impone requisitos de sincronización más rígidos que una operación de liberación.

[editar] Explicación

[editar] Ordenamiento relajado

Las operaciones atómicas etiquetadas con memory_order_relaxed no son operaciones de sincronización; no imponen un orden entre accesos concurrentes a memoria. Solamente garantizan atomicidad y consistencia del orden de modificación.

Por ejemplo, con x e y inicialmente en cero:

// Hilo 1:
r1 = y.load(std::memory_order_relaxed); // A
x.store(r1, std::memory_order_relaxed); // B
// Hilo 2:
r2 = x.load(std::memory_order_relaxed); // C 
y.store(42, std::memory_order_relaxed); // D

se permite que se genere r1 == r2 == 42 porque, aunque A está secuenciada-antes que B dentro del hilo 1 y C está secuenciada-antes que D dentro del hilo 2, nada impide que D aparezca antes que A en el orden de modificación de y, y que B aparezca antes que C en el orden de modificación de x. El efecto secundario de D en y podría ser visible a la carga A en el hilo 1 mientras que el efecto secundario de B en x podría ser visible a la carga C en el hilo 2. En particular, esto puede suceder si D se completa antes que C en el hilo 2, bien debido a reordenamiento del compilador o en tiempo de ejecución.

// Hilo 1:
r1 = x.load(std::memory_order_relaxed);
if (r1 == 42) y.store(r1, std::memory_order_relaxed);
// Hilo 2:
r2 = y.load(std::memory_order_relaxed);
if (r2 == 42) x.store(42, std::memory_order_relaxed);

El uso típico para el ordenamiento de memoria relajado es el incremento de contadores, tales como los contadores de referencias de std::shared_ptr, ya que esto solamente requiere atomicidad, pero no ordenamiento o sincronización (observa que decrementar los contadores de shared_ptr requiere sincronización tomar-liberar con el destructor).

#include <vector>
#include <iostream>
#include <thread>
#include <atomic>
 
std::atomic<int> cnt = {0};
 
void f()
{
    for (int n = 0; n < 1000; ++n) {
        cnt.fetch_add(1, std::memory_order_relaxed);
    }
}
 
int main()
{
    std::vector<std::thread> v;
    for (int n = 0; n < 10; ++n) {
        v.emplace_back(f);
    }
    for (auto& t : v) {
        t.join();
    }
    std::cout << "Valor final del contador es " << cnt << '\n';
}

Valor final del contador es 10000

[editar] Ordenamiento liberar-tomar

Si almacenamiento atómico en el hilo A está etiquetado con memory_order_release y una carga atómica en el hilo B de la misma variable está etiquetada con memory_order_acquire, todas las escrituras a memoria (no atómicas y relajadas) que sucedieron-antes del almacenamiento atómico desde el punto de vista del hilo A, se convierten en efectos secundarios visibles en el hilo B. Es decir, una vez que se completa la carga atómica, se garantiza que el hilo B verá todo lo que el hilo A escribió en memoria.

La sincronización se establece solo entre hilos que liberan y toman la misma variable atómica. Otros hilos pueden ver un orden diferente de acceso a memoria que uno o ambos hilos sincronizados.

En sistemas fuertemente ordenados—x86, SPARC TSO, IBM mainframe, etc.—, el ordenamiento liberar-tomar es automático para la mayoría de las operaciones. No se emiten instrucciones adicionales de CPU para este modo de sincronización; solo se ven afectadas ciertas optimizaciones del compilador (por ejemplo, el compilador tiene prohibido mover almacenamientos no atómicos más allá de la liberación del almacenamiento-liberación atómico o realizar cargas no atómicas antes de la carga-toma atómica). En sistemas débilmente ordenados (ARM, Itanium, PowerPC), se utilizan instrucciones de CPU especiales de carga o barreras de memoria.

Cerrojos de exclusión mutua, como std::mutex o espín atómico, son un ejemplo de sincronización de liberar-tomar: cuando el hilo A libera el cerrojo y el hilo B lo toma, todo lo que tuvo lugar en la sección crítica (antes de la liberación) en el contexto del hilo A debe ser visible para el hilo B (después de la toma) que está ejecutando la misma sección crítica .

#include <thread>
#include <atomic>
#include <cassert>
#include <string>
 
std::atomic<std::string*> ptr;
int datos;
 
void productor()
{
    std::string* p  = new std::string("Hola");
    datos = 42;
    ptr.store(p, std::memory_order_release);
}
 
void consumidor()
{
    std::string* p2;
    while (!(p2 = ptr.load(std::memory_order_acquire)))
        ;
    assert(*p2 == "Hola"); // nunca se dispara
    assert(datos == 42);   // nunca se dispara
}
 
int main()
{
    std::thread t1(productor);
    std::thread t2(consumidor);
    t1.join(); t2.join();
}

#include <thread>
#include <atomic>
#include <cassert>
#include <vector>
 
std::vector<int> datos;
std::atomic<int> bandera = {0};
 
void hilo_1()
{
    datos.push_back(42);
    bandera.store(1, std::memory_order_release);
}
 
void hilo_2()
{
    int esperado=1;
    while (!bandera.compare_exchange_strong(esperado, 2, std::memory_order_acq_rel)) {
        esperado = 1;
    }
}
 
void hilo_3()
{
    while (bandera.load(std::memory_order_acquire) < 2)
        ;
    assert(datos.at(0) == 42); // nunca se disparará
}
 
int main()
{
    std::thread a(hilo_1);
    std::thread b(hilo_2);
    std::thread c(hilo_3);
    a.join(); b.join(); c.join();
}

[editar] Ordenamiento liberar-consumir

Si un almacenamiento atómico en el hilo A está etiquetado con memory_order_release y una carga atómica en el hilo B de la misma variable que lee el valor almacenado está etiquetado con memory_order_consume, todas las escrituras a memoria (no atómicas y atómicas relajadas) que sucedieron antes del almacenamiento atómico desde el punto de vista del hilo A, se vuelven efectos secundarios visibles dentro de esas operaciones en el hilo B en el que la operación de carga conlleva dependencia, es decir, una vez que se completa la carga atómica, se garantiza que aquellos operadores y funciones en el hilo B que usan el valor obtenido de la carga verán lo que el hilo A escribió en la memoria.

La sincronización se establece solo entre los hilos que liberan y consumen la misma variable atómica. Otros hilos pueden ver un orden diferente de acceso a memoria que uno o ambos hilos sincronizados.

En todas las CPU convencionales que no sean DEC Alpha, el orden de dependencia es automático, no se emiten instrucciones de CPU adicionales para este modo de sincronización, solo se ven afectadas ciertas optimizaciones del compilador (por ejemplo, el compilador tiene prohibido realizar cargas especulativas en los objetos involucrados en la dependencia cadena).

Los casos de uso típicos para este orden implican el acceso de lectura a estructuras de datos concurrentes raramente escritas (tablas de enrutamiento, configuración, políticas de seguridad, reglas de firewall, etc.) y situaciones de publicador-suscriptor con publicación mediada por puntero, es decir, cuando el productor publica un puntero a través del cual el consumidor puede acceder a la información: no hay necesidad de hacer que todo lo demás que el productor escribió en la memoria sea visible para el consumidor (que puede ser una operación costosa en arquitecturas débilmente ordenadas). Un ejemplo de tal escenario es rcu_dereference.

Véase también std::kill_dependency y [[carries_dependency]] para el control de la cadena de dependencias más a detalle.

Observa que actualmente (2/2015) ningún compilador de producción conocido rastrea las cadenas de dependencia: las operaciones de consumo se promueven a operaciones de toma.

#include <thread>
#include <atomic>
#include <cassert>
#include <string>
 
std::atomic<std::string*> ptr;
int datos;
 
void productor()
{
    std::string* p  = new std::string("Hola");
    datos = 42;
    ptr.store(p, std::memory_order_release);
}
 
void consumidor()
{
    std::string* p2;
    while (!(p2 = ptr.load(std::memory_order_consume)))
        ;
    assert(*p2 == "Hola"); // nunca se dispara: *p2 conlleva dependencia de ptr
    assert(datos == 42);   // puede o no dispararse:
                           // datos no conlleva dependencia de ptr
}
 
int main()
{
    std::thread t1(productor);
    std::thread t2(consumidor);
    t1.join(); t2.join();
}

[editar] Ordenamiento secuencialmente consistente

Las operaciones atómicas etiquetadas con memory_order_seq_cst no solamente ordenan memoria de la misma manera que el ordenamiento liberar-tomar (todo lo que sucedió-antes que un almacenamiento en un hilo se vuelve un efecto secundario visible en el hilo que hizo la carga), sino también establecen un orden de modificación total único de todas las operaciones atómicas que están etiquetadas de la misma manera.

// Hilo 1:
x.store(1, std::memory_order_seq_cst); // A
y.store(1, std::memory_order_release); // B
// Hilo 2:
r1 = y.fetch_add(1, std::memory_order_seq_cst); // C
r2 = y.load(std::memory_order_relaxed); // D
// Hilo 3:
y.store(3, std::memory_order_seq_cst); // E
r3 = x.load(std::memory_order_seq_cst); // F

El ordenamiento secuencial puede ser necesario para situaciones de múltiples productores-múltiples consumidores donde todos los consumidores deben observar que las acciones de todos los productores ocurran en el mismo orden.

El ordenamiento secuencial requiere una instrucción de CPU de barrera de memoria total en todos los sistemas multinúcleo. Esto puede convertirse en un cuello de botella, ya que fuerza a que los accesos de memoria afectados se propagen a cada núcleo.

#include <thread>
#include <atomic>
#include <cassert>
 
std::atomic<bool> x = {false};
std::atomic<bool> y = {false};
std::atomic<int> z = {0};
 
void write_x()
{
    x.store(true, std::memory_order_seq_cst);
}
 
void write_y()
{
    y.store(true, std::memory_order_seq_cst);
}
 
void read_x_then_y()
{
    while (!x.load(std::memory_order_seq_cst))
        ;
    if (y.load(std::memory_order_seq_cst)) {
        ++z;
    }
}
 
void read_y_then_x()
{
    while (!y.load(std::memory_order_seq_cst))
        ;
    if (x.load(std::memory_order_seq_cst)) {
        ++z;
    }
}
 
int main()
{
    std::thread a(write_x);
    std::thread b(write_y);
    std::thread c(read_x_then_y);
    std::thread d(read_y_then_x);
    a.join(); b.join(); c.join(); d.join();
    assert(z.load() != 0);  // nunca sucederá
}

[editar] Relación con volatile

Dentro de un hilo de ejecución, accesos (lecturas y escrituras) a través de glvalues volátiles no se pueden reordenar más allá de los efectos secundarios observables (incluidos otros accesos volátiles) que están secuenciados-antes o secuenciados-después dentro del mismo hilo, pero no se garantiza que este orden sea observado por otro hilo, ya que el acceso volátil no establece la sincronización entre hilos.

Además, los accesos volátiles no son atómicos (la lectura y escritura concurrente es una carrera de datos) y no ordena la memoria (los accesos de memoria no volátiles pueden reordenarse libremente en torno al acceso volátil).

Una excepción notable es Visual Studio, donde, con la configuración predeterminada, cada escritura volátil tiene semántica de liberación y cada lectura volátil tiene semántica de toma. (MSDN) y, por lo tanto, los volátiles pueden usarse para la sincronización entre hilos. La semántica estándar volatile no es aplicable a la programación multiproceso, aunque son suficientes para, p. ej., comunicación con un controlador de señales (std::signal) que se ejecuta en el mismo hilo cuando se aplica a variables sig_atomic_t.

[editar] Véase también

[editar] Enlaces externos

• Protocolo MOESI

• x86-TSO: Un modelo de programador riguroso y usable para multiprocesadores x86 P. Sewell et. al., 2010
• Una tutoría de introducción a los modelos relajados de memoria ARM y POWER P. Sewell et al, 2012
• MESIF: Un protocolo de coherencia de caché de dos saltos para interconexiones de punto a punto J.R. Goodman, H.H.J. Hum, 2009