¿Cómo demostrar problemas de reordenación de instrucciones en Java?

multithreading compiler-optimization

Question

Al reordenar la instrucción de Java, el JVM cambia el orden de ejecución del código en el momento de la compilación o en el tiempo de ejecución, lo que posiblemente haga que las instrucciones no relacionadas se ejecuten fuera de orden.

Así que mi pregunta es:

Alguien puede proporcionar un ejemplo de programa Java / fragmento de código, que muestre de manera confiable un problema de reordenación de instrucciones, que no sea causado también por otros problemas de sincronización (como el almacenamiento en caché / visibilidad o r / w no atómico, como en mi intento fallido de tal demostración en mi pregunta anterior )

Para enfatizar, no estoy buscando ejemplos de temas de reordenación teórica. Lo que estoy buscando es una forma de demostrarlos realmente viendo resultados incorrectos o inesperados de un programa en ejecución.

A menos que exista un ejemplo de comportamiento defectuoso, el simple hecho de mostrar un reordenamiento real en el ensamblaje de un programa simple también podría ser bueno.

Answer 1

Prueba

Escribí una prueba JUnit 5 que verifica si la reordenación de la instrucción tuvo lugar después de que terminaran dos hilos.

• La prueba debe pasar si no se realizó una ordenación de instrucciones.
• La prueba debe fallar si se produjo el reordenamiento de la instrucción.

‌

public class InstructionReorderingTest {

    static int x, y, a, b;

    @org.junit.jupiter.api.BeforeEach
    public void init() {
        x = y = a = b = 0;
    }

    @org.junit.jupiter.api.Test
    public void test() throws InterruptedException {
        Thread threadA = new Thread(() -> {
            a = 1;
            x = b;
        });
        Thread threadB = new Thread(() -> {
            b = 1;
            y = a;
        });

        threadA.start();
        threadB.start();

        threadA.join();
        threadB.join();

        org.junit.jupiter.api.Assertions.assertFalse(x == 0 && y == 0);
    }

}

Resultados

Corrí la prueba hasta que falla varias veces. Los resultados son los siguientes:

InstructionReorderingTest.test [*] (12s 222ms): 29144 total, 1 failed, 29143 passed.
InstructionReorderingTest.test [*] (26s 678ms): 69513 total, 1 failed, 69512 passed.
InstructionReorderingTest.test [*] (12s 161ms): 27878 total, 1 failed, 27877 passed.

Explicación

Los resultados que esperamos son

• x = 0, y = 1 : el threadA ejecuta hasta que se completa el threadB .
• x = 1, y = 0 : el threadB ejecuta hasta que se completa antes del inicio del threadA .
• x = 1, y = 1 : sus instrucciones están intercaladas.

Nadie puede esperar que x = 0, y = 0 , lo que puede suceder como muestran los resultados de la prueba.

Las acciones en cada subproceso no tienen una dependencia de flujo de datos entre sí y, por lo tanto, pueden ejecutarse fuera de orden. (Incluso si se ejecutan en orden, el tiempo por el cual se vacían los cachés en la memoria principal puede hacer que parezca, desde la perspectiva del threadB , que las asignaciones en el threadA produjeron en el orden opuesto).

_{Concurrencia de Java en la práctica, Brian Goetz}

Answer 2

Esto demuestra la reordenación de ciertas asignaciones, de las iteraciones de 1M generalmente hay un par de líneas impresas.

public class App {

public static void main(String[] args) {

    for (int i = 0; i < 1000_000; i++) {
        final State state = new State();

        // a = 0, b = 0, c = 0

        // Write values
        new Thread(() -> {
            state.a = 1;
            // a = 1, b = 0, c = 0
            state.b = 1;
            // a = 1, b = 1, c = 0
            state.c = state.a + 1;
            // a = 1, b = 1, c = 2
        }).start();

        // Read values - this should never happen, right?
        new Thread(() -> {
            // copy in reverse order so if we see some invalid state we know this is caused by reordering and not by a race condition in reads/writes
            // we don''t know if the reordered statements are the writes or reads (we will se it is writes later)
            int tmpC = state.c;
            int tmpB = state.b;
            int tmpA = state.a;

            if (tmpB == 1 && tmpA == 0) {
                System.out.println("Hey wtf!! b == 1 && a == 0");
            }
            if (tmpC == 2 && tmpB == 0) {
                System.out.println("Hey wtf!! c == 2 && b == 0");
            }
            if (tmpC == 2 && tmpA == 0) {
                System.out.println("Hey wtf!! c == 2 && a == 0");
            }
        }).start();

    }
    System.out.println("done");
}

static class State {
    int a = 0;
    int b = 0;
    int c = 0;
}

}

