multithreading - ¿Cuáles son las garantías de pedido de memoria C++ 11 en este caso de esquina?

c++11 atomic

Question

Estoy escribiendo un código sin bloqueo, y se me ocurrió un patrón interesante, pero no estoy seguro de si se comportará como se espera en el orden relajado de la memoria.

La forma más sencilla de explicarlo es usando un ejemplo:

std::atomic<int> a, b, c;

auto a_local = a.load(std::memory_order_relaxed);
auto b_local = b.load(std::memory_order_relaxed);
if (a_local < b_local) {
    auto c_local = c.fetch_add(1, std::memory_order_relaxed);
}

Tenga en cuenta que todas las operaciones usan std::memory_order_relaxed .

Obviamente, en el hilo en el que se ejecuta esto, las cargas para a y b deben realizarse antes de que se evalúe la condición if .

De manera similar, la operación de lectura-modificación-escritura (RMW) en c debe realizarse después de que se evalúe la condición (porque está condicionada a esa condición ...).

Lo que quiero saber es, ¿este código garantiza que el valor de c_local esté al menos tan actualizado como los valores de a_local y b_local ? Si es así, ¿cómo es posible teniendo en cuenta el orden relajado de la memoria? ¿La dependencia de control, junto con la operación RWM, actúa como algún tipo de valla de adquisición? (Tenga en cuenta que no hay ni siquiera una versión correspondiente en cualquier lugar.)

Si lo anterior es cierto, creo que este ejemplo también debería funcionar (suponiendo que no haya desbordamiento), ¿tengo razón?

std::atomic<int> a(0), b(0);

// Thread 1
while (true) {
    auto a_local = a.fetch_add(1, std::memory_order_relaxed);
    if (a_local >= 0) {    // Always true at runtime
        b.fetch_add(1, std::memory_order_relaxed);
    }
}

// Thread 2
auto b_local = b.load(std::memory_order_relaxed);
if (b_local < 777) {
    // Note that fetch_add returns the pre-incrementation value
    auto a_local = a.fetch_add(1, std::memory_order_relaxed);
    assert(b_local <= a_local);    // Is this guaranteed?
}

En el subproceso 1, hay una dependencia de control que sospecho garantiza que a siempre se incrementa antes de que b se incremente (pero cada una de ellas continúa siendo incrementada cuello y cuello). En el hilo 2, hay otra dependencia de control que sospecho garantiza que b se carga en b_local antes de que se incremente a. También creo que el valor devuelto desde fetch_add será al menos tan reciente como cualquier valor observado en b_local y, por lo b_local , la b_local debería mantenerse. Pero no estoy seguro, ya que esto se aparta significativamente de los ejemplos usuales de ordenación de memoria, y mi comprensión del modelo de memoria C ++ 11 no es perfecta (tengo problemas para razonar sobre estos efectos de ordenación de memoria con cierto grado de certeza). Cualquier apreciación sería apreciada!

Actualización : como Bames53 ha señalado de manera útil en los comentarios, dado un compilador lo suficientemente inteligente, es posible que se pueda optimizar un if en las circunstancias adecuadas, en cuyo caso las cargas relajadas podrían reordenarse para que se produzcan después de la RMW, provocando su Los valores deben estar más actualizados que el valor de retorno de fetch_add el fetch_add podría fetch_add en mi segundo ejemplo). Sin embargo, ¿qué atomic_signal_fence si en lugar de un if , se atomic_signal_fence una atomic_signal_fence (no atomic_thread_fence )? Ciertamente, el compilador no puede ignorarlo, independientemente de las optimizaciones realizadas, pero ¿garantiza que el código se comporte como se espera? ¿Se le permite a la CPU hacer algún pedido en tal caso?

El segundo ejemplo se convierte entonces en:

std::atomic<int> a(0), b(0);

// Thread 1
while (true) {
    auto a_local = a.fetch_add(1, std::memory_order_relaxed);
    std::atomic_signal_fence(std::memory_order_acq_rel);
    b.fetch_add(1, std::memory_order_relaxed);
}

// Thread 2
auto b_local = b.load(std::memory_order_relaxed);
std::atomic_signal_fence(std::memory_order_acq_rel);
// Note that fetch_add returns the pre-incrementation value
auto a_local = a.fetch_add(1, std::memory_order_relaxed);
assert(b_local <= a_local);    // Is this guaranteed?

Otra actualización : después de leer todas las respuestas hasta el momento y repasar el estándar, no creo que se pueda demostrar que el código es correcto utilizando solo el estándar. Entonces, ¿alguien puede presentar un contraejemplo de un sistema teórico que cumpla con el estándar y también active el aserto?

Answer 1

