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?

http://en.wikipedia.org/wiki/Initialization-on-demand_holder_idiom — spudone, May 15 '15 at 17:30
@spudone thanks, I'm familiar with holder idiom, but unsure about its lock-freeness — Alex Salauyou, May 15 '15 at 17:50
It does, in effect, cause initialization to be serial, but this is less expensive than accidentally creating 2 (or more) objects, as you mentioned. — spudone, May 15 '15 at 18:02
To get true lock freedom you will need to do some sort of spinning while the object is being created. — John Vint, May 15 '15 at 18:37
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. — specializt, May 15 '15 at 18:53
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. — specializt, May 15 '15 at 19:00
@specializt locking by parking a thread is very different from locking in CAS.... — Alex Salauyou, May 15 '15 at 19:32
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. — specializt, May 15 '15 at 19:45
Jeez @specializt. The term lock-free is well known and widely used. There is no reason to argue such insignificant points in this case. — John Vint, May 16 '15 at 02:30
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. — specializt, May 16 '15 at 10:32
@SashaSalauyou What do you expect from your bounty? What is lacking in the current answers? — assylias, May 21 '15 at 11:41
@assylias *"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? — Alex Salauyou, May 21 '15 at 18:13
Possible duplicate of [How to implement thread-safe lazy initialization?](http://stackoverflow.com/questions/8297705/how-to-implement-thread-safe-lazy-initialization) — Vadzim, Mar 01 '17 at 18:36
@Vadzim not exactly. "Thread-safe" in common sense doesn't include lock- and wait-free conditions. — Alex Salauyou, Mar 12 '17 at 12:45
@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. — Vadzim, Mar 13 '17 at 05:45
@Vadzim 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. — Alex Salauyou, Mar 13 '17 at 14:28

John Vint · Accepted Answer · 2015-06-24T18:49:07.100

22

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.

edited Jun 24 '15 at 18:49

answered May 15 '15 at 18:42

John Vint

39,695
7
78
108

well, this is interesting, despite it is not wait-free. I should test it also. – Alex Salauyou May 15 '15 at 18:50
@SashaSalauyou Yes, I meant to use an AtomicBoolean – John Vint May 15 '15 at 23:04
@SashaSalauyou And you're right it's not wait-free. – John Vint May 16 '15 at 02:32
`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. – Michael Shopsin May 27 '15 at 16:56
2

Take a read into http://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. – John Vint May 27 '15 at 16:58
5

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. – John Vint May 27 '15 at 17:01

Giovanni Botta · Answer 2 · 2017-05-06T20:17:34.447

4

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.

edited May 06 '17 at 20:17

answered May 15 '15 at 18:55

Giovanni Botta

9,626
5
51
94

Thanks, I know this approach, but now I'm looking for lock-free one :) – Alex Salauyou May 15 '15 at 18:59
1

May I ask why? The alternatives (spinning, using additional atomic variables) are not very appealing IMO and make things so much more complicated. – Giovanni Botta May 15 '15 at 19:04
Atomic reference is used because it is CASed in other pieces of code. – Alex Salauyou May 15 '15 at 19:30
I mean why you wanted lock-free init. – Giovanni Botta May 15 '15 at 19:31
1

To achieve full lock- and wait-freedom. I agree, this question is not very practical. Curiosity. – Alex Salauyou May 15 '15 at 19:34
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. – Giovanni Botta May 27 '15 at 11:44
You never call `AtomicReference.set(foo)` so every call to `getInstance()` will create a `new Foo()` – lance-java Apr 26 '17 at 08:36

score 0 · Answer 3 · answered May 27 '15 at 14:38

0

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.

answered May 27 '15 at 14:38

m c

1,104
1
12
21

1

What you offer is a common pattern but it is not lock- nor wait-free. – Alex Salauyou May 27 '15 at 15:33
See in detail: http://stackoverflow.com/questions/8297705/how-to-implement-thread-safe-lazy-initialization – Vadzim Mar 13 '17 at 05:52

score 0 · Answer 4 · answered May 28 '15 at 06:35

0

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

answered May 28 '15 at 06:35

Chand Priyankara

6,739
2
40
63

1

How will it help? Please provide an example. – Alex Salauyou May 28 '15 at 07:10

score -1 · Answer 5 · answered May 26 '15 at 17:58

-1

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;
}

answered May 26 '15 at 17:58

Bhupi

387
3
16

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 . – Bhupi May 26 '15 at 20:27
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. – Alex Salauyou May 26 '15 at 20:47

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

5 Answers5

Linked