Dr. Dobb's Journal - October 2007 - (Page 57)

by Herb Sutter Effective Concurrency Use Critical Sections (Preferably Locks) to Eliminate Races In a race, no one can hear you scream EVERYONE KNOWS the basics of how to use locks: mut.lock(); // acquire lock on x read/write x mut.unlock(); // release lock on x • A shared object need not be protected in the same way for its entire lifetime: It is perfectly legitimate to protect the same object using locks at some times and lock-free techniques at others. Next month, I’ll consider some examples in detail. But why do locks, lock-free styles, and other synchronization techniques work at all, never mind interoperate well with each other and with aggressive optimizers that transform and reorder your program to make it run faster? Because every synchronization technique you’ve ever heard of must express, and every optimization that may ever be performed must respect and uphold, the common fundamental concept of a critical section. Different Ways to Spell “critical section” A “critical section” is a region of code that shall execute in isolation with respect to some or all other code in the program, and every kind of synchronization you’ve ever heard of is a way to express critical sections. Today’s most common synchronization tool is the humble lock, and every region of code that executes under a lock is a critical section. For example, consider again the earlier code: mut.lock(); read/write x mut.unlock(); // enter critical section (acquire lock) // exit critical section (release lock) Data Race A data race (or just “race”) occurs whenever the same memory location can be accessed simultaneously by more than one thread, and at least one of the accesses is a write. Consider the following code, where x is a shared object: Thread 1 x = 1; Thread 2 obj.f( x ); Thread 1 writes x and Thread 2 reads it, and so this is a classic race if there is no synchronization that prevents the two threads from executing at the same time. How potentially bad it can be to have a race? Very, depending on your language’s and/or platform’s memory model, which sets forth limits on compiler and processor reordering and on what, if any, guarantees you can expect. For example, in Java, “very strange, confusing, and counterintuitive behaviors are possible,” including seeing partly constructed objects. [1] In POSIX threads (pthreads), there is no such thing as a benign race: Nearly any race could in principle cause random code execution. Clearly, we want to eliminate races. The right way to do that is to use critical sections to prevent two pieces of code that read or write the same shared object from executing at the same time. But note: • Not every object is shared for its entire lifetime: You only need to protect it with critical sections while it is shared, or while it is in transition from unshared to shared and vice versa (for instance, when a previously private object is first “published” to other threads by being made reachable outside its original thread). The next most common synchronization tools, used by wizard guru experts only, are varieties of lock-free coding. Beyond a handful of well-known patterns such as Double-Checked Locking, lock-free styles are typically too hard to use directly in normal programming, and they are usually used inside the implementations of other abstractions (for example, in the implementation of a mutex class, an internally synchronized lock-free hashed container, or an OS kernel facility). The first lock-free style uses atomic variables (Java/.NET volatile, C++0x atomic) that enjoy special semantics with compiler and processor support. Consider an example similar to the aforementioned code, but written in a lock-free style, where myTurn is an atomic variable protecting x: while( !myTurn ) { } // enter critical section (spin read) read/write x myTurn = false; // exit critical section (write) The second lock-free coding style is to use explicit fences (also called “barriers”) such as Linux mb(), or special functions with ordering semantics such as Win32 InterlockedCompareExchange. These tools express ordering constraints by placing explicit checkpoints where key variables are used in your code. Protecting a shared variable using these tools is difficult because the fences have to be written correctly at every point you use the variable (as opposed to once at the declaration of the variable to declare it inherently atomic), and their semantics are subtle and tend to vary from platform to platform. Here is one way to write the corresponding example, where myTurn is now just an ordinary variable (that must still be readable and writable atomically) and is given special semantics by applying a simple fence at each point of use so that it still correctly protects x: while( !myTurn ) { } // enter critical section mb(); // (atomic spin read + fence) read/write x mb(); // exit critical section myTurn = false; // (fence + atomic write) The key point is that all lock-based and lock-free styles are just different ways to express the same fundamental concept—the exclusively held critical section. October 2007 l www.ddj.com l Dr. Dobb’s Journal 57 http://www.ddj.com

Table of Contents Feed for the Digital Edition of Dr. Dobb's Journal - October 2007

Cover Contents Hmmmm Alia Vox Developer Diaries Developer’s Notebook AI: It’s OK Again! Conversations Visual Cryptography and Bit-Plane Complexity Segmentation Inside the Windows Vista Disk Encryption Algorithm Memory-Aware Components Software and the Core Description Process Logging In C++ Effective Concurrency The Agile Edge Swaine’s Flames

Dr. Dobb's Journal - October 2007

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.