Состояние гонки: минимальный и максимальный диапазон целого числа
Мне недавно задали этот вопрос в интервью.
Учитывая следующий код, каково будет минимальное и максимальное возможное значение статического целого числа 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.
Как это возможно?
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В .
(Существует отсутствие , происходит - прежде отношения между действиями в потоках)
, Таким образом, Вы не можете полезно полагаться на то, что оно делает. Это - просто неправильный код.
(Кроме того, я знаю ответ на это не из-за некоторого с трудом завоеванного сражения, отлаживающего многопоточный код или глубоко техническое чтение: Я знаю это, потому что я прочитал этот ответ прежде в другом месте. Это - светский талант, ничто больше, и таким образом выяснение у минимального значения не является очень хорошим вопросом об интервью).
Ну, Мой ответ был бы Max 25 и Min 0, так как все Ваши операции являются инкрементом, и Вы инициализировали его как 0.. Я думаю, что статический энергонезависимый интервал брошен там, чтобы заставить Вас войти в эти мысли об условиях состязания, но является там чем-нибудь там, которое ПОСТЕПЕННО УМЕНЬШИЛО БЫ число в какой-либо ситуации?
Редактирование: Если это имеет значение это было бы типичным отвлечением, которое они могут ожидать, что Вы сможете преодолеть в реальном мире, выравнивая по ширине такой "обман", существует много отвлекающих маневров!
Ваши потоки обновляют переменную, которая является, не энергозависимо, который означает, что она не гарантирует, что каждый поток будет видеть обновленное значение 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
По-моему, довольно невозможно достигнуть 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.