141

I know that compound operations such as i++ are not thread safe as they involve multiple operations.

But is checking the reference with itself a thread safe operation?

a != a //is this thread-safe

I tried to program this and use multiple threads but it didn't fail. I guess I could not simulate race on my machine.

EDIT:

public class TestThreadSafety {
    private Object a = new Object();

    public static void main(String[] args) {

        final TestThreadSafety instance = new TestThreadSafety();

        Thread testingReferenceThread = new Thread(new Runnable() {

            @Override
            public void run() {
                long countOfIterations = 0L;
                while(true){
                    boolean flag = instance.a != instance.a;
                    if(flag)
                        System.out.println(countOfIterations + ":" + flag);

                    countOfIterations++;
                }
            }
        });

        Thread updatingReferenceThread = new Thread(new Runnable() {

            @Override
            public void run() {
                while(true){
                    instance.a = new Object();
                }
            }
        });

        testingReferenceThread.start();
        updatingReferenceThread.start();
    }

}

This is the program that I am using to test the thread-safety.

Weird behavior

As my program starts between some iterations I get the output flag value, which means that the reference != check fails on the same reference. BUT after some iterations the output becomes constant value false and then executing the program for a long long time does not generate a single true output.

As the output suggests after some n (not fixed) iterations the output seems to be constant value and does not change.

Output:

For some iterations:

