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

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

Учитывая следующий код, каково будет минимальное и максимальное возможное значение статического целого числа 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.
Как это возможно?

29
задан Anmol Singh Jaggi 2 October 2019 в 08:23
поделиться

4 ответа

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

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

Вызов потоки T1.. T5:

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

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

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

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

(Существует отсутствие , происходит - прежде отношения между действиями в потоках)

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

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

33
ответ дан 28 November 2019 в 00:19
поделиться

Ну, Мой ответ был бы Max 25 и Min 0, так как все Ваши операции являются инкрементом, и Вы инициализировали его как 0.. Я думаю, что статический энергонезависимый интервал брошен там, чтобы заставить Вас войти в эти мысли об условиях состязания, но является там чем-нибудь там, которое ПОСТЕПЕННО УМЕНЬШИЛО БЫ число в какой-либо ситуации?

Редактирование: Если это имеет значение это было бы типичным отвлечением, которое они могут ожидать, что Вы сможете преодолеть в реальном мире, выравнивая по ширине такой "обман", существует много отвлекающих маневров!

-4
ответ дан 28 November 2019 в 00:19
поделиться

Ваши потоки обновляют переменную, которая является, не энергозависимо, который означает, что она не гарантирует, что каждый поток будет видеть обновленное значение 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 из цифры к памяти и Потоку 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

2
ответ дан 28 November 2019 в 00:19
поделиться

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

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

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

РЕДАКТИРОВАНИЕ (2019-10-07)

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

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

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

0
ответ дан 28 November 2019 в 00:19
поделиться
Другие вопросы по тегам:

Похожие вопросы: