Double-checked locking

In software engineering, double-checked locking (also known as "double-checked locking optimization"[1]) is a software design pattern used to reduce the overhead of acquiring a lock by first testing the locking criterion (the "lock hint") without actually acquiring the lock. Only if the locking criterion check indicates that locking is required does the actual locking logic proceed.

The pattern, when implemented in some language/hardware combinations, can be unsafe. At times, it can be considered an anti-pattern.[2]

It is typically used to reduce locking overhead when implementing "lazy initialization" in a multi-threaded environment, especially as part of the Singleton pattern. Lazy initialization avoids initializing a value until the first time it is accessed.

Usage in C++11

For the singleton pattern, double-checked locking is not needed:

If control enters the declaration concurrently while the variable is being initialized, the concurrent execution shall wait for completion of the initialization.
— § 6.7 [stmt.dcl] p4
 
Singleton& instance()
{
     static Singleton s;
     return s;
}

Use C++11 acquire and release fences as given by [3]

std::atomic<Singleton*> Singleton::m_instance;
std::mutex Singleton::m_mutex;

Singleton* Singleton::getInstance() {
    Singleton* tmp = m_instance.load(std::memory_order_relaxed);
    std::atomic_thread_fence(std::memory_order_acquire);
    if (tmp == nullptr) {
        std::lock_guard<std::mutex> lock(m_mutex);
        tmp = m_instance.load(std::memory_order_relaxed);
        if (tmp == nullptr) {
            tmp = new Singleton;
            std::atomic_thread_fence(std::memory_order_release);
            m_instance.store(tmp, std::memory_order_relaxed);
        }
    }
    return tmp;
}

Usage in Java

Consider, for example, this code segment in the Java programming language as given by [2] (as well as all other Java code segments):

// Single-threaded version
class Foo {
    private Helper helper;
    public Helper getHelper() {
        if (helper == null) {
            helper = new Helper();
        }
        return helper;
    }

    // other functions and members...
}

The problem is that this does not work when using multiple threads. A lock must be obtained in case two threads call getHelper() simultaneously. Otherwise, either they may both try to create the object at the same time, or one may wind up getting a reference to an incompletely initialized object.

The lock is obtained by expensive synchronizing, as is shown in the following example.

// Correct but possibly expensive multithreaded version
class Foo {
    private Helper helper;
    public synchronized Helper getHelper() {
        if (helper == null) {
            helper = new Helper();
        }
        return helper;
    }

    // other functions and members...
}

However, the first call to getHelper() will create the object and only the few threads trying to access it during that time need to be synchronized; after that all calls just get a reference to the member variable. Since synchronizing a method could in some extreme cases decrease performance by a factor of 100 or higher,[4] the overhead of acquiring and releasing a lock every time this method is called seems unnecessary: once the initialization has been completed, acquiring and releasing the locks would appear unnecessary. Many programmers have attempted to optimize this situation in the following manner:

  1. Check that the variable is initialized (without obtaining the lock). If it is initialized, return it immediately.
  2. Obtain the lock.
  3. Double-check whether the variable has already been initialized: if another thread acquired the lock first, it may have already done the initialization. If so, return the initialized variable.
  4. Otherwise, initialize and return the variable.
// Broken multithreaded version
// "Double-Checked Locking" idiom
class Foo {
    private Helper helper;
    public Helper getHelper() {
        if (helper == null) {
            synchronized(this) {
                if (helper == null) {
                    helper = new Helper();
                }
            }
        }
        return helper;
    }

    // other functions and members...
}

Intuitively, this algorithm seems like an efficient solution to the problem. However, this technique has many subtle problems and should usually be avoided. For example, consider the following sequence of events:

  1. Thread A notices that the value is not initialized, so it obtains the lock and begins to initialize the value.
  2. Due to the semantics of some programming languages, the code generated by the compiler is allowed to update the shared variable to point to a partially constructed object before A has finished performing the initialization. For example, in Java if a call to a constructor has been inlined then the shared variable may immediately be updated once the storage has been allocated but before the inlined constructor initializes the object.[5]
  3. Thread B notices that the shared variable has been initialized (or so it appears), and returns its value. Because thread B believes the value is already initialized, it does not acquire the lock. If B uses the object before all of the initialization done by A is seen by B (either because A has not finished initializing it or because some of the initialized values in the object have not yet percolated to the memory B uses (cache coherence)), the program will likely crash.

One of the dangers of using double-checked locking in J2SE 1.4 (and earlier versions) is that it will often appear to work: it is not easy to distinguish between a correct implementation of the technique and one that has subtle problems. Depending on the compiler, the interleaving of threads by the scheduler and the nature of other concurrent system activity, failures resulting from an incorrect implementation of double-checked locking may only occur intermittently. Reproducing the failures can be difficult.

As of J2SE 5.0, this problem has been fixed. The volatile keyword now ensures that multiple threads handle the singleton instance correctly. This new idiom is described in and .

