Race condition: Min and Max range of an integer

Question

I was recently asked this question in an interview.

Given the following code, what will be the min and max possible value of the static integer 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();
    }

}

I told them that the max value would be 25 (in case there is no race condition), and min would be 5 (in case of a race condition between all the threads at every iteration).
But the interviewer said the the min value can go even below 5.
How is that possible?

Answer 1

In my opinion, it's quite impossible to reach 25 due to the lack of atomic operations (see Atomic Access in Java Tutorials).

All threads start at almost the same time, so every thread sees ThreadTest.num value as 0 in the first iteration. Since there are 5 threads accessing the same variable in parallel, at the third iteration the threads are likely to see ThreadTest.num value still as 1 or 2 and are going to increment wrongly to 2 or 3.

Depending on hardware the final value is going to be lower or higher, the fastest ones might have the lowest values and the slowest ones the higher values. But still, my claim is the maximum value cannot reach 25.

EDIT (2019-10-07)

I tested myself in my machine (Core i5 HQ), indeed the final result reached 25 almost all the times. To understand better, I tested with a bigger number in for loop:

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

Now, most of times, the final result was between 20000 and 30000, well far from 50000.

Answer 2

I claim the minimum value possible is 2.

The key to this is the non-atomicity of num++, i.e., it is a read and a write, which may have other operations in between.

Call the threads T1..T5:

• T1 reads 0, T2 reads 0;
• T1 writes 1, and then reads and writes 3 times.
• Then T2 writes 1;
• Then T1 reads 1;
• Then T2-5 do all of their work
• Then, finally, T1 writes 2.

(Note: the result 2 is not dependent either on the number of threads, or the number of iterations, provided there are at least 2 of each.)

But the honest answer to this is: it really doesn't matter. There is a data race, as defined in 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.

(There is an absence of happens-before relationships between the actions in the threads)

So you can't usefully rely on whatever it does. It is simply incorrect code.

(Moreover, I know the answer to this not because of some hard-won battle debugging multithreaded code, or deep technical reading: I know this because I have read this answer before elsewhere. It's a parlour trick, nothing more, and so asking the minimum value isn't a very good interview question).

Answer 3

Well, My answer would be Max 25, and Min 0, since all of your operations are increment, and you initialized it as 0.. I think the static non-volatile int is thrown in there to make you go into these thoughts about race conditions, but is there anything in there that would DECREMENT the number in any situation?

Edit: For what it's worth, this would be a typical distraction that they may expect you to be able to overcome in the real world, justifying such "trickery", there are a lot of red herrings!

Answer 4

Your threads are updating a variable which is is not volatile that means it does not guarantee that every thread will see the updated value of num. Let consider the below execution flow of threads:

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)

At this point, Thread 1 flushes the value 2 of num to memory and Thread 2,3,4,5 decide to read the num from the memory again (for any reason). Now:

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)

Thread 1 flushes the value 4 to the memory and after that Theard 2,3,4.. flushes the value to the memory show the current value of the number will be 3 instead of 5