竞争条件：整数的最小和最大范围

Question

我最近在面试中被问到这个问题。

给定以下代码，静态整数 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（如果没有竞争条件），最小值为 5（如果所有线程在每次迭代中都存在竞争条件）。
但是面试官说最小值甚至可以低于5。
这怎么可能？

Answer 1

您的线程正在更新一个非易失性变量，这意味着它不能保证每个线程都会看到 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 将 num 的值 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

Answer 2

我声称可能的最小值是 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:

中所定义

When a program contains two conflicting accesses (§17.4.1 ["Two accesses to (reads of or writes to) the same variable are said to be conflicting if at least one of the accesses is a write."]) that are not ordered by a happens-before relationship, it is said to contain a data race.

（线程中的操作之间不存在 happens-before 关系）

所以你不能有效地依赖它所做的一切。这只是错误的代码。

（此外，我知道这个问题的答案不是因为一些来之不易的调试多线程代码的战斗，或者深入的技术阅读：我知道这个是因为我之前在其他地方读过这个答案。这是一个客厅把戏，仅此而已，所以 求最小值 不是一个很好的面试问题）。

Answer 3

嗯，我的答案是最大 25，最小 0，因为你所有的操作都是递增的，并且你将它初始化为 0..我认为静态非易失性整数被扔在那里让你去进入这些关于竞争条件的想法，但是有什么东西可以在任何情况下减少这个数字吗？

编辑：就其价值而言，这将是一种典型的干扰，他们可能希望您能够在现实世界中克服这种干扰，证明这样 "trickery" 是正确的，有很多转移注意力的东西！

Answer 4

在我看来，由于缺乏原子操作，达到 25 是完全不可能的（参见 Java 教程中的 Atomic Access）。

所有线程几乎同时启动，因此每个线程在第一次迭代中将 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。

竞争条件：整数的最小和最大范围

Race condition: Min and Max range of an integer

java

multithreading

race-condition