Oleg Zabluda's blog
Wednesday, April 25, 2012
 
Double-checked locking pattern (http://en.wikipedia.org/wiki/Double-checked_locking), was first published by Douglas...
Double-checked locking pattern (http://en.wikipedia.org/wiki/Double-checked_locking), was first published by Douglas C. Schmidt, Editor-in-chief C++ Report, in March 1996
http://www.cs.wustl.edu/~schmidt/editorial-3.html

That double-checked locking implementation was still considered correct in Oct 1999 Dr. Dobbs Journal (DDJ) article "Singleton Creation the Thread-safe Way".
http://www.drdobbs.com/article/print?articleId=184403715

The first time people started realizing that the canonical implementation is actually wrong, was around 2001.
http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html

By 2004, there was a good comprehensive article about it:
Scott Meyers and Andrei Alexandrescu September 2004 DDJ paper:
"C++ and the Perils of Double-Checked Locking"
http://www.aristeia.com/Papers/DDJ_Jul_Aug_2004_revised.pdf

At the time, it was quite instructive to me to see how that could have slipped by so many experts for so long, and how long it took people to figure out what is trivial now:

One thread writes to variable with the lock held, but another thread reads same variable without lock held. It's a data race, plane and simple.

The reason it is so trivial now is due to heroic efforts of many people, the most by Hans Boehm, who not only figured it out, but formalized C/C++ memory model and contributed to Java memory model. He also provides the best currently known implementation on the last slide of his, from his recent ACM Bay Area talk

http://www.hpl.hp.com/personal/Hans_Boehm/misc_slides/sfacm-cleaned.pdf

C++11 fine-tuned double-checked locking

atomic x_init;
if (!x_init.load(memory_order_acquire) {
l.lock();
if (!x_init.load(memory_order_relaxed) {
initialize x;
x_init.store(true, memory_order_release);
}
l.unlock();
}
use x;

Intel/AMD finally published their official memory models in 2007-2008.
Turns out on x86 the implementation above is "free" i.e. requires no additional fences, locks or nothing.
http://www.justsoftwaresolutions.co.uk/threading/intel-memory-ordering-and-c++-memory-model.html

Also see:
https://plus.google.com/112065430692128821190/posts/EjTBDUuS38G
http://www.hpl.hp.com/personal/Hans_Boehm/misc_slides/sfacm-cleaned.pdf

Labels:


- posted by Oleg Zabluda @ 2:02 PM | permalink | | | technorati | bloglines | feedster
| |

Home

Powered by Blogger