Does this implementation work for a Lock-less Thread Safe Lazy Singleton in Java?

Question

This is what I have so far, am I going in the right direction? Aim is to use this in scenarios where one thread requires access to the singleton more frequently than other threads, hence lock-less code is desirable, I wanted to use atomic variables for practice.

public final class ThreadSafeLazyCompareAndSwapSingleton {

private ThreadSafeLazyCompareAndSwapSingleton(){}

private static volatile ThreadSafeLazyCompareAndSwapSingleton instance;
private final static AtomicBoolean atomicBoolean = new AtomicBoolean(false);

public static ThreadSafeLazyCompareAndSwapSingleton getCASInstance(){
    if (instance==null){
        boolean obs = instance==null;
        while (!atomicBoolean.compareAndSet(true, obs == (instance==null))){
            instance = new ThreadSafeLazyCompareAndSwapSingleton(); 
        }
    }
    return instance;
}

}

Answer 1

Uh, it is hard to read with those inline conditions/assigns. It is also pretty much non-standard idiom, so I wonder if you really want to use it.

It has at least the problem that it can create more than one instance (might be acceptable in your case, you cant really avoid that if you want to be lock-free). But I think it also might return more than one instance, which is not what you want to have I guess.

I am not sure if you need a boolean, you could also use a AtomicReferenceFieldUpdater directly on the instance field.

I think the obs is not needed, you would create and return a new instance if you can set the boolean, and loop otherwise:

if (instance!=null)
  return instance;

if (atomicBoolean.compareAndSet(false, true))
{
  instance = new ThreadSafeLazyCompareAndSwapSingleton();
  return instance;
}
while(instance==null);
return instance;

But I really dont think it is a good idea to go with this extra boolean.

Answer 2

Something like this would be safer - but there are better ways than this.

public final class ThreadSafeLazyCompareAndSwapSingleton {

    // THE instance.
    private static volatile ThreadSafeLazyCompareAndSwapSingleton instance;
    // Catches just one thread.
    private final static AtomicBoolean trap = new AtomicBoolean(false);

    public static ThreadSafeLazyCompareAndSwapSingleton getInstance() {
        // All threads will spin on this loop until instance has been created.
        while (instance == null) {
            // ONE of the spinning threads will get past the trap. Probably the first one.
            if ( trap.compareAndSet(false, true)) {
                // By definition of CAS only one thread will get here and construct.
                instance = new ThreadSafeLazyCompareAndSwapSingleton();
            }
        }
        // By definition instance can never be null.
        return instance;
    }

    // Dont let anyone but me construct.
    private ThreadSafeLazyCompareAndSwapSingleton() {
    }

}

Note that this fails if an exception is thrown during the construction.

Answer 3

A good mental approach here would be to separate threads into two categories: those that can instantiate the class, and those that can't. (For conciseness, I'll shorten the class name to just Singleton). Then you have to think about what each category of threads needs to do:

• instantiating threads need to store the reference they create in instance and return it
• all other threads need to wait until instance has been set, and then return it

Additionally, we need to ensure two things:

• That there is a happens-before edge between the instantiation and all returns (including ones in non-instantiating threads). This is for thread safety.
• That the set of instantiating threads has exactly one element (assuming either set is non-empty, of course). This is to ensure that there's only one instance.

Okay, so those are our four requirements. Now we can write code that satisfies them.

private final AtomicBoolean instantiated = new AtomicBoolean(false);
private static volatile Singleton instance = null;
// volatile ensures the happens-before edge

public static Singleton getInstance() {
    // first things first, let's find out which category this thread is in
    if (instantiated.compareAndSet(false, true) {
        // This is the instantiating thread; the CAS ensures only one thread
        // gets here. Create an instance, store it, and return it.
        Singleton localInstance = new Singleton();
        instance = localInstance;
        return localInstance;
    } else {
        // Non-instantiating thread; wait for there to be an instance, and
        // then return it.
        Singleton localInstance = instance;
        while (localInstance == null) {
            localInstance = instance;
        }
        return localInstance;
    }
}

Now, let's convince ourselves that each one of our conditions are met:

• Instantiating thread creates an instance, stores it, and returns it: this is the "true" block of the CAS.
• Other threads wait for an instance to be set, and then return it: That's what the while loop does.
• There is a happens-before (HB) edge between instantiation and returning: For the instantiating thread, within-thread semantics ensure this. For all other threads, the volatile keyword ensures a HB edge between the write (in the instantiating thread) and the read (in this thread)
• That the set of instantiating threads is exactly one large, assuming the method is ever invoked: The first thread to hit the CAS will have it return true; all others will return false.

So we're all set.

The general advice here is to break down your requirements into sub-requirements that are as specific as possible. Then you can address each one separately, which is easier to reason about.