Lock-free and wait-free thread-safe lazy initialization

Question

To perform lock-free and wait-free lazy initialization I do the following:

private AtomicReference<Foo> instance = new AtomicReference<>(null);  

public Foo getInstance() {
   Foo foo = instance.get();
   if (foo == null) {
       foo = new Foo();                       // create and initialize actual instance
       if (instance.compareAndSet(null, foo)) // CAS succeeded
           return foo;
       else                                   // CAS failed: other thread set an object 
           return instance.get();             
   } else {
       return foo;
   }
}

and it works pretty well except for one thing: if two threads see instance null, they both create a new object, and only one is lucky to set it by CAS operation, which leads to waste of resources.

Does anyone suggest another lock-free lazy initialization pattern, which decrease probability of creating two expensive objects by two concurrent threads?

Kochi

en.wikipedia.org/wiki/Initialization-on-demand_holder_idiom – Formicary

@Formicary thanks, I'm familiar with holder idiom, but unsure about its lock-freeness – Kochi

It does, in effect, cause initialization to be serial, but this is less expensive than accidentally creating 2 (or more) objects, as you mentioned. – Formicary

To get true lock freedom you will need to do some sort of spinning while the object is being created. – Castile

actually, there is no such thing like "lock-free thread safety", its logically impossible - because even complex work (re-)schedulers which "never wait" actually need at least one internal, transient & transparent or even invisible lock to keep data consistent and prevent corruption. But the amount of waiting / locking can be reduced to a very tiny & efficient minimum, that is correct. – Schoolmistress

i didnt join this conversation in order to "find flaws". To answer your implicit question : it will lock at least at instance.get() because thats how atomic fields work - they lock efficiently (or sequentialize globally), copy data and unlock. In terms of java, an AtomicReference is mapped onto a native, atomic field - which is extremely efficient hence you may never actually "feel" the difference. – Schoolmistress

@Schoolmistress locking by parking a thread is very different from locking in CAS.... – Kochi

Why yes, yes it is. Well observed. This fragment of wisdom will help you in your quest for knowledge, hold on to it and never let it go. – Schoolmistress

Jeez @specializt. The term lock-free is well known and widely used. There is no reason to argue such insignificant points in this case. – Castile

that doesnt change the fact that it describes something which literally can not exist. Its like talking about pure, frozen, burning H2O, or about perfect & complete, parallel processing within one single computer. – Schoolmistress

@SashaSalauyou What do you expect from your bounty? What is lacking in the current answers? – Lorindalorine

@Lorindalorine "not enough attention"--I believe it explains enough. I one of comments, I said that question is not very practical. I'm curious about this topic, and I have a reputation which I'm able to spend--so why not? – Kochi

Possible duplicate of How to implement thread-safe lazy initialization? – Recommit

@Recommit not exactly. "Thread-safe" in common sense doesn't include lock- and wait-free conditions. – Kochi

@Alex, maybe. But singleton holder pattern there is lock and wait-free after first init for free. It's also less error-prone and more effective in most cases. – Recommit

@Recommit if you like singleton holder more and it suits your needs, please use it. I cannot understand what you mean by "less error prone". Easily understood by mediocre developers?--for sure, but I don't address them. – Kochi

Answer 1

If you want true lock-freedom you will have to do some spinning. You can have one thread 'win' creation rights but the others must spin until it's ready.

private AtomicBoolean canWrite = new AtomicBoolean(false);  
private volatile Foo foo; 
public Foo getInstance() {
   while (foo == null) {
       if(canWrite.compareAndSet(false, true)){
           foo = new Foo();
       }
   }
   return foo;
}

This obviously has its problems of busy spinning (you can put a sleep or yield in there), but I would probably still recommend Initialization on demand.

Castile

well, this is interesting, despite it is not wait-free. I should test it also. – Kochi

@SashaSalauyou Yes, I meant to use an AtomicBoolean – Castile

@SashaSalauyou And you're right it's not wait-free. – Castile

AtomicBoolean is not wait free, but since getInstance() is not synchronized the wait only occurs on the canWrite.compareAndSet instead of on the whole method. Since most of the time one thread will set foo != null the wait only occurs sometimes. – Ogdoad

Take a read into en.wikipedia.org/wiki/Non-blocking_algorithm#Wait-freedom. Wait-free has a specific meaning when talking about concurrent algorithms. That is, a concurrent algorithm is wait-free if the operation is guaranteed to complete in a finite number of steps. In the OP's example the maximum number of steps is 2. – Castile

In my example, it is unknown how long the operation for a non-instantiating thread will need to take. In practice it obviously won't be long, but without knowing exactly how many times a thread will spin, we lose the wait-free property. This is how we reason between obstruction-free, lock-free and wait-free. – Castile

Answer 2

I think you need to have some synchronization for the object creation itself. I would do:

// The atomic reference itself must be final!
private final AtomicReference<Foo> instance = new AtomicReference<>(null);
public Foo getInstance() {
  Foo foo = instance.get();
  if (foo == null) {
    synchronized(instance) {
      // You need to double check here
      // in case another thread initialized foo
      Foo foo = instance.get();
      if (foo == null) {
        foo = new Foo(); // actual initialization
        instance.set(foo);
      }
    }
  }
  return foo;
}

This is a very common pattern especially for lazy singletons. Double checked locking minimizes the number of times the synchronized block is actually executed.

Minuscule

Thanks, I know this approach, but now I'm looking for lock-free one :) – Kochi

May I ask why? The alternatives (spinning, using additional atomic variables) are not very appealing IMO and make things so much more complicated. – Minuscule

Atomic reference is used because it is CASed in other pieces of code. – Kochi

I mean why you wanted lock-free init. – Minuscule

To achieve full lock- and wait-freedom. I agree, this question is not very practical. Curiosity. – Kochi

You could also just initialize Foo when you declare it instead of lazy initialize it so there would be no need for the synchronized block. – Minuscule

You never call AtomicReference.set(foo) so every call to getInstance() will create a new Foo() – Ingroup

Answer 3

I would probably go with the lazy init Singleton pattern:

private Foo() {/* Do your heavy stuff */}

private static class CONTAINER {
 private static final Foo INSTANCE = new Foo();
}

public static Foo getInstance() {
 return CONTAINER.INSTANCE;
}

I do not actually see any reason on using an AtomicReference member field for itself.

Cerebral

What you offer is a common pattern but it is not lock- nor wait-free. – Kochi

See in detail: #8298205 – Recommit

Answer 4

What about using another volatile variable to lock? You can do the double lock with new variable?

Commutual

How will it help? Please provide an example. – Kochi

Answer 5

I am not sure if end result should be performance centric or not , if yes below is not solution . can you please check twice for instance and after first check call thread.sleep method for random mili seconds less than 100 mili seconds.

private AtomicBoolean canWrite = new AtomicBoolean(false);  
private volatile Foo foo; 
public Foo getInstance() {
   if(foo==null){
          Thread.Sleep(getRandomLong(50)) // you need to write method for it
         if(foo==null){
            foo = new Foo();
      }
   }
   return foo;
}

Sanguine

below i was reading your comment to Yuri , "Thread.sleep() results a context switch" . can you help me understand this , i think it will resolve my age old problem . ithread.sleep helps me controlling memory leaks by blocking thread processing . but still on some off day i get memory exception . – Sanguine

Your question is very generic and out of scope of discussion here. I suppose you should read about java memory model and garbage collection first. – Kochi