8

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();
        }
    }
}
Matthew Foulk
  • 81
  • 1
  • 2
  • maybe because the program terminates before all threads add or subtract. So every thread adds but until the program terminates all the threads won't subtract and vise versa. – Aris Apr 14 '21 at 15:20
  • 1
    The `x++` and `x--` operations are not atomic: they are reads of `x`, then updates, then writes. The actions of the threads can interleave. Also, you don't have guaranteed visibility of the updates from other threads. – Andy Turner Apr 14 '21 at 15:24
  • Note that this happens even if x is declared `volatile`. This is because the operations are not atomic as Andy Turner says. Also, note that it prints 0 if the number of iterations is less than 10000, and non-0 if the number of iterations is more than 10000. This is presumably because the x++ is non-atomic only in JIT-compiled code. – k314159 Apr 14 '21 at 15:28
  • 1
    @Aristotle The program will wait to terminate until every thread is finished, because the threads are not marked as `setDaemon(true)` – skeeks Apr 14 '21 at 15:30
  • 3
    I think the OP is aware of `x++` and `x--` not being atomic, which is implied in them even mentioning "race condition". The question is rather why there seems to be consistency in the sign of the result depending on the order of both statements. The `println` for each thread can be removed and be replace by one in `main`; still the same thing. – akuzminykh Apr 14 '21 at 15:31
  • @k314159 Could the "10000" have anything to do with the duration of a jiffy? – Jeff Holt Apr 14 '21 at 15:38
  • Another observation: If you replace `int x` with `AtomicInteger`, you still get the same consistently positive output. So it's more than just the fact that `x++` is not atomic. – k314159 Apr 14 '21 at 15:52
  • It's probably just the optimizer realising that `x++` followed by `x--` will return `x` to the current value and then completely removing the statements. 10-million iterations are bound to capture the attention of the optimiser. It's likely that the entire loop is removed. – Software Engineer Apr 14 '21 at 15:59
  • @SoftwareEngineer No, then the result would be 0. But its mostly not. – skeeks Apr 14 '21 at 16:01
  • I can imagine that the result comes from the possible orderings of operations and has nothing to do with scheduling or visibility. I could be very wrong though. There are many possible orderings which makes verifying my assumption very tedious. – akuzminykh Apr 16 '21 at 04:28

3 Answers3

2

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.

skeeks
  • 359
  • 2
  • 8
  • It's nice general information but it doesn't answer the question. – akuzminykh Apr 14 '21 at 15:50
  • If you replace `int x` with `AtomicInteger`, you still get the same consistently positive output (or consistently negative if you reverse the decrements/increments). Can your theory explain these similar results when using AtomicInteger? – k314159 Apr 14 '21 at 15:50
  • @k314159 For me, using `AtomicInteger` always leads to 0. But if you just print out `x` once (at the end of main), you need to consider waiting for all threads to complete (`Thread.join`) or else, you will print out an intermediate value. – skeeks Apr 14 '21 at 16:02
-1

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
aksappy
  • 3,400
  • 3
  • 23
  • 49
  • 1
    Im not sure but you need to be careful with `System.out.println` as it contains a `synchronized call`. This could mean you lose some behavior which is there if you do not have `System.out.println` between the 2 statements. – skeeks Apr 14 '21 at 16:12
  • Agree that sop has a synchronized(this), but I am only demonstrating what the threads are seeing. We could use an async library to stay true to the problem, but I think the issue will remain the same, until x is atomic. – aksappy Apr 14 '21 at 16:20
-1

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.)

k314159
  • 5,051
  • 10
  • 32
  • "*there are still many other threads which have so far incremented x but have not yet decremented it*" You didn't explain why this would be the case. Considering threads are interleaved more or less randomly then it should be the case that when a given thread finishes, roughly half of the remaining threads have just performed an increment and the other half have just performed a decrement, resulting in net zero or thereabouts. So you might expect some variation above and below 0. The key question: **is why isn't it more random**, like you'd expect? You don't address that – Michael Apr 14 '21 at 16:10
  • @Michael I've edited my answer to try to explain it a little more clearly. – k314159 Apr 14 '21 at 16:11
  • As far as I'm concerned, it doesn't. The threads are started in series, one after another. The first thread should start, then maybe it gets to increment once before the 2nd thread starts, then when the 2nd thread is doing its first increment, the 1st thread is doing a decrement. Now the 3rd thread starts, the 1st is back to incrementing, the 2nd is now decrementing, and the 3rd is incrementing. (just an example of the staggering) Throw in the randomness of the scheduler, and I don't see how you can suggest that at any one time, all threads are performing the same instruction. – Michael Apr 14 '21 at 16:16
  • It doesnt make any sense to use `AtomicInteger` inside a `synchronized` block, because then, you could use a primtive integer instead. – skeeks Apr 14 '21 at 16:20
  • @Michael I'm not suggesting that "at any one time, all thread are performing the same instruction." I'm saying that when thread 1 has completed all of its 10000000 iterations, and is about to print the value of x, thread 2 may have done 5000000 iterations so far, and have done the increment, but not yet the decrement of that iteration, which means it has incremented 5000000 times but decremented only 4999999 times. On average, about half of the threads will not yet have finished all iterations, and half of those will be between the increment and decrement. – k314159 Apr 14 '21 at 16:21
  • @skeeks true, if you're using a synchronized block, then you might as well just use a primitive int. – k314159 Apr 14 '21 at 16:21
  • Furthermore, I don't think you can assume that the observed behavior in your program is the same as in the version without `AtomicInteger`. `ÀtomicInteger` will guarantee memory-visibility which we dont have, we we use plain primitive integer without volatile. The described behaviour with `AtomicInteger` is solely because of how the OS scheduler schedules the threads. – skeeks Apr 14 '21 at 16:24
  • @k314159 You say `about half of the threads will not yet have finished all iterations` but I don't see how you know that. For the CPU, the for loop is more than 2 instructions, therefore you would need to distribute the threads amongst all those instructions. I guess this results in much less than 50% of threads being between both instructions. – skeeks Apr 14 '21 at 16:29
  • @skeeks that's a good point. Each loop will have many instructions, only two of which will be the increment and decrement. But still, statistically at least a small proportion of the threads will be between those two statements. – k314159 Apr 14 '21 at 16:44