Double Checked Locking And Java Singletons

Consider a singleton class:

class FooSingleton { 
private String name;

  private FooSingleton instance; 

  private FooSingleton(String name_)
  {
      name=name_;
  }
  public FooSingleton getInstance() {
    if (instance== null) 
        instance= new FooSingleton ();
    return FooSingleton ;
    }
  // other functions and members...
  }

The Singleton pattern is used when we want to ensure that there is only one instance of a class per something. In most cases, the something is 'JVM - Classloader' combination. So, in such cases we want to ensure that there is only one instance of the Singleton class in the JVM-Classloader. But we are not restricted to this. We may need only one instance of the Singleton per Session, or per Request, or per anything else that makes sense in the software you are making.

It is clear that we want to control the instantiation process of the Singleton class. To do this, the first thing we do as shown in the example is to make the constructor private. With the constructor private, no other class can create an instance of this class. OK, so how will we create any instance of this class? We provide a public static method called getInstance() which will return an instance of this class. We will also use a private static field called instance to hold the one and only instance of this class. Since we control the getInstance() method, every time it is invoked we will return instance. The first time however, instance will not be initialized, so we put a null check in getInstance() and instantiate instance if it has not already been instantiated. Hence forth we will always return a reference to instance. This way we ensure that only one instance of our Singleton will be ever created (the one we save in the field called instance).

Is This A Safe Singleton?
Answer : No, Singleton is not thread-safe.

Explanation
Consider getInstance() method. Imagine that a thread T1 invokes getInstance(). If an instance of the Singleton has not been created till now, then instance will be null, and T1 will enter the if block. Now imagine that T1 gets pre-empted, and thread T2 also calls getInstance(). Since T1 got pre-empted before it got a chance to create instance, the reference in instance is still null. So T2 will also enter the if block. Now if T2 does not get pre-empted then it will go ahead all the way where it will create an instance of Singleton, and probably even use it. Now when T1 is resumed, unfortunately it does not know that the Singleton has already been created, since it has already gone past the null check. T1 will also happily create an instance of our Singleton, thus breaking the Singleton pattern. We have 2 instances of the Singleton which is simply not allowed.

Making Singleton threadsafe

Approach1 
Using synchronized, we can make our singleton class threadsafe.
eg.
public static synchronized FooSingleton getInstance(){}

Making a method synchronized is expensive. A thread executing a synchronized method must acquire a monitor before it can invoke the method, and release the monitor after executing the method. This takes time and CPU cycles. In early JVM's (I have read somewhere), the time to invoke (not execute) a synchronized method was as much as 100x the time taken to invoke a non synchronized method. I think this was improved in later JVM's where it was about 15x. I recently did a quick test on JDK 1.6, and the number I got was 2x. Regardless of how much slower it is, it is definitely slower, and programmers always want to make their code fast.

Approach 2 - Use Double Checked Locking

class FooSingleton { 
private String name;

  private FooSingleton instance; 

  private FooSingleton(String name_)
  {
      name=name_;
  }
  public synchronized FooSingleton getInstance() {
  if(intance==null){
      synchronized(FooSingleton.class){
        if (instance== null) 
            instance= new FooSingleton ();    
        }
    }
    return FooSingleton ;
  }
  // other functions and members...
  } 

So instead of using synchronized for getInstance, we use it for class level using :  synchronized(FooSingleton.class)

What we really should have done, is only synchronize the code which instantiates the Singleton, and not the entire method. That way we incur the expense of the synchronized block only once, when the Singleton needs to be created, and all subsequent times (instance == null) will always be false, and the instance will be returned to the calling code. We put a second check inside the synchronized block, because it is possible that a thread could get pre-empted just after the first null check, but before it enters the synchronized block. In such a case, if another thread enters this method, and goes all the way to creating the instance then the first thread will not know of it and will create a second instance. To prevent this, we put another check in the synchronized block.

Will It Work?
Answer is no. But why?
There are two reasons why it does not work. The compiler as well as the processor (as well as the JVM) may reorder instructions if they feel it might be more optimal. Off course they cannot randomly reorder instructions but they could if they can prove that the reordering will maintain as-if-serial semantics. However, this is not the only reason. On a multi-processor system, each processor has it's own memory cache. The cache is not always synchronized with main memory immediately. This can cause a write to a memory location to happen in the local cache, which will not be visible to other threads which could be running on other processors. Even if the writing thread does flush it's local cache, it is still possible that another thread which reads that value, may not have pulled in most recent values from the main memory into it's local cache. This can cause a situation very similar to reordering where the effect of a write is not visible to another thread that is reading that variable's value.

Is  statement below is atomic statement -- you might think that the statement below is an atomic statement.

instance = new FooSingleton ();

But that is not the case. For the sake of simplicity this slide shows the statement above broken into 2 operations. In the first part, an instance of the class is constructed, and in the second part a reference to that instance is assigned to the variable instance.

Compiler Reordering:

Now what if the compiler reorders the instructions in such a way that the field instance is assigned an uninitialized block of memory (created for the class FooSingleton ), and then the constructor of FooSingleton is invoked in the second step.

Compiler Reordering Pseudocode:

This slides shows pseudocode to understand the effect of compiler reordering on the double checked locking code. The code in the synchronzied block which instantiates our Singleton is broken into two steps: assignment, and initialization, where the assignment happens before the initialization.

Now imagine thread T1 enters the getInstance() method, enters the synchronized block and executes the statement which assigns the block of memory allocated for FooSingleton to the variable called instance. If T1 gets preempted and thread T2 enters getInstance() then T2 may see a non null value for instance. Thus T2 will actually be returned an initialized object of FooSingleton . This could cause all sorts of bugs in the software.