Este ejemplo presenta una variación del comportamiento similar a las lecturas del aire. La discusión relevante en la especificación se encuentra en la sección 29.3p9-11. Dado que la versión actual del estándar C11 no garantiza que se respeten las dependencias, el modelo de memoria debe permitir que se active la afirmación. La situación más probable es que el compilador optimice la comprobación de que a_local> = 0. Pero incluso si reemplaza ese cheque con una cerca de señal, las CPU podrían reordenar esas instrucciones. Puede probar dichos ejemplos de código en los modelos de memoria C / C ++ 11 utilizando la herramienta de código abierto CDSChecker. El problema interesante con su ejemplo es que para que una ejecución viole la aseveración, tiene que haber un ciclo de dependencias. Más concretamente:

El archivo b.fetch_add en el subproceso uno depende de a.fetch_add en la misma iteración de bucle debido a la condición if. El archivo a.fetch_add en el hilo 2 depende de b.load. Para una violación de aserción, tenemos que hacer que b.load de T2 se lea desde b.fetch_add en una iteración de bucle posterior a a.fetch_add de T2. Ahora considere b.fetch_add desde donde lee b.load y llámelo # para referencia futura. Sabemos que b.load depende de # ya que toma el valor de #.

Sabemos que # debe depender de a.fetch_add de T2, ya que a2 at.fetch_add de T2 lee y actualiza un a.fetch_add anterior de T1 en la misma iteración de bucle que #. Así que sabemos que # depende de a.fetch_add en el subproceso 2. Eso nos da un ciclo en las dependencias y es simplemente extraño, pero está permitido por el modelo de memoria C / C ++. La forma más probable de producir ese ciclo es (1) que el compilador se da cuenta de que a.local siempre es mayor que 0, lo que rompe la dependencia. Luego puede realizar el desenrollado de bucle y reordenar fetch_add de T1 como quiera.

Answer 2

Las vallas de señal no proporcionan las garantías necesarias (bueno, no a menos que ''subproceso 2'' sea un controlador de señal que realmente se ejecute en ''subproceso 1'').

Para garantizar el comportamiento correcto, necesitamos sincronización entre los subprocesos, y la cerca que hace eso es std::atomic_thread_fence .

Etiquetemos las declaraciones para que podamos diagramar varias ejecuciones (con cercas de hilos que reemplazan las cercas de señal, según sea necesario):

while (true) {
    auto a_local = a.fetch_add(1, std::memory_order_relaxed); // A
    std::atomic_thread_fence(std::memory_order_acq_rel);      // B
    b.fetch_add(1, std::memory_order_relaxed);                // C
}

auto b_local = b.load(std::memory_order_relaxed);             // X
std::atomic_thread_fence(std::memory_order_acq_rel);          // Y
auto a_local = a.fetch_add(1, std::memory_order_relaxed);     // Z

Así que primero asumamos que X carga un valor escrito por C. El siguiente párrafo especifica que en ese caso las cercas se sincronizan y se establece una relación de suceso antes .

29.8 / 2:

Una guía de liberación A se sincroniza con una cerca adquirida B si existen operaciones atómicas X e Y , ambas operan en algún objeto atómico M , de modo que A se secuencia antes de X , X modifica M , Y se secuencia antes de B e Y lee el valor escrito por X o un valor escrito por cualquier efecto secundario en la secuencia de liberación hipotética X encabezaría si fuera una operación de liberación.

Y aquí hay un posible orden de ejecución donde ocurren las flechas , antes de las relaciones.

Thread 1: A₁ → B₁ → C₁ → A₂ → B₂ → C₂ → ...
                ↘
Thread 2:    X → Y → Z

Si un efecto secundario X en un objeto atómico M ocurre antes de un cálculo de valores B de M , entonces la evaluación B tomará su valor de X o de un efecto secundario Y que sigue a X en el orden de modificación de M. - [C ++ 11 1.10 / 18]

Por lo tanto, la carga en Z debe tomar su valor de A₁ o de una modificación posterior. Por lo tanto, la afirmación se mantiene porque el valor escrito en A₁ y en todas las modificaciones posteriores es mayor o igual que el valor escrito en C₁ (y leído por X ).

Ahora veamos el caso donde las vallas no se sincronizan. Esto sucede cuando la carga de b no carga un valor escrito por el subproceso 1, sino que lee el valor con el que se inicializa b . Todavía hay sincronización donde se inician los hilos:

30.3.1.2/5

Sincronización : La finalización de la invocación del constructor se sincroniza con el comienzo de la invocación de la copia de f.

Esto está especificando el comportamiento del constructor de std::thread . Entonces (asumiendo que la creación del hilo está correctamente secuenciada después de la inicialización de a ) el valor leído por Z debe tomar su valor de la inicialización de a o de una de las modificaciones subsiguientes en el hilo 1, lo que significa que las aserciones aún se mantienen.