1494:true
1495:true
1496:true
19970:true
19972:true
19974:true
//after this there is not a single instance when the condition becomes true
Narendra Pathai
  • 41,187
  • 18
  • 82
  • 120
  • 2
    What do you mean by "thread-safe" in this context? Are you asking if it's guaranteed to always return false? – JB Nizet Aug 27 '13 at 08:33
  • @JBNizet yes. That's what I was thinking of. – Narendra Pathai Aug 27 '13 at 08:42
  • 5
    It doesn't even always return false in a single-threaded context. It could be a NaN.. – harold Aug 27 '13 at 09:36
  • @JBNizet Please check my updated answer with the program that I am using. The check returns `true` sometimes but there seems to be a weird behavior in the output. – Narendra Pathai Aug 27 '13 at 10:21
  • 4
    Probable explanation: the code was just-in-time compiled and the compiled code loads the variable only once. This is expected. – Marko Topolnik Aug 27 '13 at 10:28
  • @NarendraPathai: This is in line with the answer posted by Stephen. If you have a separate thread updating the value of `a`, it's quite possible that the two loads/accesses for the field `a` will actually point to different objects in heap. – Sanjay T. Sharma Aug 27 '13 at 11:42
  • With that last update, you seem to have answered your own original question and are now asking another. You should have posted that as a new question and linked between them, since you now seem to be answering your own question inside the question (instead of as an answer). – Izkata Aug 27 '13 at 12:09
  • 3
    Printing individual results is a poor way to test for races. Printing (both formatting and writing the results) is relatively costly compared to your test (and sometimes your program will end up blocking on write when the bandwith of the connection to the terminal or the terminal itself is slow). Also, IO often contains mutexes of its own which will permute the execution order of your threads (note your individual lines of `1234:true` never smash *each other*). A race test needs a tighter inner loop. Print a summary at the end (as someone did below with a unit test framework). – Ben Jackson Aug 27 '13 at 16:28
  • @BenJackson Yes I agree, that's why I removed the print statements when the check returns false and only printed when the check returns true. Will that still affect the behavior? – Narendra Pathai Aug 27 '13 at 20:50
  • If you don't mind C, check out this answer of mine for why it is multiple ops: http://stackoverflow.com/questions/4718727/thread-mutex-behaviour/4719064#4719064 – Emilio M Bumachar Aug 28 '13 at 14:12
  • So we see an **ABA problem** here .. – Ken Kin Aug 28 '13 at 15:35
  • Also you can read [this question and answers](http://stackoverflow.com/questions/18315433/critical-section-for-set-and-get-single-bool-value) It may be helpful, however it is not Java. – ST3 Aug 28 '13 at 18:55

8 Answers8

124

In the absence of synchronization this code

Object a;

public boolean test() {
    return a != a;
}

may produce true. This is the bytecode for test()

    ALOAD 0
    GETFIELD test/Test1.a : Ljava/lang/Object;
    ALOAD 0
    GETFIELD test/Test1.a : Ljava/lang/Object;
    IF_ACMPEQ L1
...

as we can see it loads field a to local vars twice, it's a non-atomic operation, if a was changed in between by another thread comparison may produce false.

Also, memory visibility problem is relevant here, there is no guarantee that changes to a made by another thread will be visible to the current thread.

Andrew Tobilko
  • 48,120
  • 14
  • 91
  • 142
Evgeniy Dorofeev
  • 133,369
  • 30
  • 199
  • 275
  • 22
    Although strong evidence, bytecode is not actually a proof. It must be somewhere in the JLS as well... – Marko Topolnik Aug 27 '13 at 09:29
  • 10
    @Marko I agree with your thinking, but not necessarily your conclusion. To me the bytecode above is the obvious/canonical way of implementing `!=`, which involves loading the LHS and RHS separately. And so if the JLS *doesn't* mention anything specific about optimisations when LHS and RHS are syntactically identical, then the general rule would apply, which means loading `a` twice. – Andrzej Doyle Aug 27 '13 at 09:35
  • Please check my updated answer with the program that I am using. The check returns true sometimes but there seems to be a weird behavior in the output. – Narendra Pathai Aug 27 '13 at 10:22
  • 1
    @AndrzejDoyle The JLS may mention something about "loading the value once and only once per expression" or something to that effect. I believe that C's *sequence points* are specified in just such terms. But I agree, it may not mention anything specific, in which case the rules stay the same for each subexpression independently, and several reads are allowed by the JLS in that case. – Marko Topolnik Aug 27 '13 at 10:24
  • 20
    Actually, assuming that the generated bytecode conforms to the JLS, it is a proof! – proskor Aug 27 '13 at 10:27
  • 1
    @proskor Proofs cannot assume their conclusions :) But yes, I'd take this as defacto proof because no compiler would possibly screw up on this. – Marko Topolnik Aug 27 '13 at 10:31
  • 1
    But does it? If the specification **allows** `a != a` to yield `true`, it does not imply anything about the correctness of the given bytecode (which would not be the case only if the specification **required** `a != a` to return `false`). Therefore, there is nothing preventing us to make this assumption. Or do I misunderstand something? – proskor Aug 27 '13 at 10:51
  • This looks like this could be what C or C++ programmers calls "Undefined Behavior" (implementation dependent). Seems like there could be a few UB in java in corner cases like this one. – kriss Aug 27 '13 at 10:54
  • 1
    I don't think this is implementation dependent. Both LHS an RHS are **expressions** and expressions must be evaluated. It's exactly the same case as in `getA() != getA()`. Nobody would assume the method `getA()` to be called only once. Evaluating for fields means loading their value. – Sulthan Aug 27 '13 at 12:45
  • It depends on how the compiler generates the code. In C and C++, based on the optimization of the compiler the behaviour could be different. So there is no universal answer for this question without making assumptions. Understanding the disassembled code in the current platform would give the answer for that specific platform. – Rahul Sundar Aug 27 '13 at 13:20
  • @proskor that is an assumption which may or may not be valid. Therefore you should go by the language specification, not what some JRE produces. – Adrian Aug 27 '13 at 14:08
  • @Adrian Well, that's the point of an assumption: it may be true or not. But that doesn't mean it can't be useful. On the contrary: if you can prove that the generated bytecode is correct (i.e. the assumption is valid), you can immediately conclude that the claim (`a != a` can yield true) is true too. Thus you reduced the problem to another, perhaps simpler, one. To decide, whether the reduced problem is indeed simpler, is yet another problem. ;-) – proskor Aug 27 '13 at 14:26
  • JLS Section 15.7.1 States that LHS needs to be evaluated first: "The left-hand operand of a binary operator appears to be fully evaluated before any part of the right-hand operand is evaluated.". I'm not sure if that's sufficient for precluding a single-read optimization though. – Alexander Torstling Aug 27 '13 at 15:24
  • 6
    @Adrian: Firstly: even if that assumption is invalid, the existence of a *single* compiler where it can evaluate to "true" is enough to demonstrate that it can sometimes evaluate to "true" (even if the spec forbade it -- which it doesn't). Secondly: Java is well-specified, and most compilers conform closely to it. It makes sense to use them as a reference in this respect. Thirdly: you use the term "JRE", but I don't think it means what you think it means . . . – ruakh Aug 27 '13 at 15:41
  • 2
    @AlexanderTorstling - *"I'm not sure if that's sufficient for precluding a single-read optimization though."* It is not sufficient. In fact, in the absence of synchronization (and the extra "happens before" relationships that imposes), the optimization is valid, – Stephen C Aug 28 '13 at 09:49
  • @ruakh, you're right on your last point (I meant the JIT not the JRE), but your first 2 are not. Just because you reference a programme behaviour does not make it true, because that behaviour may be in error. "Most" does not mean "all". I'm not precluding that this isn't a potential way of starting an argument, or even adding some weight to one, but it definitely shouldn't be left as the conclusion of one (i.e. proof). – Adrian Aug 28 '13 at 17:38
  • 1
    In the absence of synchronization, it’s even allowed to perceive the second read happening before the first read, even for the same variable. Not that it matters for a symmetric operation like `!=` and it’s unlikely to happen in a simple code like this. But it’s allowed. – Holger Nov 16 '18 at 08:17
46

Is the check a != a thread-safe?

If a can potentially be updated by another thread (without proper synchronization!), then No.

I tried to program this and use multiple threads but didn't fail. I guess could not simulate race on my machine.

That doesn't mean anything! The issue is that if an execution in which a is updated by another thread is allowed by the JLS, then the code is not thread-safe. The fact that you cannot cause the race condition to happen with a particular test-case on a particular machine and a particular Java implementation, does not preclude it from happening in other circumstances.

Does this mean that a != a could return true.

Yes, in theory, under certain circumstances.

Alternatively, a != a could return false even though a was changing simultaneously.

Concerning the "weird behaviour":

As my program starts between some iterations I get the output flag value, which means that the reference != check fails on the same reference. BUT after some iterations the output becomes constant value false and then executing the program for a long long time does not generate a single true output.

This "weird" behaviour is consistent with the following execution scenario:

  1. The program is loaded and the JVM starts interpreting the bytecodes. Since (as we have seen from the javap output) the bytecode does two loads, you (apparently) see the results of the race condition, occasionally.

  2. After a time, the code is compiled by the JIT compiler. The JIT optimizer notices that there are two loads of the same memory slot (a) close together, and optimizes the second one away. (In fact, there's a chance that it optimizes the test away entirely ...)

  3. Now the race condition no longer manifests, because there are no longer two loads.

Note that this is all consistent with what the JLS allows an implementation of Java to do.

@kriss commented thus:

This looks like this could be what C or C++ programmers calls "Undefined Behavior" (implementation dependent). Seems like there could be a few UB in java in corner cases like this one.

The Java Memory Model (specified in JLS 17.4) specifies a set of preconditions under which one thread is guaranteed to see memory values written by another thread. If one thread attempts to read a variable written by another one, and those preconditions are not satisfied, then there can be a number of possible executions ... some of which are likely to be incorrect (from the perspective of the application's requirements). In other words, the set of possible behaviours (i.e. the set of "well-formed executions") is defined, but we can't say which of those behaviours will occur.

The compiler is allowed to combine and reorder loads and save (and do other things) provided the end effect of the code is the same:

  • when executed by a single thread, and
  • when executed by different threads that synchronize correctly (as per the Memory Model).

But if the code doesn't synchronize properly (and therefore the "happens before" relationships don't sufficiently constrain the set of well-formed executions) the compiler is allowed to reorder loads and stores in ways that would give "incorrect" results. (But that's really just saying that the program is incorrect.)

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
  • Does this mean that `a != a` could return true? – proskor Aug 27 '13 at 08:34
  • I meant that maybe on my machine I could not simulate that the above code is non-thread safe. So maybe there is a theoretical reasoning behind it. – Narendra Pathai Aug 27 '13 at 09:50
  • @NarendraPathai - There is no theoretical reason why you can't demonstrate it. There is possibly a practical reason ... or maybe you just didn't get lucky. – Stephen C Aug 27 '13 at 10:17
  • Please check my updated answer with the program that I am using. The check returns true sometimes but there seems to be a weird behavior in the output. – Narendra Pathai Aug 27 '13 at 10:21
  • 1
    @NarendraPathai - See my explanation. – Stephen C Aug 27 '13 at 10:48
  • Maybe I can get the JITed code and check that. I see what you are saying. – Narendra Pathai Aug 27 '13 at 10:50
  • Maybe you can :-). But that won't prove anything. The JIT'ed code depends of the platform (hardware, OS, JVM version, switches). It also depends on the pre-JIT execution stats ... which can depend on the application inputs, arguments, properties, environment variables and so on. Really the only things that matter are what the JLS says, and whether a specific bytecode / JIT compiler's behavior is deemed to comply with the spec. – Stephen C Feb 12 '15 at 22:39
27

Proved with test-ng:

public class MyTest {

  private static Integer count=1;

  @Test(threadPoolSize = 1000, invocationCount=10000)
  public void test(){
    count = new Integer(new Random().nextInt());
    Assert.assertFalse(count != count);
  }

}

I have 2 fails on 10 000 invocations. So NO, it is NOT thread safe

Arnaud Denoyelle
  • 29,980
  • 16
  • 92
  • 148
  • 6
    You're not even checking for equality... the `Random.nextInt()` part is superfluous. You could have tested with `new Object()` just as well. – Marko Topolnik Aug 27 '13 at 09:32
  • @MarkoTopolnik Please check my updated answer with the program that I am using. The check returns true sometimes but there seems to be a weird behavior in the output. – Narendra Pathai Aug 27 '13 at 10:21
  • 1
    A side note, Random-objects are usually meant to be reused, not created every time you need a new int. – Simon Forsberg Oct 20 '13 at 23:19
15

No, it is not. For a compare the Java VM must put the two values to compare on the stack and run the compare instruction (which one depends on the type of "a").

The Java VM may:

  1. Read "a" two times, put each one on the stack and then and compare the results
  2. Read "a" only one time, put it on the stack, duplicate it ("dup" instruction) and the run the compare
  3. Eliminate the expression completely and replace it with false

In the 1st case, another thread could modify the value for "a" between the two reads.

Which strategy is chosen depends on the Java compiler and the Java Runtime (especially the JIT compiler). It may even change during the runtime of your program.

If you want to make sure how the variable is accessed, you must make it volatile (a so called "half memory barrier") or add a full memory barrier (synchronized). You can also use some hgiher level API (e.g. AtomicInteger as mentioned by Juned Ahasan).

For details about thread safety, read JSR 133 (Java Memory Model).

stefan.schwetschke
  • 8,862
  • 1
  • 26
  • 30
  • Declaring `a` as `volatile` would still imply two distinct reads, with the possibility of a change in-between. – Holger Nov 16 '18 at 15:24
6

It has all been well explained by Stephen C. For fun, you could try to run the same code with the following JVM parameters:

-XX:InlineSmallCode=0

This should prevent the optimisation done by the JIT (it does on hotspot 7 server) and you will see true forever (I stopped at 2,000,000 but I suppose it continues after that).

For information, below is the JIT'ed code. To be honest, I don't read assembly fluently enough to know if the test is actually done or where the two loads come from. (line 26 is the test flag = a != a and line 31 is the closing brace of the while(true)).

  # {method} 'run' '()V' in 'javaapplication27/TestThreadSafety$1'
  0x00000000027dcc80: int3   
  0x00000000027dcc81: data32 data32 nop WORD PTR [rax+rax*1+0x0]
  0x00000000027dcc8c: data32 data32 xchg ax,ax
  0x00000000027dcc90: mov    DWORD PTR [rsp-0x6000],eax
  0x00000000027dcc97: push   rbp
  0x00000000027dcc98: sub    rsp,0x40
  0x00000000027dcc9c: mov    rbx,QWORD PTR [rdx+0x8]
  0x00000000027dcca0: mov    rbp,QWORD PTR [rdx+0x18]
  0x00000000027dcca4: mov    rcx,rdx
  0x00000000027dcca7: movabs r10,0x6e1a7680
  0x00000000027dccb1: call   r10
  0x00000000027dccb4: test   rbp,rbp
  0x00000000027dccb7: je     0x00000000027dccdd
  0x00000000027dccb9: mov    r10d,DWORD PTR [rbp+0x8]
  0x00000000027dccbd: cmp    r10d,0xefc158f4    ;   {oop('javaapplication27/TestThreadSafety$1')}
  0x00000000027dccc4: jne    0x00000000027dccf1
  0x00000000027dccc6: test   rbp,rbp
  0x00000000027dccc9: je     0x00000000027dcce1
  0x00000000027dcccb: cmp    r12d,DWORD PTR [rbp+0xc]
  0x00000000027dcccf: je     0x00000000027dcce1  ;*goto
                                                ; - javaapplication27.TestThreadSafety$1::run@62 (line 31)
  0x00000000027dccd1: add    rbx,0x1            ; OopMap{rbp=Oop off=85}
                                                ;*goto
                                                ; - javaapplication27.TestThreadSafety$1::run@62 (line 31)
  0x00000000027dccd5: test   DWORD PTR [rip+0xfffffffffdb53325],eax        # 0x0000000000330000
                                                ;*goto
                                                ; - javaapplication27.TestThreadSafety$1::run@62 (line 31)
                                                ;   {poll}
  0x00000000027dccdb: jmp    0x00000000027dccd1
  0x00000000027dccdd: xor    ebp,ebp
  0x00000000027dccdf: jmp    0x00000000027dccc6
  0x00000000027dcce1: mov    edx,0xffffff86
  0x00000000027dcce6: mov    QWORD PTR [rsp+0x20],rbx
  0x00000000027dcceb: call   0x00000000027a90a0  ; OopMap{rbp=Oop off=112}
                                                ;*aload_0
                                                ; - javaapplication27.TestThreadSafety$1::run@2 (line 26)
                                                ;   {runtime_call}
  0x00000000027dccf0: int3   
  0x00000000027dccf1: mov    edx,0xffffffad
  0x00000000027dccf6: mov    QWORD PTR [rsp+0x20],rbx
  0x00000000027dccfb: call   0x00000000027a90a0  ; OopMap{rbp=Oop off=128}
                                                ;*aload_0
                                                ; - javaapplication27.TestThreadSafety$1::run@2 (line 26)
                                                ;   {runtime_call}
  0x00000000027dcd00: int3                      ;*aload_0
                                                ; - javaapplication27.TestThreadSafety$1::run@2 (line 26)
  0x00000000027dcd01: int3
assylias
  • 321,522
  • 82
  • 660
  • 783
  • 1
    This is a good example of the kind of code that JVM will actually produce when you have an infinite loop and everything can more or less be hoisted out. The actual "loop" here are the three instructions from `0x27dccd1` to `0x27dccdf`. The `jmp` in the loop is unconditional (since the loop is infinite). The only other two instructions in the loop are `add rbc, 0x1` - which is incrementing `countOfIterations` (despite the fact that the loop will never be exited so this value won't be read: perhaps it is needed in case you break into it in the debugger), ... – BeeOnRope May 15 '17 at 19:03
  • ... and the weird looking `test` instruction, which is actually there only for the memory access (note that `eax` is never even set in the method!): it's a special page that is set to not-readable when the JVM wants to trigger all threads to reach a safepoint, so it can do gc or some other operation that requires all threads to be in a known state. – BeeOnRope May 15 '17 at 19:04
  • More to the point, the JVM completely hoisted the `instance. a != instance.a` comparison out of the loop, and only performs it once, before the loop is entered! It knows that it is no required to reload `instance` or `a` as they are not declared volatile and there is no other code that can change them on the same thread, so it just assumes they are the same during the entire loop, which is allowed by the memory model. – BeeOnRope May 15 '17 at 19:06
5

No, a != a is not thread safe. This expression consists of three parts: load a, load a again, and perform !=. It is possible for another thread to gain the intrinsic lock on a's parent and change the value of a in between the 2 load operations.

Another factor though is whether a is local. If a is local then no other threads should have access to it and therefore should be thread safe.

void method () {
    int a = 0;
    System.out.println(a != a);
}

should also always print false.

Declaring a as volatile would not solve the problem for if a is static or instance. The problem is not that threads have different values of a, but that one thread loads a twice with different values. It may actually make the case less thread-safe.. If a isn't volatile then a may be cached and a change in another thread won't affect the cached value.

DoubleMx2
  • 375
  • 1
  • 9
  • Your example with `synchronized` is wrong: for that code to be guaranteed to print `false`, all methods that *set* `a` would have to be `synchronized`, too. – ruakh Aug 27 '13 at 15:44
  • Why so? If the method is synchronized how would any other thread gain the intrinsic lock on `a`'s parent while the method is executing, necessary to set the value `a`. – DoubleMx2 Aug 27 '13 at 16:05
  • 1
    Your premises are wrong. You can set an object's field without acquiring its intrinsic lock. Java doesn't require a thread to acquire an object's intrinsic lock before setting its fields. – ruakh Aug 27 '13 at 17:12
3

Regarding the weird behaviour:

Since the variable a is not marked as volatile, at some point it might value of a might be cached by the thread. Both as of a != a are then the cached version and thus always the same (meaning flag is now always false).

Walter Laan
  • 2,956
  • 17
  • 15
0

Even simple read is not atomic. If a is long and not marked as volatile then on 32-bit JVMs long b = a is not thread-safe.

ZhekaKozlov
  • 36,558
  • 20
  • 126
  • 155