Channels ▼
RSS

Parallel

Writing Lock-Free Code: A Corrected Queue


As we saw last month [1], lock-free coding is hard even for experts. There, I dissected a published lock-free queue implementation [2] and examined why the code was quite broken. This month, let's see how to do it right.

Lock-Free Fundamentals

When writing lock-free code, always keep these essentials well in mind:

    Key concepts. Think in transactions. Know who owns what data. Key tool. The ordered atomic variable.

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. [3] 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:

    Atomicity. Each individual read and write is guaranteed to be atomic with respect to all other reads and writes of that variable. The variables typically fit into the machine's native word size, and so are usually pointers (C++), object references (Java, .NET), or integers. Order. Each read and write is guaranteed to be executed in source code order. Compilers, CPUs, and caches will respect it and not try to optimize these operations the way they routinely distort reads and writes of ordinary variables. Compare-and-swap (CAS) [4]. There is a special operation you can call using a syntax like variable.compare_exchange( expectedValue, newValue ) that does the following as an atomic operation: If variable currently has the value expectedValue, it sets the value to newValue and 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 x to y."

Ordered atomic variables are spelled in different ways on popular platforms and environments. For example:

    volatile in C#/.NET, as in volatile int. volatile or * Atomic* in Java, as in volatile int, AtomicInteger. atomic<T> in C++0x, the forthcoming ISO C++ Standard, as in atomic<int>.

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 mb).


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Comments:

ubm_techweb_disqus_sso_-8169e3e3e07d088f82d044516aa7814f
2012-11-15T18:02:53

This code fails to be compiled w/ the latest VS – any chance to get the fixed code?


Permalink
ubm_techweb_disqus_sso_-0c074ab2a292a45bf4b19f0786aa989a
2012-08-26T14:21:12

I was reading back and forth thinking the code must be incorrect.. because I found two consumer thread could consume the same value at the same time, before realizing that there is a 'Single Consumer' phrase in page 2. I don't think multi consumer thread is possible without using compareAndSet semantics.


Permalink
dblake950
2012-06-27T17:41:10

Herb Sutter has traditionally used his own code highlighting colors in code samples, which conflicted with our "new" code presentation software when we installed it in 2011. The result was that some of Herb’s archived articles have been rendering with missing code and/or extraneous formatting artifacts. This article has been reformatted to its original layout and other classics are in the process of being corrected. If you spot any that we missed, please bring them to our attention. --Deirdre


Permalink
ubm_techweb_disqus_sso_-7bb0a7a86573da33e1b03c521db30585
2012-03-22T14:55:00

Tadzys might refer to this not being compilable code. Take these declarations for example:

Node* first; // for producer only
divider, last; // shared

The type of divider and last is missing, which should be sth like atomic< Node* >.

Same with

result = divider->next->value; // C: copy it back
= divider->next; // D: publish that we took it

in the last listing. The second statement assigns a value to ... whitespace? Again, an atomic variable is involved, so I'm guessing the problem isn't Herb's code, but possible the formatter you used. Maybe you could disable the formatter?

BTW, your site interprets <node*> in a comment as an XML tag. Maybe that's the problem?


Permalink
AndrewBinstock
2012-03-20T19:31:02

You'll need to do a lot more than asser the code is "totally incorrect." This area of coding was Herb Sutter's specialty before Microsoft hired him to head up their C++ implementation. Yours is the first comment we've rec'd on this very popular article. So, I am quite sure it's not "totally incorrect." And until you can point to specifics, I seriously doubt it's incorrect at all.


Permalink
ubm_techweb_disqus_sso_-f06d434405da006e1bd298fd9600c591
2012-03-20T16:56:59

Unfortunately I don't see how this is corrected queue at all...
the code is totally incorrect.


Permalink
ubm_techweb_disqus_sso_-71f2cb85d5d5f0d75eb4c04c50f2ad93
2012-01-25T10:26:28

I know this is an old article so its probably pointless asking, however this is the most illuminating article on this subject I have yet read. This makes me very keen to fully understand it. Anyway:

You say "Here's the class definition, which carefully marks shared variables as being of an ordered atomic type" however I dont understand where in the code snippet the "ordered atomic type" can be found.

Apologies for being a bit stoopid!


Permalink

Video