Java: Count with two Threads

Question

Suppose threads A and B are running the next function in the following Java code:

class Test
{
    int sum=0;

    void next()
    {
        for(int i=0;i<100;i++)
            sum++;
    }
}

What might be the value of sum when both threads finish running next? My answer was 100-200. However, I am missing some case.

Is there a scenario where the value of sum is less than 100?

Answer 1

My answer is minimum 1 and maximum 100.

Increment code looks like:
1-mov ax,mem[sum]
2-inc ax
3-mov mem[sum],ax

Now lets run an example with for(int i=0 ; i<3 ; i++)

T1 line 1 |==> ax = 0; mem[sum]=0;
T1 line 2 |==> ax = 1; mem[sum]=0;
T2 line 1 |==> ax = 0; mem[sum]=0;
T1 line 3 |==> ax = 0; mem[sum]=0;
T2 line 2 |==> ax = 1; mem[sum]=0;
T1 line 1 |==> ax = 0; mem[sum]=0;
T2 line 3 |==> ax = 0; mem[sum]=0;
T1 line 2 |==> ax = 1; mem[sum]=0;
T2 line 1 |==> ax = 0; mem[sum]=0;
T1 line 3 |==> ax = 0; mem[sum]=0;
T2 line 2 |==> ax = 1; mem[sum]=0;
T1 line 1 |==> ax = 0; mem[sum]=0;
T2 line 3 |==> ax = 0; mem[sum]=0;
T1 line 2 |==> ax = 1; mem[sum]=0;
T2 line 1 |==> ax = 0; mem[sum]=0;
T1 line 3 |==> ax = 0; mem[sum]=0;
T2 line 2 |==> ax = 1; mem[sum]=0;
T2 line 3 |==> ax = 1; mem[sum]=1;

The same is applicable for i=100

Answer 2

As others have stated before (including yourself implicitly), both ++ incrementation operators (prefix and postfix) are non-atomic and your code is therefore not thread-safe. The Java Language Specification describes, what happens behind the scenes during the execution of the "Postfix Increment Operator ++". The most relevant part is that it consists of the 3 steps:

1. Reading the variable
2. Incrementing
3. Writing the new value back to the variable

Since (1) and (3) are atomic for ints, there cannot be any bitwise corruption. Step (2) in itself also works perfectly fine because it works exclusively on thread-local data.

So the only possible problem we are left with is therefore the classic Lost Update Problem.

Since lost updates can only decrease the result, I agree with your upper bound of 200. This happens e.g. if the code is run on a platform where the increment operation actually is an atomic operation (the Java Language Specification doesn't forbid this case), or if all thread switches by coincidence just happen after a full increment is done, or if one thread isn't scheduled until the other one has finished.

Now the lower bound I'd put even lower than you. Your guess of 100 was probably based on the idea that in order to lose one update, we need another update to overwrite it. Therefore we can never lose more than half of the increments. But this is actually wrong because a single increment of one thread can annihilate several increments of the other thread, see this example interleaving:

Thread A                 || Thread B
=====================================================
read sum (0)             ||
                         || read sum(0)
                         || increment sum locally(1)
                         || write sum(1)
                         || read sum(1)
                         || increment sum locally(2)
                         || write sum(2)
                         || read sum(2)
                         || increment sum locally(3)
                         || write sum(3)
increment sum locally(1) ||
write sum(1)             ||

However, in order to annihilate increments of one thread, we need at least one successful increment in the other thread. Since increments of both threads have to be annihilated in order to get the lowest result (otherwise we would have at least 100 successful increments), we need at least one successful update in both threads and therefore a total of 2 successful increments.

This minimum can be achieved e.g. with the following interleaving:

Thread A                   || Thread B
========================================================
read sum (0)               ||
                           || read sum (0)
                           || increment sum locally (1)
                           || write sum (1)
                           || read sum (1)
                           || increment sum locally (2)
                           || write sum (2)
                           || read sum (2)
                           || increment sum locally (3)
                           || write sum (3)
                           ||
                           || ... 95 more increments ...
                           ||
                           || read sum (98)
                           || increment sum locally (99)
                           || write sum (99)
increment sum locally(1)   ||
write sum (1)              ||
                           || read sum (1)
read sum (1)               ||
increment sum locally(2)   ||
write sum (2)              ||
read sum (2)               ||
increment sum locally(3)   ||
write sum (3)              ||
read sum (3)               ||
increment sum locally(4)   ||
write sum (4)              ||
                           ||
... 95 more increments ... ||
                           ||
read sum (99)              ||
increment sum locally(100) ||
write sum (100)            ||
                           || increment sum locally (2)
                           || write sum (2)

So the answer is: The value can be between 2 and 200 for 2 Threads.