Double-checked locking

Encyclopedia : D : DO : DOU : Double-checked locking

In software engineering, double-checked locking is a software design pattern originally known as "double-checked locking optimization." The pattern is unsafe in some versions of some languages on some modern computer hardware and/or optimizing compilers. It can therefore sometimes be considered to be an anti-pattern.

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

Contents

1 Usage in Java
2 Usage in Microsoft Visual C++
3 See also
4 External links

Usage in Java

Consider, for example, this code segment in the Java programming language as given by [link]:

// Single threaded version
class Foo 
// other functions and members...
}

However, when using threads a lock must be obtained in case two threads attempt to initialize the helper instance simultaneously. Intuitively, the overhead of acquiring and releasing a lock every time this method is called seems unnecessary: the main use of the lock appears to be to ensure that the initialization of the instance will only be done once, but 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:

Checking that the variable is initialized (without obtaining the lock). If it is initialized, it is returned immediately.
Obtaining the lock.
Double-checking whether the variable has already been initialized: if another thread acquired the lock first, it may have already done the initialization. If so, the initialized variable is returned.
Otherwise, the variable is initialized and returned.

'Broken' example code segment in Java as given by [link]:

// Broken multithreaded version
// "Double-Checked Locking" idiom
class Foo 
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:

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 most 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 the variable is used before A finishes initializing it, 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 hardware platform, 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 [link]:

// Works with acquire/release semantics for volatile
// Broken under Java 1.4 and earlier semantics for volatile
class Foo 
}
return helper;
}
}

Correct locking example code segment in Java as given by [link]:

For correct locking in J2SE 1.4 and earlier, one possible solution is to synchronize the getHelper() method. But keep in mind that synchronizing a method can decrease performance by a factor of 100 or higher. So if getHelper() is called frequently in the application, this solution should be avoided, especially if the Helper object is not "expensive" to create.

// Correct multithreaded version for J2SE 1.4 and earlier
class Foo 
// other functions and members...
}

Usage in Microsoft Visual C++

Double-checked locking can be implemented in Visual C++ 2005 if the pointer to the resource is marked as being volatile. Visual C++ 2005 guarantees that volatile variables will behave as fences, as in J2SE 5.0, preventing both compiler and CPU arrangement of reads and 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.

External links

Issues with the double checked locking mechanism captured in [Jeu George's Blogs] [Pure Virtuals]
Implementation of Various Singleton Patterns including the [Double Checked Locking Mechanism] at [TEKPOOL]
[Description from the Portland Pattern Repository]
Paper "[C++ and the Perils of Double-Checked Locking]" (475 KB) by Scott Meyers and Andrei Alexandrescu
Article "[Double-checked locking: Clever, but broken]" by Brian Goetz
[The "Double-Checked Locking is Broken" Declaration]; David Bacon et al.
[Double-checked locking and the Singleton pattern]
[Singleton Pattern and Thread Safety]
[volatile keyword in VC++ 2005]

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.

Double-checked locking

Usage in Java

Usage in Microsoft Visual C++

See also

External links