Software Engineering is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software, and the study of these approaches; that is, the application of engineering to software...
, double-checked locking (also known as "double-checked locking optimization".) is a software design pattern used to reduce the overhead of acquiring a lock
Lock (computer science)
In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies.-Types:...
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
Anti-pattern
In software engineering, an anti-pattern is a pattern that may be commonly used but is ineffective and/or counterproductive in practice.The term was coined in 1995 by Andrew Koenig,...
.
It is typically used to reduce locking overhead when implementing "lazy initialization
Lazy initialization
In computer programming, lazy initialization is the tactic of delaying the creation of an object, the calculation of a value, or some other expensive process until the first time it is needed....
" in a multi-threaded environment, especially as part of the Singleton pattern
Singleton pattern
In software engineering, the singleton pattern is a design pattern used to implement the mathematical concept of a singleton, by restricting the instantiation of a class to one object. This is useful when exactly one object is needed to coordinate actions across the system...
. Lazy initialization avoids initializing a value until the first time it is accessed.
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
// Single threaded version
class Foo {
private Helper helper = null;
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
Lock (computer science)
In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies.-Types:...
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 = null;
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 can decrease performance by a factor of 100 or higher, 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:
Check that the variable is initialized (without obtaining the lock). If it is initialized, return it immediately.
Obtain the lock.
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.
Otherwise, initialize and return the variable.
// Broken multithreaded version
// "Double-Checked Locking" idiom
class Foo {
private Helper helper = null;
public Helper getHelper {
if (helper
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:
Thread A notices that the value is not initialized, so it obtains the lock and begins to initialize the value.
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.
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
Cache coherence
In computing, cache coherence refers to the consistency of data stored in local caches of a shared resource.When clients in a system maintain caches of a common memory resource, problems may arise with inconsistent data. This is particularly true of CPUs in a multiprocessing system...
)), the program will likely crash.
One of the dangers of using double-checked locking in J2SE 1.4
Java Platform, Standard Edition
Java Platform, Standard Edition or Java SE is a widely used platform for programming in the Java language. It is the Java Platform used to deploy portable applications for general use...
(and earlier versions) is that it will often appear to work: it is not easy to distinguish between a correct implementation
Implementation
Implementation is the realization of an application, or execution of a plan, idea, model, design, specification, standard, algorithm, or policy.-Computer Science:...
of the technique and one that has subtle problems. Depending on the compiler
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
In computer science, a scheduling is the method by which threads, processes or data flows are given access to system resources . This is usually done to load balance a system effectively or achieve a target quality of service...
In computer science, concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other...
, failures resulting from an incorrect implementation of double-checked locking may only occur intermittently. Reproducing the failures can be difficult.
Java Platform, Standard Edition or Java SE is a widely used platform for programming in the Java language. It is the Java Platform used to deploy portable applications for general use...
In computer programming, particularly in the C, C++, C#, and Java programming languages, a variable or object declared with the volatile keyword usually has special properties related to optimization and/or threading...
// Works with acquire/release semantics for volatile
// Broken under Java 1.4 and earlier semantics for volatile
class Foo {
private volatile Helper helper = null;
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 usage of the local variable result which seems unnecessary. For some versions of the Java VM, it will make the code 25% faster and for others, it won't hurt.
In software engineering, the Initialization on Demand Holder idiom is a lazy-loaded singleton. The idiom can be implemented in both single-threaded/serial and concurrent environments, but care must be taken to correctly implement the idiom under concurrent conditions.- Example Java Implementation...
See Listing 16.6 on
// Correct lazy initialization in Java
@ThreadSafe
class Foo {
private static class HelperHolder {
public static Helper helper = new Helper;
}
public static Helper getHelper {
return HelperHolder.helper;
}
}
This relies on the fact that inner 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:
public class FinalWrapper {
public final T value;
public FinalWrapper(T value) {
this.value = value;
}
}
public class Foo {
private FinalWrapper helperWrapper = null;
public Helper getHelper {
FinalWrapper wrapper = helperWrapper;
The local variable wrapper is required for correctness. Performance of this implementation is not necessarily better than the volatile implementation.
Usage in Microsoft Visual C++
Double-checked locking can be implemented in Visual C++
Visual C++
Microsoft Visual C++ is a commercial , integrated development environment product from Microsoft for the C, C++, and C++/CLI programming languages...
2005 and above if the pointer to the resource is declared with the C++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
keyword volatile. Visual C++ 2005 guarantees that volatile variables will behave as fence instructions, as in J2SE 5.0, preventing both compiler and CPU arrangement of reads and writes with acquire semantics (for reads) and release semantics (for writes). There is no such guarantee in previous versions of Visual C++. However, marking the pointer to the resource as volatile may harm performance elsewhere, if the pointer declaration is visible elsewhere in code, by forcing the compiler to treat it as a fence elsewhere, even when it is not necessary.
Usage in Microsoft .NET (Visual Basic, C#)
Double-checked locking can be implemented efficiently in .NET with careful use of the MemoryBarrier instruction:
public class MySingleton {
private static object myLock = new object;
private static MySingleton mySingleton = null;
private static bool ready = false;
private MySingleton {
}
public static MySingleton GetInstance {
if (!ready) { // 1st check
lock (myLock) {
if (!ready) { // 2nd (double) check
mySingleton = new MySingleton;
System.Threading.Thread.MemoryBarrier; // fence
ready = true;
}
}
}
return mySingleton;
}
}
In this example, the "lock hint" is the ready flag which can only change after mySingleton is fully constructed and ready for use.
Alternatively, the C# keyword volatile can be used to enforce read/write fences around all access of mySingleton, which would negate many of the efficiencies inherent in the double-checked locking strategy.
public class MySingleton {
private static object myLock = new object;
private static volatile MySingleton mySingleton = null;
private MySingleton {
}
public static MySingleton GetInstance {
if (mySingleton
null) { // check
lock (myLock) {
if (mySingleton
null) { // double check, volatile ensures that the value is re-read
mySingleton = new MySingleton;
}
}
}
return mySingleton;
}
}
In computer science, the test-and-set CPU instruction is used to implementmutual exclusion in multiprocessor environments. Although a correct lock can be implemented with test-and-set, it can lead to resource contention in busy lock .To lower the overhead a more elaborate locking...
A programming idiom is a means of expressing a recurring construct in one or more programming languages. Generally speaking, a programming idiom is an expression of a simple task or algorithm that is not a built-in feature in the programming language being used, or, conversely, the use of an...
In software engineering, the Initialization on Demand Holder idiom is a lazy-loaded singleton. The idiom can be implemented in both single-threaded/serial and concurrent environments, but care must be taken to correctly implement the idiom under concurrent conditions.- Example Java Implementation...
Scott Douglas Meyers is an American author and software consultant, specializing in the C++ computer programming language. He is known for his Effective C++ book series. He is a frequent speaker at conferences and trade shows. He holds a Ph.D. in computer science from Brown University and M.S...
Andrei Alexandrescu is a Romanian C++ programmer and author. He is particularly known for his pioneering work on policy-based design implemented via template metaprogramming. These ideas are articulated in his book Modern C++ Design and were first implemented in his programming library, Loki. He...