So in the first problem described a few slides back, we ran into the issue of having multiple instances of our Singleton, which we attempted to fix with the double checked locking idiom. However, this introduced the issue where a thread might be given a reference to an uninitialized instance of the Singleton.

Can We Prevent reordering:

Programmers never give up :-) When an even smarter programmer was explained this problem, he remarked "so let us prevent reordering and our problem will be solved !". Ok let's try that, but how do we prevent reordering? Well there is something called a memory barrier, which may help us. Instructions cannot be reordered across memory barriers (although they may be reordered within a memory barrier). Let's see if we can introduce memory barriers to prevent the reordering that's been giving us such a hard time till now.

Memory Barrier:

A memory barrier is a low level (at the level of the processor) construct which is used to create a fence around instructions. Instructions which are fenced inside a memory barrier cannot be moved out of the fence, and memory caches are also synched with main memory when a memory barrier is encountered.

slide 15 (Memory Barrier):

Now consider the instruction set :

instr1

instr2

instr3

instr4

instr5

Instructions instr1 and instr5 (in red) are not allowed to move any bottom or down, but instructions in green are allowed to reorder.

Notice that instructions (instr2, instr3, & instr3) are fenced with the memory barrier. Because of the semantics of a memory barrier these instructions can never be moved out of the barrier, but they may be re-ordered within the memory barrier. We can also see when the memory barrier is entered the local processor cache is invalidated and latest values are read from the main memory, and when the memory barrier is exited then the local cached is flushed and the main memory is updated with the latest values.

The synchronized keyword in Java creates a memory barrier

Because memory barrier is a low level construct, there is no way to explicitly create one in a high level language like Java. However, the synchronized keyword in Java implicitly creates a memory barrier. Before I read this, I had no clue that synchronization in Java is anything more than a mutex. But I read somewhere that when a monitor is obtained an memory barrier is also created and when a monitor is released the memory barrier ends (this is my understanding, please correct me if this is wrong).

Double Checked Locking With Memory Barrier:

public synchronized FooSingleton getInstance() {
  if(intance==null)
  {
      FooSingleton tempInstance;
      synchronized(FooSingleton.class)
       {
          if (tempInstance== null)
          {
               tempInstance= new FooSingleton ();    
          } 
          instance=tempInstance;
       }
    }
    return instance;
}

The fact that assignment and construction of our Singleton could be reordered created the issue of potentially having an uninitialized Singleton. We want to ensure that the reordering does not happen. For that let us separate the construction and assignment with a memory barrier and put the assignment after the construction. We do this with 2 synchronized blocks and a temporary variable. In the inner synchronized block we will initialize the Singleton and assign it to a temporary variable. We don't care if this is reordered, because the class variable instance will still be null which will prevent another thread from getting an initialized instance of the Singleton. Then we assign the reference to the temporary variable to the class variable instance. This happens outside the memory barrier. So by employing a memory barrier we are hoping to maintain program order in the execution of instructions. Again a very smart solution, but unfortunately this does not work either.

Monitor Exit Semantics:

The semantics of monitor exit specify that everything that happened before the monitor exit should happen before it, which means that nothing from the inner synchronized block (where we instantiate the Singleton) will be moved out of the inner synchronized block, however, it does not mean that something will not be moved from outside of the block to within it.

instr2

instr3

instr4

So consider  inst2 and inst3 are within the memory barrier. Neither of them will be moved out of the block, but inst4 which is out of the memory barrier may be moved in the barrier.

Double Checked Locking With Memory Barrier

So consider above code(getInstance method) with a potential reordering. With the statement instance = tempInstance inside the memory barrier it could be further reordered to the point before the actual construction of the Singleton, bringing us back to the same problem.

OK So What The Hell Will Work ?:

Alright enough of playing around... not I am getting a bit edgy.... just tell me what the hell is going to work. Is this what you are saying to yourself? Java has a special modifier called volatile. We can use these fields to help us with the Singleton.

Semantics of volatile:

The volatile modifier is used in Java to communicate state changes between threads. This slide explains the semantics of volatile with an illustration.

Double Checked Locking With Volatile:

So now our solution comes to:

private static volatile FooSingleton instance;

This elimitaes the problem of seeing an uninitialized Singleton object.

Singleton With Static Initializer:

After doing all these coding gymnastics, we show a solution which is probably the simplest solution for creating a thread safe Singleton. Instead of instantiating the Singleton in getInstance(), we use a static initializer, which will instantiate the Singleton when the class is loaded. Java semantics ensure us that all static fields of a class will be completely initialized before the class is available for use. This means that the field instance will be properly initialized before anyone makes use of the class to get an instance of the Singleton.

Singleton With Static Initializer:

In this slide we understand the pros and cons of using a static initializer. Even though using a static initializer is the simplest solution, it is possible that everything the Singleton needs to initialize itself may not be available when the class is loaded (which causes the static initializer to be invoked). It is also possible that the Singleton may be eagerly loaded, which may result in greater loading time for our application, something that may be undesirable if instantiating the Singleton is an expensive operation.

Summary:

• The compiler as well as the processor can reorder instructions under certain conditions
• Even if the instructions are not re-ordered, a thread may still see a stale value of a field due to memory caching
• Synchronization creates an implicit memory barrier
• Code cannot be moved from within the memory barrier to outside of it
• Code MAY be moved from outside a memory barrier to within it
• Volatile fields cannot be re-ordered with respect to other volatile fields, and are very difficult to reorder in respect to non volatile fields 
• A read to a volatile field invalidates the processor cache and fetches values from main memory
• A write to a volatile field flushes the value to main memory
• These semantics are all part of the Java memory model

Resources:

Links to some very good and relevant articles, including my favorite article by Bill Pugh.

One more thing before signing of - many people (here and here, but someone also disagrees) consider Singletons to be evil...