double check lock without volatile is wrong？

Question

i use jdk1.8. i think that double check lock without volatile is right. I use countdownlatch test many times and the object is singleton. How to prove that it must need “volatile”？

update 1

Sorry, my code is not formatted, because I can’t receive some JavaScript public class DCLTest {

private static /*volatile*/ Singleton instance = null;

static class Singleton {

    public String name;

    public Singleton(String name) {
        try {
            //We can delete this sentence, just to simulate various situations
            Thread.sleep(1);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        this.name = name;
    }
}

public static Singleton getInstance() {
    if (null == instance) {
        synchronized (Singleton.class) {
            if (null == instance) {
                instance = new Singleton(Thread.currentThread().getName());
            }
        }
    }
    return instance;
}

public static void test() throws InterruptedException {
    int count = 1;
    while (true){
        int size = 5000;
        final String[] strs = new String[size];
        final CountDownLatch countDownLatch = new CountDownLatch(1);
        for (int i = 0; i < size; i++) {
            final int index = i;
            new Thread(()->{
                try {
                    countDownLatch.await();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                Singleton instance = getInstance();
                strs[index] = instance.name;
            }).start();
        }
        Thread.sleep(100);
        countDownLatch.countDown();
        Thread.sleep(1000);
        for (int i = 0; i < size-1; i++) {
            if(!(strs[i].equals(strs[i+1]))){
                System.out.println("i = " + strs[i] + ",i+1 = "+strs[i+1]);
                System.out.println("need volatile");
                return;
            }
        }
        System.out.println(count++ + " times");
    }
}

public static void main(String[] args) throws InterruptedException {
    test();
}

}

Answer 1

The key problem that you are not seeing is that instructions can be reordered. So the order they are in the source code, isn't the same as they are applied on memory. CPU's and compilers are the cause or this reordering.

I'm not going through the whole example of example of double checked locking because many examples are available, but will provide you just enough information to do some more research.

if you would have the following code:

 if(singleton == null){
     synchronized{
         if(singleton == null){
            singleton = new Singleton("foobar")
         }
     }
 }

Then under the hood something like this will happen.

if(singleton == null){
     synchronized{
         if(singleton == null){
            tmp = alloc(Singleton.class)
            tmp.value = "foobar"
            singleton = tmp
         }
     }
 }

Till so far, all is good. But the following reordering is legal:

if(singleton == null){
     synchronized{
         if(singleton == null){
            tmp = alloc(Singleton.class)
            singleton = tmp
            tmp.value = "foobar"
         }
     }
 }

So this means that a singleton that hasn't been completely constructed (the value has not yet been set) has been written to the singleton global variable. If a different thread would read this variable, it could see a partially created object.

There are other potential problems like atomicity (e.g. if the value field would be a long, it could be fragmented e.g. torn read/write). And also visibility; e.g. the compiler could optimize the code so that the load/store from memory is optimized-out. Keep in mind that thinking in term of reading from memory instead of cache, is fundamentally flawed and the most frequently encountered misunderstandings I see on SO; even many seniors get this wrong. Atomicity, visibility and reordering are part of the Java memory model, and making the singleton' variable volatile, resolves all these problems. It removes the data race (you can look it up for more details).

If you want to be really hardcore, it would be sufficient to place a [storestore] barrier between the creation of an object and the assignment to the singleton and a [loadload] barrier on the reading side and make sure you use a VarHandle with opaque for the singleton.

But this goes well beyond what most engineers understand and it won't make much of a performance difference in most situations.

If you want to check if something can break, please check out JCStress:

https://github.com/openjdk/jcstress

It is a great tool and can help you help you to show that your code is broken.

Answer 2

How to prove that it must need “volatile”？

As a general rule, you cannot prove correctness of a multi-threaded application by testing. You may be able to prove incorrectness, but even that is not guaranteed. As you are observing.

The fact that you haven't succeeded in making your application fail is not a proof that it is correct.

The way to prove correctness is to do a formal (i.e. mathematical) happens before analysis.

It is fairly straightforward to show that when the singleton is not volatile there are executions in which there is a missing happens before. This may lead to an incorrect outcome such as the initialization happening more than once. But it is not guaranteed that you will get an incorrect outcome.

The flip-side is that if a volatile is used, the happens before relationships combined with the logic of the code are sufficient to construct a formal (mathematical) proof that you will always get a correct outcome.

---

(I am not going to construct the proofs here. It is too much effort.)