Al imprimir el ensamblaje para la escritura lambda se obtiene esta salida (entre otros ..)

                                                ; {metadata(''com/example/App$$Lambda$1'')}
  0x00007f73b51a0100: 752b                jne       7f73b51a012dh
                                                ;*invokeinterface run
                                                ; - java.lang.Thread::run@11 (line 748)

  0x00007f73b51a0102: 458b530c            mov       r10d,dword ptr [r11+0ch]
                                                ;*getfield arg$1
                                                ; - com.example.App$$Lambda$1/1831932724::run@1
                                                ; - java.lang.Thread::run@-1 (line 747)

  0x00007f73b51a0106: 43c744d41402000000  mov       dword ptr [r12+r10*8+14h],2h
                                                ;*putfield c
                                                ; - com.example.App::lambda$main$0@17 (line 18)
                                                ; - com.example.App$$Lambda$1/1831932724::run@4
                                                ; - java.lang.Thread::run@-1 (line 747)
                                                ; implicit exception: dispatches to 0x00007f73b51a01b5
  0x00007f73b51a010f: 43c744d40c01000000  mov       dword ptr [r12+r10*8+0ch],1h
                                                ;*putfield a
                                                ; - com.example.App::lambda$main$0@2 (line 14)
                                                ; - com.example.App$$Lambda$1/1831932724::run@4
                                                ; - java.lang.Thread::run@-1 (line 747)

  0x00007f73b51a0118: 43c744d41001000000  mov       dword ptr [r12+r10*8+10h],1h
                                                ;*synchronization entry
                                                ; - java.lang.Thread::run@-1 (line 747)

  0x00007f73b51a0121: 4883c420            add       rsp,20h
  0x00007f73b51a0125: 5d                  pop       rbp
  0x00007f73b51a0126: 8505d41eb016        test      dword ptr [7f73cbca2000h],eax
                                                ;   {poll_return}
  0x00007f73b51a012c: c3                  ret
  0x00007f73b51a012d: 4181f885f900f8      cmp       r8d,0f800f985h

No estoy seguro de por qué la última mov dword ptr [r12+r10*8+10h],1h no está marcada con el campo B y la línea 16, pero se puede ver la asignación de b y c (c justo después de a).

EDITAR: Debido a que las escrituras suceden en el orden a, b, cy las lecturas suceden en el orden inverso c, b, a nunca se debe ver un estado no válido a menos que las escrituras (o lecturas) se reordenen.

Las escrituras realizadas por una sola CPU (o núcleo) son visibles en el mismo orden por todos los procesadores; consulte, por ejemplo, esta respuesta , que apunta a la Guía de programación del sistema Intel, Volumen 3, sección 8.2.2.

Las escrituras por un solo procesador se observan en el mismo orden por todos los procesadores.

Answer 3

Para las ejecuciones de un solo subproceso, la reordenación no es un problema en absoluto, debido al Modelo de Memoria de Java (JMM) (garantiza que todas las acciones de lectura relacionadas con las escrituras están ordenadas en su totalidad) y no pueden dar resultados inesperados.

Para la ejecución concurrente, las reglas son completamente diferentes y las cosas se vuelven más complicadas de entender (incluso al proporcionar un ejemplo simple que generará aún más preguntas). Pero incluso esto está totalmente descrito por JMM con todos los casos de esquina, por lo tanto, los resultados inesperados también están prohibidos . En general, prohibido si todas las barreras se colocan a la derecha.

Para una mejor comprensión de los pedidos, recomiendo this tema con muchos ejemplos en el interior.