Why is the output of this race condition somewhat consistent?

Viewed 266

When I run the following code, the final output is always positive, and if I switch the order of the "x++" and the "x--" then the final output is always negative. Is there some semblance of order to which parts of this race condition get skipped? Any help understanding is greatly appreciated!

public class DataRace {

    private static class MyThreadCode implements Runnable {

        private static int x = 0;   // NOTE THAT X IS STATIC!!!

        @Override
        public void run() {
            for (int i = 0; i < 10000000; i++) {
                x++;
                x--;
            }
            System.out.println(x + "  " + Thread.currentThread().getName());
        }
    }
    
    public static void main(String[] args) {
        for (int i = 0; i < 100; i++) {
            Thread t = new Thread(new MyThreadCode());
            t.start();
        }
    }
}
3 Answers

We have two problems here:

  • Because x++ and x-- are not atomic (see Why is i++ not atomic?), you get a race condition. Thread 1 will load value of x (0). The CPU could then switch to Thread 2, which also loads the current x (0). Now both increment the value locally and later, they will set x. This means we lose an increment.
  • Because x is not marked volatile nor are we using the synchronized keyword, you have no guarantee that a thread really sees the actual value of x. It could be, that the value has already been updated by another thread, but because of the Java visibility guarantees, you have no guarantee what the other thread sees (the update value or some outdated "cached" value). It may also be that the other Thread did not yet write the update x value back to the memory (only to L1/L2 Cache).

I played a bit with the code and if I reduce the for loop to 1000 iterations, I get both negative and positive values for the same code. This could be a hint that the JVM optimizes the code if we have many iterations. If we only have 1000 iterations, which is not that much i guess, the JVM may decide to run the code as it is written.

I suspect both problems have some influence on the result. For example, if you load x, the processor will probably load that value into the L1 cache, and if you then execute the second operation, it may load that value directly from the L1 cache instead of the main memory. This could mean, that the 2nd operation causes no/less "lost updates".

But to really find out why that happens, I think you would to dig into the Java specification or even how the CPU handles such cases.

I suspect this is because of how the OS process scheduler works.

Since the operations on x is not synchronized, threads are going to see whatever the value of x is when the OS picked up that specific threads operation. Since the first operation is increment, and at 100 threads, even before the decrement is ready to picked up, value of x is probably at 100 or a larger number than the previous increment already.

You can add a few debug statements in your run method to see what is going on here. I reduced the run loop count to 2 and here is what I got. The statements are not in order, but the second log statement of each thread shows the deviation.