// Works with acquire/release semantics for volatile in Java 1.5 and later
// Broken under Java 1.4 and earlier semantics for volatile
class Foo {
    private volatile Helper helper;
    public Helper getHelper() {
        Helper result = helper;
        if (result == null) {
            synchronized(this) {
                result = helper;
                if (result == null) {
                    helper = result = new Helper();
                }
            }
        }
        return result;
    }

    // other functions and members...
}

Note the local variable result, which seems unnecessary. The effect of this is that in cases where helper is already initialized (i.e., most of the time), the volatile field is only accessed once (due to "return result;" instead of "return helper;"), which can improve the method's overall performance by as much as 25 percent.[6]

If the helper object is static (one per class loader), an alternative is the initialization on demand holder idiom[7] (See Listing 16.6[8] from the previously cited text.)

// Correct lazy initialization in Java
class Foo {
    private static class HelperHolder {
       public static final Helper helper = new Helper();
    }

    public static Helper getHelper() {
        return HelperHolder.helper;
    }
}

This relies on the fact that nested classes are not loaded until they are referenced.

Semantics of final field in Java 5 can be employed to safely publish the helper object without using volatile:[9]

public class FinalWrapper<T> {
    public final T value;
    public FinalWrapper(T value) {
        this.value = value;
    }
}

public class Foo {
   private FinalWrapper<Helper> helperWrapper;

   public Helper getHelper() {
      FinalWrapper<Helper> wrapper = helperWrapper;

      if (wrapper == null) {
          synchronized(this) {
              if (helperWrapper == null) {
                  helperWrapper = new FinalWrapper<Helper>(new Helper());
              }
              wrapper = helperWrapper;
          }
      }
      return wrapper.value;
   }
}

The local variable wrapper is required for correctness. Performance of this implementation is not necessarily better than the volatile implementation.

Usage in Microsoft .NET (Visual Basic, C#)

Double-checked locking can be implemented efficiently in .NET. A common usage pattern is to add double-checked locking to Singleton implementations:

public class MySingleton {
    private static object myLock = new object();
    private static volatile MySingleton mySingleton = null; // 'volatile' is unnecessary in .NET 2.0 and later

    private MySingleton() {
    }

    public static MySingleton GetInstance() {
        if (mySingleton == null) { // 1st check
            lock (myLock) {
                if (mySingleton == null) { // 2nd (double) check
                    mySingleton = new MySingleton();
                    // In .NET 1.1, write-release semantics are implicitly handled by marking mySingleton with
                    // 'volatile', which inserts the necessary memory barriers between the constructor call
                    // and the write to mySingleton. The barriers created by the lock are not sufficient
                    // because the object is made visible before the lock is released. In .NET 2.0 and later,
                    // the lock is sufficient and 'volatile' is not needed.
                }
            }
        }
        // In .NET 1.1, the barriers created by the lock are not sufficient because not all threads will
        // acquire the lock. A fence for read-acquire semantics is needed between the test of mySingleton
        // (above) and the use of its contents.This fence is automatically inserted because mySingleton is
        // marked as 'volatile'.
        // In .NET 2.0 and later, 'volatile' is not required.
        return mySingleton;
    }
}

In this example, the "lock hint" is the mySingleton object which is no longer null when fully constructed and ready for use.

In .NET Framework 4.0, the Lazy<T> class was introduced, which internally uses double-checked locking by default (ExecutionAndPublication mode) to store either the exception that was thrown during construction, or the result of the function that was passed to Lazy<T>:[10]

public class MySingleton
{
    private static readonly Lazy<MySingleton> _mySingleton = new Lazy<MySingleton>(() => new MySingleton());

    private MySingleton() { }

    public static MySingleton Instance
    {
        get
        {
            return _mySingleton.Value;
        }
    }
}

See also

References

  1. ↑ Schmidt, D et al. Pattern-Oriented Software Architecture Vol 2, 2000 pp353-363
  2. 1 2 David Bacon et al. The "Double-Checked Locking is Broken" Declaration.
  3. ↑ Double-Checked Locking is Fixed In C++11
  4. ↑ Boehm, Hans-J (Jun 2005). "Threads cannot be implemented as a library" (PDF). SIGPLAN Not. (ACM Press) 40 (6): 261–268. doi:10.1145/1064978.1065042.
  5. ↑ Haggar, Peter (1 May 2002). "Double-checked locking and the Singleton pattern". IBM.
  6. ↑ Joshua Bloch "Effective Java, Second Edition", p. 283-284
  7. ↑ Brian Goetz et al. Java Concurrency in Practice, 2006 pp348
  8. ↑ Goets, Brian; et al. "Java Concurrency in Practice – listings on website". Retrieved 21 October 2014.
  9. ↑ Javamemorymodel-discussion mailing list
  10. ↑ Albahari, Joseph (2010). "Threading in C#: Using Threads". C# 4.0 in a Nutshell. O'Reilly Media. ISBN 0-596-80095-9. Lazy<T> actually implements […] double-checked locking. Double-checked locking performs an additional volatile read to avoid the cost of obtaining a lock if the object is already initialized.

External links

This article is issued from Wikipedia - version of the Saturday, April 23, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.