Dr. Dobb's Journal - October 2008 - (Page 68)

D10Sutt_p5db 8/14/08 4:05 PM Page 68 Effective Concurrency by Herb Sutter Writing Lock-Free Code: A Corrected Queue Think in transactions, know who owns what, and use ordered atomic variables AS WE SAW last month [1], lock-free coding is hard even for experts. There, I dissected a published lockfree queue implementation [2] and examined why the code was quite broken. This month, let’s see how to do it right. 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 in C++0x, the forthcoming ISO C++ Standard, as in atomic . 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, 68 Dr. Dobb’s Journal l www.ddj.com l October 2008 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). A Corrected One-Producer, One-Consumer Lock-Free Queue Now let’s tackle the lock-free queue using our essential tools. In this first take, to allow easier comparison with the original code in [2], I’ll stay fairly close to the original design and implementation, including that I’ll continue to make the same simplifying assumption that there is exactly one Consumer thread and one Producer thread, so that we can easily arrange for them to always work in different parts of the underlying linked list. In Figure 1, the first “unconsumed” item is the one after the divider. The consumer increments divider to say it has consumed an item. The producer increments last to say it has produced an item, and also lazily cleans up consumed items before the divider. Here’s the class definition, which carefully marks shared variables as being of an ordered atomic type (using C++ to most closely follow the original code in [2]): template class LockFreeQueue { private: struct Node { Node( T val ) : value(val), next(nullptr) { } T value; Node* next; }; Node* first; // for producer only atomic divider, last; // shared http://www.ddj.com

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

Dr. Dobb's Journal - October 2008 Contents Friday Night Fish Fry Alia Vox Developer Diaries Developer’s Notebook Is Your Next Language COBOL? Conversations Safe Coding Practices Code Signing in Adobe AIR OpenID Single Sign-On The Book Cipher Algorithm Indexing and Searching Image files Extending Continuous Integration Into ALM The Agile Edge Effective Concurrency Swaine’s Flames

Dr. Dobb's Journal - October 2008

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.