@Override
public void run() {
  long start = System.currentTimeMillis();
  for (int i = 0; i < 2; i++) {
     x++;
     System.out.println("Value of x by "+ Thread.currentThread().getName() + "is "+x);
     x--;
  }
}
Value of x by Thread-53is 54
Value of x by Thread-53is 100
Value of x by Thread-81is 82
Value of x by Thread-81is 99
Value of x by Thread-57is 58
Value of x by Thread-39is 40
Value of x by Thread-39is 98
Value of x by Thread-28is 29
Value of x by Thread-28is 97
Value of x by Thread-60is 61
Value of x by Thread-94is 95
Value of x by Thread-94is 96
Value of x by Thread-99is 100
Value of x by Thread-99is 95
Value of x by Thread-78is 79
Value of x by Thread-78is 94
Value of x by Thread-87is 88
Value of x by Thread-87is 93
Value of x by Thread-84is 85
Value of x by Thread-84is 92
Value of x by Thread-41is 42
Value of x by Thread-41is 91
Value of x by Thread-74is 75
Value of x by Thread-74is 90
Value of x by Thread-92is 93
Value of x by Thread-92is 89
Value of x by Thread-12is 13
Value of x by Thread-12is 88
Value of x by Thread-98is 99
Value of x by Thread-98is 87
Value of x by Thread-8is 9
Value of x by Thread-8is 86
Value of x by Thread-66is 67
Value of x by Thread-88is 89
Value of x by Thread-49is 50
Value of x by Thread-49is 85
Value of x by Thread-47is 48
Value of x by Thread-14is 15
Value of x by Thread-14is 84
Value of x by Thread-70is 71
Value of x by Thread-61is 62
Value of x by Thread-70is 83
Value of x by Thread-91is 92
Value of x by Thread-96is 98
Value of x by Thread-96is 82
Value of x by Thread-67is 68
Value of x by Thread-27is 28
Value of x by Thread-27is 81
Value of x by Thread-0is 1
Value of x by Thread-0is 80
Value of x by Thread-75is 76
Value of x by Thread-75is 79
Value of x by Thread-3is 4
Value of x by Thread-3is 78
Value of x by Thread-56is 57
Value of x by Thread-56is 77
Value of x by Thread-97is 97
Value of x by Thread-22is 23
Value of x by Thread-22is 76
Value of x by Thread-15is 16
Value of x by Thread-15is 75
Value of x by Thread-64is 65
Value of x by Thread-63is 64
Value of x by Thread-59is 60
Value of x by Thread-33is 34
Value of x by Thread-9is 10
Value of x by Thread-45is 46
Value of x by Thread-37is 38
Value of x by Thread-10is 11
Value of x by Thread-76is 77
Value of x by Thread-77is 78
Value of x by Thread-93is 94
Value of x by Thread-6is 7
Value of x by Thread-52is 53
Value of x by Thread-26is 27
Value of x by Thread-86is 87
Value of x by Thread-30is 31
Value of x by Thread-82is 83
Value of x by Thread-83is 84
Value of x by Thread-89is 90
Value of x by Thread-73is 74
Value of x by Thread-32is 33
Value of x by Thread-79is 80
Value of x by Thread-4is 5
Value of x by Thread-79is 74
Value of x by Thread-32is 74
Value of x by Thread-73is 74
Value of x by Thread-89is 74
Value of x by Thread-83is 74
Value of x by Thread-82is 74
Value of x by Thread-30is 74
Value of x by Thread-86is 74
Value of x by Thread-26is 74
Value of x by Thread-52is 74
Value of x by Thread-6is 74
Value of x by Thread-93is 74
Value of x by Thread-77is 74
Value of x by Thread-76is 74
Value of x by Thread-10is 74
Value of x by Thread-37is 74
Value of x by Thread-45is 74
Value of x by Thread-9is 74
Value of x by Thread-33is 74
Value of x by Thread-59is 74
Value of x by Thread-63is 74
Value of x by Thread-64is 74
Value of x by Thread-97is 76
Value of x by Thread-35is 36
Value of x by Thread-24is 25
Value of x by Thread-40is 41
Value of x by Thread-67is 81
Value of x by Thread-46is 47
Value of x by Thread-58is 59
Value of x by Thread-91is 82
Value of x by Thread-36is 37
Value of x by Thread-11is 12
Value of x by Thread-25is 26
Value of x by Thread-61is 83
Value of x by Thread-31is 32
Value of x by Thread-42is 43
Value of x by Thread-34is 35
Value of x by Thread-85is 86
Value of x by Thread-47is 84
Value of x by Thread-5is 6
Value of x by Thread-29is 30
Value of x by Thread-88is 85
Value of x by Thread-66is 85
Value of x by Thread-90is 91
Value of x by Thread-21is 22
Value of x by Thread-17is 18
Value of x by Thread-7is 8
Value of x by Thread-54is 55
Value of x by Thread-62is 63
Value of x by Thread-16is 17
Value of x by Thread-80is 81
Value of x by Thread-38is 39
Value of x by Thread-2is 3
Value of x by Thread-1is 2
Value of x by Thread-13is 14
Value of x by Thread-72is 73
Value of x by Thread-20is 21
Value of x by Thread-23is 24
Value of x by Thread-51is 52
Value of x by Thread-55is 56
Value of x by Thread-95is 96
Value of x by Thread-65is 66
Value of x by Thread-50is 51
Value of x by Thread-19is 20
Value of x by Thread-60is 96
Value of x by Thread-71is 72
Value of x by Thread-68is 69
Value of x by Thread-44is 45
Value of x by Thread-57is 98
Value of x by Thread-48is 49
Value of x by Thread-48is 43
Value of x by Thread-18is 19
Value of x by Thread-69is 70
Value of x by Thread-43is 44
Value of x by Thread-69is 42
Value of x by Thread-18is 42
Value of x by Thread-44is 44
Value of x by Thread-68is 44
Value of x by Thread-71is 44
Value of x by Thread-19is 45
Value of x by Thread-50is 45
Value of x by Thread-65is 45
Value of x by Thread-95is 45
Value of x by Thread-55is 45
Value of x by Thread-51is 45
Value of x by Thread-23is 45
Value of x by Thread-20is 45
Value of x by Thread-72is 45
Value of x by Thread-13is 45
Value of x by Thread-1is 45
Value of x by Thread-2is 45
Value of x by Thread-38is 45
Value of x by Thread-80is 45
Value of x by Thread-16is 45
Value of x by Thread-62is 45
Value of x by Thread-54is 45
Value of x by Thread-7is 45
Value of x by Thread-17is 45
Value of x by Thread-21is 45
Value of x by Thread-90is 45
Value of x by Thread-29is 47
Value of x by Thread-5is 47
Value of x by Thread-85is 48
Value of x by Thread-34is 48
Value of x by Thread-42is 48
Value of x by Thread-31is 48
Value of x by Thread-25is 49
Value of x by Thread-11is 49
Value of x by Thread-36is 49
Value of x by Thread-58is 50
Value of x by Thread-46is 50
Value of x by Thread-40is 51
Value of x by Thread-24is 51
Value of x by Thread-35is 51
Value of x by Thread-4is 74
Value of x by Thread-43is 42

Leaving aside the non-atomicity of the operations x++ and x--, the effects of which are noted in the comments to the OP, there is another effect which does not rely on non-atomicity of individual operations.

The consistency of the sign (all output positive) is due to the fact that, when one thread finishes its loop and prints the current value of x, there are still many other threads which have so far incremented x but have not yet decremented it. (I mean the other threads are between the increment and decrement statements, so they've incremented x N times but decremented it (N-1) times.)

This can be proved with the following modification to your code:

private static class MyThreadCode implements Runnable {

    private static AtomicInteger x = new AtomicInteger(0);

    @Override
    public void run() {
        for (int i = 0; i < 10000000; i++) {
            x.incrementAndGet();
            x.decrementAndGet();
        }
        System.out.println(x + "  " + Thread.currentThread().getName());
        try {
            Thread.sleep(10000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println(x + "  " + Thread.currentThread().getName());
    }
}

You will see that, before the 10-second sleep, all threads print a positive number as they complete the loop (but other threads are still running). After the 10-second sleep, all threads then print the final result, which is always 0, because after 10 seconds, all threads have completed their loops and done as many decrements as increments.

To avoid this problem, you should use synchronization to ensure that the increment and decrement operations are done atomically. The following modification results in all output being 0:

        synchronized (x) {
            x.incrementAndGet();
            x.decrementAndGet();
        }

(Though if you're using x always inside a synchronized block, then you might as well make it a primitive int.)

Related