Как продемонстрировать проблемы переупорядочения инструкций Java?

При переупорядочении инструкций Java порядок выполнения кода изменяется JVM во время компиляции или во время выполнения, что может привести к тому, что несвязанные операторы будут выполняться не по порядку.

Итак, мой вопрос:

Может ли кто-нибудь предоставить пример Java-программы / фрагмента, который надежно показывает проблему переупорядочения команд, которая не вызвана также другими проблемами синхронизации (такими как кэширование / видимость или неатомарная версия, как в моей неудачной попытке такого демонстрационного примера в моем предыдущем вопросе)

Чтобы подчеркнуть, я не ищу примеры теоретических вопросов переупорядочения. То, что я ищу, это способ на самом деле продемонстрировать их, увидев неправильные или неожиданные результаты работающей программы.

Если исключить пример некорректного поведения, просто показывать фактическое изменение порядка в сборке простой программы также может быть хорошо.

Источник

3 ответа

Решение

Это демонстрирует переупорядочение определенных назначений, из 1M итераций обычно есть несколько напечатанных строк.

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;
}

}

Печать сборки для записи лямбда получает этот вывод (среди прочего..)

                                                ; {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

Я не уверен, почему последний mov dword ptr [r12+r10*8+10h],1h не помечен путфилдом b и строкой 16, но вы можете увидеть поменявшееся назначение b и c (c сразу после a).

РЕДАКТИРОВАТЬ: Поскольку записи происходят в порядке a, b, c и чтения происходят в обратном порядке c, b, a вы никогда не увидите недопустимое состояние, если записи (или чтения) не переупорядочены.

Записи, выполняемые одним процессором (или ядром), видны всем процессорам в одинаковом порядке, см., Например, этот ответ, который указывает на раздел 8.2.2 Руководства по системному программированию Intel, том 3, раздел 8.2.2.

Записи одним процессором наблюдаются в одинаковом порядке всеми процессорами.

Источник

Тестовое задание

Я написал тест JUnit 5, который проверяет, было ли изменение порядка команд после завершения двух потоков.

  • Тест должен пройти, если переупорядочивание инструкций не произошло.
  • Тест должен завершиться неудачей, если произошла переупорядочение команд. 

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);
    }

}

Результаты

Я запускал тест, пока он не провалился несколько раз. Результаты приведены ниже:

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.

объяснение

Результаты, которые мы ожидаем

  • x = 0, y = 1: threadA работает до завершения, прежде чем threadB начинается.
  • x = 1, y = 0: threadB работает до завершения, прежде чем threadA начинается.
  • x = 1, y = 1: их инструкции чередуются.

Никто не может ожидать x = 0, y = 0, что может произойти, как показали результаты теста.

Действия в каждом потоке не зависят друг от друга, и, соответственно, могут выполняться не по порядку. (Даже если они выполняются по порядку, время, за которое кэши сбрасываются в основную память, может появиться с точки зрения threadB, что назначения в threadA произошло в обратном порядке.)

Java-параллелизм на практике, Брайан Гетц

Источник

Для однопоточных исполнений переупорядочение вообще не является проблемой из-за модели памяти Java (JMM) (гарантируйте, что любые операции чтения, связанные с записью, упорядочены по совокупности) и не может привести к неожиданным результатам.

Для одновременного выполнения правила совершенно разные, и все становится более сложным для понимания (даже путем предоставления простого примера, который вызовет еще больше вопросов). Но даже это полностью описано JMM со всеми угловыми случаями, поэтому неожиданные результаты также запрещены. Как правило, запрещено, если все барьеры установлены правильно.

Для лучшего понимания переупорядочения я настоятельно рекомендую эту тему с множеством примеров внутри.

Источник
Другие вопросы по тегам