Состояние гонки: минимальный и максимальный диапазон целого числа

Мне недавно задали этот вопрос в интервью.

Учитывая следующий код, каково будет минимальное и максимальное возможное значение статического целого числа num?

import java.util.ArrayList;
import java.util.List;

public class ThreadTest {
    private static int num = 0;

    public static void foo() {
        for (int i = 0; i < 5; i++) {
            num++;
        }
    }

    public static void main(String[] args) throws Exception{
        List<Thread> threads = new ArrayList<Thread>();
        for (int i = 0; i < 5; i++) {
            Thread thread = new Thread(new Task());
            threads.add(thread);
            thread.start();
        }
        for (int i = 0; i < 5; i++) {
            threads.get(i).join();
        }
        // What will be the range of num ???
        System.out.println(ThreadTest.num);
    }
}

class Task implements Runnable {
    @Override
    public void run() {
        ThreadTest.foo();
    }

}

Я сказал им, что максимальное значение будет 25 (в случае отсутствия условия гонки), а min будет 5 (в случае условия гонки между всеми потоками на каждой итерации).
Но интервьюер сказал, что минимальное значение может быть даже ниже 5.
Как это возможно?

Ответы

Ответ 1

Я утверждаю, что минимально возможное значение составляет 2.

Ключом к этому является неатомичность num++, т.е. это чтение и запись, которые могут иметь другие операции между ними.

Вызовите темы T1..T5:

T1 читает 0, T2 читает 0;
T1 пишет 1, а затем читает и пишет 3 раза.
Затем T2 пишет 1;
Тогда T1 читает 1;
Тогда Т2-5 выполнит всю свою работу
Затем, наконец, T1 пишет 2.

(Примечание: результат 2 не зависит ни от количества потоков, ни от числа итераций, если их не менее 2).

Но честный ответ на это: это действительно не имеет значения. Существует гонка данных, как определено в JLS 17.4.5:

Когда программа содержит два конфликтующих доступа (§17.4.1 ["Два доступа к одной и той же переменной (чтение или запись в нее) называются конфликтующими, если хотя бы один из них является записью."]), Которые не упорядочены Считается, что с помощью отношения "до того, как это произошло" содержится гонка данных.

(Между действиями в потоках отсутствуют отношения "происходит до того")

Таким образом, вы не можете с пользой полагаться на то, что он делает. Это просто неверный код.

(Более того, я знаю ответ на этот вопрос не из-за какого-то с трудом выигранного многопоточного кода отладки или глубокого технического чтения: я знаю это, потому что я прочитал этот ответ раньше, чем где-либо еще. минимальное значение не очень хороший вопрос для интервью).

Ответ 2

Ваши потоки обновляют переменную, которая не является изменчивой, что означает, что она не гарантирует, что каждый поток увидит обновленное значение num. Давайте рассмотрим следующий поток выполнения потоков:

Thread 1: 0->1->2 (2 iteration left)
Thread 2: 0->1->2->3 (1 iteration left)
Thread 3: 0->1->2->3 (1 iteration left)
Thread 4: 0->1->2->3 (1 iteration left)
Thread 5: 0->1->2->3 (1 iteration left)

В этот момент поток 1 сбрасывает значение 2 num в память, а поток 2,3,4,5 решает снова прочитать num из памяти (по любой причине). Сейчас:

Thread 1: 2->3->4 (completed 2 iteration)
Thread 2: 2->3 (completed 1 iteration)
Thread 3: 2->3 (completed 1 iteration)
Thread 4: 2->3 (completed 1 iteration)
Thread 5: 2->3 (completed 1 iteration)

Поток 1 сбрасывает значение 4 в память, и после этого Theard 2,3,4.. сбрасывает значение в память, показывая, что текущее значение числа будет 3 вместо 5

Ответ 3

На мой взгляд, достичь 25 невозможно из-за отсутствия атомарных операций (см. Атомный доступ в руководствах по Java).

Все потоки запускаются практически в одно и то же время, поэтому каждый поток видит значение ThreadTest.num как 0 в первой итерации. Поскольку существует 5 потоков, параллельно обращающихся к одной и той же переменной, на третьей итерации потоки, вероятно, будут видеть значение ThreadTest.num еще в виде 1 или 2 и будут неправильно увеличивать значение до 2 или 3.

В зависимости от оборудования конечное значение будет ниже или выше, самые быстрые могут иметь самые низкие значения, а самые медленные - более высокие. Но, тем не менее, я утверждаю, что максимальное значение не может достигать 25.

ОБНОВЛЕНИЕ (2019-10-07)

Я тестировал себя на своей машине (Core i5 HQ), действительно, конечный результат достиг 25 почти все время. Чтобы лучше понять, я тестировал большее число в цикле for:

for (int i = 0; i < 10000; i++) {
    num++;
}

Теперь, в большинстве случаев, конечный результат был между 20000 и 30000, что далеко от 50000.

Ответ 4

Ну, мой ответ будет Макс 25, и Мин 0, так как все ваши операции являются инкрементными, и вы инициализировали его как 0.. Я думаю, что статический энергонезависимый int брошен туда, чтобы заставить вас задуматься о гонке условия, но есть ли что-нибудь, что уменьшит число в любой ситуации?

Изменение: Для чего бы это ни стоило, это было бы типичным отвлечением, которое они могут ожидать, что вы сможете преодолеть в реальном мире, оправдывая такую "хитрость", есть много красных селедок!