basic multithreading

Question

I have the following Interview question:

class someClass
{
    int sum=0;
    public void foo()
    {
        for(int i=0; i<100; i++)
        {
            sum++
        }
    }
}

There are two parallel threads running through the foo method. the value of sum at the end will vary from 100 to 200. the question is why. As I understand only one thread gets a cpu and threads get preempted while running. At what point can the disturbance cause the sum not reaching 200?

Answer 1

The line sum++ is a race condition.

Both threads can read the value of sum as say 0, then each increments its value to 1 and stores that value back. This means that the value of sum will be 1 instead of 2.

Continue like that and you will get a result between 100 and 200.

Answer 2

The increment isn't atomic. It reads the value, then writes out the incremented value. In between these two operations, the other thread can interact with the sum in complex ways.

The range of values is not in fact 100 to 200. This range is based on the incorrect assumption that threads either take turns or they perform each read simultaneously. There are many more possible interleavings, some of which yield markedly different values. The worst case is as follows (x represents the implicit temporary used in the expression sum++):

    Thread A            Thread B
----------------    ----------------
x     ← sum (0)
                    x     ← sum (0)
x + 1 → sum (1)
x     ← sum (1)
x + 1 → sum (2)
⋮
x     ← sum (98)
x + 1 → sum (99)
                    x + 1 → sum (1)
x     ← sum (1)
                    x     ← sum (1)
                    x + 1 → sum (2)
                    ⋮
                    x     ← sum (99)
                    x + 1 → sum (100)
x + 1 → sum (2)

Thus the lowest possible value is 2. In simple terms, the two threads undo each the other's hard work. You can't go below 2 because thread B can't feed a zero to thread A — it can only output an incremented value — and thread A must in turn increment the 1 that thread B gave it.

Answer 3

Most CPU's have multiple cores now. So if we lock a mutex at the beginning of the function foo() and unlock the mutex after the for loop finishes then the 2 threads running on different cores will still yield the answer 200.