As we saw last month , lock-free coding is hard even for experts. There, I dissected a published lock-free queue implementation  and examined why the code was quite broken. This month, let's see how to do it right.
When writing lock-free code, always keep these essentials well in mind:
When writing a lock-free data structure, "to think in transactions" means to make sure that each operation on the data structure is atomic, all-or-nothing with respect to other concurrent operations on that same data. The typical coding pattern to use is to do work off to the side, then "publish" each change to the shared data with a single atomic write or compare-and-swap.  Be sure that concurrent writers don't interfere with each other or with concurrent readers, and pay special attention to any operations that delete or remove data that a concurrent operation might still be using.
Be highly aware of who owns what data at any given time; mistakes mean races where two threads think they can proceed with conflicting work. You know who owns a given piece of shared data right now by looking at the value of the ordered atomic variable that says who it is. To hand off ownership of some data to another thread, do it at the end of a transaction with a single atomic operation that means "now it's your's."
An ordered atomic variable is a "lock-free-safe" variable with the following properties that make it safe to read and write across threads without any explicit locking:
variable.compare_exchange( expectedValue, newValue )that does the following as an atomic operation: If
variablecurrently has the value
expectedValue, it sets the value to
newValueand returns true; else returns false. A common use is
if(variable.compare_exchange(x,y)),which you should get in the habit of reading as, "if I'm the one who gets to change variable from
Ordered atomic variables are spelled in different ways on popular platforms and environments. For example:
volatilein C#/.NET, as in
* Atomic*in Java, as in
atomic<T>in C++0x, the forthcoming ISO C++ Standard, as in
In the code that follows, I'm going to highlight the key reads and writes of such a variable; these variables should leap out of the screen at you, and you should get used to being very aware of every time you touch one.
If you don't yet have ordered atomic variables yet on your language and platform, you can emulate them by using ordinary but aligned variables whose reads and writes are guaranteed to be naturally atomic, and enforce ordering by using either platform-specific ordered API calls (such as Win32's
InterlockedCompareExchange for compare-and-swap) or platform-specific explicit memory fences/barriers (for example, Linux